# Another Fibonacci identity: $F_{2n-1} = F_{n}^2 + F_{n-1}^2$

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, 2013 at 5:52
• @EuYu Thanks, I was about to ponder. Feb 5, 2013 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, 2013 at 5:57

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? Feb 9, 2013 at 5:21
• @ChristopherErnst: this is a well-known identity, the proof of which I outlined above. I do not understand your second question. Feb 9, 2013 at 6:35
• Nice proof! But let me ask you one question: we get the following: $\begin{pmatrix} F_{k+1} & F_{k} \\ F_{k} & F_{k-1} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ But how to conclude from here that $\begin{pmatrix} F_{k+1} & F_{k} \\ F_{k} & F_{k-1} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k$
– RFZ
Nov 28, 2017 at 15:41

$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.... Feb 9, 2013 at 5:22