Rozwiąż równanie rekursji.

[huciaa]

Cześć mam problem z jednym zadaniem .
Mam rozwiązać równanie rekursji.
\(\displaystyle{ T(0)=1 \\
T(n) = 2 \cdot T(n-1) + (-1) ^{n}}\)

Mam też wzór za pomocą mogę to rozwiązać, ale nic z tego nie kapuje...

\(\displaystyle{ T(n) = c \cdot a^k + \sum_{j=0}^{k-1} a ^{i} \cdot d(b ^{k-i} )}\)

[bartek118]

Czy na pewno dobrze to przepisałeś? Mamy \(\displaystyle{ (-1)^9 = -1}\) i wtedy rekurencję rozwiążesz względnie łatwo metodą podstawiania.

[huciaa]

Nie wiem skąd wzięła się tam ta 9 :O
Teraz poprawiłem wzór, zamiast 9 jest n.
Kobieta na ćwiczeniach podstawiła to równanie pod podany niżej wzór i zadanie rozwiązane, a ja nie mam pojęcia jak to zrobić...

[Premislav]

Możesz opisać, co ma reprezentować ten podany przez Ciebie wzór? Bo niestety go nie znam, więc nie mam pojęcia, co miałby on dać.

Żeby nie było, że spamuję, to zadanie można rozwiązać również tak:
metodą funkcji tworzących
\(\displaystyle{ T(n)=2T(n-1)+(-1)^n\T(n+1)=2T(n)+(-1)^{n+1}\ T(n+1)x^n=2T(n)x^n+(-1)^{n+1}x^n\ sum_{n=0}^{ infty }T(n+1)x^n=2 sum_{n=0}^{ infty }T(n)x^n+ sum_{n=0}^{ infty }(-1)^{n+1}x^n igg|igg| cdot x\ sum_{n=0}^{ infty }
T(n+1)x^{n+1}=2x sum_{n=0}^{ infty }T(n)x^n+ sum_{n=0}^{ infty }(-x)^{n+1}\ ext{ oznaczmy } G(x)= sum_{n=0}^{ infty }T(n)x^n\ G(x)-T(0)=2xG(x)- frac{x}{1+x}\ G(x)(1-2x)=T(0)+ frac{-1-x+1}{1+x}\G(x)= frac{1}{(1+x)(1-2x)}= frac{frac{1}{3}(1-2x)+frac{2}{3}(1+x)}{(1+x)(1-2x)}\G(x)= frac{1}{3}cdot frac{1}{1-(-x)}+frac{2}{3}cdot frac{1}{1-2x} \G(x)= sum_{n=0}^{ infty } frac 1 3cdot (-1)^n x^n+ sum_{n=0}^{ infty }frac 2 3cdot 2^n x^n= sum_{n=0}^{ infty }left( frac 1 3cdot (-1)^n+frac 2 3cdot 2^n
ight)x^n\ T(n)=frac 1 3cdot (-1)^n+frac 2 3cdot 2^n}\)
Kluczowe były w tym rozwiązaniu dwie rzeczy:
wykorzystanie wzoru na sumę szeregu geometrycznego
\(\displaystyle{ sum_{n=0}^{ infty } ax^{n}= frac{a}{1-x}, |x|<1}\)
oraz rozkład na ułamki proste (ten ułamek z \(\displaystyle{ frac{1}{(1+x)(1-2x)}}\)), patrz:
298450.htm