Indukcja i rekurencja

Ze względu na specyfikę metody - osobny dział.
ast3rot
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 19 kwie 2006, o 18:34
Płeć: Mężczyzna
Lokalizacja: z domu
Podziękował: 3 razy

Indukcja i rekurencja

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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 7093
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2625 razy
Pomógł: 687 razy

Indukcja i rekurencja

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

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

ast3rot
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 19 kwie 2006, o 18:34
Płeć: Mężczyzna
Lokalizacja: z domu
Podziękował: 3 razy

Indukcja i rekurencja

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
Gość Specjalny
Gość Specjalny
Posty: 8602
Rejestracja: 1 maja 2006, o 20:54
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 47 razy
Pomógł: 1817 razy

Indukcja i rekurencja

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
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 19 kwie 2006, o 18:34
Płeć: Mężczyzna
Lokalizacja: z domu
Podziękował: 3 razy

Indukcja i rekurencja

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
Gość Specjalny
Gość Specjalny
Posty: 8602
Rejestracja: 1 maja 2006, o 20:54
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 47 razy
Pomógł: 1817 razy

Indukcja i rekurencja

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
Użytkownik
Użytkownik
Posty: 311
Rejestracja: 15 mar 2007, o 16:52
Płeć: Mężczyzna
Lokalizacja: Lublin
Podziękował: 28 razy
Pomógł: 54 razy

Indukcja i rekurencja

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}\).

ODPOWIEDZ