Rozwiązywanie rekurencji za pomocą funkcji tworzących

[f33tl0v3r]

Witam,
mam problem z poniższym zadaniem:

4. Rozwiązać poniższe zależności rekurencyjne (wprowadzając pomocnicze ciągi, stosując funkcje tworzące, itp.):

\(\displaystyle{ a) a _{n+2} = 2a _{n+1} ^{2} · a _{n} ^{3} , a _{1} = a _{0} = 1 }\)

\(\displaystyle{ b) b _{n+1} = 2(n + 1)b _{n} + 3(n + 1)!, b _{0} = 1. }\)

Próbowałem zacząć od podpunktu a) w taki sposób, że wyprowadziłem sobie wzór na \(\displaystyle{ f''(x) = \sum_{n=0}^{ \infty} (n+1) ^{2} \cdot a_{n+2} \cdot X ^{n} }\) i wstawiłem do niego wzór na \(\displaystyle{ a _{n+2}: \sum_{n=0}^{ \infty} (n+1) ^{2} \cdot 2a _{n+1} ^{2} · a _{n} ^{3} \cdot X ^{n} }\).

Niestety tutaj utknąłem i nie wiem jak dalej postępować, żeby otrzymać rozwiązanie. Proszę o pomoc.

[a4karo]

a) zlogarytmuj obie strony

[f33tl0v3r]

Nie bardzo wiem co dalej z tym zrobić po zlogarytmowaniu.

[Premislav]

Podstaw \(\displaystyle{ c_{n}=\ln a_{n}+\frac{1}{4}\ln 2}\), a dostaniesz rekurencję liniową jednorodną
\(\displaystyle{ c_{n+2}=2c_{n+1}+3c_{n}}\)
Tę już bez problemu rozwiążesz za pomocą funkcji tworzących (można też np. użyć równania charakterystycznego).

Dodano po 4 minutach 53 sekundach:
Jeśli chodzi o podpunkt b), ja bym podzielił stronami przez \(\displaystyle{ (n+1)!}\), a potem podstawił \(\displaystyle{ d_{n}=\frac{b_{n}}{n!}+3}\), dostaniesz wtedy po prostu ciąg geometryczny \(\displaystyle{ d_{n+1}=2d_{n}}\).

[f33tl0v3r]

W jaki sposób otrzymałeś ten ciąg \(\displaystyle{ c_n}\) w podpunkcie a)? Mógłbyś to rozpisać?

Dodano po 37 minutach 45 sekundach:
Wyszła mi odpowiedź \(\displaystyle{ f(x) = \frac{x ^{2} }{(1-2x-3x^{2})(1-x)} }\). Czy jest ona poprawna?

[Premislav]

Po zlogorytmowaniu stronami, zgodnie z sugestią a4karo, dostajesz postać
\(\displaystyle{ \ln a_{n+2}=\ln 2+2\ln a_{n+1}+3\ln a_{n}}\)
Gdybyś teraz podstawił \(\displaystyle{ c_{n}=\ln a_{n}}\), to dostałbyś równanie liniowe niejednorodne
\(\displaystyle{ c_{n+2}=\ln 2+2c_{n+1}+3c_{n}}\)
To też się daje rozwiązać funkcjami tworzącymi, ale wolimy zwykle sobie upraszczać życie. Zamiast tego można więc podstawić
\(\displaystyle{ c_{n}=\ln a_{n}+x}\), gdzie stała \(\displaystyle{ x\in \RR}\) jest tak dobrana, by sprowadzić równanie do jednorodnego.
Zobaczmy:
podstawiamy za \(\displaystyle{ \ln a_{n}, \ c_{n}-x}\) i mamy
\(\displaystyle{ c_{n+2}-x=\ln 2+2(c_{n+1}-x)+3(c_{n}-x)\\ c_{n+2}+4x-\ln 2=2c_{n+1}+3c_{n}}\)
chcemy, by zaszło \(\displaystyle{ 4x-\ln 2=0}\), stąd właśnie \(\displaystyle{ x=\frac{1}{4}\ln 2}\).

~~~~~~~~~~~~~~~~~~~~~~~~

Co do Twojej „odpowiedzi", nie jest to z pewnością finalna odpowiedź do zadania, bo tam pytano o wzór ciągu. To, co znalazłeś, to wzór funkcji tworzącej (a jeszcze trzeba rozwinąć w szereg potęgowy, odczytać wzór ciągu \(\displaystyle{ c_{n}}\) i wrócić z podstawieniami!), i wkradł się tu pewien błąd, ponieważ jeśli \(\displaystyle{ c_{n}=\ln a_{n}+\frac{1}{4}\ln 2, \ a_{0}=a_{1}=1}\), to \(\displaystyle{ c_{0}=c_{1}=\ln 1+\frac{1}{4}\ln 2=\frac{1}{4}\ln 2}\).
Nie będę tego za Ciebie rozwiązywał, bo jest to dość mechaniczne i mi się nie chce.
Po poprawieniu wzoru funkcji tworzącej ciągu \(\displaystyle{ c_{n}}\), zostaje jeszcze rozkład na ułamki proste i rozwinięcie w szereg potęgowy. W razie problemów z rozkładem, patrz tutaj: Rozkład na ułamki proste - przykłady