# Convergence of $u_{k+1} = \frac{1}{2-u_k u_{k-1}}$

Let $$u_0, u_1 \in \mathbb{R}$$ be arbitrary. I am interested in the sequence defined by: $$u_{k+1} = \frac{1}{2-u_k u_{k-1}}.$$ In particular I would like to find $$\lim_{k\rightarrow \infty} u_k$$ for this sequence. For a value $$\bar u$$ to be a potential limiting point, this value should at least satisfy: $$\bar u = \frac{1}{2-\bar u^2},$$ it is not hard to see that this equation has $$3$$ solutions, namely: $$\bar u = 1, -\frac{1}{2}(1+\sqrt{5}), \frac{1}{2}(-1+\sqrt{5}).$$ I can numerically verify that the first two candidates do not attract the sequence $$(u_k)_k$$, thus we only have $$u_k \rightarrow 1$$ resp. $$u_k\rightarrow -\frac{1}{2}(1+\sqrt{5})$$ when $$u_0,u_1 = 1$$ resp. $$u_0,u_1=-\frac{1}{2}(1+\sqrt{5})$$ whilst the third seems to be an attractor for the sequence.

Furthermore there is the special case where $$u_0 \cdot u_1 = 2$$, which we exclude as $$u_2$$ is not defined in this case.

However, I am unable to prove that for any $$u_0, u_1 \notin \{-1, -\frac{1}{2}(1+\sqrt{5})\}$$ and $$u_0 \cdot u_1 \neq 2$$, we have $$u_k \rightarrow \frac{1}{2} (-1+\sqrt{5})$$.

A related problem was studied here, and I understand the proof given there, but I do not see how to extend this new problem.

• I think you can analyze the iterations of $f(x,y)=(y,1/(2-xy))$. – lhf Feb 7 '20 at 11:39
• @lhf : can you elaborate (or send a reference)? I would like to try and do this myself but I am not aware of what I should show. – HolyMonk Feb 7 '20 at 12:03
• Look for the fixed points of $f$ (they lie on the diagonal $x=y$) and analyze the eigenvalues of the Jacobian of $f$ at the fixed points. – lhf Feb 7 '20 at 15:44
• @lhf I have looked into your suggestion quite a bit but have only found “standard methods” for linear recurrence relations. As I am still curious as to how one can prove the convergence, I have started a bounty on my question. – HolyMonk Mar 8 '20 at 17:23
• @AlexRavsky Alternatively, when $u_ku_{k-1}=2$ you can say that $u_{k+1}=\frac{1}{0}=\infty$. This makes $u_{k+2}=0,u_{k+3}=\frac{1}{2}$ and the sequence can go on. – Ewan Delanoy Mar 9 '20 at 14:35

We are lucky : one can find a closed-form expression for $$u_n$$ (see (1) below). This will allow us to show that the sequence always converges and to determine the limit.

Let us compute a first few terms. Putting $$x=u_1,y=u_0$$ we have $$u_2=\frac{1}{2-xy}$$, $$u_3=\frac{2-xy}{4-x-2xy}$$, $$u_4=\frac{4-x-2xy}{7-2x-4xy}$$, $$u_5=\frac{7-2x-4xy}{12-4x-7xy}$$, $$u_6=\frac{12-4x-7xy}{20-7x-12xy}$$.

We start to see a pattern here. First, the denominator of $$u_n$$ seems to coincide with the numerator of $$u_{n+1}$$, and the coefficients $$1,2,4,7,12,20$$ seem to be the Fibonacci numbers minus 1. To summarize, the following holds for $$n\leq 6$$ :

$$u_n=\frac{v_n}{v_{n+1}}, \ \textrm{where} \ v_n=(F_{n+1}-1)-(F_{n-1}-1)x-(F_{n}-1)xy \tag{1}$$

Now that we have guessed (1), we can prove it rigorously by induction : if (1) holds for $$n$$ and $$n+1$$, we have $$u_{n+2}=\frac{1}{2-u_nu_{n+1}}=\frac{1}{2-\frac{v_n}{v_{n+2}}}=\frac{v_{n+2}}{2v_{n+2}-v_n} \tag{2}$$

Notice that the Fibonacci sequence satisfies $$2F_{n+2}-F_n=F_{n+2}+(F_{n+2}-F_n)=F_{n+2}+F_{n+1}=F_{n+3} \tag{3}$$

Since $$(v_n)$$ is a linear combination of $$F_{n-1},F_n$$ and $$F_{n+1}$$, it will satisfy this linear recurrence as well : $$2v_{n+2}-v_n=v_{n+3}$$, so that (2) gives $$u_{n+2}=\frac{v_{n+2}}{v_{n+3}}$$ which finishes the proof of (1) by induction.

Let $$\phi$$ be the golden ratio, $$\phi=\frac{1+\sqrt{5}}{2}$$ and $$\psi=1-\phi=\frac{1-\sqrt{5}}{2}$$ is the conjugate of $$\phi$$. Using the well-known formula $$F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}$$, we deduce

$$v_n=\frac{\phi^2-x-\phi xy}{\sqrt{5}}\phi^{n-1}-\frac{\psi^2-x-\psi xy}{\sqrt{5}}\psi^{n-1}+(xy+x-1)\tag{4}$$

There are now several cases to consider. If $$c_1=\frac{\phi^2-x-\phi xy}{\sqrt{5}}$$ is nonzero, then $$v_n \sim c_1 \phi^{n-1}$$ as $$n\to\infty$$, so that $$u_n$$ converges to $$\phi$$.

Next, assume that $$c_1=0$$ but $$c_2=xy+x-1$$ is nonzero, then $$v_{n} \to c_2$$ as $$n\to\infty$$, so that $$(u_n)$$ converges to $$1$$.

Finally, if both $$c_1$$ and $$c_2$$ are zero, then $$x=y=1$$ and $$(u_n)$$ is constant equal to $$1$$.