The ultra-classical domino tiling problem

You want to tile a 2 x N grid with dominoes. How many ways can you do this?

Experimentation step

Let’s try to experiment a bit with small cases of N.

If N = 1 we have a 2x1 grid but of course, that is just a domino so the answer is 1.

If N = 2 we have a 2x2 grid. We need to cover the upper-left square so we place a domino there and of course it can be horizontal or vertical, either of these cases gives 1 option so there is a total of 2.

If one continues experimenting, one gets 3 for N=3, 5 for N=4 and 8 for N=5. This seems like the fibonacci sequence so let’s prove that it is in fact, the fibonacci sequence.

Proving step

How do we prove something over the naturals? The most tempting answers are (strong) induction, recursion or dynamic programming.

Let’s try to use induction to prove that

Where the LHS is the solution to this problem for N and the RHS is the (N+1)st fibonacci number.

Base case:

These cases are N = 1 and N = 2 which we have already proven before.

Strong induction hypothesis: