# Induction w/ Fibonacci

• Apr 7th 2010, 05:06 PM
bakerconspiracy
Induction w/ Fibonacci
The question is prove that fn < 2^n, where fn is the nth number in the Fibonacci sequence.

I got the first steps,

For n = 3, fn = f(n-1) + f(n-2) = 1 + 1 < 2^3 = 2^n.

Assume fn < 2^n for some n. Now for n+1...

This is where I have the trouble. I'm pretty sure I have to use strong induction and break down the nth Fibonacci number, but I've been stuck on this one.

Any help is appreciated, Thanks.
• Apr 7th 2010, 07:07 PM
tonio
Quote:

Originally Posted by bakerconspiracy
The question is prove that fn < 2^n, where fn is the nth number in the Fibonacci sequence.

I got the first steps,

For n = 3, fn = f(n-1) + f(n-2) = 1 + 1 < 2^3 = 2^n.

Assume fn < 2^n for some n. Now for n+1...

...for $n+1$ we have $F_{n+1}=F_n+F_{n-1}<2^n+2^{n-1}<2^n+2^n=2^{n+1}$ and you're done

Tonio

This is where I have the trouble. I'm pretty sure I have to use strong induction and break down the nth Fibonacci number, but I've been stuck on this one.

Any help is appreciated, Thanks.

.