Równanie rekurencyjne i funkcje tworzące

[librusss]

Dzień dobry, ćwiczę rozwiązywanie równań rekurencyjnych za pomocą funkcji tworzących i chyba niezbyt mi to idzie - wydaje mi się, że robię dobrze, ale za każdym razem coś jest nie tak, ponieważ odpowiedź wychodzi nieprawdziwa. Napiszę pod spodem moje rozwiązanie, może ktoś znajdzie błąd/błędy i dzięki temu będę miał szanse się poprawić.

Treść zadania (znaleźć jawny wzór za pomocą funkcji tworzącej):
$$a_0 = 2, a_{n+1} = 2a_n +2^n$$

Moje "rozwiązanie":
Równanie z treści zadania możęmy zapisać jako:
$$a_n = 2a_{n-1} +2 ^{n-1}$$
$$A(x) = \sum_{n=1}^{ \infty }a_nx^n = 2 \cdot \sum_{n=1}^{ \infty } a_{n-1}x^n + \sum_{n=1}^{ \infty }2^{n-1}x^n = 2x \cdot \sum_{n=1}^{ \infty } a_{n-1} x^{n-1} + x \cdot \sum_{n=1}^{ \infty } 2^{n-1}x^{n-1} = 2x \cdot \sum_{n=0}^{ \infty } a_n x^n + x \cdot \sum_{n=0}^{ \infty } 2^n x^n$$
$$A(x) - a_0 = 2x \cdot (A(x) - a_0) + \frac{x}{1-2x} \Leftrightarrow A(x) - 2 = 2x \cdot (A(x)-2) + \frac{x}{1-2x}$$
$$(1-2x) A(x) = \frac{8x^2 -7x+2}{1-2x} \Rightarrow A(x) = \frac{8x^2 -7x+2}{(1-2x)^2} = -2 + \frac{1}{4} \cdot \frac{1}{1-2x} + \frac{15}{4} \cdot \frac{1}{1+2x} = -2 + \frac{1}{4} \cdot \sum_{n=0}^{ \infty } 2^nx^n + \frac{15}{4} \cdot \sum_{n=0}^{ \infty } (-2)^n x^n$$
$$a_n = -2 + \frac{1}{4} \cdot 2^n + \frac{15}{4} \cdot (-2)^n$$
Co niestety nie jest poprawną odpowiedzią (psuje się np. gdy wypróbujemy sprawdzić ile wynosi pierwszy wyraz ciągu). Nie mam pojęcia, gdzie może tkwić błąd.

Pzdr.

[Premislav]

Idea jest dobra, tylko mylisz się w granicach sumowania. Raczej jest
\(\displaystyle{ A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}}\), tak się zazwyczaj przyjmuje, a jak już chcesz mieć \(\displaystyle{ A(x)=\sum_{n=1}^{\infty}a_{n}x^{n}}\), to bądź w tym konsekwentny, a nie w jednym miejscu tak, a w drugim miejscu inaczej.
Mowa oczywiście o nieprawdziwej równości
\(\displaystyle{ A(x)-a_{0}=2x(A(x)-a_{0})+\frac{x}{1-2x}}\)


Rozwiązanie (ja przyjmuję klasycznie \(\displaystyle{ A(x)=\sum_{n=0}^{+\infty}a_{n}x^{n}}\)):
\(\displaystyle{ \sum_{n=0}^{+\infty}a_{n+1}x^{n}=2\sum_{n=0}^{+\infty}a_{n}x^{n}+\sum_{n=0}^{+\infty}2^{n}x^{n}\\\frac{1}{x}(A(x)-a_{0})=2A(x)+\frac{1}{1-2x}\\A(x)(1-2x)=2+\frac{x}{1-2x}\\A(x)=\frac{2}{1-2x}+\frac{x}{(1-2x)^{2}}\\A(x)=\sum_{n=0}^{+\infty}2^{n+1}x^{n}+\frac{1}{2}\sum_{n=0}^{+\infty}n(2x)^{n}\\ a_{n}=2^{n+1}+n\cdot 2^{n-1}}\)

Po drodze korzystam ze wzorów
\(\displaystyle{ \frac{1}{1-q}=\sum_{n=0}^{+\infty}q^{n}, \ |q|<1\\\frac{q}{(1-q)^{2}}=\sum_{n=0}^{+\infty}nq^{n}, \ |q|<1}\)

[librusss]

Idea jest dobra, tylko mylisz się w granicach sumowania. Raczej jest
\(\displaystyle{ A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}}\), tak się zazwyczaj przyjmuje, a jak już chcesz mieć \(\displaystyle{ A(x)=\sum_{n=1}^{\infty}a_{n}x^{n}}\), to bądź w tym konsekwentny, a nie w jednym miejscu tak, a w drugim miejscu inaczej.
Mowa oczywiście o nieprawdziwej równości
\(\displaystyle{ A(x)-a_{0}=2x(A(x)-a_{0})+\frac{x}{1-2x}}\)


Rozwiązanie (ja przyjmuję klasycznie \(\displaystyle{ A(x)=\sum_{n=0}^{+\infty}a_{n}x^{n}}\)):
\(\displaystyle{ \sum_{n=0}^{+\infty}a_{n+1}x^{n}=2\sum_{n=0}^{+\infty}a_{n}x^{n}+\sum_{n=0}^{+\infty}2^{n}x^{n}\\\frac{1}{x}(A(x)-a_{0})=2A(x)+\frac{1}{1-2x}\\A(x)(1-2x)=2+\frac{x}{1-2x}\\A(x)=\frac{2}{1-2x}+\frac{x}{(1-2x)^{2}}\\A(x)=\sum_{n=0}^{+\infty}2^{n+1}x^{n}+\frac{1}{2}\sum_{n=0}^{+\infty}n(2x)^{n}\\ a_{n}=2^{n+1}+n\cdot 2^{n-1}}\)

Po drodze korzystam ze wzorów
\(\displaystyle{ \frac{1}{1-q}=\sum_{n=0}^{+\infty}q^{n}, \ |q|<1\\\frac{q}{(1-q)^{2}}=\sum_{n=0}^{+\infty}nq^{n}, \ |q|<1}\)

Dziękuję, zrozumiałem już swój błąd, który wynikał z błędnych granic sumowania.

Chciałbym przy okazji poprosić o zerknięcie na drugi przykład, upewniłem się czy nie popełniłem tej samej pomyłki i wydaje mi się, że wszystko w tym względzie jest okej, a mimo to wychodzi zła odpowiedź:

$$a_0 = 1, a_n = 3 a_{n-1} + 3 \cdot (-2)^{n-1} \ \ \ \ \ \ \ \ \ A(x) = \sum_{n=0}^{ \infty } a_n x^n = 3 \sum_{n=1}^{ \infty } a_{n-1}x^n + 3 \sum_{n=1}^{ \infty } (-2)^{n-1} x^n = 3x \sum_{n=1}^{ \infty }a_{n-1}x^{n-1} + 3x \sum_{n=1}^{ \infty } (-2)^{n-1}x^{n-1} $$
$$A(x) = 3x \sum_{n=0}^{ \infty } a_n x^n + 3x \sum_{n=0}^{ \infty } (-2)^n x^n = 3x A(x) + 3x \cdot \frac{1}{1+2x} \Rightarrow A(x) = \frac{3x}{(1+2x)(1-3x)} = -\frac{3}{5} \cdot \frac{1}{1+2x} + \frac{3}{5} \cdot \frac{1}{1-3x}$$
$$A(x) = - \frac{3}{5} \sum_{n=0}^{ \infty } (-2)^n + \frac{3}{5} \cdot \sum_{n=0}^{ \infty } 3^n x^n \Rightarrow a_n = - \frac{3}{5} \cdot (-2)^n + \frac{3}{5} \cdot 3^n$$

Tym ciekawszy przykład, że wydaje mi się, że wszystkie przejścia zrobiłem prawidłowo (zapewne tylko mi się wydaje).

[Premislav]

$$A(x) = \sum_{n=0}^{ \infty } a_n x^n = 3 \sum_{n=1}^{ \infty } a_{n-1}x^n + 3 \sum_{n=1}^{ \infty } (-2)^{n-1} x^n $$

Oj, tu już jest niedobrze. Z uwagi na to, jak wygląda ta zależność rekurencyjna
\(\displaystyle{ a_{n}=3a_{n-1}+3\cdot (-2)^{n-1}}\)
masz w zasadzie dwa wyjścia:
pierwsze to przesunąć indeksy, co daje
\(\displaystyle{ a_{n+1}=3a_{n}+3\cdot (-2)^{n}}\), no i potem normalnie sumować od zera:
\(\displaystyle{ \sum_{n=0}^{+\infty}a_{n+1}x^{n}=3\sum_{n=0}^{+\infty}a_{n}x^{n}+3\sum_{n=0}^{+\infty}(-2)^{n}x^{n}}\)
(to dalej mnożysz przez \(\displaystyle{ x}\) i podobnie jak poprzednio).

Drugie wyjście to sumować od jedynki, pamiętając, że w ten sposób wyliczysz \(\displaystyle{ A(x)}\) bez \(\displaystyle{ a_{0}}\), tj.
\(\displaystyle{ \sum_{n=1}^{+\infty}a_{n}x^{n}=3\sum_{n=1}^{+\infty}a_{n-1}x^{n}+3\sum_{n=1}^{+\infty}(-2)^{n-1}x^{n}}\)

Natomiast Ty w zacytowanym fragmencie po lewej sumujesz od zera, a po prawej od jedynki, tak nic dobrego się nie uzyska, a jeśli tak, to przypadkiem.