-
September 14th, 2009, 08:19 PM
#1
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.
Last edited by coder752; September 14th, 2009 at 08:21 PM.
-
September 15th, 2009, 03:37 AM
#2
Re: Induction Question
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:
Therefore, your base case is:
- 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
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|