Câu 5. (3,0 điểm) Cho 21 ô vuông được xếp thành một hàng dọc liên tiếp nhau. Người ta tô một trong hai màu đen hoặc trắng cho mỗi ô vuông sao cho:
i) Không tô đen 2 ô liên tiếp nhau.
ii) Không tô trắng quá 2 ô liên tiếp nhau.
Hỏi có bao nhiêu cách tô màu thỏa mãn đồng thời các điều kiện trên?

LỜI GIẢI (tham khảo, SMFE - Bản luận toán học số 12):
Với mỗi số nguyên dương $n$, ký hiệu $S_n$ là cách tô màu cho $n$ ô vuông thỏa mãn đề bài; $x_n$, $y_n$ là số cách tô riêng tương ứng với ô đầu tiên được tô màu đen và trắng. Khi đó
$$S_n=x_n+y_n,\forall n\in {\mathbb{N}}^{\ast }.$$
Xét một cách tô mà ô vuông đầu tiên được tô màu đen. Theo (i.), ô vuông thứ hai phải được tô trắng nên
$$x_n=y_{n-1},\forall n⩾2.\text{\hspace{1em}(7)}$$
Xét một cách tô mà ô vuông đầu tiên được tô màu trắng và ta xét hai trường hợp sau
- Trường hợp 1. Ô vuông thứ hai được tô màu trắng. Khi đó ô vuông thứ ba là màu đen và số cách tô là $x_{n-2}$.
- Trường hợp 2. Ô vuông thứ hai là màu đen. Khi đó số cách tô là $x_{n-1}$.
Qua hai cách đếm trên, ta suy ra $y_n=x_{n-1}+x_{n-2}$ với mọi $n⩾3$. Kết hợp với (7), ta suy ra $x_n=x_{n-2}+x_{n-3}$ với mọi $n⩾4$. Mà ta có thể đếm được $x_1=1,x_2=1,x_3=2$ nên ta có thể đếm được $x_{21}=265,x_{22}=351$. Do đó
$$S_{21}=x_{21}+y_{21}=x_{21}+x_{22}=616.$$
Vậy ta có 616 cách tô thỏa mãn.