Combinatorial Fibonacci proof :$F_1 + F_2 + F_3 + \dots + F_n = F_{n + 2} - 1.$

Question

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.

Answer 1

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.