Why does Fibonacci identity $3 f_n = f_{n+2} + f_{n-2}$? This is from Proofs That Really Count.

combinatorial-proofscombinatoricsfibonacci-numbersproof-explanationtiling

I am reading the book "Proofs That Really Count" by Benjamin and Quinn.

In chapter $1$, they establish that:

$f_n = f_{n-1} + f_{n-2}$, and $f_1 = 1$, $f_2 = 2$, $f_3 = 3$, $f_4 = 5$, etc.

The chapter establishes that $f_n$ is the combination of ways to place dominoes and squares on $n$-tiled board. For example, $f_4=5$, so there are $5$ ways to place dominoes and squares on a $4$-tiled board:

  1. ▫▫▫▫
  2. ▫▫▭
  3. ▫▭▫
  4. ▭▫▫
  5. ▭▭

The first chapter continues with examples of how to prove identities with $f_n$ based on tiles and squares arguments.

In Chapter $1$, Identity $7$, they give prove this identity using tiles and squares argument:

$3 f_n = f_{n+2} + f_{n-2}$

The argument goes as follows:

You have a $n$-tiled board, and it can be converted into either a $(n+2)$ tiled board or a $(n-2)$ tiled board in the following three ways:

Given an $n$ tiled board:

  1. Add two squares to get $n+2$.
  2. Add one domino to get $n+2$.

a. If the last position of the $n$ tiled board is a square, add a domino before the last square to get $n+2$.

b. If the last position of the $n$ tiled board is a domino, remove the domino to get $n-2$.

The number of ways to tile either $(n+2)$ or $(n-2)$ tiled board is $f_{n+2} + f_{n-2}$. That concludes the proof of $3 f_n = f_{n+2} + f_{n-2}$.

The part that confuses me about this proof is in case $3$. If you assume that an $n$ tiled board's last position has a square, doesn't that mean that the ways to tile such a board is actually $f_{n-1}$? Similarly for when the last position is a domino, then wouldn't it always be $f_{n-2}$?

Maybe I'm missing a deeper intuition here about this combinatoric proof?

Edit: updating the wording to more accurately reflect the problem.

Best Answer

After the very first line, "You have three $n$-tiled boards, so there are $3f_n$ ways to tile them," I am no longer following the argument. Treated literally, there are $f_n^3$ ways to tile three boards of length $n$, but this then throws the entire rest of the argument off the rails.

Here's how I'd present it: (hopefully the differences distinguish it enough from that given in the book to give you a second look)

For a fixed $n$-tiled board and an $i\in \{1,2,3\}$, we do the following:

  1. If $i=1$, then add a domino to the end of the board, making an $(n+2)$-tiled board that ends in a domino.
  2. If $i=2$, then add two squares to the end of the board, making an $(n+2)$-tiled board that ends in two squares.
  3. If $i=3$, then we look at the last element in our board. If it is a domino, then we remove it, giving an $(n-2)$-tiled board with no restrictions. If it is a square, then we put a domino right before the square, making an $(n+2)$-tiled board that ends in a domino and then a square.

Yes, in the third case, we are implicitly using $f_n = f_{n-1} + f_{n-2}$, and in fact, we effectively are using the fact that the $(n-1)$-tiled boards correspond to the $(n+2)$-tiled boards that end in a domino followed by a square.

The main point, however, is that the $(n+2)$-tiled boards may be partitioned into three mutually exclusive types: Those that end in a domino ($f_n$ of these), those that end in two squares ($f_n$ of these), and those that end in a domino followed by a square ($f_{n-1}$ of these).

Related Question