Witam, muszę rozwiązać poniższą rekurencję funkcjami tworzącymi.
\(\displaystyle{ g_{0} =1\\
g_{1} =1\\
g_{n}= g_{n-1}+2 \cdot g_{n-1} + (-1)^{n}}\)
stworzyłem uniwersalną zależność i rozszerzam ciąg \(\displaystyle{ g_{n}}\) na ujemne n których wartości są równe 0:
\(\displaystyle{ \\ g_{n}= g_{n-1}+2 \cdot g_{n-1} + (-1)^{n}+\omega (n=1)}\)
mnożę obydwie strony przez \(\displaystyle{ z^{n}}\)
\(\displaystyle{ \\ z^{n} \cdot g_{n}= z^{n} \cdot g_{n-1}+z^{n} \cdot 2 \cdot g_{n-1} +z^{n} \cdot (-1)^{n}+z^{n} \cdot \omega (n=1)\\}\)
i sumuję po całkowitych
\(\displaystyle{ G(z)=z \cdot G(z)+ z^{2} \cdot G(z) + z + \sum_{n \in Z}^{}(-z)^{n}}\)
Ostatni szereg jest rozbieżny Ktoś może wie jak to obejść?
Funkcje tworzące - rekurencja niejednorodna
-
garrincha94
- Użytkownik
- Posty: 30
- Rejestracja: 10 lip 2014, o 19:56
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 11 razy
- Pomógł: 1 raz
-
Mariusz M
- Użytkownik
- Posty: 6909
- Rejestracja: 25 wrz 2007, o 01:03
- Płeć: Mężczyzna
- Lokalizacja: 53°02'N 18°35'E
- Podziękował: 2 razy
- Pomógł: 1246 razy
Funkcje tworzące - rekurencja niejednorodna
\(\displaystyle{ g_{0} =1\\
g_{1} =1\\
g_{n}= g_{n-1}+2 \cdot g_{n-1} + (-1)^{n}}\)
Ja rozwiązywałbym to równanie w ten sposób
\(\displaystyle{ G\left( x\right)= \sum_{n=0}^{ \infty }{g_{n}x^{n}}\\
\sum_{n=2}^{ \infty }g_{n}x^{n}= \sum_{n=2}^{ \infty }g_{n-1}x^{n}+2 \sum_{n=2}^{ \infty }g_{n-2}x^{n}+ \sum_{n=2}^{ \infty }\left( -1\right)^n x^{n}\\
\sum_{n=2}^{ \infty }g_{n}x^{n}= x\sum_{n=2}^{ \infty }g_{n-1}x^{n-1}+2x^2 \sum_{n=2}^{ \infty }g_{n-2}x^{n-2}+\frac{x^2}{1+x}\\
\sum_{n=0}^{ \infty }g_{n}x^{n}-x-1=x\sum_{n=1}^{ \infty }g_{n}x^{n}+2x^2 \sum_{n=0}^{ \infty }g_{n}x^{n}+\frac{x^2}{1+x}\\
\sum_{n=0}^{ \infty }g_{n}x^{n}-x-1=x\left( \sum_{n=0}^{ \infty }g_{n}x^{n}-1\right) +2x^2 \sum_{n=0}^{ \infty }g_{n}x^{n}+\frac{x^2}{1+x}\\
G\left( x\right)-x-1=x\left( G\left( x\right)-1 \right)+2x^2G\left( x\right)+\frac{x^2}{1+x}\\
G\left( x\right)-x-1=xG\left( x\right)-x+2x^2G\left( x\right)+\frac{x^2}{1+x}\\
\left( 1-x-2x^2\right)G\left( x\right)=1+\frac{x^2}{1+x}\\
\left( 1-x-2x^2\right)G\left( x\right)=\frac{x^2+x+1}{1+x}\\
G\left( x\right)= \frac{x^2+x+1}{\left( 1+x\right)\left( 1-x-2x^2\right) }\\
G\left( x\right)=\frac{x^2+x+1}{\left( 1-2x\right)\left( 1+x\right)^2 }\\
\frac{x^2+x+1}{\left( 1-2x\right)\left( 1+x\right)^2 }= \frac{A}{1-2x}+\frac{B}{1+x}+\frac{C}{\left( 1+x\right)^2 }\\
A\left( 1+2x+x^2\right)+B\left( 1-x-2x^2\right)+C\left( 1-2x\right)=x^2+x+1\\
\begin{cases} A+B+C=1 \\ 2A-B-2C=1\\A-2B=1 \end{cases}\\}\)
\(\displaystyle{ \begin{bmatrix} 1&1&1 \\ 2&-1&-2\\1&-2&0 \end{bmatrix} \\
w_2-2w_1\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\1&-2&0 \end{bmatrix} \\
w_3-w_1\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&-3&-1 \end{bmatrix} \\
w_3-w_{2}\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \\}\)
\(\displaystyle{ \begin{bmatrix} 1&1&1 \\ 2&-1&-2\\1&-2&0 \end{bmatrix}= \begin{bmatrix} 1&0&0 \\ 2&1&0\\1&1&1 \end{bmatrix} \cdot \begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \\
\begin{bmatrix} 1&0&0 \\ 2&1&0\\1&1&1 \end{bmatrix} \cdot \left(\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \cdot \begin{bmatrix} A \\ B\\C \end{bmatrix}\right)=\begin{bmatrix} 1 \\ 1\\1 \end{bmatrix} \\
\begin{bmatrix} 1&0&0 \\ 2&1&0\\1&1&1 \end{bmatrix} \cdot \begin{bmatrix} y_{1}\\ y_{2}\\y_{3} \end{bmatrix}= \begin{bmatrix} 1 \\ 1\\1 \end{bmatrix} \\
y_{1}=1\\
y_{2}=-1\\
y_{3}=1\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \cdot \begin{bmatrix} A \\ B\\C \end{bmatrix}= \begin{bmatrix} 1 \\ -1\\1 \end{bmatrix} \\
C=\frac{3}{9}\\
B=-\frac{1}{9}\\
A=\frac{7}{9}\\}\)
\(\displaystyle{ G\left( x\right)=\frac{7}{9} \cdot \frac{1}{1-2x}-\frac{1}{9} \cdot \frac{1}{1+x} +\frac{3}{9} \cdot \frac{1}{\left( 1+x\right)^2 }}\)
Teraz można skorzystać albo z dwumianu Newtona albo z różniczkowania szeregu geometrycznego
\(\displaystyle{ \sum_{n=0}^{ \infty }{\left( -1\right)^{n}x^{n} }=\frac{1}{1+x}\\
\frac{ \mbox{d}}{ \mbox{d}x }\left(\sum_{n=0}^{ \infty }{\left( -1\right)^{n}x^{n} }\right)=
\sum_{n=0}^{ \infty }{n\left( -1\right)^{n}x^{n-1} }=\\
\sum_{n=1}^{ \infty }{n\left( -1\right)^{n}x^{n-1} }=\\
\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n+1}x^{n} }=\\
=-\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n}x^{n} }=\\
\frac{ \mbox{d}}{ \mbox{d}x }\left( \frac{1}{\left( x+1\right) } \right)=-\frac{1}{\left( 1+x\right)^2 } \\
\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n}x^{n} }=\frac{1}{\left( 1+x\right)^2 }\\}\)
\(\displaystyle{ G\left( x\right)=\frac{7}{9} \sum_{n=0}^{ \infty }{2^nx^n}-\frac{1}{9} \sum_{n=0}^{ \infty }{\left( -1\right)^nx^n }+\frac{3}{9}\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n}x^{n} }\\
G\left( x\right)=\frac{7}{9} \sum_{n=0}^{ \infty }{2^nx^n}+\frac{1}{9} \sum_{n=0}^{ \infty }{\left( 3n+2\right)\left( -1\right)^{n}x^n } \\
g_{n}=\frac{7}{9} \cdot 2^{n}+ \frac{1}{9} \cdot \left( 3n+2\right)\left( -1\right)^n\\}\)
g_{1} =1\\
g_{n}= g_{n-1}+2 \cdot g_{n-1} + (-1)^{n}}\)
Ja rozwiązywałbym to równanie w ten sposób
\(\displaystyle{ G\left( x\right)= \sum_{n=0}^{ \infty }{g_{n}x^{n}}\\
\sum_{n=2}^{ \infty }g_{n}x^{n}= \sum_{n=2}^{ \infty }g_{n-1}x^{n}+2 \sum_{n=2}^{ \infty }g_{n-2}x^{n}+ \sum_{n=2}^{ \infty }\left( -1\right)^n x^{n}\\
\sum_{n=2}^{ \infty }g_{n}x^{n}= x\sum_{n=2}^{ \infty }g_{n-1}x^{n-1}+2x^2 \sum_{n=2}^{ \infty }g_{n-2}x^{n-2}+\frac{x^2}{1+x}\\
\sum_{n=0}^{ \infty }g_{n}x^{n}-x-1=x\sum_{n=1}^{ \infty }g_{n}x^{n}+2x^2 \sum_{n=0}^{ \infty }g_{n}x^{n}+\frac{x^2}{1+x}\\
\sum_{n=0}^{ \infty }g_{n}x^{n}-x-1=x\left( \sum_{n=0}^{ \infty }g_{n}x^{n}-1\right) +2x^2 \sum_{n=0}^{ \infty }g_{n}x^{n}+\frac{x^2}{1+x}\\
G\left( x\right)-x-1=x\left( G\left( x\right)-1 \right)+2x^2G\left( x\right)+\frac{x^2}{1+x}\\
G\left( x\right)-x-1=xG\left( x\right)-x+2x^2G\left( x\right)+\frac{x^2}{1+x}\\
\left( 1-x-2x^2\right)G\left( x\right)=1+\frac{x^2}{1+x}\\
\left( 1-x-2x^2\right)G\left( x\right)=\frac{x^2+x+1}{1+x}\\
G\left( x\right)= \frac{x^2+x+1}{\left( 1+x\right)\left( 1-x-2x^2\right) }\\
G\left( x\right)=\frac{x^2+x+1}{\left( 1-2x\right)\left( 1+x\right)^2 }\\
\frac{x^2+x+1}{\left( 1-2x\right)\left( 1+x\right)^2 }= \frac{A}{1-2x}+\frac{B}{1+x}+\frac{C}{\left( 1+x\right)^2 }\\
A\left( 1+2x+x^2\right)+B\left( 1-x-2x^2\right)+C\left( 1-2x\right)=x^2+x+1\\
\begin{cases} A+B+C=1 \\ 2A-B-2C=1\\A-2B=1 \end{cases}\\}\)
\(\displaystyle{ \begin{bmatrix} 1&1&1 \\ 2&-1&-2\\1&-2&0 \end{bmatrix} \\
w_2-2w_1\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\1&-2&0 \end{bmatrix} \\
w_3-w_1\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&-3&-1 \end{bmatrix} \\
w_3-w_{2}\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \\}\)
\(\displaystyle{ \begin{bmatrix} 1&1&1 \\ 2&-1&-2\\1&-2&0 \end{bmatrix}= \begin{bmatrix} 1&0&0 \\ 2&1&0\\1&1&1 \end{bmatrix} \cdot \begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \\
\begin{bmatrix} 1&0&0 \\ 2&1&0\\1&1&1 \end{bmatrix} \cdot \left(\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \cdot \begin{bmatrix} A \\ B\\C \end{bmatrix}\right)=\begin{bmatrix} 1 \\ 1\\1 \end{bmatrix} \\
\begin{bmatrix} 1&0&0 \\ 2&1&0\\1&1&1 \end{bmatrix} \cdot \begin{bmatrix} y_{1}\\ y_{2}\\y_{3} \end{bmatrix}= \begin{bmatrix} 1 \\ 1\\1 \end{bmatrix} \\
y_{1}=1\\
y_{2}=-1\\
y_{3}=1\\
\begin{bmatrix} 1&1&1 \\ 0&-3&-4\\0&0&3 \end{bmatrix} \cdot \begin{bmatrix} A \\ B\\C \end{bmatrix}= \begin{bmatrix} 1 \\ -1\\1 \end{bmatrix} \\
C=\frac{3}{9}\\
B=-\frac{1}{9}\\
A=\frac{7}{9}\\}\)
\(\displaystyle{ G\left( x\right)=\frac{7}{9} \cdot \frac{1}{1-2x}-\frac{1}{9} \cdot \frac{1}{1+x} +\frac{3}{9} \cdot \frac{1}{\left( 1+x\right)^2 }}\)
Teraz można skorzystać albo z dwumianu Newtona albo z różniczkowania szeregu geometrycznego
\(\displaystyle{ \sum_{n=0}^{ \infty }{\left( -1\right)^{n}x^{n} }=\frac{1}{1+x}\\
\frac{ \mbox{d}}{ \mbox{d}x }\left(\sum_{n=0}^{ \infty }{\left( -1\right)^{n}x^{n} }\right)=
\sum_{n=0}^{ \infty }{n\left( -1\right)^{n}x^{n-1} }=\\
\sum_{n=1}^{ \infty }{n\left( -1\right)^{n}x^{n-1} }=\\
\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n+1}x^{n} }=\\
=-\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n}x^{n} }=\\
\frac{ \mbox{d}}{ \mbox{d}x }\left( \frac{1}{\left( x+1\right) } \right)=-\frac{1}{\left( 1+x\right)^2 } \\
\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n}x^{n} }=\frac{1}{\left( 1+x\right)^2 }\\}\)
\(\displaystyle{ G\left( x\right)=\frac{7}{9} \sum_{n=0}^{ \infty }{2^nx^n}-\frac{1}{9} \sum_{n=0}^{ \infty }{\left( -1\right)^nx^n }+\frac{3}{9}\sum_{n=0}^{ \infty }{\left(n+1\right)\left( -1\right)^{n}x^{n} }\\
G\left( x\right)=\frac{7}{9} \sum_{n=0}^{ \infty }{2^nx^n}+\frac{1}{9} \sum_{n=0}^{ \infty }{\left( 3n+2\right)\left( -1\right)^{n}x^n } \\
g_{n}=\frac{7}{9} \cdot 2^{n}+ \frac{1}{9} \cdot \left( 3n+2\right)\left( -1\right)^n\\}\)