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
    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 induction2012-10-14
  • 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
    *Exact* duplicate of Zchpyvr's 21-minute prior answer (you've simply inlined the [lemma](http://math.stackexchange.com/questions/11477/showing-that-an-equation-holds-true-with-a-fibonacci-sequence-f-nm-f-n-1?rq=1) that he links to).2012-10-14
  • 0
    @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.2012-10-14
  • 0
    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.2012-10-14
  • 0
    @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.2012-10-14
  • 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
    I apologize for bothering You again...Have you looked at the new comment..?2017-12-11
  • 0
    https://math.stackexchange.com/questions/2559814/is-the-proof-i-am-using-sufficient-for-the-system-of-equation?2017-12-11