Principio d'induzione matematica

[pippo931]

salve, vorrei chiedervi se vi va di spiegarmi un pò il principio di induzione in modo semplice (perchè su wikipedia, altri siti o sul Courant e Robbins non capisco molto), se è troppo lungo e complicato vi chiedo se conosciate qualche sito dove venga spiegato, semplicemente, tale principio.

grazie dell'attenzione

[Dorian1]

E' molto semplice. Il principio d'induzione (nella prima forma) traduce in linguaggio matematico un'idea molto intuitiva...
Sia $p(n)_(n in NN)$ una famiglia di proposizioni. se:
(i) $p(0)$ è vera e
(ii) $p(k)$ vera => $p(k+1)$ vera
allora $p(n)$ è vera $AA n in NN$

Immagina che le $p(n)$ siano delle tessere del domino, la $p(0)$ è la prima e la (ii) dice che ciascuna tessera, cadendo, trascina con sè anche la successiva. E' pacifico che, se fai cadere la prima, tutte le altre cadranno...
Chiaro?

[pippo931]

"Dorian":E' molto semplice. Il principio d'induzione (nella prima forma) traduce in linguaggio matematico un'idea molto intuitiva...
Sia $p(n)_(n in NN)$ una famiglia di proposizioni. se:
(i) $p(0)$ è vera e
(ii) $p(k)$ vera => $p(k+1)$ vera
allora $p(n)$ è vera $AA n in NN$

Immagina che le $p(n)$ siano delle tessere del domino, la $p(0)$ è la prima e la (ii) dice che ciascuna tessera, cadendo, trascina con sè anche la successiva. E' pacifico che, se fai cadere la prima, tutte le altre cadranno...
Chiaro?

perchè $n in NN$?

[pippo931]

comunque, in modo abbastanza intuitivo l'ho capito. se non sbaglio, quindi il principio di induzione permette di "generalizzare" un'affermazione, un teorema ecc. Comunque credo che ci sia altro da dire: ho trovato pagine di spiegazioni!?!?

[Dorian1]

"pippo93":[quote="Dorian"]E' molto semplice. Il principio d'induzione (nella prima forma) traduce in linguaggio matematico un'idea molto intuitiva...
Sia $p(n)_(n in NN)$ una famiglia di proposizioni. se:
(i) $p(0)$ è vera e
(ii) $p(k)$ vera => $p(k+1)$ vera
allora $p(n)$ è vera $AA n in NN$

Immagina che le $p(n)$ siano delle tessere del domino, la $p(0)$ è la prima e la (ii) dice che ciascuna tessera, cadendo, trascina con sè anche la successiva. E' pacifico che, se fai cadere la prima, tutte le altre cadranno...
Chiaro?

perchè $n in NN$?[/quote]

Vuol dire che per ogni numero naturale c'è una proposizione... è questa la forza del ragionamento per induzione... Permette di dimostrare infinite proposizioni in un colpo solo...

[pippo931]

"Dorian":[quote="pippo93"][quote="Dorian"]E' molto semplice. Il principio d'induzione (nella prima forma) traduce in linguaggio matematico un'idea molto intuitiva...
Sia $p(n)_(n in NN)$ una famiglia di proposizioni. se:
(i) $p(0)$ è vera e
(ii) $p(k)$ vera => $p(k+1)$ vera
allora $p(n)$ è vera $AA n in NN$

Immagina che le $p(n)$ siano delle tessere del domino, la $p(0)$ è la prima e la (ii) dice che ciascuna tessera, cadendo, trascina con sè anche la successiva. E' pacifico che, se fai cadere la prima, tutte le altre cadranno...
Chiaro?

perchè $n in NN$?[/quote]

Vuol dire che per ogni numero naturale c'è una proposizione... è questa la forza del ragionamento per induzione... Permette di dimostrare infinite proposizioni in un colpo solo...[/quote]

si, ma perchè n non può essere un numero razionale o altro?

[Dorian1]

Ma allora cos'è che non ti è chiaro?

[Dorian1]

Non ha senso parlare di un numero razionale di tessere del domino... Si tratta di "oggetti" che puoi contare...

[pippo931]

"Dorian":Non ha senso parlare di un numero razionale di tessere del domino... Si tratta di "oggetti" che puoi contare...

allora non ho capito. Lasciando stare da parte le tessere del domino, facciamo un esempio: la diseguaglianza $x/(x+1)<1$,che chiamiamo $A_1$, il caso generale si indica con $A_n$ ed è : $x/(x+|n|)<1$. Ma se vogliamo indicare il caso di : $x/(x+1/2)<1$ lo indichiamo con $A_(1/2)$ Giusto? e $1/2$ non appartiene ad $NN$. Ti ringrazio della pazienza

[Studente Anonimo]

Oh, salve. Dò la mia opinione.

Nel ragionamento per induzione dimostri che se una cosa è vera per un certo numero naturale n allora è vera per il successivo numero naturale, n+1.

Questo è importante: il successivo di un certo numero naturale n è caratterizzato dall'essere il minimo naturale maggiore strettamente di n.

Ora, se parti da 0 o da 1 e consideri il successivo, poi il successivo del successivo, poi il successivo del successivo del successivo, ecc. forzatamente becchi tutti i numeri naturali, per definizione se vuoi. Quindi se una cosa è vera per 0 e quando è vera per un numero, è vera per il successivo, allora forzatamente essa è vera per tutti i numeri.

Ora, il problema dei razionali è che non si può parlare di successivo di un numero. In altre parole se q è un razionale l'insieme degli x razionali maggiori strettamente di q non ammette minimo (pensaci). Ne segue che non si può estendere in modo immediato il ragionamento per induzione ai razionali.

Se vuoi cercare di mostrare qualcosa riguardante i razionali per induzione, puoi scrivere il/i razionale/i che compaiono come rapporto di naturali e cercare di applicare l'induzione su di essi.

[pippo931]

"Martino": Quindi se una cosa è vera per 0 e quando è vera per un numero, è vera per il successivo, allora forzatamente essa è vera per tutti i numeri.

ma se prendi ad esempio i coefficienti binomiali e guardi il triangolo di tartaglia, noti che questo è vero per le prime 3,4,5 righe (fin dove hai avuto la pazienza di calcolarlo) ma solamente col triangolo non provi che la trentesima riga rispetti lo stesso ordine

[elios2]

Esatto... se $n in RR$, non avrebbe più senso cercare di dimostrare che se la proposizione vale per $n$, allora vale anche per $n+1$, a causa della completezza di $RR$.

[fedeb2]

prova per induzione che la somma dei primi $n$ numeri naturali è $n(n+1)/2$. se ti chiedessi di sommare i primi $n$ numeri razionali, dopo quanto mi sputeresti in un occhio e perchè??

[Studente Anonimo]

"pippo93":ma se prendi ad esempio i coefficienti binomiali e guardi il triangolo di tartaglia, noti che questo è vero per le prime 3,4,5 righe (fin dove hai avuto la pazienza di calcolarlo) ma solamente col triangolo non provi che la trentesima riga rispetti lo stesso ordine

Certo che no. Infatti per applicare l'induzione devi mostrare che se la riga n rispetta l'ordine di cui parli, allora lo rispetta anche la riga n+1, e questo per ogni naturale n. Questo implica (evidentemente) che non basta guardare le prime quarantamila righe, perche la quarantamilaunesima potrebbe comportarsi in modo diverso.

[alvinlee881]

Provo a spiegarti il quesito posto da fedeb, è una delle prime dimostrazioni che si fanno col principio d'induzione, cercando di farti appararire chiaro il ragionamento. Si deve dimostrare che la somma dei primi $n$ numeri naturali, cioè $sum_(k=1)^n k$ è uguale $((n+1)n)/2$. Come potresti fare? Provi con i primi numeri: con $1$ ottieni che $sum_(k=1)^1 k =1=(1*(1+1))/2$, con $2$ hai $sum_(k=1)^2 k=1+2=((2+1)*2) /2=3$, ok, e potresti andare avanti un bel pò, dicendo "e così via" (*), senza dimostrare nulla però. Se però dimostri che per $n=1$ la proprietà vale (e l'abbiamo fatto, si chiama generalmente "passo base") e che il FATTO che la proprietà valga per $n$ IMPLICA che vale anche per $n+1$, allora hai finito. Devi convincerti di questo, prima di proseguire: Con 1 vale, se dimostri l'implicazione che ho scritto sopra in base a questa deduci che per $2$ vale, e ancora,poichè per $n=2$ vale, allora, sempre per quest'implicazione dimostrata, anche per $n+1=3$ vale, e "così via". Ma questo è un "così via" diverso da quello (*), perchè adesso è dimostrato che varrà per ogni n la tua proposizione, mentre prima era solo una tua (legittima) supposizione. Venendo alla nostra dimostrazione, il passo base è fatto, resta da compiere il "passo induttivo", ossia la dimostrazione dell'implicazione. Si deve dimostrare che $P(n) vera => P(n+1) vera$, cioè che $sum_(k=1)^n k =((n+1)n)/2 => sum_(k=1)^(n+1) k = ((n+2)(n+1))/2$. La tesi, $sum_(k=1)^(n+1) k = ((n+2)(n+1))/2$, puoi riscriverla come $sum_(k=1)^(n) k + (n+1)$, giusto? Per "ipotesi induttiva" (te hai supposto vero che $sum_(k=1)^n k =((n+1)n)/2$, se lo è non ci interessa, ci interessa che la supposizione che sia vera implichi la vericidità della proposizione anche per $n+1$) sai che $sum_(k=1)^(n) k=((n+1)*n)/2$, da cui puoi scrivere $sum_(k=1)^(n+1) k =((n+1)*n)/2 +(n+1)=((n+1)n +2(n+1))/2=((n+1)(n+2))/2$, che è proprio la tesi da dimostrare!. Quindi per $1$ è vera, $P(n) vera=>P(n+1) vera$, da cui concludi che $P(n)$ è vera $AA n in NN$. All'inizio è un ragionamento un pò contorto, ma ragionandoci un pò non dovresti aver difficoltà a capire il principio su cui si fonda il principio di induzione ( )

P.S. beato te che scopri certe belle cose al primo anno di liceo, io ho scoperto la sua esistenza la primo anno di università avrei dovuto appassionarmi prima alla materia e frequentare prima il forum..

[pippo931]

"alvinlee88":P.S. beato te che scopri certe belle cose al primo anno di liceo, io ho scoperto la sua esistenza la primo anno di università avrei dovuto appassionarmi prima alla materia e frequentare prima il forum..

mi stai dicendo che queste cose non si studiano al liceo scientifico? se è così devo ammettere di essere un illuso

[alvinlee881]

Io personalmente non le ho studiate, forse qualche prof lo farà, ma di certo non rientra nel programma...te però continua a interessarti come stai facendo ora
Piuttosto, hai capito?

[pippo931]

"fedeb":prova per induzione che la somma dei primi $n$ numeri naturali è $n(n+1)/2$. se ti chiedessi di sommare i primi $n$ numeri razionali, dopo quanto mi sputeresti in un occhio e perchè??

bhe abbastanza in fretta, perchè i primi n razionali sono infiniti, giusto?

[alvinlee881]

"pippo93":[quote="fedeb"]prova per induzione che la somma dei primi $n$ numeri naturali è $n(n+1)/2$. se ti chiedessi di sommare i primi $n$ numeri razionali, dopo quanto mi sputeresti in un occhio e perchè??

bhe abbastanza in fretta, perchè i primi n razionali sono infiniti, giusto?[/quote]

Più che altro perchè non si può proprio parlare di "primi n numeri razionali": cosa si intende con questo? cosa significa parlare, ad esempio, dei primi $8$ numeri razionali? Da dove parti? Quali numeri scegli?

[pippo931]

dunque... vediamo se ho capito bene... allora noi dimostriamo che una affermazione è vera per un n qualsiasi e per il suo successivo :n+1, ora, dato che l'insieme dei naturali , come mi ha ricordato Sergio, è formato da numeri che abbiano un successore, sappiamo che se l'affermazione è vera per n e per n+1 allora è vera per tutti i numeri naturali (perchè n e n+1 rappresentano, secondo la definizione di Peano, tutti i numeri naturali). Giusto?

[alvinlee881]

"pippo93":dunque... vediamo se ho capito bene... allora noi dimostriamo che una affermazione è vera per un n qualsiasi e per il suo successivo :n+1, ora, dato che l'insieme dei naturali , come mi ha ricordato Sergio, è formato da numeri che abbiano un successore, sappiamo che se l'affermazione è vera per n e per n+1 allora è vera per tutti i numeri naturali (perchè n e n+1 rappresentano, secondo la definizione di Peano, tutti i numeri naturali). Giusto?

No.
Noi non dimostriamo che una affermazione è vera per un n qualsiasi e per n+1 (non dimostreremmo un bel nulla), ma dimostriamo che l'affermazione è vera per $1$ ( o per $0$, dipende dalla cosa da dimostrare) e dimostriamo che il fatto che sia vera per $n$ qualsiasi implica che sia vera anche per $n+1$.