Zależność rekurencyjna i wzór jawny

[Paylinka07]

Podać zależność rekurencyjną na liczbę ciągów długości \(\displaystyle{ n}\)utworzonych z liter \(\displaystyle{ a}\) i \(\displaystyle{ b}\), w których żadne dwie litery \(\displaystyle{ a}\) nie stoją obok siebie. Następnie podać wzór jawny.

[norwimaj]

Ile jest ciągów zakończonych na literę \(\displaystyle{ a}\)? Ile na literę \(\displaystyle{ b}\)?

[AdamL]

Warto zauważyć, że jeśli mamy słowo długości n, to oznaczmy je \(\displaystyle{ a_{n}}\). Ilość słów kończących się na a jest równe \(\displaystyle{ a _{n-3}}\), ilość słów kończących się na b jest równa \(\displaystyle{ a _{n-2}}\). Z każdego słowa, które kończy się na a możemy utworzyć tylko jedno, a z każdego zakończonego na b dwa, przy dodaniu jeszcze jednej litery, bo po literze b może nastąpić a lub b, a po a tylko b.

Wobec tego wzór rekurencyjny to:
\(\displaystyle{ a_{n}=2 \cdot a_{n-2} + a _{n-3}}\)

Rozwiązanie: układamy wielomian charakterystyczny
\(\displaystyle{ x ^{3}-2x-1 = (x+1)(x- \frac{1}{2} (1-\sqrt{5}))(x- \frac{1}{2} (1+\sqrt{5}))}\)
i dalej:
\(\displaystyle{ a _{n}=A*(-1) ^{n} + B*(\frac{1}{2} (1-\sqrt{5})) ^{n} + C*(\frac{1}{2} (1+\sqrt{5})) ^{n}}\)
\(\displaystyle{ a _{1}=2}\)
\(\displaystyle{ a _{2}=3}\)
\(\displaystyle{ a _{3}=5}\)
takie wartości początkowe i wyznaczamy a,b,c chyba nie ma błędów

Pozdrawiam

[norwimaj]

AdamL, trochę naokoło zrobiłeś, ale ostatecznie wynik Ci wyjdzie dobry. Liczba \(\displaystyle{ n}\)-literowych słów kończących się na \(\displaystyle{ a}\) jest równa \(\displaystyle{ a_{n-2}}\), bo wcześniej jest \(\displaystyle{ b}\) a wcześniej dowolne poprawne słowo \(\displaystyle{ n-2}\)-literowe. Liczba słów kończących się na \(\displaystyle{ b}\) jest równa \(\displaystyle{ a_{n-1}}\). Stąd równanie
\(\displaystyle{ a_n=a_{n-1}+a_{n-2}}\).

[AdamL]

AdamL, trochę naokoło zrobiłeś, ale ostatecznie wynik Ci wyjdzie dobry. Liczba \(\displaystyle{ n}\)-literowych słów kończących się na \(\displaystyle{ a}\) jest równa \(\displaystyle{ a_{n-2}}\), bo wcześniej jest \(\displaystyle{ b}\) a wcześniej dowolne poprawne słowo \(\displaystyle{ n-2}\)-literowe. Liczba słów kończących się na \(\displaystyle{ b}\) jest równa \(\displaystyle{ a_{n-1}}\). Stąd równanie
\(\displaystyle{ a_n=a_{n-1}+a_{n-2}}\).

Zauważyłem w tym ciąg Fibbonacciego o innych wartościach początkowych, ale uzasadnienia dać nie potrafiłem, za to na to co napisałem tak, ale dzieki za opis