Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Vn zadany rekurencyjnie spełnia zależność.

Strona 1 z 1

[ Posty: 4 ]

Autor

Wiadomość

Eko140 Offline

Tytuł: Vn zadany rekurencyjnie spełnia zależność.

Napisane: 16 lis 2017, o 12:32

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

Premislav Offline

Tytuł: Re: Vn zadany rekurencyjnie spełnia zależność.

Napisane: 16 lis 2017, o 12:41

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

Eko140 Offline

Tytuł: Re: Vn zadany rekurencyjnie spełnia zależność.

Napisane: 16 lis 2017, o 12:53

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

Premislav Offline

Tytuł: Re: Vn zadany rekurencyjnie spełnia zależność.

Napisane: 16 lis 2017, o 13:27

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

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 4 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

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

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]