zależność rekurencyjna słów..

[kamzeso]

Niech \(\displaystyle{ q _{n}}\) oznacza liczbę słów długości \(\displaystyle{ n}\) nad alfabetem \(\displaystyle{ \{0,1\}}\), które nie zawierają podsłowa \(\displaystyle{ 00}\). Wyprowadź zależność rekurencyjną dla \(\displaystyle{ q _{n}}\).
w jaki sposób mogę to rozwiązać??

proszę o pomoc..

[Zordon]

Wyznaczaj jednocześnie ile jest słów spełniających to i kończących się na 1, oraz kończących się na 0. Będziesz miał dwa wzajemnie rekurencyjne ciągi.

[kamzeso]

ok, z tego rozpisywania otrzymałem coś takiego:
\(\displaystyle{ \begin{cases} n= 0 \ q _{n}=1 \\ n=1 \ q _{n} = 2 \\ n=2 \ q _{n} = 3 \\ n=3 \ q _{n}=5 \\ n=4 \ q _{n}=7 \end{cases}}\)

i z tego równanie wydaje mi się że powinno wyglądać tak: \(\displaystyle{ q _{n} = q _{n-1} + 2}\)
ale nie zgadza się dla pierwszych 2 wyrazów.. co jest nie tak w moim rozumowaniu??

[Zordon]

A gdzie jest to rozumowanie? Wypisujesz kilka pierwszych wyrazów i zgadujesz wzór, który się nie zgadza?

[kamzeso]

więc nie wiem jak to można rozpisać..

[Zordon]

przeczytaj mój pierwszy post, tam jest rozwiązanie.

[kamzeso]

Wyznaczaj jednocześnie ile jest słów spełniających to i kończących się na 1, oraz kończących się na 0. Będziesz miał dwa wzajemnie rekurencyjne ciągi.

hmm, napisze to jak próbuje, ale nie wiem czy dobrze to kombinuje..

\(\displaystyle{ d _{n} ^{0}, d _{n} ^{1}}\) - to ciągi zakończone odpowiednio na 0 i 1.(nie posiadające ciągu 00).

i teraz nie jestem pewien:
\(\displaystyle{ d _{n} ^{0} = d _{n-1} ^{1}}\)
\(\displaystyle{ d _{n} ^{1} = d _{n-1} ^{0} + d _{n-1} ^{1}}\)

\(\displaystyle{ c _{n} = d _{n} ^{0} + d _{n} ^{1}= d _{n-1} ^{0} + 2 d _{n-1} ^{1} = c _{n-1} + d _{n-1} ^{1}}\)
ale dalej nie wiem jak tego \(\displaystyle{ d _{n-1} ^{1}}\) w ostatniej linijce się pozbyć..

[Zordon]

Bardzo dobrze, teraz mamy: \(\displaystyle{ d_{n-1}^1=d_{n-2}^1+d_{n-2}^0=c_{n-2}}\)