# Why is Fibonacci =< golden ration^n-1

• Sep 9th 2009, 12:31 PM
DeRSeD
Why 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, . . .

• Sep 9th 2009, 02:24 PM
Jameson
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 PM
awkward
Quote:

Originally Posted by DeRSeD
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, . . .

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.