Fibonacci identity: $f_{n-1}f_{n+1} - f_{n}^2 = (-1)^n$ Consider this Fibonacci equation:
$$f_{n+1}^2 - f_nf_{n+2}$$
The problem asked to write a program with given n, output the the result of this equation. I could use the formula 
$$f_n = \frac{(1+\sqrt{5})^n - ( 1 - \sqrt{5} )^n}{2^n\sqrt{5}}$$
However, from mathworld, I found this formula Cassini's identity 
$$f_{n-1}f_{n+1} - f_{n}^2 = (-1)^n$$
So, I decided to play around with the equation above, and I have:
$$ \text{Let } x = n + 1 $$
$$ \text{then the equation above becomes } f_x^2 - f_{x-1}f_{x+1} $$
$$ \Rightarrow -( f_{x-1}f_{x+1}  - f_x^2 ) = -1(-1)^x = (-1)^{x+1} = (-1)^{n+1+1} = (-1)^{n+2}$$
So this equation either is 1 or -1. Am I in the right track?   
Thanks,
Chan
 A: Let us try to find gcd of $F_n$ and $F_{n+1}$ using Extended Euclidean algorithm. I will write the steps algorithm in a table; this table method was also explained in some Bill Dubuque's posts. 
$\begin{array}{|l||c|c|}
  \hline
  F_{n+1} & 1 & 0 \\\hline
  F_{n}   & 0 & 1 \\\hline
  F_{n-1} & 1 & -1 \\\hline
  F_{n-2} & -1 & 2 \\\hline
  F_{n-3} & 2 & -3 \\\hline
  \vdots & \vdots & \vdots \\\hline
  F_{n-k} & (-1)^{k+1}F_k & (-1)^kF_{k+1} \\\hline
\end{array} $
After a few steps we can guess the $k$-th line, which gives us the following formula:
$F_{n-k}=(-1)^{k+1}F_kF_{n+1}+(-1)^kF_{k+1}F_n=(-1)^{k+1}(F_kF_{n+1}-F_{k+1}F_n)$.
For $k=n-1$ we get Cassini's identity $F_1=(-1)^n(F_{n-1}F_{n+1}-F_n^2)$.
So the only thing we have to do is to verify the above formula, which can be done easily by induction on $k$.
Inductive step: We know that:
$F_{n-k}=(-1)^{k+1}(F_kF_{n+1}-F_{k+1}F_n)=-(-1)^{k}(F_kF_{n+1}-F_{k+1}F_n)$
$F_{n-(k-1)}=(-1)^{k}(F_{k-1}F_{n+1}-F_{k}F_n)$  
Since $F_{n-(k+1)}=F_{n-(k-1)}-F_{n-k}$, we get
$F_{n-(k+1)}=(-1)^{k}[(F_{k-1}+F_k)F_{n+1}-(F_k+F_{k+1})F_n]=(-1)^{k+2}(F_{k+1}F_{n+1}-F_{k+2}F_n)$
which completes the inductive step.
A: We have the following (easily proved by induction):
$\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^n =
\begin{pmatrix}
f_{n+1} & f_n \\
f_n & f_{n-1} \\
\end{pmatrix}$
Equating the determinants of the matrices gives us the identity immediately.
