Pagina 1 di 1
Induzione
Inviato: 15 feb 2009, 16:08
da Sonner
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à...
Inviato: 15 feb 2009, 16:37
da fede90
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
Inviato: 15 feb 2009, 16:49
da Sonner
fede90 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
Azz, mi sono perso l'ultimissimo passaggio
, 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)
Inviato: 15 feb 2009, 16:54
da Tibor Gallai
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".