szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 lis 2017, o 12:32 
Użytkownik

Posty: 31
Lokalizacja: Kraków
Wykaż, że V _{n} zadany rekurencyjnie
V _{0}=1
V _{1}=3
V _{n+1}=V _{n}+V _{n-1}, n \ge2

spełnia zależność
V _{n}=F _{n+1}+F _{n-1}, gdzie F _{n} to n-ta liczba Fibonacciego.
Góra
Mężczyzna Offline
PostNapisane: 16 lis 2017, o 12:41 
Użytkownik

Posty: 12615
Popraw, bo coś źle napisałeś. Moim skromnym zdaniem powinno być coś takiego:
V_0=1, \ V_1=3, \ V_{n+1}=V_n+V_{n-1}, \ n\ge 1
a teza powinna być taka, że V_n=F_{n+2}, gdzie F_n jest n-tą liczbą Fibonacciego.
Ale pewny nie jestem.
Góra
Mężczyzna Offline
PostNapisane: 16 lis 2017, o 12:53 
Użytkownik

Posty: 31
Lokalizacja: Kraków
Poprawione, tak powinno być na pewno:

Wykaż, że V _{n} zadany rekurencyjnie
V _{0}=1
V _{1}=3
V _{n+1}=V _{n}+V _{n-1}, n \ge2

spełnia zależność
V _{n}=F _{n+1}+F _{n-1}, gdzie F _{n} to n-ta liczba Fibonacciego.
Góra
Mężczyzna Offline
PostNapisane: 16 lis 2017, o 13:27 
Użytkownik

Posty: 12615
Ciąg V_n jest w takim razie źle określony, no jak wygląda wyraz V_2? Powinno być to równanie rekurencyjne dla n\ge 1

Liczby Fibonacciego spełniają równanie rekurencyjne F_{n+1}=F_n+F_{n-1}, \ n\ge 1, ponadto F_0=0, \ F_1=1, generalnie jak już treść będzie poprawna, to z tego należy skorzystać. Można kombinować indukcyjnie, a można też załatwić sprawę funkcjami tworzącymi.
Gdy G(x)= \sum_{n=0}^{ \infty } V_n \ x^n, to z
V_{n+1}=V_n+V_{n-1}, \ n\ge 1, tj. V_{n+2}=V_{n+1}+V_n, \ n\ge 0
możemy wywnioskować, że w pewnym otoczeniu zera
\sum_{n=0}^{ \infty } V_{n+2}x^n= \sum_{n=0}^{ \infty } V_{n+1}x^n+ \sum_{n=0}^{ \infty } V_n \ x^n a po pomnożeniu stronami przez x^2 dostajemy
G(x)-V_0-V_1 x=x(G(x)-V_0)+x^2G(x)
czyli
G(x)= \frac{V_0(1-x)+V_1 x}{1-x-x^2}= \frac{1+2x}{1-x-x^2}
Teraz wylicz funkcję tworzącą prawej strony (robi się to analogicznie) i jeżeli wyjdzie taka sama, jak dla lewej, to mamy żądaną równość, ponieważ funkcja charakterystyczna identyfikuje jednoznacznie ciąg.

A jak nie znasz/nie chcesz znać funkcji tworzących (acz w takich tematach one są naprawdę przydatne), to można przeprowadzić, jak wspomniałem, dowód indukcyjny.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rekurencja - skomplikowana zależność  matopeja  3
 zależność i pary A omega  smyda92  3
 Rozwiąż zależność metodą równania charakterystycznego  kylercopeland  5
 ułożyć odpowiednia zależność rekurencyjną  danielek12201220  1
 Zależność rekurencyjna - zadanie 8  bolt24  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl