[Math] Fibonacci identity proof

fibonacci-numberssummation

I've been struggled for this identity for a while, how can I use combinatorial proof to prove the Fibonacci identity $$F_2+F_5+\dots+F_{3n-1}=\frac{F_{3n+1}-1}{2}$$
I know that $F_n$ is number of tilings for the board of length $n-1$, so if I rewrite the identity and let $f_n$ be the number of tilings for the board of length $n$, then I got $$f_1+f_4+\dots+f_{3n-2}=\frac{f_{3n}-1}{2}$$
the only thing that I know so far is the Right hand side, $f_{3n}-1$ is the number of tilings for the $3n$ board with at least one $(1\times 2)$ tile (or maybe I am wrong), but I have no idea of what the fraction $\frac{1}{2}$ is doing here. Can anyone help?

(P.S.: In general, when it comes to this kind of combinatorial proof question, is it ok to rewrite the question in a different way? Or is it ok to rewrite this question as $2(f_1+f_4+\dots+f_{3n-1})=f_{3n}-1$, then process the proof?

Thank you for all your useful proofs, but this is an identity from a course that I am taking recently, and it is all about combinatorial proof, so some hint about how to find the number of tilings for the board of length $3n$ would be really helpful.

Thanks for dtldarek's help, I finally came up with:

Rewrite the identity as $2F_2+2F_5+\dots+2F_{3n-1}=\frac{F_{3n+1}-1}{2}$, then the Left hand side becomes $F_2+F_2+F_5+F_5+\dots+F_{3n-1}+F_{3n-1}=F_0+F_1+F_2+F_3+\dots+F_{3n-3}+F_{3n-2}+F_{3n-1}=\sum^{3n-1}_{i=0}F_{i}\implies \sum^{3n-1}_{i=0} F_i=F_{3n+1}-1$, and recall that $f_n$ is the number of tilings for the board of length $n$, so we have $\sum^{3n-2}_{i=0}f_i=f_{3n}-1$.

For the Right hand side $f_{3n}$ is the number of tilings for the length of $3n$ board, then $f_{3n}-1$ is the number of tilings for a $3n$ board use at least one $1\times 2$ tile. Now, for the Left hand side, conditioning on the last domino in the $k^{th}$ cell, for any cells before the $k^{th}$ cell, there are only one way can be done, and all cells after the $k+1$ cell can be done in $f_{3n-k-1}$, finally sum up $k$ from 0 to $3n-1$, which is the Left hand side.

Is it ok? did I change the meaning of the original identity?

Best Answer

This is rather easy using algebra:

$$F_2+F_5+\dots+F_{3n-1}=\frac{F_{3n+1}-1}{2}$$ $$ 2F_2+2F_5+\dots+2F_{3n-1}=F_{3n+1}-1 $$ $$ (F_0+F_1)+F_2+(F_3+F_4) + F_5+\dots+(F_{3n-3} + F_{3n-2}) + F_{3n-1}=F_{3n+1}-1 $$ $$ \sum_{k=0}^{m} F_k = F_{m+2} -1 \quad\text{ for } m = 3n-1$$

where the last one is a well know identity for Fibonacci numbers. To prove it by combinatorial interpretation you might want to follow the same way. Let's start with the following from Wikipedia:

The number of binary strings of length $n$ without consecutive $1$s is the Fibonacci number $F_{n+2}$.

Let the dot $\cdot$ denote concatenation and $$F_{n+2} = \big\{ w \in \{\mathtt{0},\mathtt{1}\}^n \mid \text{ there is no two consecutive }\mathtt{1}\text{s in }w\big\}, $$

then the last identity reads: $$F_{m+2} - \{\mathtt{0}^{m+2}\} = \mathtt{10}\cdot F_m \cup \mathtt{010}\cdot F_{m-1} \cup \ldots \cup \mathtt{0}^{m-1}\mathtt{10} \cdot F_1 \cup \mathtt{0}^{m}\mathtt{10}\cdot F_0.$$

However, we could group $F_k \cup F_{k+1}$ into $F_{k+2}$, because $F_{k+2} = \mathtt{0}\cdot F_{k+1} \cup \mathtt{10} \cdot F_{k}$. Going up through all the equations in a similar manner you can find the combinatorial interpretation for the algebraic proof above.

Good luck ;-)

Related Solutions

Combinatorics – Combinatorial Proof of a Fibonacci Identity

Recall that $F_{n+1}$ is the number of ways to tile a board of length $n$ with tiles of length $1$ and $2$. So $F_{n+4}$ is the number of ways to tile a board of length $n+3$ with tiles of length $1$ and $2$. Note that $n+3$ such tilings use at most one tile of length $2$, so $F_{n+4} - (n+3)$ such tilings use at least two tiles of length $2$.

Given such a tiling, look at where the second-to-last tile of length $2$ is used. The part after this tile is a tiling of some section of length $k+1$ where exactly one tile of length $2$ is used (which can be done in $k$ ways), and the part before this tile is a tiling of the remaining portion of length $n-k$ (which can be done in $F_{n-k+1}$ ways). Sum over $k$.

(The bigger lesson to take away here is that convolution is much easier to deal with than Hadamard product. Also, since the bijection I described above preserves the number of tiles of each type, the identity can be upgraded to an identity of $q$-Fibonacci numbers.)

[Math] Sum of product of Fibonacci numbers

Let's use $$ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - (-1)^n \phi^{-n} \right) $$ where $\phi$ is a Golden ratio constant $\phi = \frac{\sqrt{5}+1}{2}$. Now the sum reduces to the combination of geometric sums: $$ \begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^k - (-1)^k \phi^{-k}\right)\left(\phi^{n-k} - (-1)^{n-k} \phi^{k-n}\right) \\ &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^n - (-1)^k \phi^{n-2k} - (-1)^{n-k} \phi^{2k-n} + (-1)^n \phi^{-n} \right) \\ &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) - \frac{\phi^{n}}{5} \sum_{k=1}^{n-1} \left( -\phi^{-2}\right)^{k} - \frac{(-1)^{n}}{5} \phi^{-n} \sum_{k=1}^{n-1} \left(-\phi^2\right)^k \end{eqnarray} $$ Using the geometric sum $\sum_{k=1}^{n-1} x^k = \frac{x-x^n}{1-x}$ we get: $$\begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) + \frac{2}{5} \frac{\phi^{n-1} + (-1)^n \phi^{1-n}}{\phi + \phi^{-1}} \\ &=& \frac{n-1}{5} L_n + \frac{2}{5} F_{n-1} \end{eqnarray} $$ where $L_n$ denotes $n$-th Lucas number.

Quick sanity check in Mathematica:

In[84]:= Table[
 Sum[Fibonacci[k] Fibonacci[n - k], {k, 1, n - 1}] == (n - 1)/
    5 LucasL[n] + 2/5 Fibonacci[n - 1], {n, 1, 6}]

Out[84]= {True, True, True, True, True, True}

The sum stated in the edited question is obtained by replacing $n$ with $n+1$ in the sum evaluated above: $$ \sum_{k=1}^{n} F_k F_{n+1-k} = \frac{n}{5} L_{n+1} + \frac{2}{5} F_n $$

Best Answer

Related Solutions

Combinatorics – Combinatorial Proof of a Fibonacci Identity

[Math] Sum of product of Fibonacci numbers

Related Question