Tra poco piu di una settimana dovrò fare l'esame di logica matematica e ancora non riesco a dimostrare per induzione.Teoricamente so come si dimostra, ma poi ogni caso è diverso dall'altro, vorrei cercare di trovare, se possibile, un procedimento un po meccanio per dimostrare. Si puo?
Potete spiegarmi il tutto con questo esercizio che non riesco a fare, ed è tipo quelli dell'esame.
Grazie
-Dimostrare per induzione che qualunque numero naturale n maggiore di 1 si scompone in al piu' log2n fattori primi.
Induzione
qui si era parlato in generale dell'induzione
viewtopic.php?t=7060
viewtopic.php?t=7060
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
-
MindFlyer
Re: Induzione
Se ti accingi a fare un esame di Logica Matematica, dovresti aver abbandonato questo atteggiamento mentale da molto tempo...Joker87 ha scritto:vorrei cercare di trovare, se possibile, un procedimento un po meccanio per dimostrare.
ma logaritmo in base 10 o naturale? con log generalmente si indica il logaritmo in base 10 e
210=2*3*5*7
$ ~\log{2\cdot210}=2.62... $ ma 210 si scompone in 4 fattori primi
se invece e' logaritmo naturale
sia f(n) il numero di fattori primi (diversi tra loro) in cui e' scomponibile n.
sia p numero primo, $ ~2p>3>e $ quindi $ ~\ln{2p}\geq f(p)=1 $
se $ ~p\geq 3 $, $ ~\ln{2p}+\ln{2}-1\geq\ln{12}-1>f(p)=1 $
Posto $ ~f(n)\leq\ln{2n}+\ln{2}-1\leq\ln{2n} $ e p numero primo tale che non divide n, allora devi avere $ ~f(np)=f(n)+1\leq\ln{2np}+\ln{2}-1\leq\ln{2np} $.
Se $ ~\ln{2np}\geq\ln{2n}+\ln{2}-1+1 $ hai risolto.
$ ~\ln{2np}=\ln{2n}+\ln{p}\geq\ln{2n}+\ln{2} $
$ ~\ln{p}\geq \ln{2} $
$ ~p\geq 2 $
tutto fuorche' meccanico!
210=2*3*5*7
$ ~\log{2\cdot210}=2.62... $ ma 210 si scompone in 4 fattori primi
se invece e' logaritmo naturale
sia f(n) il numero di fattori primi (diversi tra loro) in cui e' scomponibile n.
sia p numero primo, $ ~2p>3>e $ quindi $ ~\ln{2p}\geq f(p)=1 $
se $ ~p\geq 3 $, $ ~\ln{2p}+\ln{2}-1\geq\ln{12}-1>f(p)=1 $
Posto $ ~f(n)\leq\ln{2n}+\ln{2}-1\leq\ln{2n} $ e p numero primo tale che non divide n, allora devi avere $ ~f(np)=f(n)+1\leq\ln{2np}+\ln{2}-1\leq\ln{2np} $.
Se $ ~\ln{2np}\geq\ln{2n}+\ln{2}-1+1 $ hai risolto.
$ ~\ln{2np}=\ln{2n}+\ln{p}\geq\ln{2n}+\ln{2} $
$ ~\ln{p}\geq \ln{2} $
$ ~p\geq 2 $
tutto fuorche' meccanico!
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
devi dimostrare all'inizio il caso base (in questo caso quando n e' primo quindi ha un solo fattore primo) poi dimostri il caso di m+1 fattori primi basandoti sul caso con m fattori primi
in piu' bisognerebbe dimostrare che se p e' fattore primo di n, se vale per n vale anche per p*n, ma e' banale e l'ho omesso
l'induzione e' meccanica, la parte artistica sta nel capire come applicarla e dove.
in piu' bisognerebbe dimostrare che se p e' fattore primo di n, se vale per n vale anche per p*n, ma e' banale e l'ho omesso
l'induzione e' meccanica, la parte artistica sta nel capire come applicarla e dove.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
-
Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Ciao, Joker87 
Allora. Premessa. Lo so che lo sai, che l'avrai studiato mille volte, che me lo diresti a memoria a menadito... ma io ti consiglio di prenderti un attimo (magari due o tre) per capirlo _a fondo_, il principio d'induzione. Sei sicuro che ti sia chiarissimo? Ti hanno mai fatto l'esempietto del domino? Sai cosa stai facendo quando applichi l'induzione?
Come direbbe Gobbino, stai facendo cadere delle tessere del domino, una dopo l'altra.
Hai una proprietà dei naturali.
Diciamo che parti da 0. Dimostri che 0 ha quella proprietà.
Poi supponi che un numero n (0? 3? 4? boh! un dato numero, non t'interessa quale) abbia quella proprietà; nota che lo _supponi_, non dici che deve succedere per forza. E dimostri che se per caso questo n ha quella proprietà, allora ce l'ha n+1.
Qua devi dimostrare qualcosa. E qua non sempre il passaggio è banale, potresti faticarci un po', potresti doverlo fare in un modo o in un altro, dipende da com'è fatta quella proprietà, dipende da troppe cose perché tu possa sperare di avere un procedimento banale che funziona sempre.
Una volta che hai fatto questo, però, hai finito. Hai "vinto". Perché?
Perché per 0 quella proprietà valeva. E, siccome hai dimostrato che se ce l'ha un numero ce l'ha anche il suo successore, vale anche per 0+1=1; ma siccome vale per 1 vale per 2; siccome vale per 2 vale per 3. E così via, le tessere del domino cadono tutte.
L'induzione è un po' un modo matematico per dire "e così via".
Questo però non è l'unico modo per formulare l'induzione. Esiste la cosiddetta "induzione estesa" che è quella che devi usare nel tuo problema.
E' semplicemente una variante.
Dimostri il passo base.
Poi, stavolta, supponi che 0 (se sei partito da 0), 1, 2, ... n godano della tua proprietà, e dimostri che SE questo succede allora anche n+1 ne gode.
Sei d'accordo che è esattamente lo stesso?
Una volta dimostrate queste due cose, sai che per 0 vale. Allora vale per 1. Ma allora per 0, 1 vale. Allora vale per 2. E così via.
Scusami se con questa premessa ti ho annoiato e/o ho detto cose che sapevi già. Spero che mi perdonerai e leggerai fino in fondo.
Passiamo al problema...
Allora. Premessa. Lo so che lo sai, che l'avrai studiato mille volte, che me lo diresti a memoria a menadito... ma io ti consiglio di prenderti un attimo (magari due o tre) per capirlo _a fondo_, il principio d'induzione. Sei sicuro che ti sia chiarissimo? Ti hanno mai fatto l'esempietto del domino? Sai cosa stai facendo quando applichi l'induzione?
Come direbbe Gobbino, stai facendo cadere delle tessere del domino, una dopo l'altra.
Hai una proprietà dei naturali.
Diciamo che parti da 0. Dimostri che 0 ha quella proprietà.
Poi supponi che un numero n (0? 3? 4? boh! un dato numero, non t'interessa quale) abbia quella proprietà; nota che lo _supponi_, non dici che deve succedere per forza. E dimostri che se per caso questo n ha quella proprietà, allora ce l'ha n+1.
Qua devi dimostrare qualcosa. E qua non sempre il passaggio è banale, potresti faticarci un po', potresti doverlo fare in un modo o in un altro, dipende da com'è fatta quella proprietà, dipende da troppe cose perché tu possa sperare di avere un procedimento banale che funziona sempre.
Una volta che hai fatto questo, però, hai finito. Hai "vinto". Perché?
Perché per 0 quella proprietà valeva. E, siccome hai dimostrato che se ce l'ha un numero ce l'ha anche il suo successore, vale anche per 0+1=1; ma siccome vale per 1 vale per 2; siccome vale per 2 vale per 3. E così via, le tessere del domino cadono tutte.
L'induzione è un po' un modo matematico per dire "e così via".
Questo però non è l'unico modo per formulare l'induzione. Esiste la cosiddetta "induzione estesa" che è quella che devi usare nel tuo problema.
E' semplicemente una variante.
Dimostri il passo base.
Poi, stavolta, supponi che 0 (se sei partito da 0), 1, 2, ... n godano della tua proprietà, e dimostri che SE questo succede allora anche n+1 ne gode.
Sei d'accordo che è esattamente lo stesso?
Una volta dimostrate queste due cose, sai che per 0 vale. Allora vale per 1. Ma allora per 0, 1 vale. Allora vale per 2. E così via.
Scusami se con questa premessa ti ho annoiato e/o ho detto cose che sapevi già. Spero che mi perdonerai e leggerai fino in fondo.
Passiamo al problema...
Un po' di pratica...
La proprietà è che $ n $ ha al più $ \log_2{n} $ fattori primi.
Magari partiamo da 1, stavolta, c'è chi 0 tra i naturali lo mette e chi no, e questa proprietà mi sembra che per 0 abbia un po' poco senso. (Ti scandalizza se partiamo da 1? Se sì dimmelo.)
1 ha 0 fattori primi. Nota che 1 non è primo, e in effetti $ \log_2{1}=0 $. Ok.
Supponiamo che 1, 2, ... n abbiano rispettivamente al più $ \log_2{1}, \log_2{2}, ... \log_2{n} $ fattori primi.
Allora n+1 come si comporta? Boh, magari è primo, e in quel caso ha un solo fattore primo, quindi siamo felici, perché sicuramente $ 1\leq\log_2{(n+1)} $. Se invece non è primo, lo possiamo scomporre in due fattori. Diciamo che sono a e b, e ovviamente $ a\leq n, b\leq n $. Allora n+1 avrà tanti fattori primi quanti quelli di a più quelli di b. (Ovvio, no?) Ma noi abbiamo supposto che i fattori primi di a, che è $ \leq n $, siano al più $ \log_2{a} $, e quelli di b al più $ \log_2{b} $. Mmmh, ma allora n+1 avrà al massimo $ \log_2{a}+\log_2{b} $ fattori. Ma $ \log_2{a}+\log_2{b}=\log_2{ab}=\log_2{(n+1)} $!
E qua abbiamo vinto, perché abbiamo dimostrato che se 1, 2, ... n hanno la proprietà che volevamo, allora ce l'ha anche n+1!
EDIT: aggiustato con un po' di LaTeX, così i mod/admin non si lamentano
La proprietà è che $ n $ ha al più $ \log_2{n} $ fattori primi.
Magari partiamo da 1, stavolta, c'è chi 0 tra i naturali lo mette e chi no, e questa proprietà mi sembra che per 0 abbia un po' poco senso. (Ti scandalizza se partiamo da 1? Se sì dimmelo.)
1 ha 0 fattori primi. Nota che 1 non è primo, e in effetti $ \log_2{1}=0 $. Ok.
Supponiamo che 1, 2, ... n abbiano rispettivamente al più $ \log_2{1}, \log_2{2}, ... \log_2{n} $ fattori primi.
Allora n+1 come si comporta? Boh, magari è primo, e in quel caso ha un solo fattore primo, quindi siamo felici, perché sicuramente $ 1\leq\log_2{(n+1)} $. Se invece non è primo, lo possiamo scomporre in due fattori. Diciamo che sono a e b, e ovviamente $ a\leq n, b\leq n $. Allora n+1 avrà tanti fattori primi quanti quelli di a più quelli di b. (Ovvio, no?) Ma noi abbiamo supposto che i fattori primi di a, che è $ \leq n $, siano al più $ \log_2{a} $, e quelli di b al più $ \log_2{b} $. Mmmh, ma allora n+1 avrà al massimo $ \log_2{a}+\log_2{b} $ fattori. Ma $ \log_2{a}+\log_2{b}=\log_2{ab}=\log_2{(n+1)} $!
E qua abbiamo vinto, perché abbiamo dimostrato che se 1, 2, ... n hanno la proprietà che volevamo, allora ce l'ha anche n+1!
EDIT: aggiustato con un po' di LaTeX, così i mod/admin non si lamentano
Ultima modifica di phi il 01 feb 2007, 13:36, modificato 1 volta in totale.
...e tiriamo le conclusioni.
Dov'è andato a finire "sostituisco n+1 nella formula"?
Il problema l'abbiamo risolto ragionando un minimo, e sapendo cosa stavamo facendo, quindi non abbiamo avuto bisogno di ulteriori schemetti prefabbricati. L'induzione è già abbastanza "meccanica" di per sé.
Quello che ti consiglio davvero caldamente è imparare a risolvere i problemi con un minimo di ragionamento, perché l'induzione si può applicare a un sacco di cose con molto profitto, mentre gli schemettini prefabbricati alla "sostituisco n+1 nella formula" no. Certo, saper risolvere un numero di problemi sempre maggiore viene con l'esercizio e l'esperienza.
Se ancora dopo tutto questo stai leggendo (forse dovrei dubitarne
) e se ancora vuoi uno schemetto prefabbricato, la cosa un po' mi dispiace, ma posso dirti questo.
Quando hai una formula algebrica, meglio se un'uguaglianza, da dimostrare per ogni n naturale, di solito puoi fare così.
Sostituisci 0 al posto di n, vedi che è vera.
Sostituisci n+1 al posto di n. Ora farai alcune manipolazioni algebriche legittime (dividi per qualcosa di diverso da 0 da due parti di un'uguaglianza, aggiungi o sottrai la stessa cosa, cose del genere, che sai che mantengono vera l'uguaglianza) e speri ardentemente di riuscire a far saltar fuori la formuletta con dentro n.
Poi hai finito.
A volte funzionerà. Nei casi idioti. Spesso e volentieri no.
Bene. Se hai letto fin qui, congratulazioni. Se non hai capito qualcosa, ti prego di chiedere. Se vuoi, io ho scritto una dispensina sull'induzione, con un po' di esempi svolti... Pochi sono di quelli veramente stupidi. Se t'interessa, posso uploadarla da qualche parte.
Mi scuso con te e con tutto il forum per la mia logorrea.
Dov'è andato a finire "sostituisco n+1 nella formula"?
Il problema l'abbiamo risolto ragionando un minimo, e sapendo cosa stavamo facendo, quindi non abbiamo avuto bisogno di ulteriori schemetti prefabbricati. L'induzione è già abbastanza "meccanica" di per sé.
Quello che ti consiglio davvero caldamente è imparare a risolvere i problemi con un minimo di ragionamento, perché l'induzione si può applicare a un sacco di cose con molto profitto, mentre gli schemettini prefabbricati alla "sostituisco n+1 nella formula" no. Certo, saper risolvere un numero di problemi sempre maggiore viene con l'esercizio e l'esperienza.
Se ancora dopo tutto questo stai leggendo (forse dovrei dubitarne
) e se ancora vuoi uno schemetto prefabbricato, la cosa un po' mi dispiace, ma posso dirti questo.Quando hai una formula algebrica, meglio se un'uguaglianza, da dimostrare per ogni n naturale, di solito puoi fare così.
Sostituisci 0 al posto di n, vedi che è vera.
Sostituisci n+1 al posto di n. Ora farai alcune manipolazioni algebriche legittime (dividi per qualcosa di diverso da 0 da due parti di un'uguaglianza, aggiungi o sottrai la stessa cosa, cose del genere, che sai che mantengono vera l'uguaglianza) e speri ardentemente di riuscire a far saltar fuori la formuletta con dentro n.
Poi hai finito.
A volte funzionerà. Nei casi idioti. Spesso e volentieri no.
Bene. Se hai letto fin qui, congratulazioni. Se non hai capito qualcosa, ti prego di chiedere. Se vuoi, io ho scritto una dispensina sull'induzione, con un po' di esempi svolti... Pochi sono di quelli veramente stupidi. Se t'interessa, posso uploadarla da qualche parte.
Mi scuso con te e con tutto il forum per la mia logorrea.
La mia "dispensa" (ok è un po' presuntuoso chiamarla così) la puoi trovare a questo indirizzo
http://linuz.sns.it/~phi/induzione.pdf
E' in pratica una rielaborazione di parte della prima lezione di uno stage senior, quindi ci troverai fondamentalmente problemi sull'induzione "olimpici, carini e classici" con le loro soluzioni. L'ho scritta per un mio compagno di classe, purtroppo ai tempi in cui ancora non conoscevo LaTeX e usavo soltanto word...
Forse la dimostrazione del Teorema di Pick è un po' meno immediata, il resto spero tu possa seguirlo bene. Gli esercizi alla fine sono molto pochi.
Se ne vuoi di più numerosi e meccanici ti consiglio questo pdf
http://www.mat.unimi.it/users/massa/eserind.pdf
Prova per esempio a prendere uno di quelli, SENZA guardare la soluzione, e postare la tua soluzione (e/o i tuoi dubbi) qui.
Cmq i miei post di prima non li hai commentati... capito tutto?
Ciao!
http://linuz.sns.it/~phi/induzione.pdf
E' in pratica una rielaborazione di parte della prima lezione di uno stage senior, quindi ci troverai fondamentalmente problemi sull'induzione "olimpici, carini e classici" con le loro soluzioni. L'ho scritta per un mio compagno di classe, purtroppo ai tempi in cui ancora non conoscevo LaTeX e usavo soltanto word...
Forse la dimostrazione del Teorema di Pick è un po' meno immediata, il resto spero tu possa seguirlo bene. Gli esercizi alla fine sono molto pochi.
Se ne vuoi di più numerosi e meccanici ti consiglio questo pdf
http://www.mat.unimi.it/users/massa/eserind.pdf
Prova per esempio a prendere uno di quelli, SENZA guardare la soluzione, e postare la tua soluzione (e/o i tuoi dubbi) qui.
Cmq i miei post di prima non li hai commentati... capito tutto?
Ciao!