# Induction and Fibonacci Numbers

• Jan 4th 2009, 06:46 PM
calabrone
Induction and Fibonacci Numbers
I am trying to figure out how to show that \$\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\$ when n is a positive integer.

My Work
P(n) is \$\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^n\$ for \$\displaystyle n>=1\$

Basis step - P(1) is true because \$\displaystyle f_{2}f_{0}-f_{1}^{2}=1*0-1=-1=(-1)^1\$
Inductive step - Assume \$\displaystyle P(k)=f_{k+1}f_{k-1}-f_{k}^{2}=(-1)^k\$ is true,
then \$\displaystyle P(k+1)=f_{k+2}f_{k}-(f_{k+1}^2=(-1)^{k+1} \$is true

Then prove \$\displaystyle P(k+1)=[f_{k+1}f_{k-1}-f_{k}^{2}]+[f_{k+2}f_{k}-f_{k+1}^{2}]=(-1)^k+[f_{k+2}f_{k}-f_{k+1}^2]\$, but I can't figure out how to get this P(k+1) equation to equal \$\displaystyle (-1)^{k+1} \$

I received the reply below, which is probably a wonderful answer, but I am unclear as to where http://www.mathhelpforum.com/math-he...dda283da-1.gif in the 3rd line came from. I though you had to add the initial part of the P(k+1) equation, which is \$\displaystyle f_{k+1}f_{k}-f_{k+1}^2\$, to both sides of the P(k) equation as I did above.

Assume http://www.mathhelpforum.com/math-he...63f299fa-1.gif for n.

We want to show that http://www.mathhelpforum.com/math-he...c1962bf5-1.gif

http://www.mathhelpforum.com/math-he...dda283da-1.gif

http://www.mathhelpforum.com/math-he...e5104150-1.gif

http://www.mathhelpforum.com/math-he...b4994ac0-1.gif,<--- negative of the induction hypothesis

http://www.mathhelpforum.com/math-he...78c4ac77-1.gif by the induction hypothesis.

http://www.mathhelpforum.com/math-he...f39e74ff-1.gif

So, http://www.mathhelpforum.com/math-he...63f299fa-1.gif is true.
• Jan 4th 2009, 10:18 PM
kooker
\$\displaystyle f_n(f_{n+1}+f_n) - f_{n+1}(f_{n}+f_{n-1})\$ comes directly from the definition of the Fibonacci numbers. Remember that \$\displaystyle f_n = f_{n-1} + f_{n-2}\$?
So in your case in \$\displaystyle f_{n}f_{n+2} - f^2_{n+1}\$
\$\displaystyle f_{n+2} = f_{n+1}+f_{n}\$
and
\$\displaystyle f^2_{n+1} = f_{n+1}f_{n+1} = f_{n+1}(f_{n}+f_{n-1}) \$,
since \$\displaystyle f_{n+1} = f_{n} + f_{n-1}\$
• Jan 5th 2009, 05:32 AM
calabrone
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 \$\displaystyle {-1}^{K}\$. Doesn't the answer also still need to be \$\displaystyle {-1}^{K+1}\$?

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:

http://www.mathhelpforum.com/math-he...91ba34a0-1.gif

Then, aren't I supposed to work on the second half of this equation to make it equal \$\displaystyle {-1}^{K+1}\$?

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 http://www.mathhelpforum.com/math-he...3984cfb4-1.gif? I already understand that -\$\displaystyle {-1}^{k}={-1}^{k+1}\$ I just don't know where the exra -1 came from.
• Jan 5th 2009, 08:42 AM
kooker
First of all
\$\displaystyle (-1)^k \not= (-1)^{k+1}\$
because they have opposite signs.

Second of all, extra \$\displaystyle -1\$ comes from swapping terms in the equation of the inductive assumption, as in \$\displaystyle 5-2=3, but 2-5=-(3)\$. That's it.