rekurencja - podział prostokąta

[nova]

Znaleźć wzór rekurencyjny a(n) wskazujący ilość możliwych podziałów prostokąta o wymiarach 2 x n na prostokąty 1 x 2 i 1 x 1.

Ma ktoś jakiś pomysł, jak to rozwiązać?

[półpasiec]

niech \(\displaystyle{ D_n}\) oznacza taki podzial dla prostokata o wymiarach 2xn
chcemy obliczyc \(\displaystyle{ D_{n+1}}\)
mozemy na ostatni prostokat polozyc klocki na dwa sposoby
mozemy jednak polozyc klocek 2x1 poziomo, bedziemy zliczac takie ustawienia ze ostatnie klocki sa polozone poziomo, az nie dojdziemy do prostokata o mniejszych rozmiarach
widac ze ten przod mozemy na dwa sposoby ustawic- 1x1 na gorze albo dole
widac wiec ze \(\displaystyle{ D_{n+1}=2D_n+3D_{n-1}+2D_{n-2}+2D_{n-3}+...+2D_1+2D_0}\)
tamta trojka przy \(\displaystyle{ D_{n-1}}\) to nie przypadek w tym przypadku mamy trzy mozliwosci ulozenia przodu
zeby zwiazek byl zalezny od kilku wczesniejszych robimy tak
\(\displaystyle{ D_{n+1}= 2D_n+3D_{n-1}+2D_{n-2}+2D_{n-3}+...+2D_1+2D_0= \\ =
2D_n+D_{n-1}-D_{n-2}+2D_{n-1}+3D_{n-2}+2D_{n-3}+...+2D_1+2D_0= \\ =
2D_n+D_{n-1}-D_{n-2}+D_n=3D_n+D_{n-1}-D_{n-2}}\)