Matematyka.pl

Proszę pomóżcie ja nic nie rozumiem. Mamy ciąg zadany rekurencyjnie i mamy znaleźć wzór jawny na n-ty wyraz ciągu. I sobie patrzę na wikipedię i tam to się sprowadza do równania kwadratowego, myślę sobie fajnie. Potem patrzę na zadania i się pojawia stała z tyłu, jeszcze w ogóle do potęgi entej...
\(\displaystyle{ \begin{cases} a_{0}=4\;\; a_{1}=-6\\ a_{n}=3a_{n-1}+10a_{n-2}-7\cdot5^{n-1}\; n \ge 2 \end{cases} }\)
Komentarz "jednorodne" i potem rozwiązanie równania kwadratowego z pominięciem tej końcówki na końcu. Z jakiegoś powodu wywaliliśmy końcówkę i robimy tak jak to było na wikipedii.
\(\displaystyle{ r^{2}-3r-10=0}\)
\(\displaystyle{ r_{1}=-2,r_{2}=5}\)
A potem dzieje się magia. \(\displaystyle{ A}\),\(\displaystyle{ B}\) to stałe.
\(\displaystyle{ a_{n}=A(-2)^{n}+B5^{n}+t_{n}}\)
\(\displaystyle{ t_{n}=3t_{n-1}+10t_{n-2}-7\cdot5^{n-1}}\) dla \(\displaystyle{ n\ge 2}\). Nie rozumiem, nic nam to nie daje! Domyślam się, że \(\displaystyle{ A}\) i \(\displaystyle{ B}\) to szukane, ale tak to nie rozumiem co z czego i dlaczego.
\(\displaystyle{ c_{n}=-7\cdot5^{n-1}}\) i komentarz "taki sam stopień jak \(\displaystyle{ V(n)}\)". Co to jest \(\displaystyle{ V(n)}\)? We wcześniejszych wykładach była to permutacja, ale gdzie tu permutacja?
\(\displaystyle{ p=5}\) "czyli jest pierwiastkiem \(\displaystyle{ (r_{2})}\)" czyli co, gdyby w podstawie potęgi była jakaś inna stała, to by rekurencji się nie dało rozwiązać?
\(\displaystyle{ t_{n}=C_{n}5^{n}}\) to są notatki pisane, więc nie jestem w stanie jednoznacznie stwierdzić czy \(\displaystyle{ C_{n}}\) i \(\displaystyle{ c_{n}}\) to to samo, ale zakładam, że nie.
\(\displaystyle{ C_{n}5^{n}=3(C(n-1)5^{n-1})+10(C(n-2)5^{n-2})-7\cdot5^{n-1} }\)skąd się wzięło to równanie, co znaczą znaczki i czemu się to tak brutalnie uprościło?
\(\displaystyle{ 35C=-35}\)
\(\displaystyle{ C=-1}\), więc z tego \(\displaystyle{ a_{n}=A(-2)^{n}+B5^{n}-n5^{n}}\), przecież tam była siódemka kiedyś, co jest?
\(\displaystyle{ \begin{cases} A+B=4 \\-2A+B-5=6 \end{cases} }\)
Ostatecznie \(\displaystyle{ a_{n}=3(-2)^{n}+5^{n}-n5^{n}}\)
Układ równań rozumiem, wiadomo, muszą być jakieś stałe i po prostu musi to być spełnione dla wszystkich liczb naturalnych, więc podstawiamy do oryginalnego warunku.

Bez wyłożenie tu całej teorii równań rekurencyjnych trudno pomóc. Może miałaś równania różniczkowe zwyczajne? Wtedy byłoby łatwiej bo teoria jest bardzo podobna/wręcz identyczna jak dla równań liniowych o stałych współczynnikach. Metoda przewidywań działa tu i tu. Mamy odpowiednik między transformatą \(\displaystyle{ \mathcal{L}}\) oraz \(\displaystyle{ \mathcal{Z}}\). No i fakty są podobne. Przykładowo przestrzeń rozwiązań równania jednorodnego \(\displaystyle{ a_{n}+ \xi a_{n-1} +\eta a_{n-2}=0 }\) (gdy \(\displaystyle{ \xi^2-4\eta>0}\)) składa się z kombinacji liniowych dowolnych stałych oraz \(\displaystyle{ n}\)-tych potęg pierwiastków wielomianu charakterystycznego równania to jest \(\displaystyle{ w(x)= x^2+\xi x + \eta}\). Możesz na to patrzeć jak na uogólniony ciąg geometryczny. Bo przykładowo rekurencja \(\displaystyle{ a_{n}+ \xi a_{n-1}=0 }\) opisuje właśnie ciąg geometryczny, a ze względu na liniowość (formalnie operator przesunięcia) kombinacje liniowe zaczynają być rozwiązaniami w ogólniejszym przypadku. To tak jak w algebrze liniowi. Jak znajdziesz nietrywialne rozwiązania układu jednorodnego \(\displaystyle{ Ax=0}\) to ich kombinacje liniowe będą generować przestrzeń rozwiązań.

Potem jeszcze należało by wyjaśnić niejednorodność. Tu masz niejednorodne równanie. I teoria mówi tyle, że rozwiązaniem ogólnym jest suma rozwiązania szczególnego z ogólnym rozwiązaniem równania jednorodnego. Znów nawiązania do algebry i afinicznych przesunięć będą dobre.

Tak czy inaczej cała teoria jest dość rozbudowana i zbyt długa (dla mnie) jak na komentarz na forum. Mogę jedynie polecić szukanie informacji w Internecie i notatkach z wykładu na temat równań rekurencyjnych ze stałymi współczynnikami. Skrypty AGH standardowo nie powinny zawieść.

Bardziej polecam funkcje tworzące...

Dobrze, prō pūblicō bonō opiszę na tym przykładzie metodę wielomianu charakterystycznego, gdyż ta metoda jest zdecydowanie najlepsza do rozwiązywania liniowych zależności rekurencyjnych. Zapisujemy naszą rekurencję jako Układamy teraz wielomian charakterystyczny patrząc na współczynniki po lewej stronie. Mamy tam trzy wyrazy, wielomianem charakterystycznym będzie trójmian to jest po faktoryzacji Teraz kluczowa rzecz — gdyby nasza rekurencja była jednorodna, czyli gdyby \(b_{n} - 3b_{n - 1} - 10b_{n - 2} = 0\), to rozwiązanie byłoby postaci \(b_{n} = \alpha(n)(-2)^{n} + \beta(n)5^{n}\) dla pewnych wielomianów co najwyżej zerowego stopnia \(\alpha\) i \(\beta\) (czyli stałych po prostu). Te liczby \(-2\) i \(5\) biorą się z pierwiastków wielomianu charakterystycznego, stopnie wielomianów \(\alpha\) i \(\beta\) biorą się z krotności pierwiastków tego wielomianu.

U nas jest nieco trudniej, gdyż nasza rekurencja jest liniowa, acz nie jest jednorodna. Patrzymy na prawą stronę rekurencji — stoi tam wyrażenie \(-\frac{7}{5}\cdot 5^{n}\) — jest to wielomian zerowego stopnia pomnożony przez funkcję \(5^{n}\). Fakt, iż ponownie pojawia się tu pierwiastek który już był w wielomianie charakterystycznym mówi, iż jawna postać ciągu \(a_{n}\) to przy czym \(\alpha\) to wielomian co najwyżej zerowego stopnia, wielomian zaś \(\beta\) będzie co najwyżej pierwszego stopnia — stopień rośnie ze względu na ponowne pojawienie się liczby \(5\). Innymi słowy, przy czym \(c_{0}\), \(c_{1}\) i \(c_{2}\) to pewne stałe.

Reszta sprowadza się do wyznaczenia tych stałych. Najłatwiej jest to uczynić znając trzy początkowe wartości naszego ciągu. Dwie pierwsze są podane, trzecią doliczamy z danej rekurencji. Otóż \(a_2 = 3a_1 + 10a_0 - 7\cdot5 = -13\), a więc: Jest to prosty układ, rozwiązawszy go uzyskamy: czyli Jeśli ktoś nie dowierza w zupełności tej metodzie, to mam dobrą wiadomość — mając wynik łatwo go sprawdzić indukcyjnie.

Mogą się zrodzić pytanie, co by było, gdyby niejednorodna część rekurencji miała inną funkcję wykładniczą, albo gdyby stał tam wielomian innego stopnia. To wszystko jest uwzględnione przez ogólną teorię, ale nie chcę się zbytnio rozpisywać. Trzeba poszperać w czeluściach anglosaskiego internetu by znaleźć przykłady i wyjaśnienie.

Dowód poprawności tej metody opiera się na dość ciężkiej algebrze liniowej, samą metodą dobrze znać. Metodę funkcji tworzących lepiej zostawić na trudniejsze rekurencje, gdyż jest to bawienie się szeregami formalnymi, raczej dłuższe.

\(\displaystyle{ \begin{cases} a_{0}=4\;\; a_{1}=-6\\ a_{n}=3a_{n-1}+10a_{n-2}-7\cdot5^{n-1}\; n \ge 2 \end{cases} }\)


Arek tutaj wspomniał tutaj o funkcjach tworzących więc pokażę jak to działa

Ponieważ jest to rekurencja liniowa o stałych współczynnikach zwykła funkcja tworząca tutaj wystarczy

Zdefiniujmy sobie funkcję w postaci szeregu potęgowego którego współczynniki tworzą dany ciąg

\(\displaystyle{ A\left( x\right) = \sum\limits_{n=0}^{ \infty }a_{n}x^{n} }\)

Ponieważ rekurencja jest spełniona dla \(\displaystyle{ n \ge 2}\) więc wstawiając szereg potęgowy do równania rekurencyjnego
sumujemy od \(\displaystyle{ n=2}\)

\(\displaystyle{ \sum\limits_{n=2}^{ \infty }{a_{n}x^{n}} = \sum\limits_{n=2}^{ \infty }{\left(3a_{n-1}+10a_{n-2}-7\cdot 5^{n-1} \right)x^{n} }\\
\sum\limits_{n=2}^{ \infty }{a_{n}x^{n}} = 3\left(\sum\limits_{n=2}^{ \infty }{a_{n-1}x^{n}}\right)+10\left(\sum\limits_{n=2}^{ \infty }{a_{n-2}x^{n}}\right)-\frac{7}{5}\left(\sum\limits_{n=2}^{ \infty }{5^{n} \cdot x^{n}}\right)\\
\sum\limits_{n=2}^{ \infty }{a_{n}x^{n}} = 3x\left(\sum\limits_{n=2}^{ \infty }{a_{n-1}x^{n-1}}\right)+10x^2\left(\sum\limits_{n=2}^{ \infty }{a_{n-2}x^{n-2}}\right)-\frac{7}{5}\cdot\frac{25x^2}{1-5x}\\
\sum\limits_{n=2}^{ \infty }{a_{n}x^{n}} = 3x\left(\sum\limits_{n=1}^{ \infty }{a_{n}x^{n}}\right)+10x^2\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right)-\frac{35x^2}{1-5x}\\
\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}-4+6x = 3x\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}-4\right)+10x^2\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right)-\frac{35x^2}{1-5x}\\
\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}-4+6x = 3x\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right)-12x+10x^2\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right)-\frac{35x^2}{1-5x}\\
\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}-3x\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right)-10x^2\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right)=-18x+4-\frac{35x^2}{1-5x}\\
\left(1-3x-10x^2\right)\left(\sum\limits_{n=0}^{ \infty }{a_{n}x^{n}}\right) = \frac{\left(18x-4\right)\left(5x-1\right)-35x^2 }{\left( 1-5x\right) }\\
\left(1-3x-10x^2\right)A\left( x\right) = \frac{55x^2-38x+4}{\left( 1-5x\right) }\\
\left( 1+2x\right)\left( 1-5x\right)A\left( x\right) = \frac{55x^2-38x+4}{\left( 1-5x\right) }\\
A\left( x\right) =\frac{55x^2-38x+4}{\left( 1+2x\right)\left( 1-5x\right)^2 }\\
}\)

\(\displaystyle{
\frac{55x^2-38x+4}{\left( 1+2x\right)\left( 1-5x\right)^2 } = \frac{A}{1+2x}+\frac{B}{1-5x}+\frac{C}{\left( 1-5x\right)^2 }\\
55x^2-38x+4 = A\left( 1-5x\right)^2+B\left( 1+2x\right)\left( 1-5x\right) + C\left( 1+2x\right) \\
55x^2-38x+4 = A\left( 1-10x+25x^2\right)+B\left( 1-3x-10x^2\right) + C\left( 1+2x\right) \\
\begin{cases} A+B+C=4 \\ -10A-3B+2C = -38\\25A-10B=55 \end{cases}\\
\begin{cases} A+B+C=4 \\ -10A-3B+2C = -38\\5A-2B=11 \end{cases}\\
\begin{cases} -12A-5B=-46 \\ 5A-2B=11\\A+B+C=4 \end{cases} \\
\begin{cases} 24A+10B=92 \\ 5A-2B=11\\A+B+C=4 \end{cases} \\
\begin{cases} 24A+10B=92 \\ 5A-2B=11\\A+B+C=4 \end{cases} \\
\begin{cases} 49A=147 \\ 5A-2B=11\\A+B+C=4 \end{cases} \\
\begin{cases} A=3 \\ 5A-2B=11\\A+B+C=4 \end{cases} \\
\begin{cases} A=3 \\ B = 2\\C=-1 \end{cases} \\
}\)

\(\displaystyle{
A\left( x\right) = \frac{A}{1+2x}+\frac{B}{1-5x}+\frac{C}{\left( 1-5x\right)^2 }\\
A\left( x\right) = \frac{3}{1+2x}+\frac{2}{1-5x}-\frac{1}{\left( 1-5x\right)^2 }\\
}\)

Teraz jak rozwinąć w szereg składnik \(\displaystyle{ \frac{1}{\left( 1-5x\right)^2 }}\)
Otóż można co najmniej na trzy sposoby
1. Różniczkując szereg geometryczny
2. Stosując uogólniony dwumian Newtona
3. Korzystając ze splotu ciągów

\(\displaystyle{ \sum\limits_{n=0}^{\infty}{5^{n}x^{n}} = \frac{1}{1-5x}\\
\frac{\mbox{d}}{\mbox{d}x}\left(\sum\limits_{n=0}^{\infty}{5^{n}x^{n}}\right) = \frac{\mbox{d}}{\mbox{d}x}\left(\frac{1}{1-5x} \right) \\
\sum\limits_{n=0}^{\infty}{n \cdot 5^{n}x^{n-1}} = \frac{-1}{\left( 1-5x\right)^2 } \cdot \left( -5\right) \\
\sum\limits_{n=1}^{\infty}{n \cdot 5^{n}x^{n-1}} = \frac{5}{\left( 1-5x\right)^2}\\
\sum\limits_{n=0}^{\infty}{\left( n+1\right) \cdot 5^{n+1}x^{n}} = \frac{5}{\left( 1-5x\right)^2}\\
\sum\limits_{n=0}^{\infty}{\left( n+1\right) \cdot 5^{n}x^{n}} = \frac{1}{\left( 1-5x\right)^2}\\
}\)

\(\displaystyle{ A\left( x\right) = 3\left( \sum\limits_{n=0}^{ \infty } \left( -2\right)^{n} \right) +2\left(\sum\limits_{n=0}^{ \infty } 5^{n} \right)-\left(\sum\limits_{n=0}^{\infty}{\left( n+1\right) \cdot 5^{n}x^{n}} \right) \\
A\left( x\right) = 3\left( \sum\limits_{n=0}^{ \infty } \left( -2\right)^{n} \right)+\left(\sum\limits_{n=0}^{\infty}{\left(1-n\right) \cdot 5^{n}x^{n}} \right)\\
A\left( x\right) = \sum\limits_{n=0}^{ \infty }{\left( 3 \cdot \left( -2\right)^n+\left( 1-n\right) \cdot 5^{n} \right)x^{n} }\\
a_{n} = 3 \cdot \left( -2\right)^n+\left( 1-n\right) \cdot 5^{n}\\
}\)

No to pokażę, jak można to zrobić inaczej metodą przewidywań:
Niech `b_n=a_n+Bn5^n`.
Wtedy
`b_n-Bn5^n=3(b_{n-1}-B(n-1)5^{n-1})+10(b_{n-2}-B(n-2)5^{n-2})-7\cdot 5^{n-1}`
co po uporządkowaniu daje
`b_n=3b_{n-1}+10b_{n-2}+(35B-35)5^{n-2}`.

Jeżeli zatem wybierzemy `B=1`, to `b_n` spełniają równanie jednorodne, więc `b_n=C(-2)^n+D5^n`, czyli `a_n=C(-2)^n+(D-n)5^n`.

Gdyby `5` nie było pierwiastkiem równania charakterystycznego, to szukalibyśmy `b` w postaci `b_n=a_n+B\cdot5^n`
Gdyby `5` było podwójnym pierwiastkiem, to `b_n=a_n+(Bn+Cn^2)5^n` etc.