关于恒等式$f_n^2 - f_{n-2}^2 = f_{2n-1}$的可视化计数证明问询

Let's walk through this Fibonacci identity proof with concrete counting and visual intuition—no abstract algebra required, just good old combinatorial bijections.

First, let's ground ourselves in what $f_k$ means here:

• $f_k$ is the number of ways to tile a 1×k strip using 1×1 squares (denoted □) and 1×2 dominoes (denoted ▭).
• Base cases: $f_1 = 1$ (only a square), $f_2 = 2$ (two squares or one domino), and the recurrence $f_k = f_{k-1} + f_{k-2}$ (add a square to any (k-1)-tiling, or a domino to any (k-2)-tiling).

Let's break this down combinatorially:

• $f_n^2$ counts all pairs of n-length tilings $(A, B)$, where $A$ is one n-tiling and $B$ is another (they can be identical).
• $f_{n-2}^2$ counts the subset of these pairs where neither $A$ nor $B$ ends with a square. For a tiling to not end with a square, it must end with a domino—so the first (n-2) positions are any valid (n-2)-tiling, followed by a domino. Hence, there are $f_{n-2} \times f_{n-2}$ such pairs.
• Subtracting these gives us exactly the set we care about: all pairs $(A, B)$ where at least one of $A$ or $B$ ends with a square.

To visualize these pairs:

1. Draw two parallel 1×n strips, one for tiling $A$ (top) and one for tiling $B$ (bottom).
2. Use color coding to mark the critical ends:
   • For pairs where $A$ ends with a square: Highlight the final square in $A$ with blue. The first (n-1) positions of $A$ can be any (n-1)-tiling, and $B$ can be any n-tiling.
   • For pairs where $B$ ends with a square but $A$ does not: Highlight the final square in $B$ with red. Here, $A$ must end with a domino (so its first (n-2) positions are any (n-2)-tiling), and the first (n-1) positions of $B$ can be any (n-1)-tiling.
3. Cross out the pairs where both strips end with dominoes (these are the $f_{n-2}^2$ pairs we're excluding) to leave only the valid pairs.

The right-hand side $f_{2n-1}$ counts tilings of a 1×(2n-1) strip. We need to show every "at least one square end" pair maps to exactly one (2n-1)-tiling, and vice versa:

Case 1: $A$ ends with a square #

• $A$ can be written as $A' + □$, where $A'$ is an (n-1)-tiling.
• Map this pair $(A' + □, B)$ to the (2n-1)-tiling formed by concatenating $A'$ and $B$: $A' + B$. The total length is $(n-1) + n = 2n-1$, which is exactly the strip length we need.
• Visualize this by placing the (n-1)-length $A'$ strip followed immediately by the n-length $B$ strip to form one long strip.

Case 2: $B$ ends with a square but $A$ does not #

• $A$ can be written as $A'' + ▭$, where $A''$ is an (n-2)-tiling.
• $B$ can be written as $B' + □$, where $B'$ is an (n-1)-tiling.
• Map this pair $(A'' + ▭, B' + □)$ to the (2n-1)-tiling formed by concatenating $A''$, the domino, and $B'$: $A'' + ▭ + B'$. The total length is $(n-2) + 2 + (n-1) = 2n-1$.
• Visualize this by placing the (n-2)-length $A''$ strip, followed by the domino, then the (n-1)-length $B'$ strip.

Reverse Mapping (Prove It's a Bijection) #

Take any (2n-1)-tiling:

• Either it can be split into an (n-1)-tiling followed by an n-tiling (this maps to a pair where $A$ ends with a square), or
• It can be split into an (n-2)-tiling, followed by a domino, followed by an (n-1)-tiling (this maps to a pair where $B$ ends with a square but $A$ does not).
  These two cases are mutually exclusive and cover all possible (2n-1)-tilings, so our mapping is a perfect one-to-one correspondence.

• $f_3 = 3$, $f_1 = 1$. Left-hand side: $3^2 - 1^2 = 9 - 1 = 8$.
• Right-hand side: $f_{5} = 8$ (there are exactly 8 ways to tile a 1×5 strip).
• Valid pairs: 6 pairs where $A$ ends with a square (2 (n-1) tilings × 3 n tilings) + 2 pairs where $B$ ends with a square but $A$ doesn't (1 (n-2) tiling × 2 (n-1) tilings) = 8 pairs, which exactly matches the number of 5-length tilings.

内容的提问来源于stack exchange，提问作者tex_mate