Come funziona il principio di induzione?
Ciao,
sono alle prese col principio di induzione, a livello teorico ho capito che la dimostrazione per induzione completa avviene in due fasi, P(0) passo base e P(n+1) passo induttivo, il problema è come ragionare per la dimostrazione,
vi faccio un esempio:
ho questa sommatoria:
$ sum_(i = 1)^(n) 2i - 1 = n^2 $
il passo base P(1) si risolve sostituendo 1 ad i ed ottengo 1 = 1 , quindi il passo base è verificato,
ora devo dimostrare il passo induttivo P(n+1), la parte destra dopo l'uguale diventa
$ (n+1)^2 $
per quanto riguarda la parte sinistra non ho capito come devo aggiungare la quantità n+1, se devo sommare la quantità n+1 a 2i -1 e quindi diventerebbe $ 2n-1 + (n+1) $
o se considerare n+1 come 2n-1 e diventerebbe $2n-1 + 2n-1$
mi potreste aiutare??
forse è una domanda banale ma sono davvero confuso a riguardo...
e nel caso la sommatoria fosse stata per i che va da 1 a n+2 come si ragiona??
vi ringrazio anticipatamente
sono alle prese col principio di induzione, a livello teorico ho capito che la dimostrazione per induzione completa avviene in due fasi, P(0) passo base e P(n+1) passo induttivo, il problema è come ragionare per la dimostrazione,
vi faccio un esempio:
ho questa sommatoria:
$ sum_(i = 1)^(n) 2i - 1 = n^2 $
il passo base P(1) si risolve sostituendo 1 ad i ed ottengo 1 = 1 , quindi il passo base è verificato,
ora devo dimostrare il passo induttivo P(n+1), la parte destra dopo l'uguale diventa
$ (n+1)^2 $
per quanto riguarda la parte sinistra non ho capito come devo aggiungare la quantità n+1, se devo sommare la quantità n+1 a 2i -1 e quindi diventerebbe $ 2n-1 + (n+1) $
o se considerare n+1 come 2n-1 e diventerebbe $2n-1 + 2n-1$
mi potreste aiutare??
forse è una domanda banale ma sono davvero confuso a riguardo...
e nel caso la sommatoria fosse stata per i che va da 1 a n+2 come si ragiona??
vi ringrazio anticipatamente
Risposte
Tranquillo, non sei il primo che si impantana sulla dimostrazione per induzione. E non sarai l'ultimo 
Il passo induttivo è il seguente: tu hai l'ipotesi induttiva e devi dimostrare la tesi induttiva.
Il passo induttivo è il seguente: tu hai l'ipotesi induttiva e devi dimostrare la tesi induttiva.
[ipotesi] $sum_(i=1)^n (2i-1) =n^2$
[tesi] $sum_(i=1)^(n+1) (2i-1) =(n+1)^2$
[/list:u:35m5hdnl]
Devi dimostrare la tesi sfruttando l'ipotesi
"Gi8":
Tranquillo, non sei il primo che si impantana sulla dimostrazione per induzione. E non sarai l'ultimo
Il passo induttivo è il seguente: tu hai l'ipotesi induttiva e devi dimostrare la tesi induttiva.
[ipotesi] $sum_(i=1)^n (2i-1) =n^2$
[tesi] $sum_(i=1)^(n+1) (2i-1) =(n+1)^2$
[/list:u:22jh4q9m]
Devi dimostrare la tesi sfruttando l'ipotesi
quindi se non ho capito male nell'ipotesi noi diciamo che $(2i-1) = n^2 $ che è la P(n) di conseguenza se vogliamo dimostrare P(n+1) la parte sinistra diventerà $ (2n-1) + n^2 $ e la destra rimane $(n+1)^2$
e verifico l'equazione giusto?
Quasi, ma comunque il concetto l'hai capito. La parte sinistra diventa $[2(n+1)-1]+n^2$
6 un grande!!!
sto facendo vari esercizi ed escono!!!
davvero mille grazie!
tra i vari esercizi mi sono comparsi alcuni che hanno sommatorie che vanno da 1 a n+2,
in questo caso, quando dimostro il passo induttivo, (presumo che il passo base non cambia) nella parte destra sostituisco n con n+2, nella sinistra invece (prendendo come esempio quello di prima), ho $ [2(n+1) -1] + n^2 + n^2 $ cioè aggiungo due volte la quantità giusto??
sto facendo vari esercizi ed escono!!!
davvero mille grazie!
tra i vari esercizi mi sono comparsi alcuni che hanno sommatorie che vanno da 1 a n+2,
in questo caso, quando dimostro il passo induttivo, (presumo che il passo base non cambia) nella parte destra sostituisco n con n+2, nella sinistra invece (prendendo come esempio quello di prima), ho $ [2(n+1) -1] + n^2 + n^2 $ cioè aggiungo due volte la quantità giusto??
No, dovrebbe essere $[2(n+1)-1]+[2(n+2)-1]+n^2$
Ma forse è meglio se scrivi l'esercizio
Ma forse è meglio se scrivi l'esercizio
Ciao,
scusa il ritardo (ho passato tutte le giornate all'uni e quando tornavo a casa crollavo dal sonno e nn accendevo il pc
), ho applicato lo stesso metodo per n+2 all'esercizio e funziona
GRAZIEEEEEEEEEEE!!!!!!!!!!!!!!
scusa il ritardo (ho passato tutte le giornate all'uni e quando tornavo a casa crollavo dal sonno e nn accendevo il pc
), ho applicato lo stesso metodo per n+2 all'esercizio e funziona GRAZIEEEEEEEEEEE!!!!!!!!!!!!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo