Take the 2-minute tour ×
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.

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

share|improve this question
4  
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
1  
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
2  
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

3 Answers 3

up vote 6 down vote accepted

Hint:

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^n = \begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \\ \end{pmatrix}$

What is the determinant of the matrix on the right side?

share|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:15

NOTE $\ $ This is precisely the same answer I gave a couple months ago in this duplicate thread

share|improve this answer

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.

share|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

 
discard

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.