# Prove $\lim_{n \rightarrow \infty} \frac{u_{n+1}}{u_{n}} = C,$ with $u_{0}=1$ and $u_{1}=2$.

I have the following recurrence relation

\begin{align} u_{0} &= 1 \nonumber \\ u_{1} &= 2 \nonumber \\ u_{n} &= u_{n-2} + u_{n-1} +1 \end{align}

Now I want to prove that the ratio after $$n$$ (where $$n$$ is large) remains constant. I can see this by simple putting the equation in excel and then see that the ratio grows to the Golden Ratio (i.e. $$\frac{1+\sqrt{5}}{2}$$).

Hence I want to prove $$\lim_{n \rightarrow \infty} \frac{u_{n+1}}{u_{n}} = C,$$ for some $$C \in \mathbb{R}$$ (more specifically $$C = \frac{1+\sqrt{5}}{2}$$.

I find $$\frac{u_{n+1}}{u_{n}} = \frac{u_{n-2}+u_{n-1}+1}{u_{n-1}+u_{n}+1},$$ but this does not really help me. I would say we can ommit the $$+1$$ in the equations since $$u_{n}$$ grows large but this is not really mathematically sound.

Any suggestions are more than welcome.

• Does this answer your question? How to prove that $\lim \limits_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}$
– LHF
Commented Jan 25, 2020 at 19:00
• @OlympiadIneqByBruteForce Notice the given sequence is not the Fibonacci sequence. That said, it is fairly close and the same approaches may be applicable here. Commented Jan 25, 2020 at 19:04
• Note that $u_n=F_{n+3}-1$ where $F_n$ denotes the $n$th Fibonacci number. Commented Jan 25, 2020 at 19:33

Define the sequence $$(v_n)_{n \in \mathbb{N}}$$ by $$v_n:=u_n+1$$ so that $$v_0=2, v_1=3, v_n = v_{n-1}+v_{n-2}$$ for all $$n \geq 2$$. Then an easy induction argument yields $$v_n = F_{n+3}$$ where $$F_n$$ denotes the $$n$$-th term of the Fibonacci sequence (defined by $$F_0:=0, F_1:=1$$ and $$F_n = F_{n-1}+F_{n-2} \forall n \geq 2$$), whence for all $$n \geq 0$$ we have $$u_n = F_{n+3}-1 = \frac{1}{\sqrt{5}} (\alpha^{n+3} - \beta^{n+3})$$ where $$\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}$$, using the well-known Binet's Formula (which can be derived simply by looking at the characteristic equation of the Fibonacci sequence). This finally yields $$\lim_{n \rightarrow \infty} \frac{u_{n+1}}{u_n} = \lim_{n \rightarrow \infty} \frac{F_{n+4}-1}{F_{n+3}-1} = \lim_{n \rightarrow \infty} \frac{F_{n+1}-1}{F_n-1} = \lim_{n \rightarrow \infty} \frac{\alpha^{n+1} - \beta^{n+1} - \sqrt{5}}{\alpha^n - \beta^n - \sqrt{5}} = \alpha \left( \lim_{n \rightarrow \infty} \frac{1 - \lambda^{n+1} - \frac{\sqrt{5}}{\alpha^{n+1}}}{1 - \lambda^n - \frac{\sqrt{5}}{\alpha^n}} \right) = \alpha = \frac{1+\sqrt{5}}{2}$$ where we have used $$\beta<1<\alpha \implies \lambda := \frac{\beta}{\alpha}<1 \implies \lim_{n \rightarrow \infty} \lambda^n=0$$.
Note that we have $$\frac{u_{n+1}}{u_n}<2$$ and the sequence is monotonically increasing, and bounded above, it guarantees the existence of the limit.
• How do you know the fraction is smaller than $2$?
• See that $u_{n+1}=u_{n-1}+u_n<u_n+u_n$, fibonacci sequence is an increasing sequence. Commented Jan 26, 2020 at 5:01
• This is not the Fibonacci Sequence, but it is clear that $u_n>0$ for all $n$ (induction), and so the recursion itself yields that the sequence is increasing, and now aud098's argument works. Commented Jan 26, 2020 at 7:58