Indukcja i rekurencja

ast3rot · Post autor: **ast3rot** » 29 sie 2007, o 20:48

Zadanko z ksiazki "Wprowadzenie do algorytmów" (str 36).

Pokaż, stosując metodę indukcji matematycznej, że dla n będącego potęgą dwójki rozwiązaniem równania rekurencyjnego

\(\displaystyle{ T(n)= \lbrace 2, \quad jesli \ n=2 \\
\ \ \quad \lbrace 2T(n/2) + n, \quad jesli \ n = 2^k \ dla \ k > 1
\\\\ Jest \ T(n) = n lg n}\)

Niebardzo wiem jak sie za to zabrac. W szkole na lekcjach nie robilismy indukcji matematycznej ze wzorami rekurencyjnymi. Znalazlem jeden w zbiorze kielbasy i go zrobilem ale on byl akurat prosty, a tutaj mamy doczynienia z zupelnie inna bajka.
Bylbym wdzieczny za pomoc.

mol_ksiazkowy · Post autor: **mol_ksiazkowy** » 29 sie 2007, o 23:54

\(\displaystyle{ T(2^k)=k2^k}\)

ast3rot · Post autor: **ast3rot** » 30 sie 2007, o 00:30

No, tak. Zmienna n moge zamienic na \(\displaystyle{ 2^k}\), to wiem, ale nie wiem jak to udowodnic indukcyjnie, ze dla tego rownania rekurencyjnego rozwiazaniem jest to drugie.

luka52 · Post autor: **luka52** » 30 sie 2007, o 00:40

\(\displaystyle{ T(2^{k+1}) = 2 T(2^k) + 2^{k+1} = 2^k ( 2k + 2 ) =(k+1)2^{k+1}}\)

ast3rot · Post autor: **ast3rot** » 30 sie 2007, o 02:01

mhm, rozumiem ze pierwszy post to zal. indukcyjne a drugi to teza indukcyjna. Myslalem ze to jakos inaczej bedzie wygladac. No, ale ok. Tylko teraz nie wiem jak ma dowod tu wygladac...

luka52 · Post autor: **luka52** » 30 sie 2007, o 10:53

Zał. podał mol_ksiazkowy, dowód ja podałem. Jeżeli teraz zamienisz z powrotem \(\displaystyle{ 2^k}\) na \(\displaystyle{ n}\) wszystko będzie OK.

Rafal88K · Post autor: **Rafal88K** » 21 wrz 2007, o 16:44

Robię to samo zadanie, ale nie mogę coś przekształcić na taką postać jaką podał mol_ksiazkowy, może ktoś mi do rozpisać

Dokładnie to skąd tam się wzięło \(\displaystyle{ k}\).