Fibonacci Tilings

along with the initial conditions F₁ = 1 and F₀ = 0.

The Fibonacci name has been attached to the sequence 0, 1, 1, 2, 3, 5, ... due to the inclusion in his 1202 book Liber Abaci of a rabbit reproduction puzzle: under certain constraints the rabbit population at discrete times is given exactly by that sequence. As naturally, the sequence is simulated by counting the tilings with dominoes of a 2×n board:

A tiling of a 2×n board may end with two horizontal dominoes or a single vertical domino:

In the former case, it's an extension of a tiling of a 2×(n-2) board; in the latter case, it's an extension of a tiling of a 2×(n-1). If T_n denotes the number of domino tilings of a 2×n board, then clearly

T_n = T_n-2 + T_n-1

which is the same recurrence relation that is satisfied by the Fibonacci sequence. By a direct verification, T₁ = 1, T₂ = 2, T₃ = 3, T₄ = 5, etc., which shows that {T_n} is nothing but a shifted Fibonacci sequence. If we define, T₀ = 1, as there is only 1 way to do nothing; and T_-1 = 0, because there are no boards with negative side lengths, then F_n = T_n-1, for n ≥ 0.

The tilings of the two boards may or may not have a fault line. A fault line is a line on the two boards at which the two tilings are breakable. For example, the tilings below have three fault lines:

The trick is now to swap tails: the pieces of the two tilings (along with the boards) after the last fault line:

Since the bottom board has been shifted just one square, the swap produces one tiling of a 1×(n+1) - the top board in the diagram - and one tiling of a 1×(n-1) board - the bottom board in the diagram. Note that the old faults have been preserved and no new faults have been introduced.

Thus, in the presence of faults, there is a 1-1 correspondence between two n-tilings (T_n) and a pair of (n-1)- and (n+1)-tilings. The time is to account for the faultless combinations, if any.

But there are. Any 1×1 square induces a fault. This leaves exactly two faultless tilings. If n is odd, both n-1 and n+1 are even, there is a unique pair of (n-1)- and (n+1)-tilings:

If n is even, there is a unique n-tiling that, when shifted, generates no fault lines:

References