Principio di induzione, questo sconosciuto.....
Principio di induzione, questo sconosciuto.....
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
Re: Principio di induzione, questo sconosciuto.....
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.
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.....
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.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
L'universo è come una sfera dove il centro è ovunque e la circonferenza da nessuna parte.
"Blaise Pascal"
"Blaise Pascal"
Re: Principio di induzione, questo sconosciuto.....
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
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
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”