Postać zwarta równania rekurencyjnego funkcja tworząca

sonic88 · Post autor: **sonic88** » 3 cze 2015, o 21:09

Witam,
Mam równanie rekurencyjne postaci
\(\displaystyle{ T(n)\begin{cases} 1 : n = 0 \\ 2 : n = 1 \\ T(n-1) + T(n-2) : n > 1 \end{cases}}\)

Jest to w sumie "przesunięty" fibonacci. Mam wyznaczyć postać zwartą wykorzystują funkcję tworzącą.

To do czego doszedłem obecnie to:

\(\displaystyle{ G(x) = \sum_{n \ge 0}^{}T(n)x^n=
T(0)x^n+T(1)x^1+ \sum_{n\ge2}^{}T(n)x^n=
1+2x+ \sum_{n\ge2}^{}(T(n-1)+T(n-2))x^n=...=
1+2x+\sum_{n\ge1}^{}T(n)x^n+x^2\sum_{n\ge0}T(nn)x^n=
1+2x+x(G(x)-1)+x^2G(x)=1+2x+xG(x)-x+x^2G(x)}\)

\(\displaystyle{ 1+x=-x^2G(x)-xG(x)+G(x)}\)

\(\displaystyle{ G(x)(-x^2-x+1)=1+x}\)

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

Wiem że muszę policzyć dla wielomianu lustrzanego z mianownika:

\(\displaystyle{ Q(x)=x^2-x-1}\)

\(\displaystyle{ \Delta=5}\)

\(\displaystyle{ c_1= \frac{1- \sqrt{5} }{2}}\)

\(\displaystyle{ c_2= \frac{1+ \sqrt{5} }{2}}\)

Pytanie czy to wszystko jest dobrze i co z tym dalej?

Dziękuję za pomoc !

jutrvy · Post autor: **jutrvy** » 3 cze 2015, o 22:14

Jeśli w rachunkach nie ma błędu (mam problem z ich czytaniem), to do momentu

\(\displaystyle{ G(x)= \frac{1+x}{-x^2-x+1}}\) wygląda dobrze. Teraz funkcję, która jest po prawej stronie równości musisz rozwinąć w szereg potęgowy. Jak to zrobisz, to wystarczy przyrównać współczynnikki po obu stronach i dostaniesz coś w stylu wzoru Binneta.

Pozdrawiam

Medea 2 · Post autor: **Medea 2** » 3 cze 2015, o 22:24

Możesz śmiało rozwijać, bo błędu nie ma - początek szeregu to \(\displaystyle{ 1+2 x+3 x^2+5 x^3+8 x^4+13 x^5+21 x^6 + \dots}\).

sonic88 · Post autor: **sonic88** » 3 cze 2015, o 22:43

Dzięki za odpowiedź.
To te pierwiastki nie są do niczego potrzebne ?
Coś mi Pani profesor mówiła że muszę to rozbić na ułamki proste. O szeregach nie mam zbytnio pojęcia...

Medea 2 · Post autor: **Medea 2** » 3 cze 2015, o 22:51

Mianownik się rozkłada: \(\displaystyle{ -\frac{1}{4} \left(-2 x+\sqrt{5}-1\right) \left(2 x+\sqrt{5}+1\right)}\).

sonic88 · Post autor: **sonic88** » 4 cze 2015, o 09:08

A jak do tego doszłaś bo mi wyszło coś takiego:
\(\displaystyle{ (1- \frac{1+\sqrt{5}}{2} x)(1-\frac{1-\sqrt{5}}{2}x)}\)

Medea 2 · Post autor: **Medea 2** » 4 cze 2015, o 10:17

Sprawdź, czy to nie jest to samo przez wymnożenie. Zauważ, że czwórkę mogę wciągnąć do nawiasów.

sonic88 · Post autor: **sonic88** » 4 cze 2015, o 10:43

no nie wyjdzie jak wymnoże bo przy \(\displaystyle{ \sqrt{5}}\) zostanie x którego nie ma u Ciebie

Medea 2 · Post autor: **Medea 2** » 4 cze 2015, o 11:02

Okej, dobrze rozłożyłam mianownik (z dokładnością do znaku). Tobie wyszło to samo, tylko z plusem.

\(\displaystyle{ -\frac{1}{4} \left(-2 x+\sqrt{5}-1\right) \left(2 x+\sqrt{5}+1\right) = - \frac 1 4 \left(5 - (2x+1)^2 \right) = -1 + x + x^2.}\)

sonic88 · Post autor: **sonic88** » 4 cze 2015, o 12:13

tylko co z tym dalej ... ? bo tak jak pisałem szeregi to jakaś czarna magia dla mnie ...

Medea 2 · Post autor: **Medea 2** » 4 cze 2015, o 12:50

Rozłóż \(\displaystyle{ G(x)}\) na sumę dwóch ułamków (o licznikach \(\displaystyle{ A}\), \(\displaystyle{ B}\)) o mianownikach takich, jak napisałeś. Dalej będzie już łatwo, trzeba będzie wykorzystać własność szeregu geometrycznego:

\(\displaystyle{ \frac 1 {1-x} = \sum_{k=0}^\infty x^k.}\)

sonic88 · Post autor: **sonic88** » 4 cze 2015, o 13:34

a jak wyliczyć A i B ? nie wiem też co zrobić z licznikiem \(\displaystyle{ 1 + x}\)

Medea 2 · Post autor: **Medea 2** » 4 cze 2015, o 14:01

Napisz rozkład na ułamki, wymnóż przez wspólny mianownik, porównaj wyraz stojące przy \(\displaystyle{ x}\), potem wolny.

sonic88 · Post autor: **sonic88** » 4 cze 2015, o 17:20

Wyszło mi coś takiego, czy to ma sens ?

\(\displaystyle{ p_1 = \frac{1+\sqrt{5}}{2}}\)
\(\displaystyle{ p_1 = \frac{1-\sqrt{5}}{2}}\)

\(\displaystyle{ G(x) = \frac{x +1}{1-x-x^2} = \frac{A}{1-p_1} + \frac{B}{1-p_2}}\)

\(\displaystyle{ 1+x=A(1-p_2x)+B(1-p_1x) = A+B-x(Ap_2+Bp_1)}\)

\(\displaystyle{ \begin{cases} A+B=1\\ Ap_2+Bp_1=-1 \end{cases}}\)

\(\displaystyle{ B = 1 - A}\)

\(\displaystyle{ Ap_2+p_1-Ap_1=-1}\)

\(\displaystyle{ A(p_2-p_1) = -1-p_1}\)

\(\displaystyle{ A= \frac{p_1+1}{p_1-p_2}}\)

I co z tym dalej ? bo jak wszystko po podstawiam i za x wstawię jakaś liczbę to nie wychodzi to co powinno .-- 5 cze 2015, o 13:39 --Czy ktoś wie co z tym zrobić?

Pomocy!