Solution
Dominoes and Big Squares
Show the problem again
Using any number of 1 × 2 dominoes (horizontal or vertical) and any number of 2 × 2 squares, in how many ways can a 2 × 10 rectangle be tiled exactly? Give an integer.
Worked solution
**Answer: 683.** At the left end there are three possibilities: a vertical domino (leaving 2 × 9), two stacked horizontal dominoes (leaving 2 × 8), or a 2 × 2 square (leaving 2 × 8). So a(n) = a(n − 1) + 2a(n − 2) with a(0) = 1, a(1) = 1. This is the Jacobsthal recurrence, with closed form a(n) = (2^(n+1) + (−1)^n) / 3 (the characteristic roots are 2 and −1). For n = 10: (2048 + 1) / 3 = 683. The terms are 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.