Fibonacci proof

Printable View

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.