Let a_n represent the number of ways to tile a 2 × n rectangle using 1 × 2 dominoes. We need to find a recurrence relation for a_n. First, let's consider the base cases for small values of n.

For n=1, a 2 × 1 rectangle can only be tiled in one way: with a single vertical domino. So, a_1 = 1. For n=2, a 2 × 2 rectangle can be tiled in two ways: either with two vertical dominoes or with two horizontal dominoes. So, a_2 = 2.

For n=1, a 2 × 1 rectangle can only be tiled in one way: with a single vertical domino. So, a_1 = 1. For n=2, a 2 × 2 rectangle can be tiled in two ways: either with two vertical dominoes or with two horizontal dominoes. So, a_2 = 2.

Consider the rightmost column(s) of the 2 × n rectangle. There are two possibilities for placing the last dominoes: 1. A single vertical domino in the last column. The remaining 2 × (n-1) rectangle can be tiled in a_n-1 ways. 2. Two horizontal dominoes occupying the last two columns. The remaining 2 × (n-2) rectangle can be tiled in a_n-2 ways. These two cases are mutually exclusive and exhaustive, so a_n = a_n-1 + a_n-2.

Consider the rightmost column(s) of the 2 × n rectangle. There are two possibilities for placing the last dominoes: 1. A single vertical domino in the last column. The remaining 2 × (n-1) rectangle can be tiled in a_n-1 ways. 2. Two horizontal dominoes occupying the last two columns. The remaining 2 × (n-2) rectangle can be tiled in a_n-2 ways. These two cases are mutually exclusive and exhaustive, so a_n = a_n-1 + a_n-2.

How many ways can a 2×n rectangle be tiled using 1×2 dominoes?

Answer: The number of ways to tile a $2 \times n$ rectangle using $1 \times 2$ dominoes is $F_{n+1}$ , where $F_n$ is the $n$ -th Fibonacci number with $F_1=1$ and $F_2=1$ .

Step-by-step solution

Step 1: Define the problem and base cases

Let $a_n$ represent the number of ways to tile a $2 \times n$ rectangle using $1 \times 2$ dominoes. We need to find a recurrence relation for $a_n$ . First, let's consider the base cases for small values of $n$ .

Step 2: Calculate base cases for $n=1$ and $n=2$

For $n=1$ , a $2 \times 1$ rectangle can only be tiled in one way: with a single vertical domino. So, $a_1 = 1$ . For $n=2$ , a $2 \times 2$ rectangle can be tiled in two ways: either with two vertical dominoes or with two horizontal dominoes. So, $a_2 = 2$ .

Step 3: Derive the recurrence relation

Consider the rightmost column(s) of the $2 \times n$ rectangle. There are two possibilities for placing the last dominoes: \\ 1. A single vertical domino in the last column. The remaining $2 \times (n-1)$ rectangle can be tiled in $a_{n-1}$ ways. \\ 2. Two horizontal dominoes occupying the last two columns. The remaining $2 \times (n-2)$ rectangle can be tiled in $a_{n-2}$ ways. \\ These two cases are mutually exclusive and exhaustive, so $a_n = a_{n-1} + a_{n-2}$ .

Step 4: Recognize the Fibonacci sequence

The recurrence relation $a_n = a_{n-1} + a_{n-2}$ with initial conditions $a_1 = 1$ and $a_2 = 2$ defines a shifted Fibonacci sequence. The standard Fibonacci sequence is $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, \dots$ . Comparing, we see that $a_n = F_{n+1}$ .

More from this chapter

All Permutations and Combinations solutions →

Solve your own maths question free →