Ile ciągów - równania rekurencyjne

[Alivia]

Ile można utworzyć ciągów długości n złożonych z cyfr 0,1 i 2 tak, by żadne dwie jedynki ani żadne dwie dwójki nie stały obok siebie?
Zadanie należy rozwiązać za pomocą wzoru rekurencyjnego na n-ty wyraz ciągu.

[Premislav]

Powiedzmy, że mamy ciąg długości \(\displaystyle{ n}\) spełniający warunki zadania. Jeśli kończy się on jedynką bądź dwójką, to mamy dwie możliwości: albo dopisujemy dwójkę (odpowiednio: jedynkę), albo zero, by stworzyć ciąg o \(\displaystyle{ n+1}\) elementach spełniający warunki zadania. Jeśli natomiast ciąg długości \(\displaystyle{ n}\), w którym żadne dwie jedynki ani dwójki nie stoją obok siebie, kończy się zerem, to na \(\displaystyle{ n+1}\). pozycji możemy wstawić cokolwiek i dalej będzie dobrze.
Oznaczmy przez \(\displaystyle{ a_n}\) liczbę wszystkich dobrych ciągów długości \(\displaystyle{ n}\), zaś przez \(\displaystyle{ b_n}\) liczbę ciągów długości \(\displaystyle{ n}\) kończących się zerem i spełniających warunki zadania. Mamy więc
\(\displaystyle{ a_{n+1}=2(a_n-b_n)+3b_n=2a_n+b_n}\)
Z drugiej strony ciąg spełniający warunki zadania i kończący się zerem mający przy tym długość \(\displaystyle{ n+1}\) możemy zbudować tak: do każdego ciągu długości \(\displaystyle{ n}\) spełniającego warunki zadania dopisujemy po prostu zero (inaczej zrobić nie można, bo jeśli gdzieś wcześniej stały obok siebie jedynki bądź dwójki, to po dopisaniu zera na końcu oczywiście to się nie zmieni).
Czyli \(\displaystyle{ b_{n+1}=a_n}\)
Zatem \(\displaystyle{ a_{n+1}=2a_n+b_n=2a_n+a_{n-1}}\)

i mamy proste równanie jednorodne. Dopisz sobie \(\displaystyle{ a_1=3, a_2=7}\) (policzyłem na palcach) i rozwiązujesz to ulubioną metodą.

[Alivia]

Dzięki