For $f_n^2 - f_{n-2}^2 = f_{2n-1}$

Question

We need to provide a visual counting proof for the identity above.

At first, we count the number of pairs of $n$ tilings where at least one ends in a square. Then, conditioning on whether the first tiling ends in a square, we need prove the rest.

If we consider the R.H.S of the identity, we see that it is a strip with a length of $(2n-2)$ that we're tiling. How do we approach the problem then? How should one visualize the diagram, given that we need to find the tiling pairs where at least one ends in a square?

N.B what I'm asking for is a visual proof, not by any other means.

Answer 1

I believe your identity should in fact be:

$$f_n^2 - f_{n-2}^2 = f_{2n-1}$$

Consider the strip of length $2n$ which is breakable after the $n$-th place, in the sense that there is not a $2 \times 1$ tile at the positions $(n, n+1)$.

Clearly, such a strip can be tiled in $f_n^2$ ways since we are actually tiling two disjoint strips of length $n$.

On the other hand, consider the two possible cases:

1. There are two $2 \times 1$ tiles at positions $(n-1, n)$ and $(n+1, n+2)$
2. There is a $1 \times 1$ tile at the positions $(n)$ or $(n+1)$

In the first case, we are tiling two disjoint strips of length $n-2$, namely $(1, 2, \ldots, n-2)$ and $(n+3, n+4, \ldots, 2n)$. This can be done in $f_{n-2}^2$ ways.

In the second case, by removing a $1 \times 1$ tile from one of the positions $(n)$ or $(n+1)$ we obtain a tiling of a strip of length $2n - 1$ with no other restrictions. This can be done in $f_{2n-1}$ ways.

Therefore, $f_n^2 - f_{n-2}^2 = f_{2n-1}$.