9
$\begingroup$

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

  • 5
    Yes. $ \mbox{} $2011-02-08
  • 1
    @Mariano Suárez-Alvarez: Thanks ^_^! Happy!2011-02-08
  • 2
    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.)2011-02-08
  • 3
    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.2011-02-08
  • 0
    @Day Late Don: nice catch. It was my typo. I was practicing using Latex:(.2011-02-08
  • 0
    @Arturo Magidin: Thanks ;)! Edited.2011-02-08
  • 0
    Posts about the same identity: http://math.stackexchange.com/questions/523925/induction-proof-on-fibonacci-sequence-fn-1-cdot-fn1-fn2-1n and http://math.stackexchange.com/questions/783152/induction-proof-fn2-fn-1fn1-1n-1-for-n-ge-2-where-n-is-the2015-01-07

2 Answers 2

9

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.

3

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.

  • 0
    I tried to google a little, and I found almost the same derivation of Cassini's identity in the text [Yiu: Recreational Mathematics](http://math.fau.edu/yiu/RecreationalMathematics2003.pdf).2012-03-16