Rekurencja liniowa niejednorodna - funkcja tworząca

[conqueror]

Dany jest ciąg rekurencyjny \(\displaystyle{ (a_{n})}\), w którym
\(\displaystyle{ a_{0} = 1}\)

\(\displaystyle{ a _{1} = 2}\)

\(\displaystyle{ a_{n} + a_{n-1} - 6 a_{n-2} = 20}\) dla \(\displaystyle{ n \ge 2}\)

Za pomocą funkcji tworzącej wyznacz jawny wzór na n-ty wyraz ciągu.

Czy ktoś byłby w stanie mi pomóc? Nie wiem jak się za to zabrać...

[Premislav]

Przekształcamy:
\(\displaystyle{ a_n=-a_{n-1}+6a_{n-2}+20\ sum_{n=2}^{ infty }a_n x^n= - sum_{n=2}^{ infty }a_{n-1}x^n+ 6sum_{n=2}^{ infty }a_{n-2}x^n +20 sum_{n=2}^{ infty }x^n\sum_{n=2}^{ infty }a_n x^n= - xsum_{n=2}^{ infty }a_{n-1}x^{n-1}+ 6x^2sum_{n=2}^{ infty }a_{n-2}x^{n-2} +20 sum_{n=2}^{ infty }x^n}\)
Oznaczmy teraz \(\displaystyle{ S(x)= sum_{n=0}^{ infty }a_n x^n}\)
Wtedy mamy
\(\displaystyle{ sum_{n=2}^{ infty }a_n x^n=S(x)-a_1 x-a_0\-x sum_{n=2}^{ infty }a_{n-1}x^{n-1}=-xleft(S(x)-a_0
ight)\ 6x^2sum_{n=2}^{ infty }a_{n-2}x^{n-2}=6x^2 S(x)}\)
Ponadto ze wzoru na sumę szeregu geometrycznego:
\(\displaystyle{ 20 sum_{n=2}^{ infty }x^n= frac{20x^2}{1-x}, |x|<1}\)
Zbierając to do kupy, otrzymujemy
\(\displaystyle{ S(x)-a_1 x-a_0=-xS(x)+xa_0+6x^2S(x)+ frac{20x^2}{1-x} \ S(x)left( 6x^2-x-1
ight)=-x(a_0+a_1)-a_0- frac{20x^2}{1-x}\ S(x)= frac{-x(a_0+a_1)-a_0- frac{20x^2}{1-x}}{6x^2-x-1}}\)
Wstawiając \(\displaystyle{ a_0=1, a_1=2:}\)
\(\displaystyle{ S(x)= frac{-3x-1- frac{20x^2}{1-x}}{6x^2-x-1}= frac{-3x+3x^2+x-1-20x^2}{(6x^2-x-1)(1-x)}= frac{-17x^2-2x-1}{6(1-x)left(x+frac 1 3
ight)left( x-frac 1 2
ight) }\S(x)= frac{17x^2+2x+1}{(1-x)left( 3x+1
ight)left( 1-2x
ight) }= frac{A}{1-x}+ frac{B}{1+3x } + frac{C}{1-2x}}\)
Czyli wykonujemy rozkład na ułamki proste:
298450.htm
A więc otrzymujemy układ równań
\(\displaystyle{ egin{cases} -3C+2B-6A=17 \2C-3B+A=2 \C+B+A=1 end{cases}}\)
Rozwiąż go ulubioną metodą, wolfram twierdzi, że wychodzi tak:

Kod: Zaznacz cały

https://www.wolframalpha.com/input/?i=solve+-3C%2B2B-6A%3D17+%262C-3B%2BA%3D2%26C%2BB%2BA%3D1

Potem rozwijasz poszczególne ułamki w szeregi potęgowe:
\(\displaystyle{ S(x)=A sum_{n=0}^{ infty }x^n+B sum_{n=0}^{ infty }(-3)^n x^n+C sum_{n=0}^{ infty } 2^n x^n}\)
i \(\displaystyle{ a_n}\) to jest współczynnik przy \(\displaystyle{ x^n}\), czyli:
\(\displaystyle{ a_n= -5+ (-3)^n+ 5 cdot 2^n}\)

[GypsyHatter]

Mam trochę inny przykład, ale postępując zgodnie ze wskazówkami trafiam pod koniec na ułamek, którego chyba(?) nie można rozbić na ułamki proste, czy ktoś może pomóc?
\(\displaystyle{ a _{0} = 1\\
a _{1} = 1\\
a _{n} = a _{n-1} - a _{n-2} \\

\sum_{n=2}^{ \infty } a _{n}x^{n} = x \sum_{n=2}^{ \infty } a _{n-1}x ^{n-1} - x ^{2} \sum_{n=2}^{ \infty } a _{n-2}x ^{n-2}\\
\\S(x) - a _{1}x - a _{0} = x(S(x) - a _{0}) - x ^{2}S(x) \\
\\ \frac{1}{x ^{2} - x + 1} = S(x)}\)

[Premislav]

Obliczeń nie sprawdzałem, bo robię teraz inne zadanie, natomiast można sobie poradzić co najmniej na dwa sposoby:
1. Rozbić to całe \(\displaystyle{ \frac{1}{1-x+x^2}}\) na ułamki proste zespolone.
2. Policzyć to zupełnie inaczej, zauważając, że dla \(\displaystyle{ n\ge 2}\) jest
\(\displaystyle{ a_n=a_{n-1}-a_{n-2}\\a_{n+1}=a_n-a_{n-1}}\)
co po dodaniu stronami i skróceniu daje nam
\(\displaystyle{ a_{n+1}=-a_{n-2}, n \ge 2}\),
wystarczy jeszcze policzyć \(\displaystyle{ a_2=1}\) i dalej już łatwo napisać wzór na \(\displaystyle{ a_n}\)...

[GypsyHatter]

Miałeś rację z tym, żeby liczyć na liczbach zespolonych tylko teraz nie jestem pewien jak policzyć \(\displaystyle{ A}\) i \(\displaystyle{ B}\) mając:
\(\displaystyle{ A \cdot \left( \frac{1}{2} + \frac{ \sqrt{3} }{2}i \right) + B \cdot \left( \frac{1}{2} - \frac{ \sqrt{3} }{2}i \right) = 1}\)

[Janusz Tracz]

Liczby zespolone \(\displaystyle{ z_1}\) i \(\displaystyle{ z_2}\) są równe tylko wtedy gdy \(\displaystyle{ \Re (z_1)=\Re (z_2)}\) i \(\displaystyle{ \Im (z_1)=\Im (z_2)}\) porównaj więc te liczby a dostaniesz układ \(\displaystyle{ 2}\) liniowych z \(\displaystyle{ 2}\) niewiadomymi \(\displaystyle{ A}\) i \(\displaystyle{ B}\)

[GypsyHatter]

Czyli wychodzi:
\(\displaystyle{ \begin{cases} A = \frac{ \sqrt{3}i }{3} \\ B = -\frac{ \sqrt{3}i }{3} \end{cases}}\)
jak to teraz wszystko poskładać, żeby otrzymać wzór jawny?

[Premislav]

Nie wiem, czy tyle wychodzi, wybacz, ale nie będę poświęcał czasu na sprawdzanie obliczeń, możesz to łacno sprawdzić na wolframalpha.com…
Generalnie, jak masz już takie liczby zespolone \(\displaystyle{ A, B, C, D}\), że
\(\displaystyle{ S(x)=\frac{1}{1-x+x^2}= \frac{A}{x-C}+ \frac{B}{x-D}}\),
to rozwijasz te ułamki ze wzoru na sumę szeregu geometrycznego (przy odpowiednich założeniach),
tj.
\(\displaystyle{ \frac{A}{x-C}+ \frac{B}{x-D} =- \frac{A}{C} \cdot \frac{1}{1-\frac{1}{C} \cdot X}- \frac{B}{D} \cdot \frac{1}{1-\frac{1}{D}X}=\\= \sum_{n=0}^{ \infty }-AC^{-n-1}x^n+\sum_{n=0}^{ \infty }-BD^{-n-1}x^n=\\= \sum_{n=0}^{ \infty }\left(-AC^{-n-1}-BD^{-n-1} \right)x^n}\)