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

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.

• do you really mean $(f_{n} + 1)/f_n$, as written, or do you mean $f_{n+1}/f_n$? Nov 13 '14 at 20:00
• Sorry had a typo there, edited. Nov 13 '14 at 20:06
• What do you want to prove?That $\lambda_n$ converges or $\sigma_n$? Nov 13 '14 at 20:08
• I want to prove that $\lambda_n$ converges in the first place, using $\sigma_n$. Nov 13 '14 at 20:10
• If i showed that $\sigma_n$ converges, i have shown that $\lambda_n$ converges, right? Nov 13 '14 at 20:13

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$.
• (referring to first approach) Thank you, i really appreciate your help. Sorry to be a pain, But there is two things i don't understand : 1. How do you get from the 3rd to the fourth transformation step? And 2. I can't follow what you did in the final conclusion, i don't understand why the left side implies the right side.. Nov 13 '14 at 21:13
• The second approach makes more sense to me - i still have trouble understanding why $|\frac{\beta}{\alpha}|<1$ implies that the limit of $\sigma_n$ is 0, as we only have the recursive sequence of $\sigma_n$. Nov 13 '14 at 21:23
• @FalcoWinkler I've added some notes to explain some fine points. Is it clear now? Nov 13 '14 at 21:30
• YES yes yes, with those notes it is more clear now. I will still have to work my way through it, but thanks for the detailed answer! You should definitely get more upvotes on that. Nov 13 '14 at 21:41
• Since $\sigma_1 = -\alpha^{-2}$ and $\left( \frac{\beta}{\alpha} \right) = -\alpha^{-2}$ this answer can be simplified to $$(-1)^n \alpha^{-2n}$$. As in the third answer below. Nov 14 '14 at 16:09

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.$$

• But have i proven yet that the limit of $\lambda_n$ is $\alpha$? Nov 13 '14 at 20:23
• @FalcoWinkler: if not, it is worth proving it :) Nov 13 '14 at 20:42
• Thanks for your efforts so far - but proving $\lambda_n$ convergent is what i have to do. The task says we should do that while looking at the sequence $\sigma_n$. Do you know what i mean? Nov 13 '14 at 20:46

$$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.