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.