OliForum Matematico

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.

qui si era parlato in generale dell'induzione
viewtopic.php?t=7060

l'avevo aperto io ma non mi era servito a molto. a me interessa sapere come si svolgono gli esercizi, cioè i passaggi da fare, e cosa devo fare riuscire. per esempio dopo sostituito n+1 all'interno della formula, come devo continuare?

Joker87 ha scritto:vorrei cercare di trovare, se possibile, un procedimento un po meccanio per dimostrare.

Se ti accingi a fare un esame di Logica Matematica, dovresti aver abbandonato questo atteggiamento mentale da molto tempo...

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!

Penso intendesse $ \log_2 n $.
Che diventa semplice.

allora, io prima dimostro il caso base che spesso è uguale a 0. poi dovrei sostituire n +1 nella formula, e dopo fatto questo come dovrei gestirla la formula? cioè che passaggi dovrei fare? cosa devo far riuscire?

non c'è un minimo di "meccanicità" in questo o dipende dal caso?

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.

Joker87 ha scritto:non c'è un minimo di "meccanicità"?

Per fortuna no, se no sai che noia...

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...

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

...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.

ho letto fino in fondo

se magari puoi mettere quella dispensa o dirmi qualche sito dove ci sono esercizi facili per cominciare mi faresti un piacere

ciao

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!

le ho scaricato, dopo ci do un'occhiata

spero mi possano essere utili

ciao e grazie