# Combinatorial fibonacci proof

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.

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?"
It can be placed in any position $$i$$ for $$1\leq i, 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, 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.