5
$\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$

2 Answers 2

5
$\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$
1
$\begingroup$

Here's a generating function proof.

The left hand side is the coefficient of $x^n$ in

$$\frac{x}{1-x-x^2}\cdot\frac{1}{1-x}$$

The right hand side is the coefficient of $x^n$ in

$$\left(\frac{x}{1-x-x^2}-x\right)\cdot\frac{1}{x^2}-\frac{1}{1-x}$$

$$\frac{x}{1-x-x^2}\cdot\frac{1}{x^2}-\frac{1}{1-x}-\frac1x$$

$$=\frac{x}{1-x-x^2}\cdot\left[\frac{1}{x^2}-\frac{{1-x-x^2}}{x^2(1-x)}\right]$$

$$=\frac{x}{1-x-x^2}\cdot\left[\frac{(1-x)-(1-x-x^2)}{x^2(1-x)}\right]$$

$$=\frac{x}{1-x-x^2}\cdot\frac{1}{1-x}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .