How to prove the convergence of $\lambda_n = \frac{f_{n+1}}{f_n}$?

Question

A question about the fibonacci sequence.

I have a sequence:

$$\lambda_n = \frac{f_{n+1}}{f_n}$$

While $f_n$ is the fibonacci sequence.

I also have the equation: $$ 0 = x^2 - x -1$$ And i know that the two possible values for x are:

$$x= \frac {1\pm \sqrt{5}}{2}$$

(The famous golden ratio)

Let $\alpha$ be the positive solution for the above equation. Let $\beta$ be the negative one.

I want to show that $$\sigma_n = \frac {\lambda_n - \alpha}{\lambda_n - \beta}$$

converges (It does converge against 0 right? Because $\lambda_n$ converges against $\alpha$ But how would i go on proving it?).

I know about Cauchy's convergence criterion, and the definition for limits.. etc. I don't get how to apply them here. For me, the coherence between the fibonacci sequence and the golden ratio is really hard to understand.

P.S: This is an exercise in analysis 1 (computer science), first term. I have seen questions like: Fibonacci and the algebraic expression $x^2-x-1$

But i can't understand these because i haven't ever seen most of the stuff they do there in our lectures.

Answer 1

To prove the convergence, I'll directly compare successive terms of $\lambda_n - \phi$ where $\phi$ is the golden mean (i.e. your $\alpha$). Notice

$$\frac{\lambda_n - \phi}{\lambda_{n-1} - \phi} = \frac{F_{n+1} - \phi F_n}{F_n - \phi F_{n-1}}\frac{F_{n-1}}{F_n} = \frac{(1-\phi)F_n + F_{n-1}}{F_n - \phi F_{n-1}}\frac{F_{n-1}}{F_n}\\ \stackrel{\color{blue}{[1]}}{=} \frac{(1-\phi)F_n - F_{n-1}\phi(1-\phi)}{F_n - \phi F_{n-1}}\frac{F_{n-1}}{F_n} = (1-\phi)\frac{F_{n-1}}{F_n} $$ Since $F_n$ is increasing, $\left|\frac{F_{n-1}}{F_n}\right| \le 1$. Together with $|1 - \phi| = \phi^{-1} < 1$, we get

$$\left|\frac{\lambda_n - \phi}{\lambda_{n-1} - \phi}\right| < \phi^{-1} \quad\stackrel{\color{blue}{[2]}}{\implies}\quad | \lambda_n - \phi | \le \phi^{-(n-1)} |\lambda_1 - \phi| = \phi^{-n} \to 0\;\text{ as }\; n \to \infty $$

As a result, $\lim\limits_{n\to\infty} \lambda_n = \phi$.

Update

As an alternate approach, one can compare the successive terms of $\sigma_n$. Notice

$$\begin{align} \sigma_n &= \frac{\lambda_n - \alpha}{\lambda_n - \beta} = \frac{F_{n+1} - \alpha F_n}{F_{n+1} - \beta F_n}\\ &= \frac{(1-\alpha)F_n + F_{n-1}}{(1-\beta)F_n + F_{n-1}} = \frac{(1-\alpha)F_n - \alpha(1-\alpha)F_{n-1}}{(1-\beta)F_n - \beta(1-\beta)F_{n-1}}\\ &= \frac{1-\alpha}{1-\beta}\frac{\lambda_{n-1}-\alpha}{\lambda_{n-1}-\beta}\\ &= \frac{\beta}{\alpha}\sigma_{n-1} \end{align} $$ Since $\left|\frac{\beta}{\alpha}\right| < 1$, we find

$$\lim_{n\to\infty} \sigma_n \stackrel{\color{blue}{[2]}}{=} \lim_{n\to\infty} \left(\frac{\beta}{\alpha}\right)^{n-1} \sigma_1 = 0 \quad\implies\quad \lim_{n\to\infty} \lambda_n = \lim_{n\to\infty} \frac{\alpha-\beta\sigma_n}{1-\sigma_n} = \frac{\alpha - \beta\cdot 0}{1-0} = \alpha$$

Notes

• $\color{blue}{[1]}$ - We are using the identity $1 = -\phi(1-\phi)$ here.
• $\color{blue}{[2]}$ - We are using the fact $|\lambda_n - \phi|$ is equal to the product of $|\lambda_1 - \phi|$ with a telescoping products of ratios. More precisely, $$|\lambda_n - \phi| = \underbrace{\left|\frac{\lambda_n - \phi}{\lambda_{n-1} - \phi}\right|}_{ < \phi^{-1}} \underbrace{\left|\frac{\lambda_{n-1} - \phi}{\lambda_{n-2} - \phi}\right|}_{ < \phi^{-1}} \cdots \underbrace{\left|\frac{\lambda_{2} - \phi}{\lambda_{1} - \phi}\right|}_{ < \phi^{-1}} |\lambda_1 - \phi| < \phi^{-(n-1)}|\lambda_1 - \phi|$$ For the same sort of reasoning, we have $\sigma_n = \frac{\beta}{\alpha} \sigma_{n-1}$ for all $n > 1$ implies $\sigma_n = \left(\frac{\beta}{\alpha}\right)^{n-1}\sigma_1$.

Answer 2

We have: $$\sigma_n = \frac{f_{n+1}-\alpha\,f_n}{f_{n+1}-\beta\, f_n}=1+\frac{(\beta-\alpha)\,f_n}{f_{n+1}-\beta\,f_n}=1+\frac{\beta-\alpha}{\frac{f_{n+1}}{f_n}-\beta}$$ and since $\lim_{n\to +\infty}\frac{f_{n+1}}{f_n}=\alpha$, our limit ($\lim_{n\to +\infty} \sigma_n$) equals: $$1+\frac{\beta-\alpha}{\alpha-\beta}=0.$$

Answer 3

$$ f_n = \frac{\alpha^n-\beta^n}{\sqrt{5}} $$ where $\alpha = \frac{1 + \sqrt{5}}{2}$ and $\beta = \frac{1 - \sqrt{5}}{2} = -\frac{1}{\alpha}$.

A bit of algebra gives $$ \lambda_n = \frac{\alpha^{n+1}-\beta^{n+1}}{\alpha^n-\beta^n} $$ $$ \sigma_n =\frac{\alpha\beta^b-\beta^{n+1}}{\alpha^{n+1}-\beta\alpha^n}= \left(\frac{\beta}{\alpha}\right)^n=(-1)^n\alpha^{-2n} $$ And since $|\alpha| > 1$ this converges to zero.