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