Postać zwarta rekurencji liniowej

[kocix]

Wyznaczyć postać zwartą ze względu na \(\displaystyle{ n}\) dla rekurencji liniowej:
\(\displaystyle{ a_{0} = 0\\
a _{1} = 1\\
a_{n} = 5a _{n-1} - 6 a_{n-2}}\)

[Premislav]

Metodą funkcji tworzących:
\(\displaystyle{ a_{n} = 5a _{n-1} - 6 a_{n-2}\\ \sum_{n=2}^{ \infty } a_n x^n=5x \sum_{n=2}^{ \infty }a_{n-1}x^{n-1}-6x^2 \sum_{n=2}^{ \infty }a_{n-2}x^{n-2}\\G(x)-a_1 x-a_0=5x\left( G(x)-a_0\right) -6x^2G(x)}\)
Podstawiając \(\displaystyle{ a_0=0, \ a_1=1}\) otrzymujemy:
\(\displaystyle{ G(x)-x=(5x-6x^2)G(x)\\G(x)= \frac{x}{6x^2-5x+1} \ (*)}\)
Dalej rozkładamy prawą stronę na ułamki proste i rozwijamy w szeregi geometryczne:
\(\displaystyle{ 6x^2-5x+1=6\left( x-\frac{5}{12}\right)^2-\frac{6}{144}=6\left( x-\frac 1 3\right)\left(x-\frac 1 2 \right)\\
G(x)= \frac{A}{3\left(x-\frac 1 3\right)} + \frac{B}{2\left( x-\frac 1 2\right) }\\ G(x)=\frac{A}{3x-1}+\frac{B}{2x-1}}\)
Sprowadzając po prawej do wspólnego mianownika i porównując otrzymany licznik z licznikiem po prawej stronie w \(\displaystyle{ (*)}\), dostajemy, porównując współczynniki przy odpowiednich potęgach:
\(\displaystyle{ \begin{cases}2A+3B=1 \\ -A-B=0\end{cases}}\)
Mnożąc drugie równanie stronami przez dwa i dodając do pierwszego, mamy \(\displaystyle{ B=1}\), zatem \(\displaystyle{ A=-1}\),
Czyli:
\(\displaystyle{ G(x)= \frac{1}{2x-1}-\frac{1}{3x-1}=- \frac{1}{1-2x}+ \frac{1}{1-3x}\\ G(x)= \sum_{n=0}^{ \infty }3^n x^n- \sum_{n=0}^{ \infty } 2^n x^n, \ |x|<\frac 1 3}\)
Patrząc na współczynniki przy \(\displaystyle{ x^n}\) w \(\displaystyle{ G(x)}\), widzimy, że
\(\displaystyle{ a_n=3^n-2^n}\).

[popiszsieplay]

Czy mógłbyś wytłumaczyć, jak z linijki
\(\displaystyle{ G(x) = \sum_{n=0}^{\infty} 3^n x^n - \sum_{n=0}^{\infty} 2^n x^n}\)
przeszedłeś do
\(\displaystyle{ a_n = 3^n - 2^n}\)?
Czy to się jakoś "fachowo" nazywa? Powołałeś się na jakiś wzór?

Ps. Mam nadzieję, że wątek nie umarł...

[Premislav]

\(\displaystyle{ G(x) = \sum_{n=0}^{\infty} 3^n x^n - \sum_{n=0}^{\infty} 2^n x^n=\\= \sum_{n=0}^{ \infty } (3^n-2^n)x^n}\)
No i dalej to jest kwestia definicji funkcji tworzącej. Funkcją tworzącą ciągu
\(\displaystyle{ (a_n)_{n\ge 0}}\) jest właśnie \(\displaystyle{ \sum_{n=0}^{ \infty }a_n x^n}\).
(oczywiście ta suma zwykle nie zbiega dla dowolnego \(\displaystyle{ x}\), ale w rozważaniach związanych z funkcjami tworzącymi milcząco przyjmujemy, że operujemy wewnątrz przedziału zbieżności takiego szeregu potęgowego, wtedy też możemy różniczkować i całkować wyraz po wyrazie itd.).

Tak formalnie trzeba jeszcze wiedzieć, że funkcja tworząca jednoznacznie wyznacza ciąg, ale to się zwykle przyjmuje za znaną wiedzę (a wynika to chociażby z teorii dotyczącej szeregów Taylora).