-
September 7th, 2009, 02:35 PM
#1
Induction
I need help with this challenging question for my computer discrete structures/data structures class.
Ok I need to prove that the sum of the first n fibonacci numbers is equal to the (n+2)nd fibonacci number minus one using induction.
I don't know how to proceed since I'm stuck at the base case.
Here's my work so far:
P(n): 1+1+2+3+5+8+.........n = (n+2) -1
Base Case: P(1): 1+1+2+3+5+8....+1 = (1+2) -1
1 is not equal to 2 so I'm confused as to why the base case doesn't equal to 1...something wrong.
The question doesn't specify what value to start, but I know P(1) is normally the default case to begin a base case.
Help is greatly appreciated.
-
September 7th, 2009, 11:28 PM
#2
Re: Induction
I think you read the question wrong.
If P(n) is the sum of the first n Fibonacci numbers and F(n) is the nth Fibonacci number, then you are required to prove that for any natural number n:
Now, just for reference, let's look at the first values of the sum function (P):
Code:
P(1) = 1
P(2) = 1 + 1 = 2
P(3) = 1 + 1 + 2 = 4
P(4) = 1 + 1 + 2 + 3 = 7
.
.
Therefore, the induction base case(n=1) is:
Code:
P(n) = P(1) = 1
F(n+2) = F(3) = 2
P(1) = 1 = 2-1 = F(3)-1
as required.
Regards,
Zachm
Last edited by Zachm; September 7th, 2009 at 11:44 PM.
-
September 9th, 2009, 10:24 PM
#3
Re: Induction
So the next step would be this:
P(k): 1+1+2+3+5+8+.........k= (k+2) -1
And the next step would be this:
P(k+1) 1+1+2+3+5+8+.......k+k+1=(k+2)+1-1 which would simply be:
P(k+1) 1+1+2+3+5+8+.......k+k+1=(k+2) OR would it be:
P(k+1) 1+1+2+3+5+8+.......k+k+1=(k+3)-1 since the k+1 was added to the original k+2.
Am I correct on one of these?
-
September 10th, 2009, 03:20 AM
#4
Re: Induction
Originally Posted by coder752
So the next step would be this:
P(k): 1+1+2+3+5+8+.........k= (k+2) -1
And the next step would be this:
P(k+1) 1+1+2+3+5+8+.......k+k+1=(k+2)+1-1 which would simply be:
P(k+1) 1+1+2+3+5+8+.......k+k+1=(k+2) OR would it be:
P(k+1) 1+1+2+3+5+8+.......k+k+1=(k+3)-1 since the k+1 was added to the original k+2.
Am I correct on one of these?
No, you made a small but significant mistake:
Code:
P(k): 1+1+2+3+5+8+.........k= (k+2) -1
k represents an index of a number in the Fibonacci series, and NOT the number itself.
This induction assumption should be that for each k = 1 to n:
Code:
P(k) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k)= F(k+2) -1
Now, the induction step is to see that the assumption is true also for k+1:
Code:
P(k+1) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k) + F(k+1) = F(k+2) -1 + F(k+1)
This was just adding F(K+1) to both flanks.
If we organize it a bit:
Code:
P(k+1) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k) + F(k+1) = (F(k+1) + F(k+2)) -1
now, remember that each number in the Fibonacci series equals to the sum of it's 2 predecessors, hence you can replace
with
Finally you will get:
Code:
P(k+1) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k) + F(k+1) = F(k+3) - 1
As required.
Regards,
Zachm
Last edited by Zachm; September 10th, 2009 at 03:22 AM.
-
September 14th, 2009, 04:30 PM
#5
Re: Induction
I got a Question
about this part:
P(k) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k)= F(k+2) -1
i understand F(K+n) is the index of the number but where did you get F(k-2) + F(k-1) + F(k) from???
P(k+1) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k) + F(k+1) = F(k+2) -1 + F(k+1)
why do we need F(k+1) in it?
and about the last part
how do we know the left part is equal to the right part?
-
September 15th, 2009, 03:30 AM
#6
Re: Induction
Originally Posted by DarksMagician
about this part:
P(k) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k)= F(k+2) -1
i understand F(K+n) is the index of the number
F(k+n) is NOT the index of the number!
F(k+n) is THE (k+n)th Fibonacci number.
k+n is the index of that number in your case, but I don't see where I used such an index in my proof.
Originally Posted by DarksMagician
but where did you get F(k-2) + F(k-1) + F(k) from???
P(k+1) = 1+1+2+3+5+8+.........+F(k-2) + F(k-1) + F(k) + F(k+1) = F(k+2) -1 + F(k+1)
F(i) is the value of the ith Fibonacci number.
P(n) is the sum of the Fibonacci series numbers up to n:
Code:
[1] P(n) = 1 + 1 + 2 + 3 + 5 + ..... + F(n-5) + F(n-4) + F(n-3) + F(n-2) + F(n-1) + F(n)
This is just the definition of P(n).
Originally Posted by DarksMagician
why do we need F(k+1) in it?
This is the induction step - you assume the theorem holds for P(k) and prove it holds also for P(k+1).
If you replace n with k+1 you would get:
Code:
[2] P(k+1) = 1 + 1 + 2 + 3 + 5 + ..... + F(k-4) + F(k-3) + F(k-2) + F(k-1) + F(k) + F(k+1)
Where P(k+1) is the sum of the Fibonnaci series numbers up to k+1.
This is JUST the definition of P(k+1).
As you might have seen,
Code:
[3] P(k+1) = P(k) + F(k+1)
- this is also deduced from the definition of P.
The induction assumption was that:
Code:
[4] P(k) = F(k+2)-1
In statement [3], replace P(k) according to statement [4] and you will get:
Code:
[5] P(k+1) = F(k+2) - 1 + F(k+1)
Originally Posted by DarksMagician
and about the last part
how do we know the left part is equal to the right part?
From this question I can assume that you either didn't follow all the steps or don't fully understand the notion of induction.
If the 1st is true - follow all the steps again.
If the latter is true, you should understand that proof by induction means that you assume the theorem holds for P(k), and you use this assumption to prove that it also holds for P(k+1).
This is exactly what I did,
I showed that assuming that P(k) = F(k+2)-1, the equation at the end is true.
By showing this (as well as truthfullness of some base case) I show that it will be true for ANY given k >= 1.
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
|