$$f_{n+2} + f_{n-2} = 3f_n \text{ for n} \ge 1 $$
I am trying to understand the combinatorial proof that I see in the book I am reading for the above identity. Here $f_n$ represents the number of ways to tile a rectangular board of size $1 \times n$ with tiles of size $1 \times 1$ and $1 \times 2$. In the book, the author establishes a 1-to-3 correspondence between the set of $1 \times n$ tilings and the set of $1 \times (n-2)$ tiling and $1 \times (n+2)$ tilings, referred to hereafter as Set 1 and Set 2 respectively, such that for every object in Set 1, we can create three unique objects in Set 2.
Set 1: Tilings of an $1 \times n$ board
Set 2: Tilings of an $1 \times (n+2)$ board or an $1 \times (n-2)$ board.
The author then explains the 1-to-3 correspondence as below:
The first tiling is an $1 \times (n+2)$ tiling created by appending a tile of size $1 \times 2$ to the $1 \times n$ tiling
The second tiling is an $1 \times (n+2)$ tiling created by appending two tiles of size $1 \times 1$ to the $1 \times n$ tiling
For the third tiling, the author comes-up with something that I can't quite wrap my head around. They say that if the $1 \times n$ tiling ends with a
i) $1 \times 2$ tile, then remove the $1 \times 2$ tiling to create a $1 \times (n-2)$ tiling.
ii) $1 \times 1$ tile, then insert a $1 \times 2$ tile before the last $1 \times 1$ tile to create a $1 \times (n+2)$ tiling.
Then, to prove the 1-to-3 correspondence, they prove that every tiling of size $1 \times (n+2)$ or size $1 \times (n-2)$ is created exactly once from some $1 \times n$ tiling. They reason it out as below:
For a given $1 \times (n+2)$ tiling, we can obtain the $1 \times n$ tiling that creates it by examining its ending and removing
i) the last $1 \times 2$ tile (if it ends with a $1 \times 2$ tile)
ii) the last two $1 \times 1$ tiles (if it ends with two $1 \times 1$ tiles)
iii) the last $1 \times 2$ tile (if it ends with a $1 \times 1$ tile preceded by a $1 \times 2$ tile)
And for a given $1 \times (n-2)$ tiling, we can simply append a tile of size $1 \times 2$ for the $1 \times n$ tiling that creates it.
And they conclude that since Set 2 is three times the size of Set 1, that the identity follows.
Although I understand all of that, I don't quite get how a tiling of size $1 \times n$ can be formed in exactly one way from a tiling of size $1 \times (n-2)$, since I could append either a tile of size $1 \times 2$ or two tilings of size $1 \times 1$ to the $1 \times (n-2)$ tiling to create an $1 \times n$ tiling.
Furthermore, I could also just as well, insert a tile of size $1 \times 1$ to a $1 \times n$ tiling, to form a $1 \times (n+1)$ tiling, if the board of $1 \times n$ ended with a tile of $1 \times 2$. Which would mean $f_{n+2} + f_{n+1} = 3f_n$. But I know this is false. I just don't know why my reasoning is incorrect.
I am sorry this one's lengthy. I would appreciate any explanations for the above two concerns.
The claim is not that a $1\times n$ tiling can be formed in only one way from a $1\times(n-2)$ tiling. At that point you’ve been given a very specific procedure that produces three $1\times(n+2)$ or $1\times(n-2)$ tilings from each $1\times n$ tiling, and the claim is that there is exactly one $1\times n$ tiling that could have produced any given $1\times(n-2)$ tiling by that procedure. The procedure produces a $1\times(n-2)$ tiling only by removing a $1\times 2$ tile from the end of a $1\times n$ tiling, never by removing two $1\times 1$ tiles, so the only $1\times n$ tiling from which a given $1\times(n-2)$ tiling could have resulted is the one that you get when you append a $1\times 2$ tile.
The whole second part of the argument is showing that each $1\times(n-2)$ or $1\times(n+2)$ tiling is the result of applying the procedure in the first part of the argument to a unique $1\times n$ tiling. That is, if you’re given a $1\times(n-2)$ or $1\times(n+2)$ tiling, you can always work backwards to discover the one and only $1\times n$ tiling that gives rise to it when you apply the procedure described in the first part of the argument. That is what shows that the procedure really does define a $1$-to-$3$ correspondence between Set $1$ and Set $2$: given a $1\times n$ tiling, there is a rule that specifies exactly $3$ corresponding members of Set $2$, and given any member of Set $2$, there is a rule that tells you the unique member of Set $1$ to which it corresponds.