Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.