pokrywanie prostokąta kostkami

[JakubCh]

(i) na ile sposobów można pokryć prostokąt \(\displaystyle{ 3 \times n}\) kostkami \(\displaystyle{ 1 \times 2}\)?

(ii) na ile sposobów można pokryć prostokąt \(\displaystyle{ 2 \times n}\) kostkami \(\displaystyle{ 2 \times 1}\) i kostką o polu \(\displaystyle{ 3}\) złożoną z trzech pól nie tworzących prostokąta?

[abc666]

W pierwszym zauważ, że kostki mają parzystą powierzchnię, więc \(\displaystyle{ n}\) musi być parzyste. Ułóż równanie rekurencyjnie na liczbę sposobów dla prostokąta w zależności od liczby ułożeń dla mniejszych prostokątów.