Induction with Fibonacci Numbers

• Jan 4th 2009, 03:10 PM
calabrone
Induction with Fibonacci Numbers
I am trying to figure out how to show that f_(n+1)f_(n-1)-(f_n)^2=(-1)^n when n is a positive integer.

My Work
P(n) is f_(n+1)f_(n-1)-(f_n)^2=(-1)^n for n>=1
Basis step - P(1) is true because f_2f_0-(f_1)^2=1*0-1=-1=(-1)^1
Inductive step - Assume P(k)=f_(k+1)f_(k-1)-(f_k)^2=(-1)^k is true, then P(k+1)=f_(k+2)f_(k)-(f_(k+1))^2=(-1)^(k+1) is true

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]

I can't figure out how to get this equation to equal (-1)^(k+1)
• Jan 4th 2009, 03:35 PM
galactus
Assume \$\displaystyle f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n}\$ for n.

We want to show that \$\displaystyle f_{n}f_{n+2}-f_{n+1}^{2}=(-1)^{n+1}\$

\$\displaystyle =f_{n}(f_{n+1}+f_{n})-f_{n+1}(f_{n}+f_{n-1})\$

\$\displaystyle =f_{n}f_{n+1}+f_{n}^{2}-f_{n}f_{n+1}-f_{n+1}f_{n+1}\$

\$\displaystyle =f_{n}^{2}-f_{n+1}f_{n-1} \;\ = \;\ -(-1)^n\$,<--- negative of the induction hypothesis

\$\displaystyle =-(-1)^{n}=(-1)^{n+1}\$ by the induction hypothesis.

\$\displaystyle \therefore, \;\ f_{n}f_{n+2}-f_{n+1}^{2}=-(-1)^{n}\$

So, \$\displaystyle f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n}\$ is true.
• Jan 4th 2009, 04:04 PM
calabrone
Thank you!
I am having such a hard time with this problem but you definitely opened up my eyes to a totally new approach. Thank you sooo much. I understand all the math but I am not totally sure where you came up with the following:

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

I'm sure its obvious, I have just gotten myself so confused. Do you add the k+1 equation \$\displaystyle f_(k+1)f_(k-1)-(f_k)^2\$
to both sides of http://www.mathhelpforum.com/math-he...63f299fa-1.gif? I was trying to teach myself by looking at examples but it doesn't seem to be working out.
• Jan 4th 2009, 07:16 PM
qpmathelp
Quote:

Originally Posted by calabrone
I am having such a hard time with this problem but you definitely opened up my eyes to a totally new approach. Thank you sooo much. I understand all the math but I am not totally sure where you came up with the following:

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

I'm sure its obvious, I have just gotten myself so confused. Do you add the k+1 equation \$\displaystyle f_(k+1)f_(k-1)-(f_k)^2\$
to both sides of http://www.mathhelpforum.com/math-he...63f299fa-1.gif? I was trying to teach myself by looking at examples but it doesn't seem to be working out.

--------------
definition of fibonacci sequence

f(n+2) = f(n) +f(n+1)

and one of the f(n)'s in the second term with
with f(n) = f(n-1) +f(n)
• Jan 4th 2009, 08:32 PM
calabrone
My Work So Far With Your Help
I am trying to get the following equation to equal \$\displaystyle {-1}^{k+1}\$

\$\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}]\$

Steps
\$\displaystyle P(k+1)={-1}^{k}+[f_{k+2}f_{k}-f_{k+1}^{2}]\$
\$\displaystyle ={-1}^{k}+(f_{k}+f_{k+1})f_{k}-(f_{k-1}+f_{k})f_{k+1}\$
\$\displaystyle ={-1}^{k}+f_{k}^{2}+f_{k}f_{k+1}-f_{k-1}f_{k+1}-f_{k}f_{k+1}\$
\$\displaystyle ={-1}^{k}+f_{k}^2-f_{k+1}f_{k-1}\$
\$\displaystyle
={-1}^{k}+f_{k}(f_{k-1}+f_{k-2})-(f_{k}+f_{k-1})f_{k-1}
\$
\$\displaystyle
={-1}^{k}+f_{k}f_{k-1}+f_{k}f_{k-2}-f_{k}f_{k-1}-f_{k-1}f_{k-1}
\$
\$\displaystyle
={-1}^{k}+f_{k}f_{k-2}-f_{k-1}f_{k-1}
\$
\$\displaystyle
={-1}^{k}
\$

Does anyone know how to get the extra -1 to turn \$\displaystyle {-1}^{k}\$ into \$\displaystyle {-1}^{k+1}\$?
• Jan 5th 2009, 08:47 AM
galactus
Look my my post. Perhaps it is hard to see. But, the negative of the induction hypothesis is \$\displaystyle -(-1)^{k}=-1(-1)^{k}=(-1)^{k+1}\$.

See?.
• Jan 5th 2009, 09:00 AM
calabrone
Now I understand that part
Thank you! I'm concentrating so hard that I'm missing the obvious!

You simply switched the terms around to get an extra negative on the right side of the equation? and you simplified the P(k+1) equation which made it the negative of the P(k) equation, correct?

Also, am I incorrect to think you have to make the following equation equal http://www.mathhelpforum.com/math-he...e0cc649a-1.gif, not just the \$\displaystyle f_{k+2}f_{k}-f_{k+1}^{2}={-1}^{k}\$?:

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