Witam, mam problem z rozwiązaniem następującej rekursji:
\(\displaystyle{ a_{n+1} = n\cdot a_{n} + 2}\)
Wiem, że trzeba skorzystać z funkcji tworzących, czyli:
\(\displaystyle{ \sum_{n\ge0} a_{n+1} x^{n+1} = \sum_{n\ge0} n \cdot a_{n} \cdot x^{n} +\frac{2}{1-x}}\)
Jakoś nie umiem sobie poradzić z sumą z \(\displaystyle{ n\cdot a_{n}}\), jak to rozłożyć ?
Rozwiąż rekursję.
-
sardom
- Użytkownik
- Posty: 40
- Rejestracja: 25 lis 2012, o 10:06
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
Rozwiąż rekursję.
Nie ogarniam. Chodzi o takie coś? Bo nie widzę tego
\(\displaystyle{ \sum_{n\ge0} a_{n+1}\frac{x^{n+1}}{(n+1)!} = \sum_{n\ge0} \frac{n a_{n} x^{n+1}}{(n+1)!} +2\sum_{n\ge0}\frac{x^{n+1}}{(n+1)!}}\)
\(\displaystyle{ \sum_{n\ge0} a_{n+1}\frac{x^{n+1}}{(n+1)!} = \sum_{n\ge0} \frac{n a_{n} x^{n+1}}{(n+1)!} +2\sum_{n\ge0}\frac{x^{n+1}}{(n+1)!}}\)
-
Mariusz M
- Użytkownik
- Posty: 6908
- 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
Rozwiąż rekursję.
Gdybyś nie skorzystał z funkcji tworzącej dającej exponentę dla ciągu jedynek
tylko z funkcji tworzącej dającej szereg geometryczny dla ciągu jedynek
to musiałbyś rozwiązać równanie różniczkowe
Sumę \(\displaystyle{ \sum_{n\ge0} n \cdot a_{n} \cdot x^{n}}\) możesz też otrzymać różniczkując szereg
Jytug, a czy musi podawać jednoznaczne rozwiązanie ?
\(\displaystyle{ a_{n+1} = n\cdot a_{n} + 2\\
a_{n}=\left( n-1\right)a_{n-1}+2 \qquad n\ge 1\\
A\left( x\right)= \sum_{n=0}^{ \infty }{a_{n}x^n}\\
\sum_{n=1}^{ \infty }{a_{n}x^{n}}=\sum_{n=1}^{\infty}{\left( n-1\right)a_{n-1}x^{n} }+\sum_{n=1}^{ \infty }{2x^n}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-a_{0}=\sum_{n=0}^{\infty}{na_{n}x^{n+1}}+\frac{2x}{1-x}\\
A\left( x\right)-a_{0}=\sum_{n=0}^{ \infty }{\left( n+2\right)a_{n}x^{n+1} }-\sum_{n=0}^{\infty}{2a_{n}x^{n+1}}+\frac{2x}{1-x}\\
A\left( x\right)-a_{0}=\left( x^2A\left( x\right) \right)^{\prime}-2xA\left( x\right)+\frac{2x}{1-x}\\
-a_{0}-\frac{2x}{1-x}=2xA\left( x\right)+x^2A^{\prime}\left( x\right)-2xA\left( x\right)-A\left( x\right)\\
x^2 \frac{ \mbox{d}A}{dx}-A=-a_{0}-\frac{2x}{1-x}\\
x^2 \frac{ \mbox{d}A}{dx}-A=0\\
x^2 \frac{ \mbox{d}A}{dx}=A\\
\frac{ \mbox{d}A}{A}=\frac{ \mbox{d}x }{x^2}\\
\ln{\left| A\right| }=-\frac{1}{x}+C\\
A=Ce^{-\frac{1}{x}}\\
A=C\left( x\right)e^{-\frac{1}{x}}\\
x^2 \left( C^{\prime}\left( x\right)e^{-\frac{1}{x}}+\frac{1}{x^2}C\left( x\right) e^{\frac{1}{x}} \right) -C\left( x\right)e^{ \frac{1}{x} } =-a_{0}-\frac{2x}{1-x}\\
x^2C^{\prime}\left( x\right)e^{- \frac{1}{x} }=-a_{0}-\frac{2x}{1-x}\\
C^{\prime}\left( x\right)=-\frac{a_{0}}{x^2}e^{\frac{1}{x}}-\frac{2x}{x^2\left( 1-x\right) }e^{\frac{1}{x}} \\
\int{\left(-\frac{a_{0}}{x^2}e^{\frac{1}{x}}-\frac{2x}{x^2\left( 1-x\right) }e^{\frac{1}{x}} \right) \mbox{d}x }\\
t=\frac{1}{x}\\
\mbox{d}t=-\frac{1}{x^2} \mbox{d}x \\
\int{a_{0}e^{t}+\frac{\frac{2}{t}}{1-\frac{1}{t}}e^{t} \mbox{d}t}=\\
\int{a_{0}e^{t}+\frac{2}{t-1}e^{t} \mbox{d}t}\\
=a_{0}e^{t}+2e\rm{Ei}{\left( t-1\right) }+C_{1}\\}\)
\(\displaystyle{ C\left( x\right)=a_{0}e^{\frac{1}{x}}+2e\rm{Ei}{\left( \frac{1}{x}-1\right) }+C_{1}\\
A\left( x\right)=\left(a_{0}e^{\frac{1}{x}}+2e\rm{Ei}{\left( \frac{1}{x}-1\right) }+C_{1} \right)e^{-\frac{1}{x}} \\
A\left( x\right)=a_{0}+2e^{\left( 1-\frac{1}{x}\right) }\rm{Ei}{\left( \frac{1}{x}-1\right)}+C_{1}e^{-\frac{1}{x}}\\}\)
Teraz pozostaje tylko rozwinąć tę funkcję w szereg w otoczeniu zera
Wykładniczą funkcją tworzącą to będzie tak
\(\displaystyle{ a_{n+1} = n\cdot a_{n} + 2\\
a_{n}=\left( n-1\right)a_{n-1}+2 \qquad n\ge 1\\
A\left( x\right)= \sum_{n=0}^{ \infty }{ \frac{a_{n}}{n!}x^{n} }\\
\sum_{n=1}^{ \infty }{\frac{a_{n}}{n!}x^{n}}=\sum_{n=1}^{ \infty }{\frac{\left( n-1\right)a_{n-1} }{n!}x^{n}}+ \sum_{n=1}^{ \infty }{\frac{2}{n!}x^n}\\
A\left( x\right)-a_{0}=\sum_{n=1}^{ \infty }{\frac{a_{n-1}}{\left( n-1\right)! }x^{n}}- \sum_{n=1}^{ \infty }{ \frac{a_{n-1}}{n!}x^{n} }+2e^{x}-2\\
A\left( x\right)-a_{0}=x\sum_{n=0}^{ \infty }{\frac{a_{n}}{n!}x^{n}}-\sum_{n=0}^{ \infty }{ \frac{a_{n}}{n!} \cdot \frac{x^{n+1}}{\left( n+1\right) } }+2e^{x}-2\\
A\left( x\right)-a_{0}=xA\left( x\right)- \int{A\left( x\right) \mbox{d}x }+2e^{x}-2\\
-2e^{x}+2-a_{0}=A\left( x\right)\left( x-1\right)-\int{A\left( x\right) \mbox{d}x }\\
P\left( x\right)=\int{A\left( x\right) \mbox{d}x }\\
-2e^{x}+2-a_{0}=\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x } -P}\)
Znów mamy równanie różniczkowe liniowe pierwszego rzędu
\(\displaystyle{ -2e^{x}+2-a_{0}=\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x } -P\\
\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x } -P=0\\
\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x }=P\\
\frac{ \mbox{d}P}{P}= \frac{ \mbox{d}x }{x-1}\\
\ln{\left|P\right| }=\ln{\left| x-1\right| }+C\\
P=C\left( x-1\right)\\
P\left( x\right)=C\left( x\right)\left( x-1\right)\\
\left( x-1\right)\left( C^{\prime}\left( x\right)\left( x-1\right) +C\left( x\right) \right)-C\left( x\right)\left( x-1\right)=-2e^{x}+2-a_{0}\\
\left( x-1\right)^2C^{\prime}\left(x \right)=-2e^{x}+2-a_{0}\\
C^{\prime}\left(x \right)=\frac{-2e^{x}}{\left( x-1\right)^2 }+\frac{2-a_{0}}{\left( x-1\right)^2 }\\
C\left( x\right)=\frac{2e^{x}}{x-1}-2\int{\frac{e^{x}}{x-1} \mbox{d}x}+ \frac{a_{0}-2}{x-1}\\
C\left( x\right)=\frac{2e^{x}}{x-1}-2e\rm{Ei}{\left( x-1\right) }+ \frac{a_{0}-2}{x-1}+C_{1}\\
P\left( x\right)=2e^{x}+a_{0}-2-2e\left( x-1\right) \rm{Ei}{\left( x-1\right) }+C_{1}\left( x-1\right) \\
A\left( x\right)= \frac{ \mbox{d}}{ \mbox{d}x }P\left( x\right)\\
A\left( x\right)=2e^{x}-2e\left(\rm{Ei}{\left( x-1\right) }+\left( x-1\right) \cdot \frac{e^{x-1}}{x-1} \right)+C_{1}\\
A\left( x\right)=2e^{x}-2e\rm{Ei}{\left( x-1\right) }-2e^{x}+C_{1}\\
A\left( x\right)=-2e\rm{Ei}{\left( x-1\right) }+C_{1}}\)
Jak policzysz kilka pochodnych w zerze to zauważysz że spełniają one zależność rekurencyjną
Ciekawe jak znaleźć wzór ogólny na współczynniki szeregu będącego rozwinięciem tej funkcji tworzącej
Gdyby przyjąć \(\displaystyle{ C_{1}=0}\) w tej geometrycznej funkcji tworzącej to po obliczeniu granicy z kolejnych pochodnych to współczynniki spełniają zależność rekurencyjną
Bez tego założenia trzeba brać granice prawostronne
tylko z funkcji tworzącej dającej szereg geometryczny dla ciągu jedynek
to musiałbyś rozwiązać równanie różniczkowe
Sumę \(\displaystyle{ \sum_{n\ge0} n \cdot a_{n} \cdot x^{n}}\) możesz też otrzymać różniczkując szereg
Jytug, a czy musi podawać jednoznaczne rozwiązanie ?
\(\displaystyle{ a_{n+1} = n\cdot a_{n} + 2\\
a_{n}=\left( n-1\right)a_{n-1}+2 \qquad n\ge 1\\
A\left( x\right)= \sum_{n=0}^{ \infty }{a_{n}x^n}\\
\sum_{n=1}^{ \infty }{a_{n}x^{n}}=\sum_{n=1}^{\infty}{\left( n-1\right)a_{n-1}x^{n} }+\sum_{n=1}^{ \infty }{2x^n}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-a_{0}=\sum_{n=0}^{\infty}{na_{n}x^{n+1}}+\frac{2x}{1-x}\\
A\left( x\right)-a_{0}=\sum_{n=0}^{ \infty }{\left( n+2\right)a_{n}x^{n+1} }-\sum_{n=0}^{\infty}{2a_{n}x^{n+1}}+\frac{2x}{1-x}\\
A\left( x\right)-a_{0}=\left( x^2A\left( x\right) \right)^{\prime}-2xA\left( x\right)+\frac{2x}{1-x}\\
-a_{0}-\frac{2x}{1-x}=2xA\left( x\right)+x^2A^{\prime}\left( x\right)-2xA\left( x\right)-A\left( x\right)\\
x^2 \frac{ \mbox{d}A}{dx}-A=-a_{0}-\frac{2x}{1-x}\\
x^2 \frac{ \mbox{d}A}{dx}-A=0\\
x^2 \frac{ \mbox{d}A}{dx}=A\\
\frac{ \mbox{d}A}{A}=\frac{ \mbox{d}x }{x^2}\\
\ln{\left| A\right| }=-\frac{1}{x}+C\\
A=Ce^{-\frac{1}{x}}\\
A=C\left( x\right)e^{-\frac{1}{x}}\\
x^2 \left( C^{\prime}\left( x\right)e^{-\frac{1}{x}}+\frac{1}{x^2}C\left( x\right) e^{\frac{1}{x}} \right) -C\left( x\right)e^{ \frac{1}{x} } =-a_{0}-\frac{2x}{1-x}\\
x^2C^{\prime}\left( x\right)e^{- \frac{1}{x} }=-a_{0}-\frac{2x}{1-x}\\
C^{\prime}\left( x\right)=-\frac{a_{0}}{x^2}e^{\frac{1}{x}}-\frac{2x}{x^2\left( 1-x\right) }e^{\frac{1}{x}} \\
\int{\left(-\frac{a_{0}}{x^2}e^{\frac{1}{x}}-\frac{2x}{x^2\left( 1-x\right) }e^{\frac{1}{x}} \right) \mbox{d}x }\\
t=\frac{1}{x}\\
\mbox{d}t=-\frac{1}{x^2} \mbox{d}x \\
\int{a_{0}e^{t}+\frac{\frac{2}{t}}{1-\frac{1}{t}}e^{t} \mbox{d}t}=\\
\int{a_{0}e^{t}+\frac{2}{t-1}e^{t} \mbox{d}t}\\
=a_{0}e^{t}+2e\rm{Ei}{\left( t-1\right) }+C_{1}\\}\)
\(\displaystyle{ C\left( x\right)=a_{0}e^{\frac{1}{x}}+2e\rm{Ei}{\left( \frac{1}{x}-1\right) }+C_{1}\\
A\left( x\right)=\left(a_{0}e^{\frac{1}{x}}+2e\rm{Ei}{\left( \frac{1}{x}-1\right) }+C_{1} \right)e^{-\frac{1}{x}} \\
A\left( x\right)=a_{0}+2e^{\left( 1-\frac{1}{x}\right) }\rm{Ei}{\left( \frac{1}{x}-1\right)}+C_{1}e^{-\frac{1}{x}}\\}\)
Teraz pozostaje tylko rozwinąć tę funkcję w szereg w otoczeniu zera
Wykładniczą funkcją tworzącą to będzie tak
\(\displaystyle{ a_{n+1} = n\cdot a_{n} + 2\\
a_{n}=\left( n-1\right)a_{n-1}+2 \qquad n\ge 1\\
A\left( x\right)= \sum_{n=0}^{ \infty }{ \frac{a_{n}}{n!}x^{n} }\\
\sum_{n=1}^{ \infty }{\frac{a_{n}}{n!}x^{n}}=\sum_{n=1}^{ \infty }{\frac{\left( n-1\right)a_{n-1} }{n!}x^{n}}+ \sum_{n=1}^{ \infty }{\frac{2}{n!}x^n}\\
A\left( x\right)-a_{0}=\sum_{n=1}^{ \infty }{\frac{a_{n-1}}{\left( n-1\right)! }x^{n}}- \sum_{n=1}^{ \infty }{ \frac{a_{n-1}}{n!}x^{n} }+2e^{x}-2\\
A\left( x\right)-a_{0}=x\sum_{n=0}^{ \infty }{\frac{a_{n}}{n!}x^{n}}-\sum_{n=0}^{ \infty }{ \frac{a_{n}}{n!} \cdot \frac{x^{n+1}}{\left( n+1\right) } }+2e^{x}-2\\
A\left( x\right)-a_{0}=xA\left( x\right)- \int{A\left( x\right) \mbox{d}x }+2e^{x}-2\\
-2e^{x}+2-a_{0}=A\left( x\right)\left( x-1\right)-\int{A\left( x\right) \mbox{d}x }\\
P\left( x\right)=\int{A\left( x\right) \mbox{d}x }\\
-2e^{x}+2-a_{0}=\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x } -P}\)
Znów mamy równanie różniczkowe liniowe pierwszego rzędu
\(\displaystyle{ -2e^{x}+2-a_{0}=\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x } -P\\
\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x } -P=0\\
\left( x-1\right) \frac{ \mbox{d}P}{ \mbox{d}x }=P\\
\frac{ \mbox{d}P}{P}= \frac{ \mbox{d}x }{x-1}\\
\ln{\left|P\right| }=\ln{\left| x-1\right| }+C\\
P=C\left( x-1\right)\\
P\left( x\right)=C\left( x\right)\left( x-1\right)\\
\left( x-1\right)\left( C^{\prime}\left( x\right)\left( x-1\right) +C\left( x\right) \right)-C\left( x\right)\left( x-1\right)=-2e^{x}+2-a_{0}\\
\left( x-1\right)^2C^{\prime}\left(x \right)=-2e^{x}+2-a_{0}\\
C^{\prime}\left(x \right)=\frac{-2e^{x}}{\left( x-1\right)^2 }+\frac{2-a_{0}}{\left( x-1\right)^2 }\\
C\left( x\right)=\frac{2e^{x}}{x-1}-2\int{\frac{e^{x}}{x-1} \mbox{d}x}+ \frac{a_{0}-2}{x-1}\\
C\left( x\right)=\frac{2e^{x}}{x-1}-2e\rm{Ei}{\left( x-1\right) }+ \frac{a_{0}-2}{x-1}+C_{1}\\
P\left( x\right)=2e^{x}+a_{0}-2-2e\left( x-1\right) \rm{Ei}{\left( x-1\right) }+C_{1}\left( x-1\right) \\
A\left( x\right)= \frac{ \mbox{d}}{ \mbox{d}x }P\left( x\right)\\
A\left( x\right)=2e^{x}-2e\left(\rm{Ei}{\left( x-1\right) }+\left( x-1\right) \cdot \frac{e^{x-1}}{x-1} \right)+C_{1}\\
A\left( x\right)=2e^{x}-2e\rm{Ei}{\left( x-1\right) }-2e^{x}+C_{1}\\
A\left( x\right)=-2e\rm{Ei}{\left( x-1\right) }+C_{1}}\)
Jak policzysz kilka pochodnych w zerze to zauważysz że spełniają one zależność rekurencyjną
Ciekawe jak znaleźć wzór ogólny na współczynniki szeregu będącego rozwinięciem tej funkcji tworzącej
Gdyby przyjąć \(\displaystyle{ C_{1}=0}\) w tej geometrycznej funkcji tworzącej to po obliczeniu granicy z kolejnych pochodnych to współczynniki spełniają zależność rekurencyjną
Bez tego założenia trzeba brać granice prawostronne
-
Mariusz M
- Użytkownik
- Posty: 6908
- 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
Rozwiąż rekursję.
Wykładnicza funkcja tworząca z wzoru Taylora powinna wyjśćCiekawe jak znaleźć wzór ogólny na współczynniki szeregu będącego rozwinięciem tej funkcji tworzącej
Po obliczeniu pierwszej pochodnej następne można policzyć z wzoru Leibniza
\(\displaystyle{ A\left( x\right)=-2e\rm{Ei}{\left( x-1\right) }+C_{1}}\)
\(\displaystyle{ \frac{ \mbox{d}A}{ \mbox{d}x }=-2e \cdot \frac{e^{x-1}}{x-1}=\frac{2e^{x}}{1-x} \\
\frac{ \mbox{d}^n}{ \mbox{d}x^n }e^{x}=e^{x}\\
\frac{ \mbox{d}^n}{ \mbox{d}x^n }\left( \frac{1}{1-x} \right)= \frac{n!}{\left( 1-x\right)^{n+1} }\\
\frac{ \mbox{d}^n}{ \mbox{d}x ^n} A\left( x\right) = 2\sum_{k=0}^{n-1}{ {n-1 \choose k}k!\frac{e^{x}}{\left( 1-x\right)^{k+1} } } \qquad n\geq 1\\}\)
\(\displaystyle{ a_{n}= \begin{cases} a_{0} \in \mathbb{R} \qquad n=0\\ a_{n}=2 \sum_{k=0}^{n-1} {n-1 \choose k}k! \end{cases}}\)
Zamiast \(\displaystyle{ \mathbb{R}}\) może być wasz ulubiony zbiór
Gdybyśmy mieli rekurencję
\(\displaystyle{ a_{n+1} = n\cdot a_{n} + 2 \qquad n \geq 1}\)
to moglibyśmy skorzystać także z czynnika sumacyjnego
ale wyklucza to zdanie
oraz próby sumowania od zeraWiem, że trzeba skorzystać z funkcji tworzących,