Using a specific definition to find limit of Fibonacci Sequence

Question

Problem:

Use $f_{n+2}$ = $f_{n+1}$ + $f_n$ and the fact that $\{\frac{f_{n+1}}{f_n}\}_{n=1}^{\infty}$ converges to find the $\lim_{n \to \infty}$ $\frac{f_{n+1}}{f_n}$.

Attempt:

Since $\lim_{n \to \infty}$ $\frac{f_n+1}{f_n}$ converges, then $\lim_{n \to \infty}$$\frac{f_n+1}{f_n} = L$ by properties of limit.

We have $f_{n+2} = f_{n+1} + f_n$ which is equal to $f_{n+1} = f_{n+2} - f_n$.

Then $\lim_{n \to \infty} \frac{f_n+1}{f_n} \implies \lim_{n \to \infty} \frac{f_{n+2} - f_n}{f_n} = L \implies\lim_{n \to \infty}\frac{f_{n+2}}{f_n} - 1 = L$.

I actually don't know where to go on from here.

Answer 1

Since it is given that $f_{n+1}/f_n$ has a limit you can use that

$$1 + {f_{n+1}\over f_n} = {f_n+f{n+1}\over f_n} = {f_{n+2}\over f_n} = {f_{n+2}f_{n+1}\over f_{n+1}f_n} = {f_{n+2}\over f_{n+1}}{f_{n+1}\over f_n} $$

Since we can assume that the limit exists we know that the limit of the LHS and RHS exists. If $L = \lim_{n\to\infty} f_{n+1}/f_n$ we have that. $$1 + L = L^2$$ This has the solutions $L = (1\pm \sqrt5)/2$, one of these are negative, but it's quite easy to see by induction that $f_n\ge 0$ for all $n$ which means that the limit can't be negative. So the limit must be $(1+\sqrt5)/2$

The problem would have been harder if you couldn't assume that the limit exists in the first place. To do this you can either find a closed form expression for $f_n$ or you can consider the sequence $q_n = f_{n+1}/f_n$ and find a recursion formula for $q_{2n}$ and $q_{2n+1}$ and use that to find their limits. These limits will exists since one can from the recurrence relation show that one of them is bounded decreasing and one is bounded increasing.

The recurrence relation for $q_n$ is $$q_{n+1} = {2q_n + 1\over q_n}$$ By studying the function $\phi(x) = (2x+1)/(x+1)$ we can see that if $q_n > (1+\sqrt5)/2$ we have that $(1+\sqrt5)/2< q_{n+2} < q_n$, and that if $q_n<(1+\sqrt5)/2$ we have that $q_n < q_{n+2} < (1+\sqrt5)/2$. This makes $q_{2n}$ and $q_{2n+1}$ to be both bounded and one decreasing and one increasing. On then uses that their limit must fulfill $q = (2q+1)/(q+1)$ which gives that $\lim_{n\to\infty}q_{2n} = \lim_{n\to\infty}q_{2n+1} = (1+\sqrt5)/2= \lim_{n\to\infty}q_n$