3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$$ $\endgroup$
    – EuYu
    Feb 5, 2013 at 5:52
  • $\begingroup$ @EuYu Thanks, I was about to ponder. $\endgroup$
    – user123454321
    Feb 5, 2013 at 5:53
  • $\begingroup$ 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? $\endgroup$
    – EuYu
    Feb 5, 2013 at 5:57

2 Answers 2

Reset to default
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ How did you come up with the 2x2 matrix identity above? What basis do you have to use that in your derivation? $\endgroup$
    – Eleven-Eleven
    Feb 9, 2013 at 5:21
  • $\begingroup$ @ChristopherErnst: this is a well-known identity, the proof of which I outlined above. I do not understand your second question. $\endgroup$
    – Ron Gordon
    Feb 9, 2013 at 6:35
  • $\begingroup$ 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$ $\endgroup$
    – RFZ
    Nov 28, 2017 at 15:41
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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.... $\endgroup$
    – Eleven-Eleven
    Feb 9, 2013 at 5:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .