# Bijective Proof of a Fibonacci Identity

Prove (Using bijections):

$F_{1}+F_{3}+\cdots+F_{2n-1}=F_{2n}$

Where $F_{i}$ is the $i$th Fibonacci number.

Apparently you use monomers and dimers to prove this, but I don't really know what to do.

-
You should probably explain what monomers and dimers are, and how they're related to Fibonacci numbers, since they're not well-known concepts. – Ted Nov 8 '12 at 4:54

HINT: A monomer is a $1\times 1$ square, and a dimer is a $2\times 1$ rectangle, a domino. The number of ways to tile a $1\times n$ strip using monomers and dimers is $F_{2n+1}$. (For example, a $1\times 4$ strip can be tiled in $F_5=5$ ways: $1+1+1+1,1+1+2,1+2+1,2+1+1$, and $2+2$. The sum

$$F_1+F_3+F_5+\ldots+F_{2n-1}\tag{1}$$

is therefore the number of ways to tile any strip of even length less than $2n$: there are $F_1$ ways to tile a $1\times 0$ strip, $F_3$ ways to tile a $1\times 2$ strip, $F_5$ ways to tile a $1\times 4$ strip, and so on, up through $F_{2n-1}$ ways to tile a $1\times(2n-2)$ strip.

$F_{2n}$, on the other hand, is the number of ways to tile a $1\times(2n-1)$ strip. We’d like somehow to set up a bijection between tilings of a $1\times(2n-1)$ strip and tilings of even strips shorter than that. Here’s a table of tilings for the case $n=3$:

$$\begin{array}{l|l} \text{Tilings of shorter even length}&\text{Tilings of }1\times 3\\ \hline \text{no tile}&\color{red}{1+2+2}\\ \hline 1+1&1+1+\color{red}{1+2}\\ 2&2+\color{red}{1+2}\\ \hline 1+1+1+1&1+1+1+1+\color{red}{1}\\ 1+1+2&1+1+2+\color{red}{1}\\ 1+2+1&1+2+1+\color{red}{1}\\ 2+1+1&2+1+1+\color{red}{1}\\ 2+2&2+2+\color{red}{1} \end{array}$$

I’ve arranged the table so that it represents a natural bijection between the two sets. For example, the tiling $1+1$ of a $1\times 2$ strip is paired with the tiling $1+1+1+2$ of a $1\times 5$ strip, while the tiling $1+2+1$ of a $1\times 4$ strip is paired with the tiling $1+2+1+1$ of a $1\times 5$ strip. The horizontal lines separate the different shorter even lengths; for $n=3$ those are $0,2$, and $4$, corresponding to the terms $F_1,F_3$, and $F_5$ in the sum $(1)$.

Pay close attention to the red parts of the tilings of a $1\times 5$ strip: they’re the key to how the bijection works. In case that isn’t quite enough, here’s one more bit of evidence: for $n=6$ the bijection that I have in mind would pair the tiling $$1+2+1+\color{red}{1+2+2+2}$$ of a $1\times 11$ strip with the tiling $1+2+1$ of a $1\times 4$ strip.

That should be enough information to give you a reasonable chance of discovering how the bijection works, but I can provide further help if necessary.

-
Thankyou so much! It makes sense now. – user8603 Nov 8 '12 at 7:15
@user8603: You’re welcome! – Brian M. Scott Nov 8 '12 at 7:20