1. ## 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.

2. 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 $\displaystyle n+1$ we have $\displaystyle 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.
.