Rozwiąż rekurencję wykorzystując funkcje tworzące

[elc09]

Mam taką rekurencję
\(\displaystyle{ a_{n}=\begin{cases} 0 &\text{dla } n<0 &\ 5a_{n-1}-4a_{n-2} + 2^n &\text{dla } n \ge 0 \end{cases}}\)
Z tego wyszła mi taka funkcja tworząca.
\(\displaystyle{ G(x)=\frac{1}{(1-2x)(1- \frac{1}{4x})(1-x)}}\)
Do tego momentu rozumiem to zadanie nie wiem co mam robić dalej.Mógłby mnie ktoś naprowadzić.

[Mariusz M]

Dalej to rozłóż na sumę ułamków postaci

\(\displaystyle{ \frac{A_{j}}{\left( 1-a_{j}x\right)^{k} }}\)

ale ja bym sprawdził czy aby na pewno dobrze wyznaczyłeś funkcję tworzącą

Ten rozkład na sumę ułamków jest po to abyś łatwiej rozwinął funkcję w szereg
korzystając z szeregu geometrycznego i jego pochodnych bądź z dwumianu Newtona

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

\(\displaystyle{ G\left( x\right)= \sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=\sum_{n=2}^{ \infty }{5a_{n-1}x^{n}}-\sum_{n=2}^{ \infty }{4a_{n-2}x^{n}}+\sum_{n=2}^{ \infty }{2^{n}x^{n}}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-a_{1}x-a_{0}=5x\left( \sum_{n=2}^{ \infty }a_{n-1}x^{n-1} \right)-4x^2\left( \sum_{n=2}^{ \infty }{a_{n-2}x^{n-2}} \right)+ \frac{4x^2}{1-2x}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-a_{1}x-a_{0}=5x\left( \sum_{n=1}^{ \infty }a_{n}x^{n} \right)-4x^2\left( \sum_{n=0}^{ \infty }{a_{n}x^{n}} \right)+ \frac{4x^2}{1-2x}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-a_{1}x-a_{0}=5x\left( \sum_{n=0}^{ \infty }a_{n}x^{n} -a_{0}\right)-4x^2\left( \sum_{n=0}^{ \infty }{a_{n}x^{n}} \right)+ \frac{4x^2}{1-2x}\\
G\left( x\right)-a_{1}x-a_{0}=5x\left( G\left( x\right)-a_{0} \right)-4x^2G\left( x\right)+\frac{4x^2}{1-2x}\\
G\left( x\right)\left( 1-5x+4x^2\right)=\left( a_{1}-5a_{0}\right)x+a_{0}+\frac{4x^2}{1-2x}\\
G\left( x\right)= \frac{\left( \left( a_{1}-5a_{0}\right)x+a_{0}\right)\left( 1-2x\right)+4x^2 }{\left( 1-x\right)\left( 1-4x\right)\left( 1-2x\right) } \\}\)

[elc09]

Faktycznie miałem błąd, moja funkcja tworząca wyszła z takiego sposobu
\(\displaystyle{ G(x)= \sum_{n=0}^{ \infty }a _{n}x^n=a_{0}x^0+a_{1}x^1 + \sum_{n=2}^{\infty} a_{n}x^n}\)
pierwsze wyrazy ciągu
\(\displaystyle{ a_{0} = 1,
a_{1} = 7}\)
dalej:
\(\displaystyle{ G(x) = 1 + 7x + \sum_{n=2}^{\infty} (5a_{n-1} -4a_{n-2}+2^n)x^n}\)
następnie rozdzielam sumę
\(\displaystyle{ G(x) = 1+ 7 + 5x\sum_{n=2}^{\infty} (a_{n-1}x^n-1) -4x^2\sum_{n=2}^{\infty} (a_{n-2}x^{n-2}) + \sum_{n=0}^{\infty}2^nx^n \\
G(x) = 1+ 7 + 5x\sum_{n=1}^{\infty} (a_{n}x^n) -4x^2\sum_{n=0}^{\infty} (a_{n}x^{n}) + \sum_{n=2}^{\infty}2^nx^n}\)
[/latex]
\(\displaystyle{ G(x) = 1+ 7x +5x(G(x) - 1)-4x^2G(x) + \frac{4x^2}{1-2x} \\
G(x) - 5xG(x) + 4x^2G(x)=1+7x -5x + \frac{4x^2}{1-2x}}\)
to daje nam
\(\displaystyle{ G(x)(4x^2 - 5x + 1)=\frac{1}{1-2x}
\newline
G(x)(1-4x)(1-x) = \frac{1}{1-2x}
\newline
G(x)=\frac{1}{(1-x)(1-4x)(1-2x)}}\)
następnie:
\(\displaystyle{ \frac{1}{(1-x)(1-4x)(1-2x)} = \frac{A}{1-x} + \frac{B}{1-4x} + \frac{C}{1-2x}
\\\\
1=A(1-4x)(1-2x)+B(1-x)(1-2x)+C(1-x)(1-4x)}\)
po wymnożeniu
\(\displaystyle{ 1=A(8x^2-6x+1)+B(2x^2-3x+1)+C(4x^2-5x+1)
\newline}\)
\(\displaystyle{ \begin{cases} 1 = A+B+C\\ 0 = -6A - 3B - 5C \\ 0 = 8A+ 2B+4C \end{cases}}\)
z układu wychodzi
\(\displaystyle{ A= \frac{1}{3}
\\\\
B=\frac{8}{3}
\\\\
C= -2}\)
I znowu mam tutaj problem ;/ Co z tym zrobić?

[Mariusz M]

Skorzystaj z szeregu geometrycznego albo dwumianu Newtona

Widzę że dodałeś warunki początkowe , dzięki temu dostaniesz jeden ciąg

[elc09]

Wyszło mi coś takiego
\(\displaystyle{ G(x) = \frac{1}{3}\sum_{n=0}^{\infty}1^nx^n + \frac{8}{3}\sum_{n=0}^{\infty}4^nx^n -2\sum_{n=0}^{\infty}2^nx^n
\newline
a_{n}= \frac{1}{3} \cdot 1^n + \frac{8}{3} \cdot 4^n -2 \cdot 2^n
\newline
a_{n}= \frac{1}{3} + \frac{8}{3} \cdot 4^n -2 \cdot 2^n}\)

[popiszsieplay]

Mam pytanie. A nawet dwa

1) W jaki sposób przeszedłeś z tego \(\displaystyle{ G(x) = \frac{1}{3} \sum_{n=0}^{\infty} 1^nx^n + \frac{8}{3} \sum_{n=0}^{\infty} 4^nx^n - 2 \sum_{n==0}^{\infty}2^nx^n}\)
do wzoru na \(\displaystyle{ a_n}\)?

Jak dokładnie to tego doszlo, czy to się jakoś "fachowo" nazywa, użyłeś jakiegoś wzoru?

2) I drugie:
Jak z \(\displaystyle{ \sum_{n=0}^{\infty} 2^nx^n}\) (przy początkowych obliczeniach \(\displaystyle{ G(x)}\))
otrzymałeś \(\displaystyle{ \frac{4x^2}{1-2x}}\)? A raczej, skąd wziął się ten niestandardowy mianownik?

Dziękuję i pozdrawiam

Ps. Mam nadzieję, że wątek nie umarł...