# Finding the number of ways to tile a rectangular board

In how many ways can a 2 × n rectangular board be tiled using 1 × 2 and 2 × 2 pieces?

What i tried

I used to inclusion exclusion principle where

no of ways the 2 × n rectangular board can be tiled using 1 × 2 AND 2 × 2 pieces

=the no of ways the 2 × n rectangular board can be tiled using 1 × 2 pieces +

no of ways the 2 × n rectangular board can be tiled using 2 × 2 pieces - no of ways the 2 × n rectangular board can be tiled using 1 × 2 OR 2 × 2 pieces

Then solving each of the three parts indivually

no of ways the 2 × n rectangular board can be tiled using 1 × 2 pieces=$(n/2*2)=n$ ways

no of ways the 2 × n rectangular board can be tiled using 2 × 2 pieces =$(n/2)$ ways

no of ways the 2 × n rectangular board can be tiled using 1 × 2 OR 2 × 2 pieces=$(3*n/2)$ ways

You have several problems. The question is intended to allow you to mix $1 \times 2$ and $2 \times 2$ pieces. You have assumed that a given tiling only allows one type to be used. Given your assumption, there is only one way to tile using $2 \times 2$ pieces, and that only if $n$ is even. For $1 \times 2$, there are at least as many tilings as if you tile it with $2 \times 2$ blocks, then cut each block in half. As you can cut each block either horizontally or vertically, this accounts for $2^{\frac n2}$ tilings and there are many more.
The intended solution is by a recurrence relation. A tiling of a $2 \times n$ board can either end with a $2 \times 2$ block on the right, a pair of horizontal $1 \times 2$ blocks on the right, or a vertical $1 \times 2$ block on the right. Let $A(n)$ be the number of ways to tile a $2 \times n$ rectangle. Can you write the recurrence based on the first sentence?
What you want to do here is work out a recurrence and then solve it. Let $a_n$ be the number of ways of tiling the $2\times n$ board; we want to express $a_n$ in terms of one or more $a_k$’s with $k<n$.
A tiling of the $2\times n$ board can end in a vertical $1\times 2$ tile, a $2\times 2$ tile, or a pair of horizontal $1\times 2$ tiles. How many tilings of each kind are there?
• The vertical $1\times 2$ tile can be placed after any tiling of the $2\times(n-1)$ board, so there are $a_{n-1}$ of these tilings of the $2\times n$ board.
• Either the $2\times 2$ tile or the pair of horizontal $1\times 2$ tiles can be placed after any tiling of the $2\times(n-2)$ board, so there are $2a_{n-2}$ of these tilings.
Thus, $a_n=a_{n-1}+2a_{n-2}$. To finish the problem, you need to work out the initial values for the recurrence (either $a_0$ and $a_1$ or $a_1$ and $a_2$) and then solve the recurrence to get a closed form for $a_n$ in terms of $n$.