# Fibonnaci identity

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.

-
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

$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}$$

-
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

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.

-
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