Tiling The Rectangle

Let us denote the number of tilings of the rectangle $3 \times 2n$ as $a_n$ and number of tilings of the rectangle $3 \times (2n-1)$ without the right lower corner as $b_n$ . From the picture, we see that $a_1=3$ and trivially $b_1=1$ .

From the following set of pictures, we can infer that $a_n=a_{n-1}+2b_n$ and $b_n=a_{n-1}+b_{n-1}$ for $n>1$ : The key here is to realize that these options for $a_n$ and $b_n$ encompass all possibilities and that there are no duplicities.

We have a recursive relationship for the two sequences and first members of both sequences, which is enough for calculating $a_5$ (the number we are looking for). Easily, we find that it is $\boxed{571}$ .

---

Source: Slovak/Czech High School Math Olympiad, 2013/14, Home Round of category A (upperclass students), Problem number 5, author: Stanislava Sojakova (me :)