ciągi n-wyrazowe - rekurencja

[niebieska_biedronka]

Ile jest ciągów n - wyrazowych o wyrazach ze zbioru \(\displaystyle{ \{ 1, 2, 3, 4, 5\}}\) takich, że dwie parzyste liczby nie mogą stać obok siebie? Znajdź zależność rekurencyjną.

Na razie znalazłam tylko \(\displaystyle{ a_0 =0, a_1 = 5, a_2 = 21}\), tworzenie kolejnych ciągów polega na dodaniu do już istniejących jednej liczby na końcu - parzystej lub nieparzystej, w zależności od tego, co w danym ciągu się znajduje. Jak to jednak wykorzystać do rekurencji? Będę wdzięczna za pomoc

[Qń]

\(\displaystyle{ \begin{cases} a_0 = 1 \\ a_1 = 5\\ a_n=3a_{n-1}+6a_{n-2}\end{cases}}\)
Ciągi długości \(\displaystyle{ n}\) dzielimy na dwa typy - zakończone liczbą parzystą (wtedy przedostania liczba musi być nieparzysta, a reszta dowolnie) lub nieparzystą (wtedy reszta dowolnie). Spróbuj sama dopracować szczegóły.

Q.

[niebieska_biedronka]

Dlaczego \(\displaystyle{ a_0 = 1}\)?
Wiem, jak taki ciąg stworzyć, ale nadal nie wiem, skąd ten wzór... Jeśli ciąg kończy się liczbą parzystą, to możemy do niego dostawić 3 znaki, czyli z każdego takiego ciągu powstają 3 nowe; ale jeśli kończy się nieparzystą, to możemy dostawić 5. Nie widzę jednak związku ze wzorem

[Qń]

Dlaczego \(\displaystyle{ a_0 = 1}\)?

Bo istnieje tylko jedna idąca do podanego zbioru.

możemy do niego dostawić

Ale my nic nie dostawiamy.

W takich zadaniach rozumowanie idzie w drugą stronę - rozważamy zbiór ciągów \(\displaystyle{ n}\)-wyrazowych i dzielimy je na takie, które kończą się liczbą parzystą i takie które kończą się liczbą nieparzystą. I następnie badamy co w takim razie może się znajdować na \(\displaystyle{ n-1}\) pierwszych miejscach ciągu.

Przykładowo, jeśli ciąg \(\displaystyle{ n}\) wyrazowy kończy się dwójką, to przedostatnia cyfra może być tylko jedynką, trójką lub piątką. A wtedy na \(\displaystyle{ n-2}\) pierwszych miejscach może być dowolny ciąg spełniający warunki zadania - a tych jest oczywiście \(\displaystyle{ a_{n-2}}\). Stąd wniosek, że żądanych ciągów o długości \(\displaystyle{ n}\) kończących się dwójką jest \(\displaystyle{ 3\cdot a_{n-2}}\).

Q.

[niebieska_biedronka]

... a ponieważ sytuacja, kiedy mamy czwórkę zamiast dwójki jest analogiczna, dlatego we wzorze mamy 6, tak?
Zupełnie inaczej patrzyłam na to zadanie. Bardzo dziękuję za pomoc