3
$\begingroup$

$ 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

6 Answers 6

1

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}

3

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.

  • 0
    Not useful to the OP, perhaps, but still very nice.2012-10-14
3

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.

3

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)\;.$

  • 0
    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.2012-10-14
1

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

1

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

  • 0
    https://math.stackexchange.com/questions/2559814/is-the-proof-i-am-using-sufficient-for-the-system-of-equation?2017-12-11