Solution
Tiling with Dominoes
Show the problem again
How many ways are there to tile a 2 × 10 board completely with 1 × 2 dominoes?
Worked solution
The answer is 89. Let T(n) count tilings of a 2 × n board. The leftmost column is covered either by one vertical domino (leaving 2 × (n−1)) or by two horizontal dominoes (leaving 2 × (n−2)): T(n) = T(n−1) + T(n−2), with T(1) = 1, T(2) = 2. Iterating gives T(10) = 89: Fibonacci again.
Source: Standard domino-tiling recurrence from introductory combinatorics texts. Statement written for AxiomIQ.