# Math Help - Recursion Proof

1. ## Recursion Proof

Can anyone help me with this proof?

"Show that $f_{n+1}f_{n-1}-f^2_n=(-1)^n$ when $n$ is a positive integer."

2. Use induction and the recursion formula: $f_0 = 0, \ f_1 = 1, \ f_{n+1} = f_{n} + f_{n-1} \quad \forall n \geq 1$

Let $P_n$ be the statement that $f_{n+1}f_{n-1}-f^{\ 2}_n=(-1)^n$, for all positive integer $n$.

Base case: $P_1$ says that $f_2f_0 - f_1^{\ 2} = (-1)^1$ which is true.

Inductive step: Assume $P_k$ to be true, that is, $f_{k+1}f_{k-1}-f^{\ 2}_k=(-1)^k$ for some positive $k$. It remains to show that $P_{k+1}$ is also true, that is, $f_{k+2}f_{k}-f^{\ 2}_{k+1}=(-1)^{k+1}$.

$f_{k+2}f_{k}-f^{\ 2}_{k+1}$
$= \left(f_{k+1} + f_{k}\right)f_{k} - f_{k+1}^2$
$= f_{k+1}f_{k} + f_k^{\ 2} - f_{k+1}^{\ 2}$
$= f_{k+1} \left( {\color{red}f_{k} - f_{k+1}}\right) + f_{k}^{\ 2}$ ........... What is the red equal to? Recall the recursive definition and everything should work out.

3. Alright, I've been trying to prove this through induction and using the Fibonacci Sequence.

$f_{n+1}f_{n-1}-f^2_n=(-1)^n$ when $n$ is a positive integer.

Assume this is true for $n$, and prove this for $n=n+1$ by Induction Hypothesis

Basis: $f_{2}f_{0}-f^2_1=(-1)^1$
Fibonacci Sequence: $F(0)=0 F(1)=1$ for $F(n+1)=F(n)+F(n-1)$
Therefore, this is trivially true.

$f_{n+1+1}f_{n+1-1}f^2_{n+1}=(-1)^{n+1}$
$f_{n+2}f_n-f^2_{n+1}=(-1)(-1)^n$

Scratch:
When using Fibonacci's Sequence we can use the relationships between $f_n, f_{n+1}, f_{n+2}$. But I think we're missing a fourth term, so I added $f_{n+3}$.

I tried to multiply the first terms to get the third and manipulate it by the Fibonacci's numbers and write one in terms of the other. But I ended up with some fractional expressions such as: $f_n=(f_{n+3})/(f_{(n+1})$ and $f_{n+1}=(f_{n+3})/(f_{n+2})$

I'm not sure how close I am to solving it or if there is an easier way. Could anyone finish this for me or work it out differently? Thanks.

4. Define the matrix $A = \begin{bmatrix} 1&1\\1&0 \end{bmatrix}$

We can show $A^n = \begin{bmatrix} f_{n+1}&f_n \\ f_n&f_{n-1} \end{bmatrix}$

It follows $\det A^n = (\det A)^n$

Therefore, $f_{n+1}f_{n-1} - f_n^2 = (-1)^n$

5. See here