Liczba ciągów zerojedynkowych długości n, w których nie ma dwóch zer obok siebie.

[amf3tam1nz]

Znajdź równanie rekurencyjne rozwiązujące następujący problem: Liczba ciągów zero-jedynkowych długości \(n\), w których nie ma dwóch zer obok siebie.

[kerajs]

Zadanie sprowadza się do policzenia ile jest n−elementowych ciągów zawierających wyłącznie cyfry 0 i 1 ograniczonych regułami:
− po 1 może następować 0 lub 1
− po 0 może być tylko 1
wprowadzam ciągi \(a_n \ , \ b_n\) zliczające ile n−elementowych ciągów kończy się odpowiednio cyfrą 0 lub 1
Reguły narzucają układ równań rekurencyjnych:
\( \begin{cases} a_n=b_{n−1} \\ b_n=a_{n−1} +b_{n−1} \end{cases} \)

Można by go rozwiązać, jednak w zadaniu pytają o sumę \(S_n\) tych ciągów.
\(S_n=a_n+b_n =b_{n−1}+a_{n−1} +b_{n−1} =S_{n−1} +b_{n−1} =\\=S_{n−1} +a_{n−2}+b_{n−2} =S_{n−1} +S_{n−2} \)
I to jest zależnością o którą pyta autor zadania.

Wzór ogólny dostanie się zliczając ciągi \(S_1: { (0), (1)} \ i \ S_2:{(0,1), (1,0), (1,1)}\) i rozwiązując równanie rekurencyjne, jednak od razu narzuca się skojarzenie z przesuniętym ciągiem Fibonacciego, a wzór Bineta jest powszechnie znany.

[Młodociany całkowicz]

Niech \(a\) będzie ciągiem kolejnych liczb takich ciągów
Wiemy, że
\(a_0 = 0 \)
\(a_1 = 1 \)
Rozważmy teraz ciąg długości \(n\).
Niech \(k\) będzie najwcześniejszą pozycją, na której jest 0. Wówczas wszystkie wcześniejsze pozycje i jedna następująca będą zajęte przez jedynki. Wobec tego liczba takich ciągów to \(a_{n-k-1}\)
Dlatego też
\(a_n = \sum_{k=2}^{n-1} a_{n-k} = \sum_{k=1}^{n-2} a_k\)
\( \begin{cases} a_n =\sum_{k=1}^{n-2} a_k\\ a_{n+1} = \sum_{k=1}^{n-1} a_k \end{cases}\)
Po odjęciu stronami otrzymujemy:
\(a_{n+1}- a_n =a_{n-1} \Rightarrow a_{n+1} = a_n + a_{n-1}\)