# Thread: Induction with Fibonacci Numbers

1. ## 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)

2. Assume $f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n}$ for n.

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

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

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

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

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

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

So, $f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n}$ is true.

3. ## 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:

I'm sure its obvious, I have just gotten myself so confused. Do you add the k+1 equation $f_(k+1)f_(k-1)-(f_k)^2$
to both sides of ? I was trying to teach myself by looking at examples but it doesn't seem to be working out.

4. 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:

I'm sure its obvious, I have just gotten myself so confused. Do you add the k+1 equation $f_(k+1)f_(k-1)-(f_k)^2$
to both sides of ? 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)

5. ## My Work So Far With Your Help

I am trying to get the following equation to equal ${-1}^{k+1}$

$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
$P(k+1)={-1}^{k}+[f_{k+2}f_{k}-f_{k+1}^{2}]$
$={-1}^{k}+(f_{k}+f_{k+1})f_{k}-(f_{k-1}+f_{k})f_{k+1}$
$={-1}^{k}+f_{k}^{2}+f_{k}f_{k+1}-f_{k-1}f_{k+1}-f_{k}f_{k+1}$
$={-1}^{k}+f_{k}^2-f_{k+1}f_{k-1}$
$
={-1}^{k}+f_{k}(f_{k-1}+f_{k-2})-(f_{k}+f_{k-1})f_{k-1}
$

$
={-1}^{k}+f_{k}f_{k-1}+f_{k}f_{k-2}-f_{k}f_{k-1}-f_{k-1}f_{k-1}
$

$
={-1}^{k}+f_{k}f_{k-2}-f_{k-1}f_{k-1}
$

$
={-1}^{k}
$

Does anyone know how to get the extra -1 to turn ${-1}^{k}$ into ${-1}^{k+1}$?

6. Look my my post. Perhaps it is hard to see. But, the negative of the induction hypothesis is $-(-1)^{k}=-1(-1)^{k}=(-1)^{k+1}$.

See?.

7. ## 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 , not just the $f_{k+2}f_{k}-f_{k+1}^{2}={-1}^{k}$?: