Rozważmy pokrycie szachownicy o wymiarach
\(\displaystyle{ 3 \times n}\). Niech
\(\displaystyle{ a_n}\) oznacza ilość takich pokryć. Wtedy
\(\displaystyle{ a_0=1, a_1=0, a_2=3, a_3=0.}\)
\(\displaystyle{ a_0=1, a_1=0}\) oraz
\(\displaystyle{ a_3=0}\) są oczywiste. Na Rysunku 1 przedstawiono ilość pokryć dla
\(\displaystyle{ n=2}\).
Zauważmy, że pokrywając dwie pierwsze kolumny szachownicy na jeden z trzech powyższych sposobów otrzymujemy problem pokrycia szachownicy o wymiarach
\(\displaystyle{ 3 \times (n-2)}\). Możemy jednak ułożyć trzy pierwsze klocki w inny sposób niż na rysunku, tak aby nie zamykały układu
\(\displaystyle{ 3 \times 2}\). W przypadku układu pierwszego z Rysunku 1, po położeniu dwóch poziomych klocków, trzeci zawsze zamknie układ. W przypadku drugim i trzecim tak być nie musi. Przypadki te są symetryczne, więc opiszę jeden z nich (środkowy) (Rysunek 2). Połóżmy poziomy klocek oraz ten pionowy, który jest w pierwszej kolumnie (1) i (2). Dołożenie obok klocka pionowego zamyka układ. Kładziemy więc klocek poziomy (3). Wtedy mamy jedną możliwość na położenie kolejnego poziomego (4) oraz jeszcze kolejnego poziomego (5). Teraz dołożenie klocka pionowego (6) zamyka układ i otrzymujemy szachownicę
\(\displaystyle{ 3 \times (n-4).}\)
Możemy jednak nie zamykać układu i położyć klocek (6) poziomo (Rysunek 3). Wtedy kolejne musimy położyć poziomo (7), (8) i powtarzamy tę procedurę, aż skończy nam się szachownica.
Otrzymujemy zatem następującą rekurencję liniową:
\(\displaystyle{ a_n=3a_{n-2}+2a_{n-4}+2a_{n-6}+2a_{n-8}+\ldots}\)
Dla dowolnego
\(\displaystyle{ n}\) będzie ciężko wyznaczyć pierwiastki wielomianu charakterystycznego. Zauważmy jednak, że skoro rekurencja jest spełniona dla dowolnego
\(\displaystyle{ n,}\) więc też dla
\(\displaystyle{ n-2, (n\geqslant2)}\). Wstawmy więc do powyższej rekurencji
\(\displaystyle{ n-2}\) zamiast
\(\displaystyle{ n}\). Otrzymujemy:
\(\displaystyle{ a_{n-2}=3a_{n-4}+2a_{n-6}+2a_{n-8}+2a_{n-10}+\ldots}\)
Odejmując te dwie rekurencje stronami otrzymujemy:
\(\displaystyle{ a_{n}-a_{n-2}=3a_{n-2}+2a_{n-4}-3a_{n-4}}\)
co jest równoważne:
\(\displaystyle{ a_{n}=4a_{n-2}-a_{n-4}}\)
Możemy zauważyć, że dla
\(\displaystyle{ n}\) nieparzystych
\(\displaystyle{ a_n=0}\).
Niech zatem
\(\displaystyle{ b_n:=a_{2n}}\). Wtedy mamy
\(\displaystyle{ b_0=1, b_1=3}\). Otrzymujemy rekurencję:
\(\displaystyle{ b_n=4b_{n-1}-b_{n-2}}\)
Jej wielomian charakterystyczny to:
\(\displaystyle{ x^2-4x+1}\). Zatem pierwiastkami tego wielomianu są:
\(\displaystyle{ 2+\sqrt{3}, 2-\sqrt{3}}\). Zatem:
\(\displaystyle{ b_n=A\cdot (2+\sqrt{3})^n+B\cdot (2-\sqrt{3})^n}\)
z warunkami początkowymi
\(\displaystyle{ b_0=1, b_1=3}\).
\(\displaystyle{ \left\{\begin{array}{l}
A+B=1\\
A(2+\sqrt{3})+B(2-\sqrt{3})=3
\end{array}\right.}\)
Stąd otrzymujemy:
\(\displaystyle{ A=\dfrac{3+\sqrt{3}}{6}, \qquad B=\dfrac{3-\sqrt{3}}{6}}\)
Ostatecznie:
\(\displaystyle{ a_{2n}=b_n=\dfrac{(3+\sqrt{3})(2+\sqrt{3})^n+(3-\sqrt{3})(2-\sqrt{3})^n}{6}}\)