Induction Question

[coder752]

I have another induction question. Here's my work. I think I got it right(except the base case).

Help is greatly appreciated. Thanks in advance.

The question goes as this: Prove using induction that the nth Fibonacci # is at most 2^n.

my work:

P(1) aka base case is ...k = 2^k

1= 2^1 I don't understand how to get it equal and making it check.

P(k): 1+1+3+5+........+k+ 2^k

P(k+1): 1+1+3+5+........k +(k+1) = 2^k +(k+1)

And that's all I got up to. I think it will hold true.