Dla \(\displaystyle{ n=1}\) kostkę domina ułożymy na jeden sposób - połozymy ją pionowo.
Dla \(\displaystyle{ n=2}\) 2 kostki domina ułozymy na dwa sposoby - obie pionowo albo obie poziomo.
To były przypadki bazowe rekurencji.
Co, jeżeli mamy wyznaczyć liczbę ułożeń dla planszy o wymiarach 2xn?
Wprowadźmy sobie oznaczenie, niech \(\displaystyle{ T(n)}\) będzie liczbą ułożeń kostek domina na planszy 2xn.
Przypadek 1
Ostatnią kostkę domina mogliśmy ułożyć pionowo, wtedy liczba ułożeń dla tego przypadku wynosi \(\displaystyle{ T(n-1)}\).
Przypadek 2
Ostatnie kostki były ułożone poziomo, wtedy liczba ułożeń dla tego przypadku wynosi \(\displaystyle{ T(n-2)}\).
Czyli \(\displaystyle{ T(n)=T(n-1)+T(n-2)}\), jak napisałeś.