Induzione

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Sonner
Messaggi: 364
Iscritto il: 12 feb 2009, 16:02
Località: Susa (TO)

Induzione

Messaggio da Sonner » 15 feb 2009, 16:08

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à...

fede90
Messaggi: 287
Iscritto il: 04 apr 2007, 21:36
Località: Udine

Messaggio da fede90 » 15 feb 2009, 16:37

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 :wink:
Bene, prendiamo un pentagono di [tex]$n$[/tex] lati...

Sonner
Messaggi: 364
Iscritto il: 12 feb 2009, 16:02
Località: Susa (TO)

Messaggio da Sonner » 15 feb 2009, 16:49

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 :wink:
Azz, mi sono perso l'ultimissimo passaggio :oops: , comunque in che cosa può essere utile la conoscenza di questa formula?

Edit: capito scusa la domanda da tard :P, 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

Messaggio da Tibor Gallai » 15 feb 2009, 16:54

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. :shock:

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".

Rispondi