Rekurencja i funkcje tworzące - sprawdzenie.

[Nakamakakami]

Witam rozwiązuje zadanie. Niestety nie potrafię doliczyć się dobrego, ostatecznego wyniku. Bardzo proszę aby ktoś sprawdzić czy dobrze rozwiązuje.

Rozwiąż rekurencję za pomocą funkcji tworzącej.

\(\displaystyle{ T(n) = \begin{cases} 0 dla n < 0 \\ 5 _{n-1} -4 _{n-2} + 2^{n} dla n \ge 0 \end{cases}}\)

Dla ułatwienia policzono pierwsze wyrazy tego ciągu.

\(\displaystyle{ T(n) = \begin{cases} 1 dla n = 0\\ 7 dla n = 1 \\ 5 _{n-1} -4 _{n-2} + 2^{n} dla n \ge 2 \end{cases}}\)

Weźmy funkcję tworzącą T postaci

\(\displaystyle{ T(x) = \sum_{ k=0 }^{\infty} a _{k} x^{k}}\)

Wówczas na mocy zależności rekurencyjnej wyliczamy

\(\displaystyle{ T(x) = \sum_{ k=0 }^{\infty} a _{k} x^{k} = a _{0} + a _{1}x + \sum_{ k=2 }^{\infty} a _{k} x^{k}}\)
\(\displaystyle{ T(x) = 1 + 7x + \sum_{k=2}^{\infty} (5a _{k-1} - 4a _{k-2} + 2^{k} )x^{k}}\)

Skorzystano z prawa rozdzielności sum, a także przeprowadzono operację wydzielenia wyrazu poza
sumę:
\(\displaystyle{ T(x) = 1 + 7x + 5x \sum_{k=1}^{\infty} a _{k} x^{k} - 4x ^{2} \sum_{k=0}^{\infty}a _{k} x^{k} + \sum_{k=2}^{\infty} 2 ^{k} x ^{k} =}\)

//Sumę \(\displaystyle{ \sum_{k=2}^{\infty} 2 ^{k} x ^{k}}\)
obliczono korzystając z postaci zwartej Funkcji tworzącej ciągu stałego =1

\(\displaystyle{ \frac{1}{1-x} = 1 + x + x^{2} + x^{3} + ...}\) analogicznie
\(\displaystyle{ A(x) 1 + 2x + 2 ^{2} x^{2} + 2 ^{3} x^{3} + ... = \frac{1}{1-2x}}\)//

\(\displaystyle{ T(x) = 1 + 7x + 5x(T(x) - 1) - 4x^{2}T(x) + \frac{1}{1-2x} - (1 + 2x)}\)
\(\displaystyle{ T(x) = 1 + 7x + 5xT(x) -5x - 4x^{2}T(x) + \frac{1}{1-2x} -1 - 2x}\)
\(\displaystyle{ T(x) - 5xT(x) + 4x^{2}T(x) = \frac{1}{1-2x}}\)
\(\displaystyle{ T(x)(1 - 5x + 4x^{2}) = \frac{1}{1-2x} / (1 - 5x + 4x^{2})}\)
\(\displaystyle{ T(x) = \frac{1}{(1-2x)(1 - 5x + 4x^{2})}}\)

\(\displaystyle{ x_{1} = 1}\)
\(\displaystyle{ x_{2} = \frac{1}{4}}\)

\(\displaystyle{ T(x) = \frac{1}{(1-2x)(x- \frac{1}{4} )(x-1)}}\)-- 24 cze 2014, o 00:46 --Już znalazłem błąd, można zamknąć .