Dimostrazione per induzione e sommatoria
Salve a tutti,
un pò perchè non sono ancora pratico delle dimostrazioni per induzione, un pò perchè non so come interpretare il simbolo della sommatoria nelle dimostrazioni per induzioni, mi trovo a non riuscire a fare dimostrazioni tipo questa:
$AA n >= 0 sum_{i=0}^N (4i+1) = (2n+1)(n+1)$
So che la dimostrazione per induzione recita che:
Devo dimostrare vero il passo base;
Supporre vera la P(n);
Trovare la P(n+1).
Ma non mi ci trovo proprio. Se potete dimostrarmela voi con qualche commento ve ne sarei grato.
un pò perchè non sono ancora pratico delle dimostrazioni per induzione, un pò perchè non so come interpretare il simbolo della sommatoria nelle dimostrazioni per induzioni, mi trovo a non riuscire a fare dimostrazioni tipo questa:
$AA n >= 0 sum_{i=0}^N (4i+1) = (2n+1)(n+1)$
So che la dimostrazione per induzione recita che:
Devo dimostrare vero il passo base;
Supporre vera la P(n);
Trovare la P(n+1).
Ma non mi ci trovo proprio. Se potete dimostrarmela voi con qualche commento ve ne sarei grato.
Risposte
Benvenuto nel forum.
Comincia a verificare che la formula vale per $n=0$ (che è banale: viene $1=1$). Ok, quindi il "passo base", come lo chiami, è vero.
Ora devi far vedere che $P(n)=>P(n+1)$.
Quindi, cerchiamo di capire come scrivere $sum_(i=0)^(n+1) (4i+1)$. Per sfruttare l'ipotesi induttiva spezzi la sommatoria in due: $sum_(i=0)^(n+1) (4i+1)=sum_(i=0)^n(4i+1)+4[(n+1)+1]$, dove il secondo termine è quello che trovi sostituendo $i$ con $n+1$.
Siccome questo è il passaggio forse più delicato, ti propongo un esempio numerico nel caso in cui non avessi capito. Supponi di voler sommare tutti i numeri da 1 a 6: sei d'accordo che puoi mettere insieme i primi cinque e poi aggiungere al risultato 6: $sum_(i=1)^6i=sum_(i=1)^5i+6$? Ci sei fin qui?
Ora sono solo conti: sfrutti l'ipotesi induttiva per cui l'espressione diventa $sum_(i=0)^n(4i+1)+4[(n+1)+1]=(2n+1)(n+1)+4[(n+1)+1]$. Se calcoli i prodotti e poi scomponi, trovi $(2n+3)(n+2)$ che è proprio uguale a $[2(n+1)+1][(n+1)+1]=P(n+1)$.
Concludi quindi che per induzione quella formula è vera $forall n >=0$.
Tutto chiaro? Se hai dubbi scrivi. Ciao!
Comincia a verificare che la formula vale per $n=0$ (che è banale: viene $1=1$). Ok, quindi il "passo base", come lo chiami, è vero.
Ora devi far vedere che $P(n)=>P(n+1)$.
Quindi, cerchiamo di capire come scrivere $sum_(i=0)^(n+1) (4i+1)$. Per sfruttare l'ipotesi induttiva spezzi la sommatoria in due: $sum_(i=0)^(n+1) (4i+1)=sum_(i=0)^n(4i+1)+4[(n+1)+1]$, dove il secondo termine è quello che trovi sostituendo $i$ con $n+1$.
Siccome questo è il passaggio forse più delicato, ti propongo un esempio numerico nel caso in cui non avessi capito. Supponi di voler sommare tutti i numeri da 1 a 6: sei d'accordo che puoi mettere insieme i primi cinque e poi aggiungere al risultato 6: $sum_(i=1)^6i=sum_(i=1)^5i+6$? Ci sei fin qui?
Ora sono solo conti: sfrutti l'ipotesi induttiva per cui l'espressione diventa $sum_(i=0)^n(4i+1)+4[(n+1)+1]=(2n+1)(n+1)+4[(n+1)+1]$. Se calcoli i prodotti e poi scomponi, trovi $(2n+3)(n+2)$ che è proprio uguale a $[2(n+1)+1][(n+1)+1]=P(n+1)$.
Concludi quindi che per induzione quella formula è vera $forall n >=0$.
Tutto chiaro? Se hai dubbi scrivi. Ciao!
La regola l'avevo capita, cioè ti dice:
Verifica il passo base P(0);
Supponi vero il passo P(n);
Verifica il passo P(n+1);
E' quel verifica che non mi trovo.
Cioè devo verificare che: $AA n >= 0 sum_{i=0}^N (4i+1)$ sia uguale a $(2n+1)(n+1)$ prima per n= al passo base e cioè 0 (perchè n>=0) e poi per n+1?
E' per questo che nel verificare la formula si prova che sia vera $sum_{i=0}^N+1 (4i+1)$ sia sostituendo direttamente ad n l'n+1, sia sommando alla sommatoria di n l'elemento successivo?
Come dire che "se facendo a mano la somma" esce; "Eseguendo la formula sostituendo ad n l'n+1" esce, allora il passo P(n+1) è verificato e quindi abbiamo supposto bene il nostro passo induttivo P(n)? E' questo che si intende per verificare?
Verifica il passo base P(0);
Supponi vero il passo P(n);
Verifica il passo P(n+1);
E' quel verifica che non mi trovo.
Cioè devo verificare che: $AA n >= 0 sum_{i=0}^N (4i+1)$ sia uguale a $(2n+1)(n+1)$ prima per n= al passo base e cioè 0 (perchè n>=0) e poi per n+1?
E' per questo che nel verificare la formula si prova che sia vera $sum_{i=0}^N+1 (4i+1)$ sia sostituendo direttamente ad n l'n+1, sia sommando alla sommatoria di n l'elemento successivo?
Come dire che "se facendo a mano la somma" esce; "Eseguendo la formula sostituendo ad n l'n+1" esce, allora il passo P(n+1) è verificato e quindi abbiamo supposto bene il nostro passo induttivo P(n)? E' questo che si intende per verificare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo