Ilość słów w alfabecie

[uczen23]

Niech \(\displaystyle{ \Sigma =\{a,b,c \}}\)

Niech \(\displaystyle{ s_n}\) oznacza liczbę słów długości \(\displaystyle{ n}\) w alfabecie \(\displaystyle{ \Sigma}\), w których nie występuje ciąg \(\displaystyle{ aa}\). Obliczyć pięć pierwszych wyrazów ciągu \(\displaystyle{ s_n}\) i znaleźć dla niego wzór rekurencyjny.

Ktoś mógłby pokazać jak robić takiego typu zadania?

[Premislav]

Nie „ilość", tylko „liczba".

Obliczać aż pierwszych pięciu wyrazów nie będę, pokażę natomiast, jak można (choć być może da się lepiej) „wydobyć" rekurencję.
Oznaczmy przez \(\displaystyle{ x_n}\) liczbę wyrazów (utworzonych oczywiście ze znaków tego alfabetu) mających długość \(\displaystyle{ n}\), spełniających warunki zadania (tj. bez \(\displaystyle{ aa}\)) i kończących się znakiem \(\displaystyle{ a}\) oraz przez \(\displaystyle{ y_n}\) liczbę wyrazów długości \(\displaystyle{ n}\) spełniających warunki zadania i kończących się innym znakiem niż \(\displaystyle{ a}\). Wówczas oczywiście mamy
\(\displaystyle{ x_n+y_n=s_n}\).
Ponadto widzimy, że spełnione są zależności \(\displaystyle{ x_{n+1}=y_n}\) oraz \(\displaystyle{ y_{n+1}=2s_n}\)
Ta pierwsza zależność zachodzi, ponieważ wykreślając z ciągu długości \(\displaystyle{ n+1}\), w którym nie ma sąsiadujących \(\displaystyle{ a}\) i który kończy się znakiem \(\displaystyle{ a}\), ostatni wyraz, otrzymamy ciąg długości \(\displaystyle{ n}\), w którym nie ma sąsiadujących \(\displaystyle{ a}\) i który kończy się innym znakiem niż \(\displaystyle{ a}\) (poza tym z drugiej strony, dopisując na jeden sposób do ciągu z \(\displaystyle{ y_n}\)…). Natomiast zależność
\(\displaystyle{ y_{n+1}=2s_n}\) widać analogicznie (dopisujemy \(\displaystyle{ b}\) albo \(\displaystyle{ c}\) do dowolnego ciągu spełniającego warunki zadania, który ma długość \(\displaystyle{ n}\)).

Stąd mamy
\(\displaystyle{ \begin{cases} x_n+y_n=s_n \\ x_{n+1}=y_n\\y_{n+1}=2s_n \end{cases}}\)
czyli dla\(\displaystyle{ n\ge 2}\) będzie także
\(\displaystyle{ y_{n-1}+y_n=s_n}\) i korzystając teraz w tej zależności z:\(\displaystyle{ y_{n+1}=2s_n}\) z przesuniętymi indeksami, dla \(\displaystyle{ n\ge 3}\) mamy
\(\displaystyle{ 2s_{n-2}+2s_{n-1}=s_n}\).
Teraz obliczamy \(\displaystyle{ s_1=3, \ s_2=8=3^2-1}\) i dalej już raczej wiadomo.

[uczen23]

Dzieki. Mam klopoty z takimi zdaniami. Masz może jakieś wskazówki do tego typu zadań? Ob czego zacząć? Na co zwrócić uwagę?