ý tưởng là hệ thức truy hồi :
Đánh số các ô từ trái qua phải là:$(1,2,3,...,n)$ (hàng 1) và $(n+1,n+2,...,2n)$ (hàng 2).Lát chúng bằng các viên $1\times 2$ sao cho chúng phủ kín hcn ,với $n$ lẻ thì ta bổ sung thêm viên $2\times 2$ để chúng phủ hết 2 ô $n,n+1$
Gọi $S_{n}$ là số cách lát thoả đề
Giả sử ta đã lát được hcn $2\times (n+1)$ ,xét viên gạch phủ lên ô vuông $n$
TH1:Viên gạch phủ lên $2$ ô$(n,2n)$ ,suy ra phần còn lại là một hcn $2\times n$ ,số cách lát :$S_{n}$
TH2:Viên gạch phủ lên $2$ ô $(n,n+1)$,suy ra phải có một viên phủ 2 ô $(2n-1,2n)$ ,phần còn lại là 1 hcn $2\times n-1$ ,suy ra số cách lát :$S_{n-1}$
TH3: viên gạch phủ lên 2 ô $(n,n+1)$ ($n$ lẻ) ,vậy phần còn lại chỉ được lát bởi các viên gạch nằm ngang (nếu có viên nào nằm dọc thì nó sẽ chia hcn thành 2 phần ,mỗi phần có 1 số lẻ ô chưa được lát ,số cách lát trong TH này : 1 cách.
Vậy công thức truy hồi cho bài này là:
$S_{2k}=S_{2k-1}+S_{2k-2}-1$(nếu n chẵn thì phải bớt đi 1 cách của $S_{2k-1}$)
Hoặc $S_{2k+1}=S_{2k}+S_{2k-1}$
Xử lí dãy số này ,ta tìm được số cách lát:
$S_{n}=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n})+\frac{1-(-1)^{n}}{2}$