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.

  • $\begingroup$ I think you can analyze the iterations of $f(x,y)=(y,1/(2-xy))$. $\endgroup$ – lhf Feb 7 '20 at 11:39
  • $\begingroup$ @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. $\endgroup$ – HolyMonk Feb 7 '20 at 12:03
  • $\begingroup$ 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. $\endgroup$ – lhf Feb 7 '20 at 15:44
  • $\begingroup$ @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. $\endgroup$ – HolyMonk Mar 8 '20 at 17:23
  • 1
    $\begingroup$ @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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.