Fibonacci golden ratio question without assuming convergence a priori

Question

Prove $\frac{F(n+1)}{F(n)}$ converges to $\phi$ without assuming a priori that it converges

If I know it converges, then I know it converges to $\phi$

Since, if $\lim_{n\to\infty} \frac{F(n+1)}{F(n)} \to r$ then,

$\lim_{n\to\infty}\frac{F(n+1)}{F(n)} = \lim_{n\to\infty}\frac{F(n)+F(n-1)}{F(n)} = 1+\frac{1}{r} = r \to r=\phi$

But how do I know $\lim_{n\to\infty} \frac{F(n+1)}{F(n)}$ converges in the first place?

Answer 1

Let $\phi, \varphi$ be the positive & negative solutions, respectively, of $$x^2 = x + 1$$ So $$\phi + \varphi = 1$$ and $$\phi\varphi = -1$$ That is, $$\varphi = 1 - \phi = -\phi^{-1}$$ So $$\phi, \varphi = \frac{1\pm\sqrt5}2$$ That is, $$\phi\approx 1.6180339$$ and $$\varphi\approx -0.6180339$$ Also, $$\phi - \varphi = \sqrt5$$

Now, for any $n$, $$x^{n+1} = x^n + x^{n-1}$$ and so with a simple induction we can construct a Fibonacci sequence of powers of $x$, as this table shows:

n	$F_n$	$x^n$	$x^n$
0	0	$x^0$	$0x +1$
1	1	$x^1$	$1x + 0$
2	1	$x^2$	$1x + 1$
3	2	$x^3$	$2x + 1$
4	3	$x^4$	$3x + 2$
5	5	$x^5$	$5x + 3$
n	$F_n$	$x^n$	$F_nx + F_{n-1}$

Thus $$\phi^n = F_n\phi+ F_{n-1}$$ and $$\varphi^n = F_n\varphi+ F_{n-1}$$ We can easily use these results to derive the Binet formula, but we don't need that here.

$$\varphi^n= F_n\varphi+ F_{n-1}$$ $$(-1)^n\phi^{-n} = F_n(1 - \phi) + F_{n-1}$$ $$\frac{(-1)^n}{\phi^n} = F_{n+1} - \phi F_n$$ $$\frac{F_{n+1}}{F_n} = \phi + \frac{(-1)^n}{F_n\phi^n}$$

Clearly, the RHS converges to $\phi$.

Answer 2

you can easily show that it is bounded, as all terms $t_n$ are greater (or equal to) than 0, $t_n\ge0$, and we can also know that

$$t_{n+1}=t_n+t_{n1}\le t_n+t_n$$ as the next Fibonacci number is grater then the one before, from this we can show, assuming $t_n \neq0. $$ \frac{t_{n+1}}{t_{n}}=\frac{t_n+t_{n1}}{t_n}\le \frac{2t_n}{t_n}=2$$

so $\frac{t_{n+1}}{t_{n}} \le 2$ and as all the number are greater than $0$ so we get that $$0\le \frac{t_{n+1}}{t_{n}} \le 2$$ and as $t_{n+1}\ge t_n$ we know that it converges to a value and doesn't oscillate.

Hope that helps

Answer 3

Binet's formula gives an answer:

$F(n)=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt(5)}$

so

$\lim_{n_\to\infty}\frac{F(n+1)}{F(n)}=$

$\lim_{n_\to\infty}\frac{(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}}{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}=$

$\lim_{n_\to\infty}\frac{(\frac{1+\sqrt(5)}{2})(-3-\sqrt(5))^n-(\frac{1-\sqrt(5)}{2})}{(-3-\sqrt(5))^n-1}=$

$\lim_{n_\to\infty}\frac{1+\sqrt(5)}{2}=$

$\phi$