Thread: Induction and Fibonacci Numbers

I am trying to figure out how to show that when n is a positive integer.

My Work
P(n) is for

Basis step - P(1) is true because
Inductive step - Assume is true,
then is true

Then prove , but I can't figure out how to get this P(k+1) equation to equal

I received the reply below, which is probably a wonderful answer, but I am unclear as to where in the 3rd line came from. I though you had to add the initial part of the P(k+1) equation, which is , to both sides of the P(k) equation as I did above.

First Reply
Assume for n.

We want to show that





,<--- negative of the induction hypothesis

by the induction hypothesis.



So, is true.

comes directly from the definition of the Fibonacci numbers. Remember that ?
So in your case in

and
,
since

The math makes sense but I still do not understand why you are allowed to do the "negative of the inductive hypothesis" to get the extra -1 to make the answer . Doesn't the answer also still need to be ?

Also, I thought it wasn't supposed to prove the exact P(k+1) equation in the inductive step but rather the P(k) equation with the first part of P(k+1) added to both sides as follows:



Then, aren't I supposed to work on the second half of this equation to make it equal ?


EDIT:

The math makes sense but I still do not understand why you are allowed to do the "negative of the inductive hypothesis" to get the extra -1 to make the answer be ? I already understand that - I just don't know where the exra -1 came from.

First of all

because they have opposite signs.

Second of all, extra comes from swapping terms in the equation of the inductive assumption, as in . That's it.