Funkcja tworząca ciągu rekurencyjnego

[RippeR37]

Potrzebuję pomocy z funkcją tworzącą następującego ciągu:

\(\displaystyle{ a_{0} = 1}\)
\(\displaystyle{ a_{n+1} = \sum_{k=0}^{n} \frac{a_{n-k}}{k!}}\)

O ile wzory nie zawierały tak skomplikowanych sum (wszystkie poprzednie elementy) dawałem sobie radę np. z wzorami:

\(\displaystyle{ a_{n+2} = A \cdot a_{n+1} + B \cdot a_{n} + C}\)
Ale mając tak dużo wyrazów jakoś nie potrafię do tego podejść...

Wdzięczny będę za zarówno łatwe w zrozumieniu wskazówki jak i rozwiązanie

[Qń]

Oznaczmy sobie \(\displaystyle{ b_n=\frac{1}{n!}}\) - oczywiście wtedy funkcja tworząca tego ciągu to \(\displaystyle{ B(x) =e^x}\). Przyjmijmy też standardową konwencję, że \(\displaystyle{ c_n}\) dla \(\displaystyle{ n<0}\) jest równe zero dla dowolnego ciągu.

Naszą rekurencję można zapisać jako:
\(\displaystyle{ a_n = \sum_{k=0}^{n-1}b_ka_{n-1-k}}\) dla \(\displaystyle{ n\ge 1}\)

Żeby wzór działał dla dowolnych \(\displaystyle{ n}\), użyjmy notacji Iversona:
\(\displaystyle{ a_n = \sum_{k}b_ka_{n-1-k} + [n=0]}\)
i pomnóżmy przez \(\displaystyle{ x^n}\) oraz zsumujmy stronami po \(\displaystyle{ n}\):
\(\displaystyle{ A(x)= \sum _{n,k}b_ka_{n-1-k}x^n+1 =\\ = \left( \sum_{k}b^kx^k\right) \cdot \left( x\sum_{n} a_{n-1-k}x^{n-k-1}\right) +1 =\\ = B(x)\cdot x \cdot A(x)+1 = xe^xA(x)+1}\)
skąd rzecz jasna:
\(\displaystyle{ A(x) = \frac{1}{1-xe^x}}\)

Q.

[RippeR37]

Dzięki wielkie. Mógłbym zapytać, czy to:
\(\displaystyle{ A(x)= \sum _{n,k}b_ka_{n-1-k}x^n+1}\)
Jest równoznaczne zapisowi:
\(\displaystyle{ A(x) = \ \sum_{n=0}^{\infty} ( \sum_{k=0}^{n-1} ( b_ka_{n-1-k}x^n ) )+1}\)
Bo rozumiem, że ta jedynka jest poza sumą już? (wtedy ma sens, bo 1 dochodzi tylko do wyrazu, gdy n=0), w przeciwynm razie (jeśli była by w sumie) to było by trochę dla mnie bez sensu?).

Rozumiem że nasze rozbicie wtedy na iloczyn dwóch sum pochodzi z jakby odwrotnego przebiegu gdybyśmy mnożyli dwie funkcje tworzące ze sobą, to mamy wtedy sumę sum? Tylko co się dzieje wtedy z \(\displaystyle{ x^n}\), gdyż w podanym rozwiązaniu jakoś to fajnie wyszło, a w ogólnej sytuacji jak na to patrzeć? Po wymnożeniu z obu sum x'y mają dać potęgę \(\displaystyle{ n}\) ? Bo w rozwiązaniu jest:

\(\displaystyle{ x^{k} \cdot x \cdot x^{n-k-1}}\)

[Qń]

Dzięki wielkie. Mógłbym zapytać, czy to:
\(\displaystyle{ A(x)= \sum _{n,k}b_ka_{n-1-k}x^n+1}\)
Jest równoznaczne zapisowi:
\(\displaystyle{ A(x) = \ \sum_{n=0}^{\infty} ( \sum_{k=0}^{n-1} ( b_ka_{n-1-k}x^n ) )+1}\)

Tak, a wynika to z przyjętej konwencji, że wyrazy ciągów o ujemnych indeksach są równe zero. Stąd możemy śmiało sumować po wszystkich liczbach całkowitych, bo na przykład \(\displaystyle{ b_{-1}a_n}\) jest równe zero dla dowolnego \(\displaystyle{ n}\).

Bo rozumiem, że ta jedynka jest poza sumą już?

Oczywiście, przecież w wyjściowej sytuacji \(\displaystyle{ [n=0]}\) jest poza sumą, stąd też po wymnożeniu przez \(\displaystyle{ x^n}\) i zsumowaniu po \(\displaystyle{ n}\) wyrażenie \(\displaystyle{ \sum_n [n=0]x^n= 1}\) jest poza pierwszą sumą.

Rozumiem że nasze rozbicie wtedy na iloczyn dwóch sum pochodzi z jakby odwrotnego przebiegu gdybyśmy mnożyli dwie funkcje tworzące ze sobą, to mamy wtedy sumę sum?

Nie wiem czy dobrze rozumiem, ale mniej więcej tak.

Tylko co się dzieje wtedy z \(\displaystyle{ x^n}\), gdyż w podanym rozwiązaniu jakoś to fajnie wyszło, a w ogólnej sytuacji jak na to patrzeć?

W ogólnej sytuacji analogiczne postępowanie nie działa - można tak robić tylko wtedy gdy mamy do czynienia ze splotem ciągów, tak jak w naszym zadaniu.

Q.