[Ciągi] Rekurencja dla ciągu

[justynian]

Znaleźć mamy rekurencyjny wzór na liczbę \(\displaystyle{ n}\) - elementowych ciągów o elementach ze zbioru \(\displaystyle{ \left\{ 0,1,2\right\}}\), gdzie dwie \(\displaystyle{ 1}\) ani dwie \(\displaystyle{ 2}\) nie mogą po sobie następować.

[Qń]

Szkic rozwiązania:

Oznaczmy przez \(\displaystyle{ a_n}\) szukaną liczbę i podzielmy wszystkie takie ciągi \(\displaystyle{ n}\)-elementowe następująco:
i) kończące się zerem
ii) kończące się sekwencją \(\displaystyle{ \textrm{nie jedynka}, 1}\)
iii) kończące się sekwencją \(\displaystyle{ \textrm{nie dwójka}, 2}\)

Oczywiście ciągów typu i) jest \(\displaystyle{ a_{n-1}}\).

Natomiast by policzyć ilość ciągów w pozostałych typach, zastanówmy się najpierw ile jest ciągów długości \(\displaystyle{ n-1}\) kończących się jedynką. Wszystkich jest \(\displaystyle{ a_{n-1}}\), w tym kończących się zerem \(\displaystyle{ a_{n-2}}\), a niekończących się zerem - \(\displaystyle{ a_{n-1}-a_{n-2}}\). Ale kończących się jedynką jest tyle samo co kończących się dwójką, więc jednych i drugich jest \(\displaystyle{ \frac{a_{n-1}-a_{n-2}}{2}}\). Tak więc niekończących się jedynką jest \(\displaystyle{ \frac{a_{n-1}+a_{n-2}}{2}}\) (i tyle samo jest niekończących się dwójką).

Tak więc ciągów typu ii) jest \(\displaystyle{ \frac{a_{n-1}+a_{n-2}}{2}}\) i tyle samo jest ciągów typu iii).

Otrzymujemy więc rekurencję:
\(\displaystyle{ a_n= a_{n-1}+\frac{a_{n-1}+a_{n-2}}{2}+\frac{a_{n-1}+a_{n-2}}{2}=2a_{n-1}+a_{n-2}}\)
a warunki początkowe to jak łatwo policzyć na piechotę:
\(\displaystyle{ a_1=3, a_2=7}\)

Q.

[leszczu450]

Podczepiam się pod stary temat, ale mam tutaj jedno pytanie.

Robię to zadanie standardową metodą której jestem uczony na ćwiczeniach i o dziwo mój wynik jest inny od wyniku podanej wyżej.

Moje rozwiązanie:

Ciągi mogą się zaczynać od:
0
1
2

Po zerze mam \(\displaystyle{ n-1}\) możliwości.
Potem
10
12
20
21

Po każdej z w.w opcji mogą być \(\displaystyle{ n-2}\) możliwości.

W sumie: \(\displaystyle{ a_n= a_{n-1} + 4 a_{n-2}}\)

Gdzieś w moim rozumowaniu musi być błąd.

Z góry dzięki za odpowiedź : )

[justynian]

po sekwencji 12 i 21 nie masz wcale \(\displaystyle{ a_{n-2}}\) możliwości bo nie może być np. 12|2....