4. In how many ways can a rectangular board of size $2 \times 18$ be covered with identical rectangular tiles of size $1 \times 2$? The tiles must be placed so that they fit entirely on the board and do not overlap.

(12 points)
Solution. Let there be a board of size $2 \times$ n. Denote the number of ways to tile it with tiles of size $1 \times 2$ by $P_{n}$. Then the following recurrence relation holds: $P_{n}=P_{n-1}+P_{n-2}$. Since $P_{1}=1, P_{2}=2$, performing sequential calculations using the recurrence relation, we arrive at the answer $P_{18}=4181$.

Answer: 4181.