wzór rekurencyjny- równanie charakterystyczne

[matematyk1995]

Witam.

Mamy ciąg : \(\displaystyle{ \begin{cases}a_1=-4 \\ a_{n+1}=3a_n+2n \end{cases}}\)

Chcę go przedstawić w postaci \(\displaystyle{ a_n=...}\) czyli w postaci ogólnej. Jak przejść do równania charakterystycznego ze wzoru rekurencyjnego? Jest to możliwe?

[Chromosom]

Proponuję zastosować funkcje tworzące.

[matematyk1995]

Tzn jak ? Nie wiem

[yorgin]

Chcę go przedstawić w postaci \(\displaystyle{ a_n=...}\) czyli w postaci ogólnej. Jak przejść do równania charakterystycznego ze wzoru rekurencyjnego? Jest to możliwe?

Jest to możliwe, ale najpierw musisz rozwiązać równanie jednorodne (bez \(\displaystyle{ 2n}\)), a potem metodą przewidywań znaleźć jakieś rozwiązanie ogólnego równania.

Funkcje tworzące mają taką przewagę, że nie trzeba w ogóle rozdrabniać się na typy równań.

[matematyk1995]

Czyli równanie jednorodne bedzie wglądało tak: \(\displaystyle{ x ^{1}=3x^0 \Rightarrow x=3}\)?

I co dalej ?


edit.

A jak bedzie wyglądać funkcja tworząca?

[bakala12]

Równanie charakterystyczne źle. Trzeba się pozbyć składnika \(\displaystyle{ 2n}\). Rozpisz Jeszcze z rekurencji zależność na \(\displaystyle{ a_{n+2}}\) i odejmij zależność na \(\displaystyle{ a_{n+1}}\). Po tym w rekurencji zostaje już tylko 2. Też je usuwamy analogicznie jak napisałem powyżej. Gdy dostaniemy rekurencje zawierającą tylko wyrazy ciągu dopiero możemy układać równanie charakterystyczne i przejść do rozwiązania rekurencji.

[Chromosom]

A jak bedzie wyglądać funkcja tworząca?

\(\displaystyle{ f(x)=\sum\limits^\infty_{n=0}a_nx^n\\f(x)=a_0+x\sum\limits^\infty_{n=1}\bigl(3a_{n-1}+2n\bigr)x^{n-1}}\)

[Naed Nitram]

Jak dwa posty powyżej:

Niech

\(\displaystyle{ b_1=a_1=-4}\)

\(\displaystyle{ b_n=a_{n+1}-a_n}\), dla \(\displaystyle{ n>1}\).

Wówczas

\(\displaystyle{ a_n=\sum_{i=1}^n b_i}\).

ponadto:

\(\displaystyle{ b_{n+1}=a_{n+2}-a_{n+1}=3a_{n+1}+2(n+1)-3a_n-2n=3(a_{n+1}-a_n)+1=3b_n+2}\).

Rekurencję: \(\displaystyle{ b_{n+1}=3b_n+2}\) łatwo rozwiązać bez żadnych dalszych komplikacji (od razu widać), ale jeśli musi być równanie charakterystyczne, to rozważmy kolejny ciąg pomocniczy:

\(\displaystyle{ c_1=b_1=-4}\)

\(\displaystyle{ c_n=b_{n+1}-b_n}\) dla \(\displaystyle{ n>1}\).

Wówczas

\(\displaystyle{ b_n=\sum_{i=1}^n c_i}\)

oraz

\(\displaystyle{ c_{n+1}=b_{n+2}-b_{n+1}=3b_{n+1}+2-3bn-2=3(b_{n+1}-b_n)=3 c_n}\).

I mamy równanie charakterystyczne dla ciągu \(\displaystyle{ c_n}\):

\(\displaystyle{ x^2=3x}\)

Stąd:

\(\displaystyle{ c_n=c_1\cdot 3^{n-1}=-4\cdot 3^{n-1}}\)

i dalej:

\(\displaystyle{ b_n=\sum c_i=-4\cdot\frac{3^n-1}{2}=-2\cdot (3^n-1)}\)

ostatecznie:

\(\displaystyle{ a_n=\sum b_i =-2\left(\frac{3^{n+1}-1}2-n\right)=2n+1-3^{n+1}}\)

[vpprof]

Naed Nitram, nie wiem jak tobie, ale mi wychodzą inne wyniki z twojego równania jawnego niż z rekurencyjnego.
\(\displaystyle{ a_1=-4 \\
a_2 = 3a_1+2 \cdot 1=-10 \\
a_3 = 3a_2+2 \cdot 2=-26}\)

\(\displaystyle{ a_1=2 \cdot 1+1-3^2=-6 \\
a_2=2 \cdot 2+1-3^3=-22 \\
a_3=2 \cdot 3+1-3^4=-74}\)

Coś źle odczytuję? Ja też postaram się przedstawić kompletne rozwiązanie przy użyciu funkcji tworzących, tylko że gdzieś się regularnie mylę, bo mi wychodzi wzór dający o 1 za mało. W każdym razie prawidłowy (sprawdzony dla kilkudziesięciu \(\displaystyle{ n}\)) jest taki wzór ogólny: \(\displaystyle{ a_n=-2,5 \cdot 3^{n-1}-n-1,5}\).

[Naed Nitram]

Tak, pokręciłem. Trzeba skrupulatniej przyglądać się początkowym wyrazom ciągów \(\displaystyle{ b_n, c_n}\). Można jednak wykręcić się ze skrupulatnych rachunków (i tu zaczyna się nieco krótsze rozwiązanie) zauważywszy, że dla odpowiednio dużych \(\displaystyle{ n}\) (tu wystarczy 3) zachodzi:

\(\displaystyle{ c_n=3c_{n-1}}\)

skąd dla odpowiednio dużych \(\displaystyle{ n}\) elementy \(\displaystyle{ b_n}\) są postaci:

\(\displaystyle{ b_n = \alpha3^n+\beta}\)

skąd dla odpowiednio dużych \(\displaystyle{ n}\) elementy \(\displaystyle{ a_n}\) są postaci:

\(\displaystyle{ a_n=x3^n+yn+z}\).

Teoria powiada, że jeśli od pewnego miejsca \(\displaystyle{ a_n=x3^n+yn+z}\), to w ogóle dla wszystkich \(\displaystyle{ n}\) tak jest, więc wartości \(\displaystyle{ x,y,z}\) wyznaczamy wstawiając wartości \(\displaystyle{ a_n}\) dla małych \(\displaystyle{ n}\).

\(\displaystyle{ \begin{cases} 3x+y+z=-4\\
9x+2y+z=-10\\
27x+3y+z=-26\end{cases}}\)

Skąd \(\displaystyle{ x=-\frac 56, y=-1, z=-\frac 12}\).

Rozwiązanie może nie tak satysfakcjonujące, jak dojście do wyniku na drodze dyscypliny arytmetycznej, ale za to znacznie odporniejsze na błędy obliczeniowe.

[vpprof]

Naed Nitram, to dalej nie jest rozwiązanie, twój wzór będzie dawał wartość o 1 za dużą. Nieważne zresztą, poniżej wpiszę swoje rozwiązanie.

Funkcją tworzącą ciągu \(\displaystyle{ \begin{cases}a_0 = 0 \\ a_1=-4 \\ a_{n+1}=3a_n+2n &\text{dla } n>0 \end{cases}}\)
jest
\(\displaystyle{ f(x)=
\sum_{n=0}^{ \infty } a_nx^n
=a_0+\sum_{n=1}^{ \infty } a_nx^n
=a_1x+\sum_{n=1}^{ \infty } a_{n+1}x^{n+1}
=x\left( a_1+ \sum_{n=1}^{ \infty } a_{n+1}x^n\right)
=x\left( -4+ \sum_{n=1}^{\infty}\left( 3a_n+2n\right) x^n \right)
=x\left( -4+3 \sum_{n=1}^{\infty}a_nx^n +2 \sum_{n=1}^{\infty}nx^n \right)
=x\left( -4+3f(x)+2x \frac{1}{\left( 1-x\right)^2 } \right)}\)

\(\displaystyle{ f(x)-3xf(x)=x\left( -4+ \frac{2x}{\left( 1-x\right)^2} \right) \\
f(x)=x\left( \frac{-4}{1-3x} + \frac{2x}{\left( 1-x\right)^2\left( 1-3x\right) }\right)}\)

Teraz musimy rozłożyć na ułamki proste:
\(\displaystyle{ \frac{2x}{\left( 1-x\right)^2\left( 1-3x\right) }= \frac{A}{1-x} + \frac{B}{\left( 1-x\right)^2} + \frac{C}{1-3x}=\frac{- \frac{1}{2} }{1-x} + \frac{-1}{\left( 1-x\right)^2} + \frac{ \frac{3}{2} }{1-3x}}\)

\(\displaystyle{ f(x)=x \sum_{n=0}^{\infty}\left( -4 \cdot 3^n- \frac{1}{2} -\left( n+1\right) + \frac{3}{2} \cdot 3^n \right) x^n =\sum_{n=0}^{\infty}\left( -2 \frac{1}{2} \cdot 3^n - n - 1 \frac{1}{2} \right)x^{n+1}}\)

Stąd:
\(\displaystyle{ a_{n+1}=-2 \frac{1}{2} \cdot 3^n - n - 1 \frac{1}{2}}\)

[Naed Nitram]

Naed Nitram, to dalej nie jest rozwiązanie, twój wzór będzie dawał wartość o 1 za dużą.

Tylko zasygnalizuję, że moim zdaniem powyższe to nieprawda.

[vpprof]

Naed Nitram, to dalej nie jest rozwiązanie, twój wzór będzie dawał wartość o 1 za dużą.

Tylko zasygnalizuję, że moim zdaniem powyższe to nieprawda.

Racja, obydwa wzory są równoważne Tylko mój jest dla \(\displaystyle{ n>0}\), twój dla \(\displaystyle{ n>1}\).