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 Im unsure of my answers. Could anyone please explain. Thanks

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?