# Fibonacci proof

• December 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.
• December 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??
• December 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 $f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $n\geq 1$.
Which is true for $n=1$. Suppose it is true for all $k\leq n$. Then $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$
• December 26th 2007, 07:37 AM
Isomorphism
Quote:

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