Metodo di induzione
Ragazzi, ho notato che risolvete molti quesiti con il metodo induttivo.
Io non lo avevo mai sentito prima d'ora e mi incuriosisce sapere di cosa si tratta.
Se potete "appagarmi" vi rigrazio. [:D]
Io non lo avevo mai sentito prima d'ora e mi incuriosisce sapere di cosa si tratta.
Se potete "appagarmi" vi rigrazio. [:D]
Risposte
Supponiamo di avere una proprieta' p(n) dipendente da un parametro n intero positivo.
Ad esempio:
p(n) = 2n + 1 e' dispari.
Noi vogliamo dimostrare che questa proprieta' e' vera per ogni n naturale. Per farlo cominciamo a controllare che sia vera per il PIU' PICCOLO naturale (0 o 1 a seconda delle convenzioni).
Nel nostro esempio
p(0) e' vera poiche' 2 * 0 + 1 = 1 DISPARI.
Poi l'idea e' questa: noi dovremmo mostrare che p e' vera anche per 1,2,3,... perche' non farlo usando una tecnica tipo "domino"? Ovvero lo dimostriamo per 0 e mostriamo che se e' vero per 0 lo e' per 1:
p(0) ==> p(1)
Poi con la tessera p(1) facciamo cadere p(2) etc...
p(0) ==> p(1) ==> p(2) ==> ...
Ovvero dimostriamo che se p e' vero per un certo n lo e' anche per n+1!
Nel nostro esempio:
p(n) e' supposta vera.
p(n+1) = 2 (n+1) + 1 e' dispari.
2 * (n + 1) + 1 = 2 n + 1 + 2
Svolgendo i conti. Ora 2 n + 1 e' sicuramente dispari perche' p(n) e' supposta vera, ma la somma di un numero dispari e di un numero pari e' certamente dispari (volendo essere pignoli bisognerebbe dimostrare anche questo) per cui p(n+1) e' VERA.
Cosi' facendo abbiamo creato la catena di implicazioni infinita:
p(0) ==> p(1) ==> p(2) ==> p(3) ==> ... p(n) ==> p(n+1) ==> ...
Siccome abbiamo mostrato che p(0) e' vera all'inizio abbiamo la tesi.
Il principio di induzione e' una di quelle cose che gli studenti fanno piu' fatica a capire per cui se non capisci a pieno il mio discorso non preoccuparti anche perche' le mie spiegazioni di solito risultano poco chiare a tutti...
Comunque il principio di induzione puo' essere generalizzato a proposizioni valide su insiemi ben-ordinati (in cui tutti i sotto-insiemi ammettono un minimo), ad esempio a proposizioni valide soltanto da un certo k in avanti o ad insiemi piu' esotici. Esiste anche una dimostrazione di questo principio.
Esistono poi molte varianti:
https://www.matematicamente.it/forum/top ... IC_ID=6120
Ad esempio:
p(n) = 2n + 1 e' dispari.
Noi vogliamo dimostrare che questa proprieta' e' vera per ogni n naturale. Per farlo cominciamo a controllare che sia vera per il PIU' PICCOLO naturale (0 o 1 a seconda delle convenzioni).
Nel nostro esempio
p(0) e' vera poiche' 2 * 0 + 1 = 1 DISPARI.
Poi l'idea e' questa: noi dovremmo mostrare che p e' vera anche per 1,2,3,... perche' non farlo usando una tecnica tipo "domino"? Ovvero lo dimostriamo per 0 e mostriamo che se e' vero per 0 lo e' per 1:
p(0) ==> p(1)
Poi con la tessera p(1) facciamo cadere p(2) etc...
p(0) ==> p(1) ==> p(2) ==> ...
Ovvero dimostriamo che se p e' vero per un certo n lo e' anche per n+1!
Nel nostro esempio:
p(n) e' supposta vera.
p(n+1) = 2 (n+1) + 1 e' dispari.
2 * (n + 1) + 1 = 2 n + 1 + 2
Svolgendo i conti. Ora 2 n + 1 e' sicuramente dispari perche' p(n) e' supposta vera, ma la somma di un numero dispari e di un numero pari e' certamente dispari (volendo essere pignoli bisognerebbe dimostrare anche questo) per cui p(n+1) e' VERA.
Cosi' facendo abbiamo creato la catena di implicazioni infinita:
p(0) ==> p(1) ==> p(2) ==> p(3) ==> ... p(n) ==> p(n+1) ==> ...
Siccome abbiamo mostrato che p(0) e' vera all'inizio abbiamo la tesi.
Il principio di induzione e' una di quelle cose che gli studenti fanno piu' fatica a capire per cui se non capisci a pieno il mio discorso non preoccuparti anche perche' le mie spiegazioni di solito risultano poco chiare a tutti...
Comunque il principio di induzione puo' essere generalizzato a proposizioni valide su insiemi ben-ordinati (in cui tutti i sotto-insiemi ammettono un minimo), ad esempio a proposizioni valide soltanto da un certo k in avanti o ad insiemi piu' esotici. Esiste anche una dimostrazione di questo principio.
Esistono poi molte varianti:
https://www.matematicamente.it/forum/top ... IC_ID=6120
Grazie mille david_e.
Con questa sono 50 replies. Ho raggiunto la prima stella!!!!!!
[:D][:D][:D][:D][:D][:D]
Sono new member prima che il sito venga aggiornato!
Con questa sono 50 replies. Ho raggiunto la prima stella!!!!!!
[:D][:D][:D][:D][:D][:D]
Sono new member prima che il sito venga aggiornato!
congratulazioni!!!!
ehehe
ehehe
Non ho capito però cosa si deve fare dopo aver scritto il passo induttivo.
Se potete postare un esercizio cercherò di risolverlo per vedere se ho capito bene.
Non troppo complesso s'intende
Se potete postare un esercizio cercherò di risolverlo per vedere se ho capito bene.
Non troppo complesso s'intende
Prova a dimostrare che la somma dei primi n numeri pari è n(n+1)
Non saprei...
Da quello che ho capito si dovrebba fare così:
p(0)=0 ==> che è pari
e poi p(n+1)=(n+1)*(n+1)=n^2+2n+1
e adesso nn so che fare. Dimmi tu
Da quello che ho capito si dovrebba fare così:
p(0)=0 ==> che è pari
e poi p(n+1)=(n+1)*(n+1)=n^2+2n+1
e adesso nn so che fare. Dimmi tu
2+4+6+...+2n=n(n+1)
Passo base
Per n=1 si ha:
p(n)=2 ok
Passo indittivo
Nella relazione sopra sommiamo ad entrambi i membri dell'equazione 2(n+1)
2+4+6+...+2n+2(n+1)=n(n+1)+2(n+1)
n(n+1)+2(n+1)=(n+1)(n+2)
Passo base
Per n=1 si ha:
p(n)=2 ok
Passo indittivo
Nella relazione sopra sommiamo ad entrambi i membri dell'equazione 2(n+1)
2+4+6+...+2n+2(n+1)=n(n+1)+2(n+1)
n(n+1)+2(n+1)=(n+1)(n+2)
In pratica il mio procedimento è tutto sbagliato! 
Allora non ho capito niente
e neanche la tua spiegazione mi è chiara. Puoi rispiegarmela in maniera + semplificata?
Allora non ho capito niente
e neanche la tua spiegazione mi è chiara. Puoi rispiegarmela in maniera + semplificata?
Mi permetto di postare un esercizio un po' atipico, ma molto semplice, sull'induzione che ho trovato su un libro di testo americano.
L'esercizio e': trova l'errore nel mio ragionamento.
------------------------
Dimostriamo che su un tavolo da biliardo tutte le palline hanno sempre lo stesso colore.
Lo dimostriamo per induzione. Per k=1 abbiamo una sola pallina per cui l'ipotesi e' verificata.
p(1) e' vera.
Assumiamo quindi p valida per un certo k generico e mostriamolo per k+1.
Sia P l'insieme delle k+1 palline che ci sono in questo momento sul tavolo da biliardo.
Siano A e B due insiemi di k palline ciascuno tali che:
A unione B = P
Per l'ipotesi di induzione tutte le palline in A hanno lo stesso colore. Anche le palline in B hanno lo stesso colore fra di loro.
L'insieme C di k palline costituito di k-1 palline dell'insieme A e 1 pallina dell'insieme B gode della medesima proprieta' (visto che p(k) e' vera).
Segue che la pallina presa da B ha lo stesso colore di quelle contenute nell'insieme A.
Quindi le palline di A e quelle di B hanno tutte lo stesso colore. Da cui segue che tutte le palline in P hanno lo stesso colore.
Questo conclude la fanta-dimostrazione.
L'esercizio e': trova l'errore nel mio ragionamento.
------------------------
Dimostriamo che su un tavolo da biliardo tutte le palline hanno sempre lo stesso colore.
Lo dimostriamo per induzione. Per k=1 abbiamo una sola pallina per cui l'ipotesi e' verificata.
p(1) e' vera.
Assumiamo quindi p valida per un certo k generico e mostriamolo per k+1.
Sia P l'insieme delle k+1 palline che ci sono in questo momento sul tavolo da biliardo.
Siano A e B due insiemi di k palline ciascuno tali che:
A unione B = P
Per l'ipotesi di induzione tutte le palline in A hanno lo stesso colore. Anche le palline in B hanno lo stesso colore fra di loro.
L'insieme C di k palline costituito di k-1 palline dell'insieme A e 1 pallina dell'insieme B gode della medesima proprieta' (visto che p(k) e' vera).
Segue che la pallina presa da B ha lo stesso colore di quelle contenute nell'insieme A.
Quindi le palline di A e quelle di B hanno tutte lo stesso colore. Da cui segue che tutte le palline in P hanno lo stesso colore.
Questo conclude la fanta-dimostrazione.
In effetti sono stato un pò ostruso.
Allora devi dimostrare che:
2+4+6+...+2n=n(n+1)
PASSO BASE: verificare che la proprietà sia valida per il primo termine della successione.
p(1)=2 ok
infatti la somma del primo numero è 2.
PASSO INDUTTIVO: verificare che, supposta vera p(n), vale anche p(n+1).
2+4+6+...+2n=n(n+1)
sommando ad entrambi i membri 2(n+1) si ha:
2+4+6+...+2n+2(n+1)=n(n+1)+2(n+1)
ora considera il secondo membro:
n(n+1)+2(n+1)=(n+1)(n+2) che è esattamente p(n+1).
Allora devi dimostrare che:
2+4+6+...+2n=n(n+1)
PASSO BASE: verificare che la proprietà sia valida per il primo termine della successione.
p(1)=2 ok
infatti la somma del primo numero è 2.
PASSO INDUTTIVO: verificare che, supposta vera p(n), vale anche p(n+1).
2+4+6+...+2n=n(n+1)
sommando ad entrambi i membri 2(n+1) si ha:
2+4+6+...+2n+2(n+1)=n(n+1)+2(n+1)
ora considera il secondo membro:
n(n+1)+2(n+1)=(n+1)(n+2) che è esattamente p(n+1).
Avevo abbandonato, ma voglio ritentare... 
Potete propormi un altro esercizio simie a quello di giuseppe, per vedere se riesco a risolverlo?
Potete propormi un altro esercizio simie a quello di giuseppe, per vedere se riesco a risolverlo?
E' un esercizio Ultra-Famoso ed e' gia' apparso sul Forum, comunque e' di solito uno dei primi esercizi che si danno dopo aver spiegato l'induzione.
L'esercizio e':
Dimostrare che la somma dei primi n numeri (da 1 a n) e':
$ sum_(i=1)^n i = (n(n+1))/2 $
Gauss scopri' questa identita' alla tenera eta' di 7 anni...
L'esercizio e':
Dimostrare che la somma dei primi n numeri (da 1 a n) e':
$ sum_(i=1)^n i = (n(n+1))/2 $
Gauss scopri' questa identita' alla tenera eta' di 7 anni...
Non mi linciate se scrivo corbellerie. (Casomai aiutatemi a capire dove sbaglio).
Prima di tutto
Dimostrare che 1+2+3+4+...+n=$(n(n+1))/2 $ ?
passo base
n=1
p(n)=1 ?
passo induttivo
1+2+3+4+...+n+$(n+1)/2$=$(n(n+1)/2$+$(n+1)/2$ e ora?
Non so se è giusto!?! Correggetemi in caso
Prima di tutto
Dimostrare che 1+2+3+4+...+n=$(n(n+1))/2 $ ?
passo base
n=1
p(n)=1 ?
passo induttivo
1+2+3+4+...+n+$(n+1)/2$=$(n(n+1)/2$+$(n+1)/2$ e ora?
Non so se è giusto!?! Correggetemi in caso
Nel passo induttivo devi dimostrare che se $P(n)$ è vera allora anche $P(n+1)$ lo è. In questo caso devi dimostare che $\sum_{i=1}^{n+1}i=\frac{(n+1)(n+2)}{2}$
Quindi fai così:
$\sum_{i=1}^{n+1}i=n+1+\sum_{i=1}^{n}i=n+1+\frac{n(n+1)}{2}=\frac{(n+1)(n+2)}{2}$
Quindi fai così:
$\sum_{i=1}^{n+1}i=n+1+\sum_{i=1}^{n}i=n+1+\frac{n(n+1)}{2}=\frac{(n+1)(n+2)}{2}$
Integro quello che ha scritto cavallipurosangue con qualche commento.
Il passo di base e' giusto.
Per quello induttivo devi dimostrare che vale:
$p(n+1)$
Per dimostrarlo non devi fare altro che svolgere i conti e usare la $p(n)$ che e' considerata vera.
La $p(n+1) $ e' : $ \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2} $
Come dice Cavallipurosangue. Poi svolgi i conti come ha fatto lui.
Il passo di base e' giusto.
Per quello induttivo devi dimostrare che vale:
$p(n+1)$
Per dimostrarlo non devi fare altro che svolgere i conti e usare la $p(n)$ che e' considerata vera.
La $p(n+1) $ e' : $ \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2} $
Come dice Cavallipurosangue. Poi svolgi i conti come ha fatto lui.
Ok.
Ma ditemi, dove posso trovare degli esercizi di questo genere?
Ma ditemi, dove posso trovare degli esercizi di questo genere?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo