szukanie zaawansowane
 [ Posty: 14 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 cze 2015, o 21:09 
Użytkownik

Posty: 9
Lokalizacja: polska
Witam,
Mam równanie rekurencyjne postaci
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:

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)

1+x=-x^2G(x)-xG(x)+G(x)

G(x)(-x^2-x+1)=1+x

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

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

Q(x)=x^2-x-1

\Delta=5

c_1= \frac{1- \sqrt{5} }{2}

c_2= \frac{1+ \sqrt{5} }{2}

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

Dziękuję za pomoc !
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2015, o 22:14 
Użytkownik
Avatar użytkownika

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

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
Góra
Kobieta Offline
PostNapisane: 3 cze 2015, o 22:24 
Użytkownik
Avatar użytkownika

Posty: 2505
Możesz śmiało rozwijać, bo błędu nie ma - początek szeregu to 1+2 x+3 x^2+5 x^3+8 x^4+13 x^5+21 x^6 + \dots.
Góra
Mężczyzna Offline
PostNapisane: 3 cze 2015, o 22:43 
Użytkownik

Posty: 9
Lokalizacja: polska
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... :(
Góra
Kobieta Offline
PostNapisane: 3 cze 2015, o 22:51 
Użytkownik
Avatar użytkownika

Posty: 2505
Mianownik się rozkłada: -\frac{1}{4} \left(-2 x+\sqrt{5}-1\right) \left(2 x+\sqrt{5}+1\right). Pierwszym krokiem będzie rozłożenie ułamka...
Góra
Mężczyzna Offline
PostNapisane: 4 cze 2015, o 09:08 
Użytkownik

Posty: 9
Lokalizacja: polska
A jak do tego doszłaś bo mi wyszło coś takiego:
(1- \frac{1+\sqrt{5}}{2} x)(1-\frac{1-\sqrt{5}}{2}x)
Góra
Kobieta Offline
PostNapisane: 4 cze 2015, o 10:17 
Użytkownik
Avatar użytkownika

Posty: 2505
Sprawdź, czy to nie jest to samo przez wymnożenie. Zauważ, że czwórkę mogę wciągnąć do nawiasów.
Góra
Mężczyzna Offline
PostNapisane: 4 cze 2015, o 10:43 
Użytkownik

Posty: 9
Lokalizacja: polska
no nie wyjdzie jak wymnoże bo przy \sqrt{5} zostanie x którego nie ma u Ciebie
Góra
Kobieta Offline
PostNapisane: 4 cze 2015, o 11:02 
Użytkownik
Avatar użytkownika

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

-\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.
Góra
Mężczyzna Offline
PostNapisane: 4 cze 2015, o 12:13 
Użytkownik

Posty: 9
Lokalizacja: polska
tylko co z tym dalej ... ? bo tak jak pisałem szeregi to jakaś czarna magia dla mnie ...
Góra
Kobieta Offline
PostNapisane: 4 cze 2015, o 12:50 
Użytkownik
Avatar użytkownika

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

\frac 1 {1-x} = \sum_{k=0}^\infty  x^k.
Góra
Mężczyzna Offline
PostNapisane: 4 cze 2015, o 13:34 
Użytkownik

Posty: 9
Lokalizacja: polska
a jak wyliczyć A i B ? nie wiem też co zrobić z licznikiem 1 + x
Góra
Kobieta Offline
PostNapisane: 4 cze 2015, o 14:01 
Użytkownik
Avatar użytkownika

Posty: 2505
Napisz rozkład na ułamki, wymnóż przez wspólny mianownik, porównaj wyraz stojące przy x, potem wolny.
Góra
Mężczyzna Offline
PostNapisane: 4 cze 2015, o 17:20 
Użytkownik

Posty: 9
Lokalizacja: polska
Wyszło mi coś takiego, czy to ma sens ?

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

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

1+x=A(1-p_2x)+B(1-p_1x) = A+B-x(Ap_2+Bp_1)

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

B = 1 - A

Ap_2+p_1-Ap_1=-1

A(p_2-p_1) = -1-p_1

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! :(
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 14 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozwiazywanie rownania z uzyciem wzoru Newtona  birdy1986  7
 zamiana ciagu rekurencyjnego na ogolny  eoor  1
 Mały problem z funkcją tworzącą  kogutto  1
 m dyskretna - Ile jest całkowitych rozwiązań równania .  torbol  1
 Kombinatoryka (rozwiąż równania)  allexx  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl