1
$\begingroup$

Question: Use a tiling argument to give a combinatorial proof that $$F_1 + F_2 + F_3 + \dots + F_n = F_{n + 2} - 1.$$

What I did: First off I found out that the number of ways of tiling a $1 \times n$ rectangle with $1 \times 1$ and $1 \times 2$ tiles is $F_{n + 1}.$ Therefore, $F_{n + 2}$ is the number of ways of tiling a $1 \times n+1$ rectangle. The subtract 1 is taking away one of the cases and so I decided to take away the case which was created with all $1 \times 1$. I also realized that the LHS is just basically a bunch of cases together and since the RHS is just the arrangements of $1 \times 1$ and $1 \times 2$ tiles but at least one $1 \times 2$ tile in the arrangement. But however, I am having trouble finding out how to make these cases.

$\endgroup$
1
$\begingroup$

You're on the right track. Like you mentioned, the right hand side counts the number of ways of tiling a $1\times(n+1)$ with $1\times1$ and $1\times2$ tiles such that at least $1\times2$ tile is used. Therefore, we can ask: "in what position is the right-most $1\times2$ tile placed?"

If you just wanted a hint, you can stop reading here.

It can be placed in any position $i$ for $1\leq i<n+1$, after which all the tiles to the right of it will be $1\times1$ tiles. As for tiling the positions $1,\dots,i-1$, we are free to use either type of block; that is, we're just tiling the leftmost $1\times(i-1)$ rectangle. Therefore, there are $F_i$ many ways to tile the $1\times(n+1)$ so that the right-most $1\times2$ is placed at position $i$.

Allowing $i$ to range freely $1\leq i<n+1$, we get that the number of ways of tiling a $1\times(n+1)$ such that we use at least one $1\times2$ is $F_1+\dots+F_n$, so this must coincide with the right hand side $F_{n+2}-1$, as desired.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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