# Fibonacci proof

• Dec 26th 2007, 02:57 AM
asc
Fibonacci proof
The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

Plz give a counting prof instead of induction.
• Dec 26th 2007, 03:30 AM
Isomorphism
Quote:

Originally Posted by asc
The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

Plz give a counting prof instead of induction.

Can use fibonacci formula??
• Dec 26th 2007, 07:26 AM
ThePerfectHacker
Quote:

Originally Posted by asc
The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

Plz give a counting prof instead of induction.

We want to prove $\displaystyle f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $\displaystyle n\geq 1$.
Which is true for $\displaystyle n=1$. Suppose it is true for all $\displaystyle k\leq n$. Then $\displaystyle f_{n+1} = f_n+f_{n-1} \leq \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-2}= \left( \frac{1+\sqrt{5}}{2} \right)^n$
• Dec 26th 2007, 07:37 AM
Isomorphism
Quote:

Originally Posted by ThePerfectHacker
We want to prove $\displaystyle f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $\displaystyle n\geq 1$.
Which is true for $\displaystyle n=1$. Suppose it is true for all $\displaystyle k\leq n$. Then $\displaystyle f_{n+1} = f_n+f_{n-1} \leq \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-2}= \left( \frac{1+\sqrt{5}}{2} \right)^n$

The original poster wrote
Quote:

Plz give a counting prof instead of induction.