Problem
COM-B1-M10-P014 Prove the Domino Recurrence
#14
★★★☆☆ Level 3 of 5
Prove that the number of domino tilings of a \(2\times n\) board satisfies \(a_n=a_{n-1}+a_{n-2}\).
Look at how the upper-right cell is covered.
If the upper-right cell is covered by a vertical domino, then the whole last column is covered, leaving \(2\times(n-1)\): \(a_{n-1}\) ways. If it is covered by a horizontal domino, then the lower-right cell must also be covered by a horizontal domino from the previous column, leaving \(2\times(n-2)\): \(a_{n-2}\) ways. There are no other cases and they do not overlap. Hence \(a_n=a_{n-1}+a_{n-2}\).
Formal proof of the standard recurrence.