Zależność rekurencyjna.

[1608]

Bardzo proszę o jakieś wskazówki do zadania:

Ile jest różnych ciągów binarnych długości n, w których nie ma dwóch kolejnych zer? Znajdź zależność rekurencyjną.

[szw1710]

Oznacz to przez np. \(\displaystyle{ T_n}\). Mamy \(\displaystyle{ T_1=2}\), \(\displaystyle{ T_2=3}\). Jak powstaje ciąg \(\displaystyle{ n+1}\) wyrazowy? Do \(\displaystyle{ n}\) wyrazowego dopisujesz zero lub jedynkę na końcu. A więc trzeba pewne rzeczy wykluczyć. Dopisanie jedynki nie da kolejnych zer. Dopisanie zera może dać i to trzeba wykluczyć. Z dopisania jedynki mamy \(\displaystyle{ T_n}\) ciągów, a z dopisania zera? Policz, zastanów się. Potem policz na piechotę \(\displaystyle{ T_4}\), zobacz czy pasuje itd.

[1608]

Policzyłem sobie i próbuje znaleźć jakąś zależność.
Wiem że np. w \(\displaystyle{ T_{2}}\) jest jeden ciąg z którego będą już zawsze powstawać ciągi gdzie występuje podciąg 00, w \(\displaystyle{ T_{3]}\) są już trzy ciągi które teraz zawsze będą mieć podciąg 00. W \(\displaystyle{ T_{4}}\) będzie już tych elementów 9. Szukam tych zależności z dopisywaniem zer i jedyneko, ale po prostu dalej nie pokazuje mi się jakiś sensowny wzór.-- 10 lis 2013, o 02:14 --Coś mi tu nie pasuje. Bo jeśli np. \(\displaystyle{ T_{2}=3}\) (są trzy ciągi gdzie nie ma podwójnego zera) , a \(\displaystyle{ T_{3}=5}\) a dla \(\displaystyle{ T_{4}=8}\) to wydaje mi się że twoja propozycja wzoru jest błędna ?

[vpprof]

\(\displaystyle{ 01{\red10} \\
10{\red10} \\
11{\red10} \\
010{\green1} \\
110{\green1} \\
011{\green1} \\
101{\green1} \\
111{\green1} \\}\)-- 11 lis 2013, o 23:45 --Rozumiesz, co to obrazuje? Jakie człony będzie miała rekurencja?