Wzór jawny funkcji i procedura

robo5000 · Post autor: **robo5000** » 13 maja 2013, o 21:59

Mam mały problem jak rozwiązać to zadanie. Czy ktoś może udzielić mi wskazówek? Będę bardzo wdzięczny.

Treść zadania:
1. Znajdź wzór jawny dla funkcji \(\displaystyle{ f(n)}\), zdefiniowanej rekurencyjnie poniżej. Jeżeli wzór został odgadnięty musi zostać następnie udowodniony przez indukcję.

2. Napisz procedurę rekurencyjną realizującą obliczanie funkcji \(\displaystyle{ f}\) i ułóż zależność rekurencyjną opisującą koszt czasowy zaproponowanej procedury ze względu na liczbę wykonanych operacji arytmetycznych.

wzór:

\(\displaystyle{ f(0) = 0, f(1) = 11, 2 \cdot f(n+2) = 14 \cdot f(n+1) - 20 \cdot f(n)}\)

yorgin · Post autor: **yorgin** » 13 maja 2013, o 22:50

A jakich metod mamy używać do rozwiązania tej rekurencji?

Innymi słowy, jakie znasz albo miałeś wyłożone metody rozwiązywania tego typu zadań?

robo5000 · Post autor: **robo5000** » 14 maja 2013, o 23:08

mam do wyboru takie metody:

metoda iteracji
metoda podstawiania
metoda wielomianu charakterystycznego

yorgin · Post autor: **yorgin** » 15 maja 2013, o 21:42

No to metoda wielomianu charakterystycznego - dla mnie szybka i łatwa.

Tutaj wielomianem jest

\(\displaystyle{ x^2=14x-20}\)

Co dalej?

robo5000 · Post autor: **robo5000** » 18 maja 2013, o 12:27

a nie przypadkiem \(\displaystyle{ x^2-7x+10}\) ?

yorgin · Post autor: **yorgin** » 18 maja 2013, o 16:02

Nie, bo to nawet równanie nie jest.

I rzeczywiście, Twój zapis w jednej linijce wszystkiego sprawia, że się mylę za pierwszym razem i poprawiam za drugim: równanie ma postać

\(\displaystyle{ 2x^2=14x-20}\)