Buongiorno,qualcuno può mostrarmi come si dimostra questa regola per induzione? devo dimostrare che f(n) è un o piccolo di n^m ossia che esiste una costante c >0 per cui f(n) è > di c per n^m
Buongiorno,qualcuno può mostrarmi come si dimostra questa regola per induzione? devo dimostrare che f(n) è un o piccolo di n^m ossia che esiste una costante c >0 per cui f(n) è > di c per n^m
7
punti
Livello 0
Usando il principio di induzione, proviamo per m=0:
$a_0<=C_0$ che è banale
per m=1:
$a_1 n + a_0 <= C_1 n$
qui dividiamo per n a sinistra e destra:
$a_1+\frac{a_0}{n}<=C_1$
Questa è certamente vera per un qualche n=n* e per ogni n>n*
adesso supponi che sia vera per un certo m*, quindi
e vogliamo dimostrare che:
Possiamo procedere così: maggioriamo la sommatoria con quello che sappiamo essere valido per m*:
e quindi:
Dividiamo tutto per $n^{m*+1}$:
Anche questa disuguaglianza risulta vera per un qualche n e per tutti gli n maggiori di lui, quindi abbiamo provato la tesi.
17092
punti
Livello 9
Ti ringrazio per la spiegazione molto chiara. Grazie, sei stato gentilissimo.
@BlueSky: prego, non c'è di che. 🙂