Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
Yes. $ \mbox{} $ – Mariano Suárez-Alvarez Feb 8 '11 at 5:44
@Mariano Suárez-Alvarez: Thanks ^_^! Happy! – Chan Feb 8 '11 at 5:47
In your first expression, should the subscript on the square be "n+1" instead of "n-1"? If so, then you are on the right track. (Also, you'll want parentheses around your "-1"s.) – Blue Feb 8 '11 at 5:47
Note: You should write $(-1)^{n+2}$, and not $-1^{n+2}$; exponentiation takes precedence, so the former is either $-1$ or $1$ depending on the parity of $n$, but the latter is $-1^{n+2} = -(1^{n+2}) = -1$ always. – Arturo Magidin Feb 8 '11 at 5:50
@Day Late Don: nice catch. It was my typo. I was practicing using Latex:(. – Chan Feb 8 '11 at 5:51
up vote 6 down vote accepted

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.

share|cite|improve this answer
NOTE $\ $ This is precisely the same answer I gave a couple months ago in this duplicate thread – Bill Dubuque Feb 28 '11 at 4:06

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:

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:

Since $F_{n-(k+1)}=F_{n-(k-1)}-F_{n-k}$, we get
which completes the inductive step.

share|cite|improve this answer
I tried to google a little, and I found almost the same derivation of Cassini's identity in the text Yiu: Recreational Mathematics. – Martin Sleziak Mar 16 '12 at 11:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.