(nie)ciekawa rekurencja

[admi99]

Witajcie,
proszę o pomoc w rozwiązaniu rekurencji za pomocą funkcji tworzących:

\(\displaystyle{ \begin{cases} g_{0}=0\\g_{1}=1\\g_{n}=g_{n-1}+g_{n-2}+...+g_{0}\end{cases}}\)


pierwsze kroki w lateX'ie

[max]

W LaTeX-u...

Zauważ, że:
\(\displaystyle{ g_{n+2} =
g_{n + 1} + g_{n} + g_{n - 1} + \ldots + g_{0} =
g_{n + 1}+ g_{n} + g_{n} = g_{n + 1} + 2g_{n}}\)
Dalej powinno pójść łatwo...

[admi99]

jak tutaj użyć wzoru :
G(z)=\(\displaystyle{ \sum_{n} g_{n}z^n}\)

[max]

\(\displaystyle{ G(z) = \sum_{n=0}^{\infty} g_{n}z^{n} = g_{0} + g_{1}z + \sum_{n=0}^{\infty} g_{n+2}z^{n+2} =\\
= z + z^{2}\sum_{n=0}^{\infty} ft(g_{n + 1} + 2g_{n}\right)z^{n} =\\
= z + z\sum_{n=0}^{\infty} g_{n + 1}z^{n + 1} + 2z^{2}\sum_{n=0}^{\infty} g_{n}z^{n} =\\
= z + z\sum_{n=0}^{\infty} g_{n}z^{n} - z\cdot g_{0} + 2z^{2}\sum_{n=0}^{\infty} g_{n}z^{n} =\\
= z + zG(z) - 0 + 2z^{2}G(z)}\)
Z tego wyznaczasz \(\displaystyle{ G(z)}\), rozwalasz na ułamki proste, rozwijasz w szereg potęgowy i sprawdzasz współczynnik przy \(\displaystyle{ z^{n}}\).

[admi99]

nie rozumiem tylko przejścia:

z\(\displaystyle{ \sum_{n\geqslant0} g_{n+1}z^{n+1}}\) w \(\displaystyle{ \sum_{n\geqslant0} g_{n}z^{n} - z*g_{0}}\)

[max]

\(\displaystyle{ \sum_{n qslant 0}g_{n + 1}z^{n + 1} = g_{1}z^{1} + g_{2}z^{2} + \ldots =\\
= -g_{0}z^{0} + g_{0}z^{0} + g_{1}z^{1} + g_{2}z^{2} + \ldots = \sum_{n qslant 0}g_{n}z^{n} - g_{0}}\)
I teraz mnożąc tę tożsamość stronami razy \(\displaystyle{ z}\) otrzymujemy co trzeba.

[admi99]

trzeba chyba wcześniej zapisać
\(\displaystyle{ \ g_{n}= g_{n-1} + ... + [n=1]}\)

i na końcu wynik :

\(\displaystyle{ \ G(z)=\frac {2z}{1-z-z^{2}}}\)

tylko co z nim dalej?

[max]

wystarczyłoby rozbić na ułamki proste i rozwinąć w szereg... tylko że...
... właśnie znalazłem błąd w swoim pierwszym poście, na którym opiera się rozwiązanie ^^
(tożsamość nie zachodzi dla \(\displaystyle{ n = 1}\))
Sorki za głupi błąd jutro rano poprawię, bo teraz już nie mam czasu
Pozdrawiam

[ Dodano: 20 Czerwca 2007, 08:23 ]
Od nowa:

Pierwszy sposób (analogicznie jak wyżej tylko bez błędów):
Dla \(\displaystyle{ n > 1}\) jest (bezpośrednio z określenia rekurencji):
\(\displaystyle{ g_{n} = g_{n-1}+\ldots + g_{0}}\)
Stąd:
\(\displaystyle{ g_{n + 1} = g_{n} + g_{n-1} + \ldots + g_{0} = g_{n} + g_{n} = 2g_{n}}\)
Bierzemy funkcję tworzącą:
\(\displaystyle{ G(z) = \sum_{n=0}^{\infty}g_{n}z^{n} = 0 + \sum_{n=0}^{\infty}g_{n+1}z^{n+1}=\\
= g_{1}z + g_{2}z^{2} + \sum_{n=2}^{\infty}g_{n+1}z^{n+1} =\\
= z + z^{2} + \sum_{n=2}^{\infty}2g_{n}z^{n+1} =\\
= z + z^{2} + 2z\sum_{n=2}^{\infty}g_{n}z^{n} =\\
= z + z^{2} + 2z\left(\sum_{n = 0}^{\infty}g_{n}z^{n} - g_{0}z^{0} - g_{1}z\right)=\\
= z + z^{2} + 2z\left(G(z) - 0 - z)= z - z^{2} + 2zG(z)}\)
Stąd otrzymujemy:
\(\displaystyle{ G(z) = \frac{z - z^{2}}{1 - 2z} = \frac{\frac{1}{2}z(1 - 2z) - \frac{1}{4}(1 - 2z) + \frac{1}{4}}{1 - 2z} =\\
= \frac{1}{2}z - \frac{1}{4} + \frac{1}{4}\cdot\frac{1}{1 - 2z} = \frac{1}{2}z - \frac{1}{4} + \frac{1}{4}\sum_{n= 0}^{\infty}2^{n}z^{n}}\)
A zatem:
\(\displaystyle{ \left\{\begin{array}{l}g_{0} = 0\\g_{1} = 1\\g_{n} =\frac{1}{4}\cdot 2^{n} = 2^{n - 2}, \ \mbox{dla} \ n > 1 \end{array}}\)

Drugi sposób:
Bezpośrednio z określenia rekurencji, dla \(\displaystyle{ n > 1}\):
\(\displaystyle{ g_{n} = g_{n-1} + \ldots + g_{0} = \sum_{k = 0}^{n-1}g_{k}}\)
Stąd, korzystając z postaci Cauchy'ego iloczynu szeregów, tzn:
\(\displaystyle{ \sum_{n = 0}^{\infty}\sum_{k = 0}^{n}a_{n - k}b_{k} = \left(\sum_{n = 0}^{\infty}a_{n}\right)\cdot \left(\sum_{n=0}^{\infty}b_{n}\right)}\)
otrzymujemy:
\(\displaystyle{ G(x) = \sum_{n = 0}^{\infty}g_{n}z^{n} = g_{0} + g_{1}z + \sum_{n=2}^{\infty}g_{n}z^{n}=\\
=0 + z + \sum_{n=2}^{\infty}\sum_{k = 0}^{n-1}g_{k}z^{n} = \\
= z + \sum_{n=2}^{\infty}\sum_{k = 0}^{n-1}\left(g_{k}z^{k}\right)z^{n - k} =\\
= z + \sum_{n=2}^{\infty}\sum_{k = 0}^{n}\left(g_{k}z^{k}\right)z^{n - k} - \sum_{n = 2}^{\infty}g_{n}z^{n} =\\
= z + \sum_{n=0}^{\infty}\sum_{k = 0}^{n}\left(g_{k}z^{k}\right)z^{n - k} - (g_{0} + g_{0} + g_{1}z) - \sum_{n = 0}^{\infty}g_{n}z^{n} + g_{0} + g_{1}z =\\
= z + \left(\sum_{n = 0}^{\infty}g_{n}z^{n} \right)\cdot \left(\sum_{n=0}^{\infty}z^{n}\right) -\sum_{n = 0}^{\infty}g_{n}z^{n} =\\
= z + \frac{G(z)}{1 - z} - G(z)}\)
Stąd otrzymujemy:
\(\displaystyle{ \left(2 - \frac{1}{1 - z}\right)G(z) = z \\
\frac{1 - 2z}{1 - z}G(z) = z\\
G(z) = \frac{z(1 - z)}{1 - 2z}}\)
Dalsza część tak jak w sposobie pierwszym.

Jeszcze raz przepraszam za te bzdury, które napisałem na początku... to nie powinno się zdarzyć...

Pozdrawiam

[admi99]

co się dzieje z \(\displaystyle{ \frac {1}{2}z-}\) \(\displaystyle{ \frac{1}{4}}\)\(\displaystyle{ +\frac{1}{4}}\)\(\displaystyle{ \sum_{n} 2^{n}z^{n}}\)

wynik w książce jest \(\displaystyle{ 2^{n-1}}\) ale tam jest dużo błędów (:

[max]

\(\displaystyle{ G(z) = \frac{1}{2}z -\frac{1}{4} + \frac{1}{4}\sum_{n = 0}^{\infty} 2^{n}z^{n}= 0 + z + \sum_{n= 2}^{\infty}2^{n - 2}z^{n}}\)
I skoro mamy już funkcję tworzącą rozwiniętą w szereg potęgowy to wzór na wyraz ogólny ciągu dostajemy ustalając wzór na współczynnik stojący przy n-tej potędze \(\displaystyle{ z}\)

A wzór z książki jest niedobry, bo np dla \(\displaystyle{ n = 2}\) jest z definicji rekurencyjnej:
\(\displaystyle{ g_{2} = g_{1} + g_{0} = 1}\)
a wg podanego wzoru byłoby:
\(\displaystyle{ g_{2} = 2^{2 - 1} = 2}\)
chyba, że to ma być wzór na \(\displaystyle{ g_{n+1}}\)