Funkcja tworząca

[ebasse]

Proszę o pomoc.
Używając funkcji generujących znajdź rozwiązanie schematu rekurencyjnego:

\(\displaystyle{ a_{n} = a_{n-1} + 4a_{n-2} + 3(-2)^{n-3}\ \ \ \ \ n \ge 2 \ \ \ \ \ \ a_0 = 1\ \ \ a_1 = 2}\)

[Crizz]

Pokaż, jak liczysz funkcję tworzącą, podpowiemy.

[ebasse]

\(\displaystyle{ a_{n} = a_{n-1} + 4a_{n-2} + 3(-2)^{n-3}\ \ \ \ \ n \ge 2 \ \ \ \ \ \ a_0 = 1\ \ \ a_1 = 2\\
a_{n} = a_{n-1} + 4a_{n-2} + 3(-2)^{n-3} [n \ge 2] + \alpha [n=0] + \beta [n=1]\\\\


0: a_{0} = a_{-1} + 4 a_{-2} + \alpha \ \ \ \ \ \alpha =1\\
1: a_{1} = a_{0} + 4a _{-1} \ \ \ \ \ \beta =1\\

\sum_{}^{} a_{n} z^{n} = \sum_{}^{}a_{n-1}z^{n} + \sum_{}^{}4a_{n-2}z^{n} + \sum_{}^{}3(-2)^{n-3} [n \ge 2]z^{n} + \sum_{}^{} [n=0] z^{n}+ \sum_{}^{} [n=1]z^{n}\\

A(z)= z A(z) + 4 z^{2} A(z) + 3 \frac{- \frac{ z^{2} }{2} }{1+2z} + 1 + z\\
A(z)(1-z-4z^{2} )= \frac{ \frac{-3z ^{2} }{2}+1+2z+z+2z ^{2} }{1+2z}\\
A(z)= \frac{ \frac{z ^{2} }{2}+3z+1 }{(1+2z)(1-z-4z ^{2}) }\\
A(z)= \frac{ \frac{z ^{2} }{2}+3z+1 }{(1+2z)( \frac{8z}{1- \sqrt{17} }-1)( \frac{8z}{1+ \sqrt{17} }-1)}\\

a_{n}=(-2) ^{n} \cdot A + ( \frac{8}{1- \sqrt{17} } )^{n} \cdot B + ( \frac{8}{1+ \sqrt{17} } )^{n} \cdot C\\

1 = a_{0} = A + B + C\\
2=a_{1}=-2A+( \frac{8}{1- \sqrt{17} } ) \cdot B+ ( \frac{8}{1+ \sqrt{17} } ) \cdot C\\
4,5=a_{2}=4A+( \frac{8}{1- \sqrt{17} } )^{2} \cdot B+ ( \frac{8}{1+ \sqrt{17} } )^{2} \cdot C\\}\)

Dotąd doszedłem.
Nie wiem czy jest to dobrze, a nawet jak tak to nie wiem co dalej. Prosze o sprawdzenie i dalszą pomoc

[Crizz]

Hmmm... wygląda OK (nie sprawdzałem, czy dobrze przekształcony mianownik ). Masz dwa równania i trzy niewiadome, więc dołóż trzecie równanie.

[ebasse]

Dołożyłem trzecie równanie, ale w tym momencie to max moich możliwości, nie wiem jak to dalej liczyć. Nie umiem

[Crizz]

Układ równań paskudny, ale nic się na to nie poradzi. Polecam wzory Cramera.

Alternatywnie, zawsze możesz rozłożyć otrzymany wzór na funkcję tworzącą na ułamki proste. To chyba prostsza metoda.

[ebasse]

No dobrze tylko ja nie wiem jak. Ale dzieki.

[abc666]

Jakby nie liczyć wyniki wychodzą strasznie brzydkie.

[Crizz]

No dobrze tylko ja nie wiem jak.

\(\displaystyle{ \frac{ \frac{z ^{2} }{2}+3z+1 }{ \left( 1+2z \right) \left( \frac{8z}{1- \sqrt{17} }-1 \right) \left( \frac{8z}{1+ \sqrt{17} }-1 \right) } \equiv \frac{A}{1+2z}+\frac{B}{\frac{8z}{1- \sqrt{17} }-1}+\frac{C}{\frac{8z}{1+ \sqrt{17} }-1}}\)
i teraz pomnóż obie strony przez mianownik lewej strony, a następnie porównaj współczynniki przy poszczególnych potęgach wielomianu po obu stronach. Tak czy siak - układ równań do rozwiązania.