Fibonacci equality, proving it someway

$F_{2n} = F_n(F_n+2F_{n-1})$

$F_n$ is a nth Fibonacci number. I tried by induction but i didn't get anywhere

-

An answer just by induction on $n$ of the equality $F_{2n}=F_n(F_{n-1}+F_{n+1})$ is as follows:

For $n=2$ we have $3=F_4=(1+3)\cdot 1=(F_1+F_3)F_2$.

To go from $n$ to $n+1$:

\begin{align} F_{2n+2}&=3F_{2n}-F_{2n-2}\\ &=3(F_{n-1}+F_{n+1})F_n-(F_{n-2}+F_n)F_{n-1}\\ &=F_{n-1}(3F_n-F_n-F_{n-2})+3F_{n+1}F_n\\ &=F_{n-1}(F_n+F_{n-1})+3F_{n+1}F_n\\ &=F_{n-1}F_{n+1}+3F_{n+1}F_n\\ &=F_{n+1}(3F_n+F_{n-1})\\ &=F_{n+1}(2F_n+F_{n+1})\\ &=F_{n+1}(F_n+F_{n+2}) \end{align}

-

A combinatorial interpretation:

$F_n$ is the number of ways to tile a row of $(n-1)$ squares with $1\times 1$ blocks and $1\times 2$ blocks.

The left hand side is the number of ways to tile a $1\times (2n-1)$ block with $1\times 1$ and $1\times 2$ blocks. Consider the middle square (the $(n-1)$th square.)

Case 1: It is used in a $1\times 1$ block. Then, there are $F_{n}$ ways to tile each of the $1 \times (n-1)$ blocks on each side of the middle, so $F_n^2$ total.

Case 2: It is used in a $1\times 2$ block. This block contains the $(n-1)$th square and either the $n$th or the $(n-2)$th square. In either case, there are $F_{n-1}$ ways to tile the shorter side and $F_n$ ways to tile the longer side.

We thus have $F_{2n} = F_n^2 + 2F_nF_{n-1},$ as desired.

-
I didn't have mentioned about your way of doing it. I can't fully understand your solution. The man said it's solutionable by induction –  matiit Oct 14 '12 at 15:27
Not useful to the OP, perhaps, but still very nice. –  Brian M. Scott Oct 14 '12 at 15:46

This is very related to the answer at Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

That question has the identity:

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

which can be modeled to your identity by letting $n=m$

$F_{2n} = F_{n-1}F_n + F_n F_{n+1}$

$F_{2n} = F_n(F_{n-1} + F_{n+1})$

Setting the expression inside the parenthesis to:

$F_{n-1} + F_{n+1} = F_{n-1}+ F_{n-1} + F_{n} = F_n + 2F_{n-1}$

We get

$F_{2n} = F_n(F_n+2F_{n-1})$

Which is your identity. So work backwards to that identity and use the proof at the linked question to prove your relation.

-

Here’s a purely computational proof. Let $$A=\pmatrix{F_2&F_1\\F_1&F_0}=\pmatrix{1&1\\1&0}\;;$$ a straightforward induction shows that $$A^n=\pmatrix{F_{n+1}&F_n\\F_n&F_{n-1}}$$ for all $n\ge 1$. Then

\begin{align*} \pmatrix{F_{m+n+1}&F_{m+n}\\F_{m+n}&F_{m+n-1}}&=A^{m+n}\\ &=A^mA^n\\\\ &=\pmatrix{F_{m+1}&F_m\\F_m&F_{m-1}}\pmatrix{F_{n+1}&F_n\\F_n&F_{n-1}}\\\\ &=\pmatrix{F_{m+1}F_{n+1}+F_mF_n&F_{m+1}F_n+F_mF_{n-1}\\F_mF_{n+1}+F_{m-1}F_n&F_mF_n+F_{m-1}F_{n-1}}\;, \end{align*}

so $F_{m+n}=F_{m+1}F_n+F_mF_{n-1}$. Take $m=n$, and this becomes

$$F_{2n}=F_{n+1}F_n+F_nF_{n-1}=F_n\left(F_{n+1}+F_{n-1}\right)=F_n\left(F_n+2F_{n-1}\right)\;.$$

-
Exact duplicate of Zchpyvr's 21-minute prior answer (you've simply inlined the lemma that he links to). –  Bill Dubuque Oct 14 '12 at 19:06
@Bill: I’m not terribly surprised. However, I didn’t see his answer until after I posted, and when I did see it, I was busy and didn’t feel like chasing down the link. And quite frankly, I don’t consider it an exact duplicate for that very reason. –  Brian M. Scott Oct 14 '12 at 21:52
It is most certainly an exact duplicate. As I said, you've simply inlined the link in the other answer. Lacking anything new, it should be deleted for the sake of the readers. –  Bill Dubuque Oct 14 '12 at 21:58
@Bill: You have a rather inexact definition of exact. The fact that the information is right on the page is a difference, in convenience if nothing else. And deleting it does not serve the readers; slightly the reverse, if anything, for that same reason. The only person whom it might possibly ill serve is Zchpyvr, and I’ve upvoted his answer. And that’s the end of it as far as I’m concerned. –  Brian M. Scott Oct 14 '12 at 22:04
Posting duplicate answers potentially wastes many reader's time, since they may read two or more answers when it would have sufficed to read one. Not to mention that the abstraction in Zchpyvr's answer gained by calling the lemma by name (vs. value) only serves to make the answer more comprehensible. By your argument, every textbook should inline the proof of all lemma's so that they are "right on the page". That is, of course, absurd. –  Bill Dubuque Oct 14 '12 at 22:14

Another direct proof, using the fact that

$$F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt5}\tag1$$

where

$$\phi=\frac{1+\sqrt5}{2},\qquad1-\phi=\frac{1-\sqrt5}{2}=-\frac{1}{\phi}.$$

From $(1)$ we have

$$s_n\equiv\frac{F_{2n}}{F_n}=\frac{\phi^{2n}-(1-\phi)^{2n}}{\phi^n-(1-\phi)^n}=\phi^n+(1-\phi)^n$$

then

\begin{align} s_n-F_n&=\phi^n+(1-\phi)^n-\frac{\phi^n-(1-\phi)^n}{\sqrt5}=\\ &=\frac{1}{\sqrt5}\left[\sqrt5\phi^n+\sqrt5(1-\phi)^n-\phi^n+(1-\phi)^n\right]=\\ &=\frac{1}{\sqrt5}\left[-(1-\sqrt5)\phi^n+(1+\sqrt5)(1-\phi)^n\right]=\\ &=\frac{1}{\sqrt5}\left[-2(1-\phi)\phi^n+2\phi(1-\phi)^n\right]=\\ &=-\frac{2\phi(1-\phi)}{\sqrt5}\left[\phi^{n-1}-(1-\phi)^{n-1}\right]=2F_{n-1} \end{align}

-

This can be done also using the fact that

$$F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\bar{\sigma}^n\right),$$

from which it is easy to get

$$F_{2n} = F_n L_n,$$

(where $L_n$ is the $n$-th Lucas number) and we have only to prove

$$L_n= F_n+2F_{n-1},$$

that is true since $\{L_n\}_{n\in\mathbb{N}}$ and $\{F_n+2F_{n-1}\}_{n\in\mathbb{N}}$ are sequences with the same characteristic polynomial ($x^2-x-1$) and the same starting values $L_1=F_1+2F_0=1$, $L_2=F_2+2F_1=3$.

-