Principio di induzione, questo sconosciuto.....

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
TheDragon
Messaggi: 12
Iscritto il: 10 dic 2012, 13:33

Principio di induzione, questo sconosciuto.....

Messaggio da TheDragon »

Salve lo so che può sembrare una domanda banale, ma qualcuno potrebbe spiegarmi il principio di induzione, oppure consigliarmi una dispenza o pagina dove ne parla, lo so che dovrebbe essere la cosa più facile del mondo, ma è un'oretta che lo sto guardando e ancora sento che qualcosa mi sfugge, grazie
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Principio di induzione, questo sconosciuto.....

Messaggio da EvaristeG »

Il suggerimento più rapido è di guardare qui, aprire una cartella qualsiasi Senior_NN (sono le lezioni degli stages senior che si fanno a pisa a settembre), andare nella cartella Basic e scegliere il pdf o il video della lezione indicata con P, che è la lezione su induzione e pigeonhole.
Es: (2012) home/Training/Senior_12/Basic/Pdf/S12B_P-Aner.pdf
oppure la versione "live" home/Training/Senior_12/Basic/Video/S12B_P-Aner.avi
(2011) home/Training/Senior_11/Basic/Pdf/S11B_P-Michele.pdf
oppure la versione "live" home/Training/Senior_11/Basic/Video/S11B_P-Michele.avi
e così via.
Robertopphneimer
Messaggi: 426
Iscritto il: 14 lug 2012, 15:43

Re: Principio di induzione, questo sconosciuto.....

Messaggio da Robertopphneimer »

TheDragon ha scritto:Salve lo so che può sembrare una domanda banale, ma qualcuno potrebbe spiegarmi il principio di induzione, oppure consigliarmi una dispenza o pagina dove ne parla, lo so che dovrebbe essere la cosa più facile del mondo, ma è un'oretta che lo sto guardando e ancora sento che qualcosa mi sfugge, grazie
Non è la cosa più semplice del mondo... ti consiglio (se no l'hai già fatto ) di guardare anche un pò di logica poiché usa le proposizioni logiche.
L'universo è come una sfera dove il centro è ovunque e la circonferenza da nessuna parte.
"Blaise Pascal"
_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Principio di induzione, questo sconosciuto.....

Messaggio da _Ipazia_ »

Provo a spiegarlo, anche se con qualche mese di ritardo, anche solo per vedere se l'ho capito bene io :)
Hai una proprietà $ P $ che vuoi dimostrare, ad esempio vuoi dimostrare che valga per un qualsiasi numero naturale $ n $. Devi fare due passaggi:
-Prima la dimostri per $ 0 $, sostituendo semplicemente $ 0 $ a $ n $ e, facendo i calcoli, verificando che venga vera. (se ad esempio dovevi verificare la proprietà per $ n\ge2 $, la verificavi per 2 e non per 0, il numero da verificare lo scegli tu in base al problema)
-Poi dimostri che se quella proprietà valesse per un numero $ n $, allora vale anche per $ n+1 $
Quindi, avendo verificato che la proprietà vale per $ 0 $, sai che deve valere anche per $ 0+1 $, cioè $ 1 $, e se vale per $ 1 $ allora vale anche per $ 2 $ e così via..
Hai così dimostrato che quella proprietà vale per tutti i numeri maggiori di $ 0 $, cioè per tutti i numeri naturali! (se ti serviva dimostrare che valesse per i numeri minori di $ 0 $, bastava che dimostrassi che, una volta che vale per $ n $, vale anche per $ n-1 $)
Detto così è facile, il problema è dimostrare che se quella proprietà vale per $ n $, vale anche per $ n+1 $.
Forse riesco a spiegarmi meglio con un esempio:
- Dimostrare che per ogni $ n $ appartenente a $ N $ la somma dei quadrati dei primi $ n $ numeri naturali è $ \frac{n(n+1)(2n+1)}{6} $, cioè che $ 1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6} $
Prima verifico che sia vera per $ n=0 $:
$ 0^2=\frac{0(0+1)(2*0+1)}{6} \to 0=0 $
Poi devo dimostrare che se la proprietà vale per $ n $, allora vale per $ n+1 $.
Quindi l'ipotesi della dimostrazione è che la proprietà valga per $ n $:
$ 1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6} $
E la tesi è che valga per $ n+1 $:
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{(n+1)(n+2)(2(n+1)+1)}{6} $
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{(n+1)(n+2)(2n+3)}{6} $
Quindi, per dimostrarlo, bisogna partire dall'ipotesi. Per arrivare alla tesi, per fare in modo che valga anche per $ n+1 $, si nota (confrontando l'ipotesi con la tesi) che al primo membro va aggiunto un $ (n+1)^2 $. Ma, siccome è un'equazione, se si aggiunge una quantità al primo membro va aggiunta anche al secondo per far sì che l'equazione rimanga invariata. Quindi:
$ 1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6} \to 1^2+2^2+...+n^2+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2 $
Svolgendo i calcoli al secondo membro, si ottiene la tesi. Come volevasi dimostrare.
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{n(n+1)(2n+1)+6(n+1)^2}{6} $
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{(n+1)(6n+6+n(2n+1))}{6} $
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{(n+1)(6n+6+2n^2+n)}{6} $
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{(n+1)(2n^2+7n+6)}{6} $
$ 1^2+2^2+...+n^2+(n+1)^2=\frac{(n+1)(n+2)(2n+3)}{6} $
Ora, siccome hai già verificato che la proprietà vale per $ n=0 $, vale per tutti i numeri naturali :)
Spero di essere riuscita a farmi capire :D
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”
Rispondi