.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 we have 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.