How can it be proved by induction that the Fibonaaci series is always:

Fn <= ( (1 +sqrt 5)/2 )^(n−1).

F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn, for n = 0, 1, 2, . . .

golden ratio= http://upload.wikimedia.org/math/7/f...ab1e8044aa.png

Printable View

- Sep 9th 2009, 12:31 PMDeRSeDWhy is Fibonacci =< golden ration^n-1
How can it be proved by induction that the Fibonaaci series is always:

Fn <= ( (1 +sqrt 5)/2 )^(n−1).

F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn, for n = 0, 1, 2, . . .

golden ratio= http://upload.wikimedia.org/math/7/f...ab1e8044aa.png - Sep 9th 2009, 02:24 PMJameson
I don't know if you can just use the well-known formula for the nth term of the Fibonacci sequence, but if not you can find a derivation here as well as some other identities.

- Sep 10th 2009, 06:26 PMawkward
Start by showing that $\displaystyle F_n \leq \phi ^{n-1}$ for n = 0 and n = 1.

Then assume $\displaystyle F_n \leq \phi ^{n-1}$ for all $\displaystyle n \leq k$, where $\displaystyle k > 1$. If so, then

$\displaystyle F_{k+2} = F_{k} + F_{k+1} \leq \phi ^{k-1} + \phi ^k$

If you can show $\displaystyle \phi ^{k-1} + \phi ^k \leq \phi ^{k+1}$ then you will be done. You might want to start by looking at the case k=1.