# Convergence of $a_{n+2}^3+a_{n+2}=a_{n+1}+a_n$

Let $$(a_n) _{n\ge 0}$$ $$a_{n+2}^3+a_{n+2}=a_{n+1}+a_n$$,$$\forall n\ge 1$$, $$a_0,a_1 \ge 1$$. Prove that $$(a_n) _{n\ge 0}$$ is convergent.
I could prove that $$a_n \ge 1$$ by mathematical induction, but here I am stuck.

• If it helps, if $\lim a_n$ exists and equals $L$, then $L^3=L$, i.e. $L\in\{0,1\}$ Commented Feb 9, 2019 at 19:35
• @JeanMarie as to your answer, taking $g = f^{-1},$ note that we can write this as system $x_{n+1} = y_n, \; y_{n+1} = g(x_n + y_n)$ and consider the distance to $(1,1)$ using two variable Taylor series. Commented Feb 9, 2019 at 20:12
• @Will Jagy Thanks. I hadn't thought to it ! Commented Feb 9, 2019 at 20:39
• @Will Jagy I realized just now that your idea was to use the analogy between (systems of) differential equations and sequences. The solution I have (a little painfully) found uses mainly bracketing and, as often in suche issues, an auxiliary sequence tending to 0. Commented Feb 9, 2019 at 23:01
• @JeanMarie yes, a discrete dynamical system, $X_{n+1} = F(X_n),$ where here $X_n$ is in $\mathbb R^2.$ Not my field, but i would guess there is a fairly large "attracting basin" around (1,1). It seems to me less mysterious than trying to keep everything in one dimension, but might require worse computations. Commented Feb 9, 2019 at 23:31

There might be an easier and more elegant solution, but this should work.

First observe that: $$a_{n+1}+a_{n}=a_{n+2}^3+a_{n+2}\geq2\sqrt{a_{n+2}^4}=2a_{n+2}^2\geq4a_{n+2}-2$$ Here I used the AM-GM inequality and the simply fact that $$(a_{n+2}-1)^2\geq0$$. Hence, $$a_n\leq b_n$$ with $$b_{n+2}=\frac{b_{n+1}+b_{n}+2}{4}\\ b_{0,1}=a_{0,1}$$

Now, the recurrence equation for this reads: $$b_{n}=1 + (\tfrac{1 - \sqrt{17}}{8})^n C_1 + (\tfrac{1 + \sqrt{17}}{8})^n C_2$$ Since $$|\tfrac{1 \pm \sqrt{17}}{8}|<1$$ we can deduct that $$b_n\to1$$ for $$n\to\infty$$. So together with $$1\leq a_n\leq b_n$$ we can conclude that $$a_n\to1$$.

• Very interesting ! I am indebted to your first inequality for the finalization of my solution. A little remark : one should first ensure that the initial relationship always defines a unique $a_{n+2}$. Commented Feb 9, 2019 at 22:46
• Moreover, though I utilized a different auxiliary sequence, I find back your constant $\dfrac{1+\sqrt{17}}{8}$... Commented Feb 10, 2019 at 0:17
• Clever! I was puzzled by the choice of the lower bound at first, then I realized that it comes from the tangent line of $f(x) = x^3 + x$ at $x = 1$, which should lie below $f$ on $[1, \infty)$ due to the convexity of $f$. Commented Feb 10, 2019 at 9:34
• I've posted a variant that might be slightly easier. Commented Feb 10, 2019 at 14:02
• is it sufficient that $a_n < b_n$ implies $a_n$ is convergent? Commented Feb 10, 2019 at 14:11

This is the first time I see this type of recusrion relation where the next term in the sequence is not given directly but instead a function of it is given. This makes the problem particularly interesting (for me, at least).

Hence an uncommon approach seems to be justified. I am going to relate convergence to the stability of simple (constant) solutions.

1. Layout of the solution

Let us start with the observation that there are three constant solutions of the recursion

$$a_{n+2}^3+a_{n+2}=a_{n+1}+a_{n}\tag{1}$$

These are given by the roots of the equation

$$z^3+z = z + z\tag{2}$$

that is

$$s_1 = \{a_n = - 1\}$$ $$s_2 = \{a_n = 0\}\tag{3}$$ $$s_3=\{a_n = + 1\}$$

We show below that $$s_1$$ and $$s_3$$ are stable solutions, and $$s_2$$ is unstable.

A stable solution is definied as one where a sufficiently small deviation from the solution is damped out for $$n\to\infty$$. In an unstable solution, in contrast, small deviations increase so that the sequence departs from the solution for large $$n$$.

Depending on the initial values $$a_1$$ and $$a_2$$ (except the singular case $$a_1 = a_2=0$$) the solution approches one of the stable solutions. This statement is equivalent to saying the sequence is convergent.

2. Stability analysis

Applying the common procedure we let

$$a_k= s + \delta_k\tag{4}$$

where $$s$$ is the constant solution to be studied and $$\delta_k$$ is a small deviation. Small is defined as $$|\delta_k|<<1$$

Inserting $$(4)$$ into $$(1)$$ gives

$$(s + \delta_{n+2})^3 +(s + \delta_{n+2})= (s + \delta_{n+1})+(s + \delta_{n})$$

Expanding the 3rd power and keeping only the linear term in $$\delta$$ gives

$$s^3 + 3 s^2 \delta_{n+2} +(s + \delta_{n+2})= (s + \delta_{n+1})+(s + \delta_{n})$$

Observing that $$s$$ solves $$(2)$$ this can be simplified to

$$(1+3 s^2)\delta_{n+2} =\delta_{n+1}+\delta_{n}\tag{5}$$

This is a linear recursion equation which can be solved by standard methods.

In the case $$s=0$$ $$(5)$$ reduces to the Fibonacci recursion which is known to diverge, in agreement with our identifying this solution as unstable.

For the cases $$s=\pm 1$$ I leave as an exercise to the reader to show that the solutions $$\delta_n \to 0$$ for $$n\to\infty$$ and arbitrary but suffciently small initial conditions.

3. Numerical study (in Mathematica)

As an example of how to treat the recursion $$(1)$$ numerically I used these commands in Mathematica

a[1] := 1; a[2] := 0;
Table[a[n] =
z /. FindRoot[z^3 + z == a[n - 1] + a[n - 2], {z, 0}], {n, 3, 20}]

{0.682328, 0.53187, 0.765544, 0.794984, 0.879716, 0.913186, 0.946085, \
0.963849, 0.977093, 0.985069, 0.990473, 0.993857, 0.996071, 0.997477, \
0.998385, 0.998965, 0.999337, 0.999575}


Explanation: in the first line the initial values are defined. The FindRoot command solves for $$z$$ and thus finds the value of $$a_{n+2}$$ for the given right Hand side, i.e. as a function of $$a_{n+1}$$ and $$a_{n}$$. The Table command provides a list of the first few terms of the sequence.

We can see that with these initial conditions the values approach the stable solution $$a_n=+1$$

In this case

a[1] := -0.1; a[2] := 0;
Table[a[n] =
z /. FindRoot[z^3 + z == a[n - 1] + a[n - 2], {z, 0}], {n, 3, 20}]

{-0.0990289, -0.0980852, -0.19023, -0.268877, -0.396685, -0.522729, \
-0.647697, -0.749461, -0.828489, -0.884939, -0.924151, -0.950462, \
-0.967888, -0.979268, -0.986656, -0.991426, -0.994498, -0.996472}


the stable solution $$a_n=-1$$ is approached.

Initial remarks :

a) In case of convergence to a limit $$L$$, we would have $$L^3+L=L+L$$, with solutions $$L=-1,0,1$$.

b) We assume that, up to a switching operation, $$a_1 \leq a_0.$$

We are going to show that $$a_n$$ is convergent with limit $$L=1.$$

First step : the recurrence "definition"

$$a_{n+2}^3+a_{n+2}=a_{n+1}+a_n$$

of sequence $$a_n$$, rewritten under the form

$$f(a_{n+2})=a_{n+1}+a_n \ \ \text{where} \ \ f(x):=x^3+x, \tag{0}$$

cannot be considered as a "definition" unless it has been proved that $$a_{n+2}$$ is determined in a unique way by (1). This will be the consequence of

Lemma $$0$$ : $$f$$ is a bijection.

Proof : $$f'(x)=3x^2+1\geq 1>0$$. Thus function $$f$$ is strictly increasing, therefore is bijective. $$\square$$.

Let us write (0) under the form :

$$a_{n+2}=f^{-1}(a_{n+1}+a_n)\tag{1}$$

Lemma $$1$$ : $$a_n \geq 1$$ whatever $$n$$.

Proof : by recurrence, using the fact that $$f^{-1}(2,+\infty)=(1,\infty). \ \square$$

Lemma $$2$$ : for any $$x \geq 0, f(x) \geq 2x^2$$

Proof by observing that $$x^3+x-2x^2=x(x-1)^2 \geq 0. \ \square$$

As a consequence of lemma $$2$$,

$$f^{-1}(u) \leq \sqrt{\tfrac{u}{2}}.\tag{2}$$

Thus, for any $$n$$,

$$a_{n+2} \leq \sqrt{\tfrac{a_{n+1}+a_n}{2}}\tag{3}.$$

Let us define an auxiliary sequence $$b_n$$ by

$$b_n=a_n-1\tag{4}$$

Our objective is thus to prove that $$b_n \to 0$$. (3) becomes :

$$b_{n+2} \leq \sqrt{1+\tfrac{b_{n+1}+b_n}{2}}-1\tag{5}.$$

Lemma $$3$$ : $$b_n$$ is a positive decreasing sequence bounded from below by $$0$$.

Proof : By recurrence. True (see initial remark b)) for the two first elements. For the general case, use in (5) the (classical) result :

$$\text{for all} \ x>0, \ \ \ 1 \leq \sqrt{1+x}\leq 1+\tfrac{x}{2}.\tag{5}$$

$$\ \square$$

Lemma $$3$$ allows to conclude that $$a_n$$ is a positive decreasing sequence bounded from below by $$1$$. Thus $$a_n$$ converges to a limit which is necessarily $$L=1$$ (see initial remark a)).

Remark about the rate of convergence : I have observed that sequence $$b_n$$ behaves asymptotically as a geometrical sequence with ratio $$r=0.640388...$$ whatever the initial values $$a_0$$ and $$a_1$$. This value is in fact equal to the value $$(1+\sqrt{17})/8$$ found for one of the roots of characteristic equation found by @maxmilgram. I have no true proof of this fact.

This is a variant on maxmilgram's answer. If we write $$a_n=1+u_n$$ with $$u_n\ge0$$ (as the OP observes), the recursion becomes

$$u_{n+2}^3+3u_{n+2}^2+4u_{n+2}=u_{n+1}+u_n$$

This implies $$4u_{n+2}\le u_{n+1}+u_n$$, at which point we have $$u_n\le v_n$$ with $$v_0=u_0$$, $$v_1=u_1$$, and

$$v_{n+2}={v_{n+1}+v_n\over4}$$

so that

$$0\le u_n\le v_n=C_1\left(1-\sqrt{17}\over8\right)^n+C_2\left(1+\sqrt{17}\over8\right)^n\to0$$