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

[Eko140]

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

spełnia zależność
\(\displaystyle{ V _{n}}\)=\(\displaystyle{ F _{n+1}+F _{n-1}}\), gdzie \(\displaystyle{ F _{n}}\) to n-ta liczba Fibonacciego.

[Premislav]

Popraw, bo coś źle napisałeś. Moim skromnym zdaniem powinno być coś takiego:
\(\displaystyle{ V_0=1, \ V_1=3, \ V_{n+1}=V_n+V_{n-1}, \ n\ge 1}\)
a teza powinna być taka, że \(\displaystyle{ V_n=F_{n+2}}\), gdzie \(\displaystyle{ F_n}\) jest n-tą liczbą Fibonacciego.
Ale pewny nie jestem.

[Eko140]

Poprawione, tak powinno być na pewno:

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

spełnia zależność
\(\displaystyle{ V _{n}}\)=\(\displaystyle{ F _{n+1}+F _{n-1}}\), gdzie \(\displaystyle{ F _{n}}\) to n-ta liczba Fibonacciego.

[Premislav]

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

Liczby Fibonacciego spełniają równanie rekurencyjne \(\displaystyle{ F_{n+1}=F_n+F_{n-1}, \ n\ge 1}\), ponadto \(\displaystyle{ 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 \(\displaystyle{ G(x)= \sum_{n=0}^{ \infty } V_n \ x^n}\), to z
\(\displaystyle{ V_{n+1}=V_n+V_{n-1}, \ n\ge 1}\), tj. \(\displaystyle{ V_{n+2}=V_{n+1}+V_n, \ n\ge 0}\)
możemy wywnioskować, że w pewnym otoczeniu zera
\(\displaystyle{ \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 \(\displaystyle{ x^2}\) dostajemy
\(\displaystyle{ G(x)-V_0-V_1 x=x(G(x)-V_0)+x^2G(x)}\)
czyli
\(\displaystyle{ 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.