Principio di induzione
Salve, sto cercando di imparare il principio di induzione, vorrei sapere se sono sulla buona strada.
Ad esempio questo esercizio:
dimostrare che per ogni $n>=1$ la somma $S(n)$ dei primi n numeri naturali è
$S(n) = \frac{n(n+1)}{2} = \frac{(n^2+n)}{2}$
1) Faccio il paso base, in questo caso $S(1)$
$S(1) = 1$ qundi è verificato
2) Faccio il passo induttivo $S(n+1)$
$S(n+1) = \frac{(n+1)(n+2)}{2}$
3) Adesso (se ho capito bene) devo riuscire a scrivere $S(n+1)$ in modo che al suo interno figuri l'ipostesi $S(n)$
quindi:
$ S(n+1) = \frac{n^2+2n+n+2}{2} = \frac{n^2+n}{2} + \frac{2n+2}{2}$
$S(n+1) = S(n) + \frac{2n+2}{2}$
Quindi è dimostrato? L'esercizio è finito?
Vorrei sapere se ho capito bene.
Grazie
Ad esempio questo esercizio:
dimostrare che per ogni $n>=1$ la somma $S(n)$ dei primi n numeri naturali è
$S(n) = \frac{n(n+1)}{2} = \frac{(n^2+n)}{2}$
1) Faccio il paso base, in questo caso $S(1)$
$S(1) = 1$ qundi è verificato
2) Faccio il passo induttivo $S(n+1)$
$S(n+1) = \frac{(n+1)(n+2)}{2}$
3) Adesso (se ho capito bene) devo riuscire a scrivere $S(n+1)$ in modo che al suo interno figuri l'ipostesi $S(n)$
quindi:
$ S(n+1) = \frac{n^2+2n+n+2}{2} = \frac{n^2+n}{2} + \frac{2n+2}{2}$
$S(n+1) = S(n) + \frac{2n+2}{2}$
Quindi è dimostrato? L'esercizio è finito?
Vorrei sapere se ho capito bene.
Grazie
Risposte
Ok, ma non ho capito, cioè i passaggi sono:
1) Faccio il paso base
2) Faccio il passo di induzione (n+1)
3) Qui non ho capito che cosa devo cercare di dimostrare, cioè cosa si deve dimostrare (in parole povere)?
1) Faccio il paso base
2) Faccio il passo di induzione (n+1)
3) Qui non ho capito che cosa devo cercare di dimostrare, cioè cosa si deve dimostrare (in parole povere)?
In parole povere (spero non troppo altrimenti non si capisce niente ... 
) dimostrare il passo induttivo significa che se tu IPOTIZZI (ripeto IPOTIZZI) che la proprietà in esame è vera per un certo indice $n$ e con questa ipotesi RIESCI a dimostrare che è vera per l'indice successivo cioè $n+1$ allora hai dimostrato la validità della proprietà per TUTTI gli indici.
Nell'esempio postato cosa si fa?
- si IPOTIZZA che sia vero questo $sum_(i=1)^n i=\ (n(n+1))/2\ \ \ \ $ (ripeto: non sappiamo se è vero, facciamo finta che lo sia, ok?)
- la somma dei primi $n+1$ numeri interi (cioè $sum_(i=1)^(n+1) i$) la possiamo scrivere come $sum_(i=1)^(n+1) i=sum_(i=1)^n i+ (n+1)$ (cioè detto a parole: la somma dei primi $n+1$ numeri interi è uguale alla somma dei primi $n$ a cui sommiamo $(n+1)$). Questa non è ancor la dimostrazione ma solo un'equivalenza (convincitene prima di andare avanti).
- A questo punto, data l'IPOTESI fatta, lavoriamo con questa sostituzione $sum_(i=1)^n i=\ (n(n+1))/2\ \ \ \ $; perciò l'equivalenza del punto precedente diventa $sum_(i=1)^(n+1) i=(n(n+1))/2+(n+1)$
- Adesso basta sviluppare l'espressione di destra per ottenere $sum_(i=1)^(n+1) i=((n+1)(n+2))/2$ che è precisamente quello che dovevamo dimostrare.
In conclusione usando QUELLA ipotesi (cioè che la proprietà è vera per un certo $n$) abbiamo dimostrato che è vera anche per il successivo cioè $n+1$.
Con ciò abbiamo dimostrato il passo induttivo.
Ok?
Cordialmente, Alex
) dimostrare il passo induttivo significa che se tu IPOTIZZI (ripeto IPOTIZZI) che la proprietà in esame è vera per un certo indice $n$ e con questa ipotesi RIESCI a dimostrare che è vera per l'indice successivo cioè $n+1$ allora hai dimostrato la validità della proprietà per TUTTI gli indici.Nell'esempio postato cosa si fa?
- si IPOTIZZA che sia vero questo $sum_(i=1)^n i=\ (n(n+1))/2\ \ \ \ $ (ripeto: non sappiamo se è vero, facciamo finta che lo sia, ok?)
- la somma dei primi $n+1$ numeri interi (cioè $sum_(i=1)^(n+1) i$) la possiamo scrivere come $sum_(i=1)^(n+1) i=sum_(i=1)^n i+ (n+1)$ (cioè detto a parole: la somma dei primi $n+1$ numeri interi è uguale alla somma dei primi $n$ a cui sommiamo $(n+1)$). Questa non è ancor la dimostrazione ma solo un'equivalenza (convincitene prima di andare avanti).
- A questo punto, data l'IPOTESI fatta, lavoriamo con questa sostituzione $sum_(i=1)^n i=\ (n(n+1))/2\ \ \ \ $; perciò l'equivalenza del punto precedente diventa $sum_(i=1)^(n+1) i=(n(n+1))/2+(n+1)$
- Adesso basta sviluppare l'espressione di destra per ottenere $sum_(i=1)^(n+1) i=((n+1)(n+2))/2$ che è precisamente quello che dovevamo dimostrare.
In conclusione usando QUELLA ipotesi (cioè che la proprietà è vera per un certo $n$) abbiamo dimostrato che è vera anche per il successivo cioè $n+1$.
Con ciò abbiamo dimostrato il passo induttivo.
Ok?
Cordialmente, Alex
Ricapitolando:
1) Hai verificato che la tua "formula" vale per un certo $n$ (in genere $n=1$, il tuo passo base).
2) Hai dimostrato che se vale per un qualsiasi $n$ allora vale anche per il successivo $n+1$.
3) Come conseguenza hai che vale per ogni $n$. Infatti per 1) sai che vale per $n=1$, per 2) hai che vale per $n=2$, sempre per 2) sai che vale per $n=3$ e così via.
1) Hai verificato che la tua "formula" vale per un certo $n$ (in genere $n=1$, il tuo passo base).
2) Hai dimostrato che se vale per un qualsiasi $n$ allora vale anche per il successivo $n+1$.
3) Come conseguenza hai che vale per ogni $n$. Infatti per 1) sai che vale per $n=1$, per 2) hai che vale per $n=2$, sempre per 2) sai che vale per $n=3$ e così via.
"axpgn":
In parole povere (spero non troppo altrimenti non si capisce niente ...
...
Sinceri complimenti per la chiarezza!
Ad esempio:
$2^n+3^n<4^n \forall n>=2$
1) Passo base
$P(2)$ verificato
2) Passo induttovo
$P(n+1) = 2^(n+1) + 3^(n+1) < 4^(n+1)$
$P(n+1) = 2*2^n+2*3^n+3^n<4*4^n$
adesso utilizzo l'ipotesi induttiva dentro il passo induttivo:
$ 2(2^n+3^n)+3^n<2(4^n)+3^n<4*4^n$
E' corretto?
$2^n+3^n<4^n \forall n>=2$
1) Passo base
$P(2)$ verificato
2) Passo induttovo
$P(n+1) = 2^(n+1) + 3^(n+1) < 4^(n+1)$
$P(n+1) = 2*2^n+2*3^n+3^n<4*4^n$
adesso utilizzo l'ipotesi induttiva dentro il passo induttivo:
$ 2(2^n+3^n)+3^n<2(4^n)+3^n<4*4^n$
E' corretto?
"marco123":
$ 2(2^n+3^n)+3^n<2(4^n)+3^n<4*4^n$
E' corretto?
Chi ti dice che questa sia vera (la seconda disequazione intendo) ? Hai fatto il contrario, hai preso come ipotesi la tesi ...
Premesso che non c'è un metodo standard da usare, in questo caso parti dall'ipotesi ...
$2^n+3^n<4^n\ =>\ 4*(2^n+3^n)<4*4^n\ =>\ 4*2^n+4*3^n<4^(n+1)\ $
ma noi sappiamo che $2*2^n<4*2^n\ =>\ 2^(n+1)<4*2^n$ ed anche che $3*3^n<4*3^n\ =>\ 3^(n+1)<4*3^n$ quindi sostituendo nella precedente otteniamo la tesi $2^(n+1)+3^(n+1)<4^(n+1)$.
Ti ripeto, non esistono metodi prefabbricati, spesso si parte direttamente dall'ipotesi ma ...
Cordialmente, Alex
$2^n+3^n<4^n\ =>\ 4*(2^n+3^n)<4*4^n\ =>\ 4*2^n+4*3^n<4^(n+1)\ $
ma noi sappiamo che $2*2^n<4*2^n\ =>\ 2^(n+1)<4*2^n$ ed anche che $3*3^n<4*3^n\ =>\ 3^(n+1)<4*3^n$ quindi sostituendo nella precedente otteniamo la tesi $2^(n+1)+3^(n+1)<4^(n+1)$.
Ti ripeto, non esistono metodi prefabbricati, spesso si parte direttamente dall'ipotesi ma ...
Cordialmente, Alex
scusa non ho capito l'ultimo passaggio, cioè come fai a concludere che è vera la tesi?
Precisamente, fino a dove ti ritrovi?
fino a quando dici "quindi sostituendo nella precedente..."
da lì non ho capito come fai a concludere.
da lì non ho capito come fai a concludere.
Allora ... su questo $2^(n+1)<4*2^n$ e su questo $3^(n+1)<4*3^n$ siamo d'accordo mi pare ...
Sommo membro a membro e ottengo $2^(n+1)+3^(n+1)<4*2^n+4*3^n$ ma dalla prima eravamo giunti alla conclusione che $4*2^n+4*3^n<4^(n+1)$ perciò $2^(n+1)+3^(n+1)<4^(n+1)$
Sommo membro a membro e ottengo $2^(n+1)+3^(n+1)<4*2^n+4*3^n$ ma dalla prima eravamo giunti alla conclusione che $4*2^n+4*3^n<4^(n+1)$ perciò $2^(n+1)+3^(n+1)<4^(n+1)$
grazie, chiarissimo.
Ok, per curiosità vorrei sapere se questa dimostrazione è corretta ( non l'ho fatta io, ma a questo punto credo sia sbagliata perchè parte dalla tesi), la riporto uguale com'è:
Per quanto riguarda il passo induttivo prendiamo per ipotesi $P(n)$ e dimostriamo $P(n+1)$, si ha
$2^(n+1) + 3^(n+1) = 2 x 2^n + 3 x 3^n = 2 x 2^n + 2 x 3^n + 3^n =
2 x (2^n + 3^n) + 3^n < 2 x (4^n) + 3^n < 2 x (4^n) + 4^n = 3 x 4^n < 4 x 4^n = 4^(n+1)$
Per quanto riguarda il passo induttivo prendiamo per ipotesi $P(n)$ e dimostriamo $P(n+1)$, si ha
$2^(n+1) + 3^(n+1) = 2 x 2^n + 3 x 3^n = 2 x 2^n + 2 x 3^n + 3^n =
2 x (2^n + 3^n) + 3^n < 2 x (4^n) + 3^n < 2 x (4^n) + 4^n = 3 x 4^n < 4 x 4^n = 4^(n+1)$
Attenzione: partire dalla tesi non è di per sé sempre errato; se riesci ad arrivare all'ipotesi quasi sicuramente hai raggiunto lo scopo.
Nell'ultimo esempio che hai fatto basta che tu legga la sequenza da destra a sinistra invece che da sinistra a destra e ti rendi conto che parti dall'ipotesi e arrivi alla tesi.
Ma non è sempre così ... un discorso più completo e articolato però non mi è possibile ... né ci sarebbe spazio ...
Cordialmente, Alex
Nell'ultimo esempio che hai fatto basta che tu legga la sequenza da destra a sinistra invece che da sinistra a destra e ti rendi conto che parti dall'ipotesi e arrivi alla tesi.
Ma non è sempre così ... un discorso più completo e articolato però non mi è possibile ... né ci sarebbe spazio ...
Cordialmente, Alex
ok
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo