rekurencja i funkcja tworzaca

[Gogeta]

Pokazac funkcje tworzaca i podac wzor jawny ciagu:
\(\displaystyle{ a_n=5a_{n-1}-6a_{n-2}}\)
\(\displaystyle{ a_1=1}\) \(\displaystyle{ a_2=2}\)

Ja robiem to w nastepujący sposób:
\(\displaystyle{ A(x)= \sum_{n=0}^{ \infty }a_nx^n=1+2x+ \sum_{n=0}^{ \infty }5a_{n-1}-6a_{n-2}x^n=1+2x+5x\sum_{n=1}^{ \infty }a_nx^n-6x^2\sum_{n=0}^{ \infty }a_nx^n=1+2x+5x\sum_{n=0}^{ \infty }a_nx^n-5x-6x^2\sum_{n=0}^{ \infty }a_nx^n=1-3x+5x\sum_{n=0}^{ \infty }a_nx^n-6x^2\sum_{n=0}^{ \infty }a_nx^n}\)

\(\displaystyle{ A(x)=1-3x+5x\sum_{n=0}^{ \infty }a_nx^n-6x^2\sum_{n=0}^{ \infty }a_nx^n}\)

Dobrze to zrobilem? W jaki sposob moge z tej postaci wyznaczyc wzor jawny ciagu?

[Vardamir]

Ja robiem to w nastepujący sposób:
\(\displaystyle{ A(x)= \sum_{n=0}^{ \infty }a_nx^n=1+2x+ \sum_{n={\red 2}}^{ \infty }5a_{n-1}-6a_{n-2}x^n=1+2x+5x\sum_{n=1}^{ \infty }a_nx^n-6x^2\sum_{n=0}^{ \infty }a_nx^n=\cdots}\)

Drobny błąd przy indeksie sumy. W tym momencie możemy już wyznaczyć funkcję tworzącą bez dalszych przekształceń.

\(\displaystyle{ A(x)= \sum_{n=0}^{ \infty }a_nx^n=1+2x+ \sum_{n=2}^{ \infty }5a_{n-1}-6a_{n-2}x^n=1+2x+5x\sum_{n=1}^{ \infty }a_nx^n-6x^2\sum_{n=0}^{ \infty }a_nx^n=1+2x+5x\left( A(x)-1\right) -6x^2A(x)}\)

Otrzymujemy równanie:

\(\displaystyle{ A(x)=1+2x+5x\left( A(x)-1\right) -6x^2A(x)}\)

Zatem mamy po wymnożeniu i przeniesieniu na jedną stronę, że funkcja tworząca jest postaci:

\(\displaystyle{ A(x)=\frac{1-3x}{1-5x+6x^2}}\)

Aby dostać jawny wzór rozwiń tą funkcję w szereg potęgowy.

[Gogeta]

Rozbiłem \(\displaystyle{ A(x)=\frac{1-3x}{1-5x+6x^2}}\) na ułamki proste i wyszło mi \(\displaystyle{ \frac{0}{3x-1} - \frac{1}{2x-1}}\) a to jest równe \(\displaystyle{ \frac{1}{2x-1}}\) i nie wiem jak to zamienic na szereg potegowy :/ Mogłbym prosić ponownie o pomoc? Byłbym bardzo wdzieczny.

[Vardamir]

Zgubiłeś jeszcze minus \(\displaystyle{ A(x)=\frac{1-3x}{1-5x+6x^2}=\frac{-1}{2x-1}=\frac{1}{1-2x}}\)

Teraz trzeba skorzystać z tego że \(\displaystyle{ \frac{1}{1-ax}= \sum_{n=0}^{\infty} a^n x^n}\)

[Gogeta]

Aha czyli rozumiem ze \(\displaystyle{ A(x)=\frac{1}{1-2x}= \sum_{n=0}^{\infty} 2^n x^n}\)
Moj wzor jawny to to co stoi przy \(\displaystyle{ x^n}\)
czyli z tego jak rozumiem to \(\displaystyle{ a_n = 2^n}\)
Lecz jak rozwiazuje ta rekurencje poprzez rownanie charakterystyczne wychodzi mi, ze \(\displaystyle{ a_n = \frac{1}{2} \cdot 2^n}\)

Skad mam wziac ta \(\displaystyle{ \frac{1}{2}}\) ?

[Vardamir]

A no tak. Tylko zauważ, że masz podany \(\displaystyle{ a_1}\) i \(\displaystyle{ a_2}\) wyraz. Wcześniej tego nie zauważyłem i wszystko jest rozwiązywane w oparciu o \(\displaystyle{ a_0=1 \ , \ a_1=2}\).

Stąd wyniknie to 'przesunięcie' o jeden wyraz. Czyli \(\displaystyle{ a_n=2^{n-1}}\)

Nie bardzo chce mi się to wszystko on nowa rozpisywać. Tam trzeba uważać przy tych szeregach z numerowaniem. Rozumiesz o co mi chodzi?

[Gogeta]

No własnie troche niedokonca. Czyi za kazdym razem jak licze w ten sposob od pierwszego wyrazu poprostumoge w koncowym rozwazaniu od \(\displaystyle{ n}\) odjac poprostu 1 zeby bylo ze licze od \(\displaystyle{ a_0}\) tak?

[Vardamir]

Wprowadziłem trochę zamieszania tym niedopatrzeniem, więc może jednak rozpiszę

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

O to chodziło z tymi indeksami.

Teraz na końcu otrzymujemy, że

\(\displaystyle{ a_{n+1}=2^n}\) a z tego mamy już wzór na n-ty wyraz \(\displaystyle{ a_n=2^{n-1}}\)

[Gogeta]

Dzieki wielkie! Teraz wszystko jasne Wlasnie takie wytlumaczenia potrzebowalem