Come dimostrare il principio di induzione

di Effe W. tramite: O2O difficoltà: media

Iniziamo la trattazione introducendo innanzitutto il principio di induzione, definito come un assioma dei numeri naturali. Ricorre frequentemente l'uso di questo metodo in alcune dimostrazioni di proposizioni al cui interno compare una variabile legata ai numeri naturali. Per una migliore comprensione pratica, possiamo dire che è basato, per esempio, sull'effetto della "scala infinita": se si è capaci di salire il primo gradino della scala, si potrà salire anche il secondo e, se cosi accade, si potranno salire tutti i gradini della scala all'infinito; ulteriormente può essere associato a "l'effetto domino": mettiamo in successione le tessere del domino, se ne cade una, cadrà anche quella successiva e se cade la prima, cadranno tutte. Perciò, data una famiglia di proposizioni, se si dimostra che una è vera e se una è vera, si dimostra che sia vera anche la successiva, risulterà dimostrata anche la validità di tutte le proposizioni della famiglia.

1 Enunciamo il principio di induzione Consideriamo una proposizione Pn, con n appartenente all'insieme dei numeri naturali, e una proposizione P (n+1). Si può affermare che nel caso in cui la Pn sia vera, sarà vera anche la P (n+1). Più precisamente, le due ipotesi del principio dicono che: I) se esiste un valore m, appartenente all'insieme N, tale che Pm sia vera e II) se per qualsiasi valore di m fissato, risulta essere Pm vera e di conseguenza risulta essere vera anche P (m+1), allora saranno vere tutte le proposizioni Pn, per ogni valore di n maggiore o uguale a m. Pn è detta ipotesi induttiva.

2 Dimostrazione del principio Si può realizzare una dimostrazione del principio induttivo, utilizzando il principio del minimo per esempio. Consideriamo l'insieme A, che coincide con l'insieme dei numeri naturali, e per dimostrare appunto che A = N, passiamo a prendere in esame l'insieme B, complementare dell'insieme A, provando che sia un insieme vuoto. Per assurdo, supponiamo che l'insieme B sia diverso dall'insieme vuoto e l'assioma del minimo ci indica che l'insieme B avrà un minimo y. Ora cerchiamo una contraddizione: suppongo di aver trovato un altro minimo w, nell'insieme N, tale che risulti che w sia minore o uguale di y: questo contraddice che y fosse un minimo in B.

Continua la lettura

3 Esempio di applicazione del principio di induzione Uno degli esempi classici in cui si utilizza il principio induttivo risulta essere quello in cui la somma S dei primi numeri naturali da 0 ad n, sia uguale a [n*(n+1)]/2.  In questo caso la Pn risulta essere proprio pari a: 1+2+3+……+n = [n*(n+1)]/2.  Approfondimento Come utilizzare il principio di induzione per una dimostrazione (clicca qui) Analizziamo il caso in cui n=1, valore iniziale, e dimostriamo che Pn sia vera.  Quando n=1, dobbiamo sommare solo un numero naturale, perciò a sinistra dell’uguaglianza avremo 1 mentre a destra andremo a sostituire il valore 1 al posto della n, ottenendo quindi: 1 = [ 1*(1+1)]/2 => 1 = 1! Abbiamo cosi verificato l’ipotesi I).  Ora verifichiamo anche l’ipotesi II): se Pn è vera, sarà vera anche P (n+1), quindi andando a sostituire (n+1) al posto di n, otterremo che S (n+1) = [(n+1)(n+2)] / 2.  Lavorando con i numeri e svolgendo semplici passaggi meccanici, si potrà scrivere che S (n+1) = S (n) + (n+1); al posto di S (n) sostituiremo proprio l’ipotesi iniziale, ovvero [n*(n+1)]/2 e risulteranno verificate le nostre ipotesi.

4 Conclusioni Tale principio può essere applicato in tanti casi: quello analizzato insieme è abbastanza immediato. In conclusione, perciò, all'interno di un processo di induzione, è importante legare sempre il passaggio successivo a quello precedente, cosa che non è sempre di facile intuizione.

Come dimostrare la non numerabilità dell'insieme R L'esempio più noto di un insieme non numerabile è l ... continua » Guida alla verifica delle ipotesi Quando si studia un determinato avvenimento scientifico, in molti casi si ... continua » Teorema dell'infinità dei numeri primi: dimostrazione La matematica è una scienza esatta e si avvale di particolari ... continua » Teorema di Heine-Borel: dimostrazione Il Teorema di Heine-Borel afferma che un sottospazio di R ^ n ... continua »

Stampa la guida Segnala inappropriato
Devi inserire una descrizione del problema

Altre guide

I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer»”.