Induction Question

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.

Quote:

---

Originally Posted by coder752

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.

---

You should show that the nth Fibonacci number is AT MOST 2^n,
Mathematically speaking, you should show that for any n:

Code:

---

F(n) ≤ 2^n

---

Therefore, your base case is:

Code:

---

F(1) = 1 ≤ 2^1

---

- check !

Don't confuse F(n) (the nth Fibonacci number) with P(n) from your last posts.
You should be able to continue from here on your own.

Regards,
Zachm