Using 'tiling' proof technique to create combinatoric proofs about number relationships.

Question

The number of ways of tiling a $1\times n$ rectangle with $1\times 1$ and $1\times 2$ tiles is $F_{n+1}$.

(a) Use a tiling argument to give a combinatorial proof that $$F_n^2+F_{n+1}^2=F_{2n+1}\;.$$ (b) Use a tiling argument to give a combinatorial proof that $$F_1+F_2+F_3+\ldots+F_n=F_{n+2}-1\;.$$

Answer 1

Hints:

1. For the first one, what happens if you have a strip of length $2n.$ Imagine what are the two possibilities for the slots at $n$ and $n+1.$ They are either separated or united by a tile.
2. For the second one, what if you split the tilings in how many $2\times 1$ tiles you have at the end? What if you have $1$ what if you have $2$? If i do this, which kind of configuration do i miss? Notice that you have to put a $1\times 1$ after you put all your $2\times 1$ tiles to be sure you are not overcounting.