Równanie rekurencyjne Maciek: Niech ∑ = {a, b, c} i niech s_n oznacza liczbę słów długości n, które nie mają kolejnych liter a. Podaj wzór rekurencyjny. s₀ = 1 s₁ = 3 s₂ = 8 s₃ = 22 s₄ = 60 Jeśli na końcu znajduje się a, wówczas mogę stworzyć 2 wyrazy kończące się na b lub c. Jeśli na końcu znajduje się b lub c, wówczas mogę stworzyć 3 wyrazy kończące się dowolną literą. Prosiłbym o wyjaśnienie jak to rozpisać rekurencyjnie.

jc: s_n = x_n + y_n (z literą a na końcu, bez litery a na końcu) x_n+1 = y_n y_n+1 = 2(x_n + y_n) stąd s_n = y_n−1 + y_n, podstawiłem y_n+1 = 2(y_n−1 + y_n), podstawiłem y_n = 2(y_n−2 + y_n−1), zamieniłem n na n−1 dodajemy stronami 2 ostatnie równania s_n+1 = 2(s_n−1 + s_n), co wraz z warunkami s₀=1, s₁ = 3 definiuje ciąg s_n.