Proof by induction (Fibonacci numbers)

[jwpaine]

Hello!

My given problem: The Fibonacci numbers are defined as follows: Fib(0) = 1, Fib(1) = 1 and Fib(n) = Fib(n-1) + Fib(n-2). Using the Principle of Induction prove the following result for all n ≥ 0: Fib(1) + Fib(3) + Fib(5) + , ... , + Fib(2n+1) = Fib(2n+2)-1

Here is what I have done thus far:

Let P(n) be the property I wish to prove; that is, Fib(1) + Fib(3) + Fib(5) + , ... , + Fib(2n+1) = Fib(2n+2)-1
Base case: P(0) = Fib(2(0)+1) = Fib(2(0)+2) - 1; Fib(1) = Fib(2) - 1; 1 = 2-1; 1=1
Induction Hypothesis: for all n = k, P(k) = Fib(1) + Fib(3) + Fib(5) + , ... , + Fib(2k+1) = Fib(2k+2)-1

Then, P(k+1) = Fib(1) + Fib(3) + Fib(5) + , ... , + Fib(2(k+1)+1) = Fib(2(k+1)+2)-1
We may then separate out the next to last term, on the left hand side of the above equation, such that:

[ (Fib(1) + Fib(3) + Fib(5) + , ... , + Fib(2k+1) ] + Fib(2(k+1)+1) = Fib(2(k+1)+2)-1

By substitution of P(k), in the above LHS:

Fib(2k+2) - 1 + Fib(2(k+1) = Fib(2(k+1)) - 1

.....Am I even on the right track, here?
Thank you for any help!

 

[ksdhart]

I think you made a mistake in transcribing, but otherwise the logic seems okay to me, and seems to produces exactly the desired answer. When you get to this step, the error happens:

[ Fib(1) + Fib(3) + Fib(5) + ... + Fib(2k+1) ] + Fib(2(k+1)+1) = Fib(2(k+1)+2)-1

Replacing the expression in brackets with its equivalent, we should get the following, which is not what you wrote:

Fib(2k+2) - 1 + Fib(2(k+1)+1) = Fib(2(k+1)+2)-1

Clean that up a bit to get rid of nested parentheses, and add 1 to both sides:

Fib(2k+2) + Fib(2k+3) = Fib(2k+4)

And the above equation, by the known properties of Fibonacci numbers, must be true.

 

[jwpaine]

Oops! Thank you!