Induzione
Induzione
Qualcuno mi fa un esempio di applicazione del teorema dell'induzione? Faccio seconda e sono andato a leggere cos'è su wikipedia ma non ho capito niente asd, magari con un esempio potrei chiarirmi un po la sua utilità...
Esempio super-classico. Vogliamo dimostrare che $ $1+2+\dots+n=\frac{n(n+1)}{2}$ $ per ogni $ $n$ $ naturale.
Passo base: la proprietà vale per $ $n=0$ $? Sì, perchè $ $0=\frac{0\cdot(0+1)}{2}$ $.
Ipotesi induttiva: supponiamo, per ipotesi, che la proprietà valga per un generico numero naturale, che chiameremo $ $m$ $. Quindi ipotizziamo che $ $1+2+\dots+m=\frac{m(m+1)}{2}$ $.
Passo induttivo: vogliamo ora dimostrare che la proprietà vale per il numero $ $m+1$ $, cioè vogliamo dimostrare che $ $1+2+\dots+(m+1)=\frac{(m+1)(m+2)}{2}$ $.
Scriviamo la nostra somma: $ $1+2+\dots+m+(m+1)$ $. Ora entra in gioco l'ipotesi induttiva: possiamo sostituire alla somma $ $1+2+\dots+m$ $ la quantità $ $\frac{m(m+1)}{2}$ $. Allora abbiamo $ $(1+2+\dots+m)+(m+1)=\frac{m(m+1)}{2}+(m+1)=\frac{(m+1)(m+2)}{2}$ $. Abbiamo vinto!
Abbiamo dimostrato che la proprietà vale per $ $n=0$ $ e in più abbiamo dimostrato che, se vale per un numero, allora vale anche per il successivo. Quindi vale per tutti i naturali
Passo base: la proprietà vale per $ $n=0$ $? Sì, perchè $ $0=\frac{0\cdot(0+1)}{2}$ $.
Ipotesi induttiva: supponiamo, per ipotesi, che la proprietà valga per un generico numero naturale, che chiameremo $ $m$ $. Quindi ipotizziamo che $ $1+2+\dots+m=\frac{m(m+1)}{2}$ $.
Passo induttivo: vogliamo ora dimostrare che la proprietà vale per il numero $ $m+1$ $, cioè vogliamo dimostrare che $ $1+2+\dots+(m+1)=\frac{(m+1)(m+2)}{2}$ $.
Scriviamo la nostra somma: $ $1+2+\dots+m+(m+1)$ $. Ora entra in gioco l'ipotesi induttiva: possiamo sostituire alla somma $ $1+2+\dots+m$ $ la quantità $ $\frac{m(m+1)}{2}$ $. Allora abbiamo $ $(1+2+\dots+m)+(m+1)=\frac{m(m+1)}{2}+(m+1)=\frac{(m+1)(m+2)}{2}$ $. Abbiamo vinto!
Abbiamo dimostrato che la proprietà vale per $ $n=0$ $ e in più abbiamo dimostrato che, se vale per un numero, allora vale anche per il successivo. Quindi vale per tutti i naturali
Bene, prendiamo un pentagono di [tex]$n$[/tex] lati...
Azz, mi sono perso l'ultimissimo passaggiofede90 ha scritto:Esempio super-classico. Vogliamo dimostrare che $ $1+2+\dots+n=\frac{n(n+1)}{2}$ $ per ogni $ $n$ $ naturale.
Passo base: la proprietà vale per $ $n=0$ $? Sì, perchè $ $0=\frac{0\cdot(0+1)}{2}$ $.
Ipotesi induttiva: supponiamo, per ipotesi, che la proprietà valga per un generico numero naturale, che chiameremo $ $m$ $. Quindi ipotizziamo che $ $1+2+\dots+m=\frac{m(m+1)}{2}$ $.
Passo induttivo: vogliamo ora dimostrare che la proprietà vale per il numero $ $m+1$ $, cioè vogliamo dimostrare che $ $1+2+\dots+(m+1)=\frac{(m+1)(m+2)}{2}$ $.
Scriviamo la nostra somma: $ $1+2+\dots+m+(m+1)$ $. Ora entra in gioco l'ipotesi induttiva: possiamo sostituire alla somma $ $1+2+\dots+m$ $ la quantità $ $\frac{m(m+1)}{2}$ $. Allora abbiamo $ $(1+2+\dots+m)+(m+1)=\frac{m(m+1)}{2}+(m+1)=\frac{(m+1)(m+2)}{2}$ $. Abbiamo vinto!
Abbiamo dimostrato che la proprietà vale per $ $n=0$ $ e in più abbiamo dimostrato che, se vale per un numero, allora vale anche per il successivo. Quindi vale per tutti i naturali
, comunque in che cosa può essere utile la conoscenza di questa formula?Edit: capito scusa la domanda da tard
, resta la domanda sull'utilità (evidentemente è molto utile, solo non ho capito in cosa)-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Pensa alle tessere del domino (Gobbino docet, credo)!
Le tessere del domino sono messe tutte in fila, e hanno la proprietà che se una cade, anche la successiva cade. Se uno fa cadere la prima, che succede? Cade la seconda, quindi la terza, quindi la quarta... Cadono tutte.
L'utilità dell'induzione sta nel fatto che dimostrare l'IMPLICAZIONE "cade n --> cade n+1" è in genere più facile che dimostrare in una botta sola l'affermazione "tutte le tessere cadono".
Le tessere del domino sono messe tutte in fila, e hanno la proprietà che se una cade, anche la successiva cade. Se uno fa cadere la prima, che succede? Cade la seconda, quindi la terza, quindi la quarta... Cadono tutte.
L'utilità dell'induzione sta nel fatto che dimostrare l'IMPLICAZIONE "cade n --> cade n+1" è in genere più facile che dimostrare in una botta sola l'affermazione "tutte le tessere cadono".