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

Wykaż, że zadany rekurencyjnie
=1
=3
=, n

spełnia zależność
=, gdzie to n-ta liczba Fibonacciego.

Popraw, bo coś źle napisałeś. Moim skromnym zdaniem powinno być coś takiego:

a teza powinna być taka, że , gdzie jest n-tą liczbą Fibonacciego.
Ale pewny nie jestem.

Poprawione, tak powinno być na pewno:

Wykaż, że zadany rekurencyjnie
=1
=3
=, n

spełnia zależność
=, gdzie to n-ta liczba Fibonacciego.

Ciąg jest w takim razie źle określony, no jak wygląda wyraz ? Powinno być to równanie rekurencyjne dla

Liczby Fibonacciego spełniają równanie rekurencyjne , ponadto , 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 , to z
, tj.
możemy wywnioskować, że w pewnym otoczeniu zera
a po pomnożeniu stronami przez dostajemy

czyli

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.