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.

Here's a problem that is leading me in circles.

Consider the Fibonacci number $F_n$ defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n \geq 2$.

Prove that $F_{2n-1} = F_{n}^2 + F_{n-1}^2$.

Tried an induction proof that lead me nowhere fast. So far we have only been given limited identities, and they are all basically summation formulas for the odd terms, or even terms, or all terms up to n. I also though that maybe if it was a difference, the difference of squares could factor to something, but I'm just not getting it.

share|improve this question
    
This is impossible. $$F_{2n-1}^2 > F_{n+1}^2 = F_n^2 + 2F_nF_{n-1} + F_{n-1}^2 > F_n^2 + F_{n-1}^2$$ –  EuYu Feb 5 '13 at 5:52
    
@EuYu Thanks, I was about to ponder. –  GYC Feb 5 '13 at 5:53
    
It appears that the correct identity has no square for the $F_{2n-1}$ term, i.e. $$F_{2n-1} = F_n^2 + F_{n-1}^2$$ Is that what you meant? –  EuYu Feb 5 '13 at 5:57
add comment

2 Answers

up vote 3 down vote accepted

Using Binet's Fibonacci Number Formula,

$F_r=\frac{a^r-b^r}{a-b}$ where $a,b$ are the roots of $x^2-x-1=0\implies ab=-1,a+b=1$

So, $$F_n^2+F_{n-1}^2=\frac{(a^n-b^n)^2+(a^{n-1}-b^{n-1})^2}{(a-b)^2}$$

$$=\frac{a^{2n}+b^{2n}+a^{2n-2}+b^{2n-2}-2(ab)^{n-1}(ab+1)}{(a-b)^2}$$

$$=\frac{a^{2n-1}\left(a+\frac1a\right)+b^{2n-1}\left(b+\frac1a\right)}{(a-b)^2}\text{ as } ab=-1$$

$$=\frac{a^{2n-1}(a-b)+b^{2n-1}(b-a)}{(a-b)^2} \text{ as } \frac1a=-b,\frac1b=-a$$

$$=\frac{a^{2n-1}-b^{2n-1}}{(a-b)}=F_{2n-1}$$

share|improve this answer
    
This was exactly what I needed. I noticed, buried in my notes from class that the professor had briefly gone over the formula, but failed to show its use in applications. Now I feel dumb for having been told of its existence and not figuring it out.... –  Eleven-Eleven Feb 9 '13 at 5:22
add comment

The identity may be derived from the interesting fact that

$$\left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right ) ^k = \left ( \begin{array} \\ F_{k+1} & F_k\\F_k & F_{k-1} \\ \end{array} \right )$$.

From this, we may observe that

$$\begin{align} \left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right ) ^m \left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right ) ^n &= \left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right ) ^{m+n} \\ &= \left ( \begin{array} \\ F_{m+1} & F_m\\F_m & F_{m-1} \\ \end{array} \right ) \left ( \begin{array} \\ F_{n+1} & F_n\\F_n & F_{n-1} \\ \end{array} \right )\\ &= \left ( \begin{array} \\ F_{m+n+1} & F_{m+n}\\F_{m+n} & F_{m+n-1} \\ \end{array} \right ) \end{align} $$

Therefore we can say that, for example,

$$F_{m+n-1} = F_m F_n + F_{m-1} F_{n-1}$$

Plug in $m=n$ and the desired identity follows.

EDIT

The first identity quoted above follows from putting the Fibonacci recurrence into matrix form:

$$\left ( \begin{array} \\F_{k+2} \\ F_{k+1} \\ \end{array} \right ) = \left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right ) \left ( \begin{array} \\F_{k+1} \\ F_k \\ \end{array} \right )$$

which may be immediately verified. We may repeat this matrix multiplication $k$ times to get

$$\left ( \begin{array} \\F_{k+2} \\ F_{k+1} \\ \end{array} \right ) = \left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right )^k \left ( \begin{array} \\F_{2} \\ F_1 \\ \end{array} \right ) = \left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right )^k \left ( \begin{array} \\1 \\ 1 \\ \end{array} \right )$$

Noting that $F_{k+2}= F_{k+1}+ F_k$ and $ F_{k+1} = F_k + F_{k-1}$, the stated identity follows.

share|improve this answer
    
How did you come up with the 2x2 matrix identity above? What basis do you have to use that in your derivation? –  Eleven-Eleven Feb 9 '13 at 5:21
    
@ChristopherErnst: this is a well-known identity, the proof of which I outlined above. I do not understand your second question. –  Ron Gordon Feb 9 '13 at 6:35
add comment

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.