Induction

[coder752]

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.

[Zachm]

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:

P(n) = F(n+2) - 1

Now, just for reference, let's look at the first values of the sum function (P):

 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:

P(n) = P(1) = 1

F(n+2) = F(3) = 2

P(1) = 1 = 2-1 = F(3)-1
as required.

Regards,
Zachm

[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?

[Zachm]

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:

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:

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:

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:

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

 (F(k+1) + F(k+2))

with

F(k+3)

Finally you will get:

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

[DarksMagician]

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?

[Zachm]

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:

[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:

[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,

[3]   P(k+1) = P(k) + F(k+1)

- this is also deduced from the definition of P.

The induction assumption was that:

[4]   P(k) = F(k+2)-1

In statement [3], replace P(k) according to statement [4] and you will get:

[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