0
$\begingroup$

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.

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

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$.
$\endgroup$
5
  • $\begingroup$ (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.. $\endgroup$ Nov 13 '14 at 21:13
  • $\begingroup$ 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$. $\endgroup$ Nov 13 '14 at 21:23
  • $\begingroup$ @FalcoWinkler I've added some notes to explain some fine points. Is it clear now? $\endgroup$ Nov 13 '14 at 21:30
  • $\begingroup$ 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. $\endgroup$ Nov 13 '14 at 21:41
  • $\begingroup$ 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. $\endgroup$ Nov 14 '14 at 16:09
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ But have i proven yet that the limit of $\lambda_n$ is $\alpha$? $\endgroup$ Nov 13 '14 at 20:23
  • $\begingroup$ @FalcoWinkler: if not, it is worth proving it :) $\endgroup$ Nov 13 '14 at 20:42
  • $\begingroup$ 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? $\endgroup$ Nov 13 '14 at 20:46
-1
$\begingroup$

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

$\endgroup$

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.