Matematyka.pl

Niech \(\displaystyle{ \sum_{}^{} =\{a,b \}}\)
Niech \(\displaystyle{ s_n}\) oznacza liczbę słów długości \(\displaystyle{ n}\) w alfabecie \(\displaystyle{ \sum_{}^{}}\) niezawierających ciągu \(\displaystyle{ ab}\). Obliczyć
pięć pierwszych wyrazów ciągu \(\displaystyle{ s_n}\), znaleźć jawny wzór na \(\displaystyle{ s_n}\) i go udowodnić.

dla \(\displaystyle{ n=1}\)
słowa: \(\displaystyle{ a,b}\)

dla \(\displaystyle{ n=2}\)
słowa: \(\displaystyle{ aa,ba,bb}\)

dla \(\displaystyle{ n=3}\)
słowa: \(\displaystyle{ aaa,baa,bbb,bba}\)

dla \(\displaystyle{ n=4}\)
słowa: \(\displaystyle{ aaaa,baaa,bbbb,bbaa,bbba}\)

więc chyba wzór to \(\displaystyle{ s_n=n+1}\)

teraz pytanie, jak go udowodnić?

Tutaj rekurencje nawet nie są potrzebne. Jeśli mają być tylko znaki \(\displaystyle{ a,b}\) i nie mogą wystąpić nigdzie w porządku \(\displaystyle{ ab}\), to mamy trzy możliwości:
1) w słowie mamy same \(\displaystyle{ a}\) (jest tylko jedno takie słowo długości \(\displaystyle{ n}\)),
2) w słowie mamy same \(\displaystyle{ b}\) (jak wyżej),
3) słowo zaczyna się od pewnej liczby wystąpień znaku \(\displaystyle{ b}\), a od pewnego miejsca później występują już same znaki \(\displaystyle{ a}\). Widzimy, że taki nasz ciąg długości \(\displaystyle{ n}\) jest jednoznacznie identyfikowany przez miejsce wystąpienia pierwszy raz znaku \(\displaystyle{ a}\). Żeby nie było samych \(\displaystyle{ a}\), ani samych \(\displaystyle{ b}\), musi wystąpić pierwsze \(\displaystyle{ a}\) na jednym z miejsc o numerach \(\displaystyle{ 2, \ldots n}\), czyli łącznie mamy tu \(\displaystyle{ n-1}\) możliwości.

Sumując liczby ciągów z tych trzech przypadków, dostajemy istotnie \(\displaystyle{ n+1}\).