Il principio di induzione è un metodo di dimostrazione che permette di provare una proprietà per tutti i numeri naturali. Si verifica un caso iniziale e poi si mostra che la verità per implica la verità per .
| Concetto | Definizione | Nota essenziale |
|---|---|---|
| Passo base | Si verifica che la proposizione è vera, oppure se l’enunciato parte da . | È il punto di partenza della dimostrazione. |
| Ipotesi induttiva | Si assume vera per un generico . | L’assunzione vale solo per il passaggio logico, non per tutti i casi. |
| Passo induttivo | Si dimostra che da segue . | Questa è la catena che collega un caso al successivo. |
| Conclusione | Se base e passaggio sono veri, allora è vera per ogni . | Si ottiene la validità per tutti gli interi naturali ammessi. |
| Induzione forte | Si assume vere tutte le proposizioni da a , e si dimostra . | Si usa quando un solo caso precedente non basta. |
| Somma dei primi naturali | La proprietà tipica è . | È un esempio classico di dimostrazione per induzione. |
| Bernoulli | Per e , si prova che . | Mostra bene il ruolo del passo induttivo nelle disuguaglianze. |
| Potenze e formule ricorsive | Si verifica spesso una formula per o una relazione definita in modo ricorsivo. | L’induzione è utile per successioni, somme e disuguaglianze. |
Il principio di induzione, cioè il metodo che permette di provare una proposizione per tutti i numeri naturali, risponde a un problema preciso.
Si vuole evitare di controllare uno per uno tutti i casi. Si cerca invece una regola che colleghi un caso al successivo.
L'idea si può pensare come una fila di tessere del domino. Se la prima cade e ogni tessera ne fa cadere un'altra, allora cadono tutte.
Questa idea è utile in aritmetica, in algebra e nella logica matematica, cioè nel ramo che studia le dimostrazioni e le regole del ragionamento.
[IMMAGINE: Fila di tessere del domino su una linea orizzontale. La prima tessera è etichettata P(1). Le tessere successive sono etichettate P(2), P(3), P(4), ... Una freccia indica che ogni tessera fa cadere la successiva. Sul lato sinistro compare la scritta passo base, sul lato destro passo induttivo.]
Il punto decisivo è che non si dimostra ogni caso separatamente. Si dimostra solo l'inizio e il meccanismo di passaggio da un caso al successivo.
Per esempio, se la proprietà vale per e da segue , allora vale per .
La dimostrazione per induzione si divide in due parti obbligatorie. La prima verifica l'inizio. La seconda mostra che il passaggio funziona sempre.
Il passo base, cioè la verifica del primo caso, controlla che la proposizione sia vera per oppure per , secondo l'enunciato.
Per esempio, nella formula della somma dei primi numeri naturali, si controlla prima il caso .
Si ottiene . Il passo base è quindi verificato.
L' ipotesi induttiva, cioè l'assunzione temporanea della verità di , serve come strumento di lavoro. Non è ancora la conclusione finale.
Il passo induttivo, cioè la dimostrazione del passaggio da a , mostra che la proprietà si trasmette al caso successivo.
Per esempio, se da una relazione per si ricava la stessa relazione con , il meccanismo è completo.
Una dimostrazione per induzione si scrive in modo ordinato. Si enuncia la proprietà, si verifica il caso iniziale e si costruisce il passaggio generale.
Il procedimento ricorda una catena. Ogni anello regge il successivo. Se il primo è saldo, tutta la catena è controllata.
Per esempio, nella somma , il passaggio usa la stessa formula con e con .
La proprietà da dimostrare è che la somma dei primi numeri naturali ha una formula chiusa, cioè una scrittura diretta senza sommare tutti i termini.
Per si ha . Il caso iniziale è corretto.
Si assume ora che la formula valga per . Quindi si scrive .
Si raccoglie a fattor comune.
Si ottiene così la formula con . Il passo induttivo è completo.
Si verifica la formula per n = 4.
La somma vale .
Il risultato coincide. La formula è coerente con il caso numerico.
Un altro uso importante dell'induzione riguarda le formule per , cioè le potenze con esponente fisso. Si dimostrano spesso relazioni ottenute da somme ripetute o da identità algebriche.
Si considera per esempio la proprietà generale legata alle potenze e alle disuguaglianze. Il principio non crea la formula da solo. Verifica che una formula già proposta è valida per tutti i naturali.
Questa relazione si dimostra con l'induzione e viene usata spesso per stimare crescite e approssimazioni.
Per si ha e il secondo membro è .
Se si assume vera la stima per , allora si moltiplica per , che è positivo quando .
Poiché , si conclude .
Per esempio, con e , si ottiene e . La disuguaglianza è verificata.
La disuguaglianza di Bernoulli, cioè la stima che lega una potenza a una funzione lineare, è uno degli esempi classici dell'induzione.
Il caso base è . Si ha , quindi l'uguaglianza vale.
Per il passo induttivo si assume e si moltiplica per .
Se , allora il termine è non negativo. Quindi si ottiene la tesi per .
Per esempio, con e , si ha e . La stima risulta vera.
La correttezza dell'induzione dipende dalla struttura dei numeri naturali. Ogni numero successivo ha un predecessore immediato.
Se la proprietà è vera per il primo numero e ogni volta passa al successivo, allora nessun naturale può essere escluso.
Si può leggere questa idea come un effetto a catena. Il primo anello è il passo base. Ogni anello successivo è garantito dal passo induttivo.
Formalmente, il principio sfrutta l'ordinamento dei naturali. Non esistono salti tra due numeri consecutivi.
Per esempio, se si dimostra che una certa proprietà passa da un intero al successivo, allora vale per , per , per e così via senza interruzione.
L'induzione forte, cioè la variante in cui si assume vera tutta la famiglia di casi precedenti, è utile quando il caso successivo dipende da più valori anteriori.
Nel passo forte si assume che , e fino a siano vere. Poi si dimostra .
La struttura finale è simile all'induzione ordinaria. La differenza sta nella quantità di ipotesi disponibili nel passaggio.
Questa variante compare spesso in problemi di fattorizzazione, ricorrenze e dimostrazioni su successioni definite per più termini precedenti.
Per esempio, se un termine dipende dalla somma dei due precedenti, l'ipotesi forte fornisce più informazioni utili del passo classico.
Si considera una successione definita da valori precedenti.
Si verifica prima il numero iniziale. Poi si assume vera tutta la parte precedente fino a k.
In questo modo la conclusione usa più dati del caso standard.
Il principiodi induzione, cioè il metodo di dimostrazione che prova una proprietà per tutti i naturali a partire da un caso iniziale, si riassume in una struttura logica precisa.
Nella scrittura precedente, indica la proposizione da verificare per il naturale . Il simbolo significa "per ogni".
La proprietà fondamentale è questa: se il primo caso è vero e ogni caso vero trascina il successivo, allora tutti i casi risultano veri.
Si consideri la proprietà "ogni numero naturale maggiore di 1 ha almeno un divisore primo" come schema logico.
Se il passaggio da un caso al successivo è garantito, la conclusione vale per tutti i naturali a partire dal primo caso verificato.
Questo non prova ancora una proprietà concreta. Mostra però la forma della dimostrazione per induzione.
Il passo base, cioè la verifica del primo valore ammesso, stabilisce l'ancora iniziale della catena logica.
Se la proprietà parte da , il caso iniziale viene spostato su . La scelta dipende dall'enunciato della proprietà.
Si vuole dimostrare che la formula della somma dei primi naturali vale per ogni n.
Per si ottiene proprio . Il passo base è quindi verificato.
Il controllo iniziale è essenziale. Senza questo punto di partenza, la catena induttiva non avrebbe un primo anello.
L'ipotesi induttiva, cioè l'assunzione provvisoria che la proprietà sia vera per un naturale generico , serve come strumento di lavoro nel passo successivo.
Qui non si conclude ancora nulla sul caso generale. Si usa soltanto l'ipotesi come base algebrica o logica per ottenere il caso successivo.
Si assume vera la formula per un indice generico k.
L'uguaglianza non viene ancora dimostrata per tutti i valori. Viene accettata solo per il valore generico .
Da questa assunzione si ricava il caso . Questo è il cuore dell'induzione.
Il passo induttivo, cioè la dimostrazione di a partire da , realizza la trasmissione della verità da un caso al successivo.
La struttura è sempre la stessa. Si parte da un'uguaglianza o da una disuguaglianza nota per , poi si manipola l'espressione fino a ottenere il caso .
Si parte dall'ipotesi induttiva e si aggiunge il termine successivo.
Si raccoglie a fattor comune.
Si ottiene la formula per . Il passo induttivo è concluso.
Per le somme compare spesso la forma ricorsiva, cioè la relazione che collega il termine successivo alla somma precedente.
Qui indica la somma dei primi termini. Il termine è l'ultimo addendo aggiunto.
Si consideri la successione delle somme parziali di 1, 2, 3, 4.
Se , allora .
La forma ricorsiva rende immediato il legame tra casi consecutivi, che è ciò che l'induzione sfrutta.
Per una potenza intera si usa spesso la proprietà , cioè una potenza con esponente naturale fissato.
Questa è la forma classica della disuguaglianza di Bernoulli. Il parametro è reale e deve soddisfare .
Si controlla il caso numerico con un valore semplice di x.
Il confronto con il membro destro dà .
Si osserva che . Il caso è coerente con l'enunciato.
Una variante importante è il principio di induzione forte, cioè la versione in cui si assumono veri tutti i casi precedenti fino a .
L'induzione forte è utile quando il caso dipende da più casi precedenti, non solo da .
Si consideri una proprietà definita per ogni intero maggiore di 1.
Per provare il caso si usa la fattorizzazione di numeri minori già noti.
La variante forte è adatta quando la dipendenza tra i casi non è solo immediata.
Verificare per induzione che per ogni .
Si deve dimostrare una proprietà numerica, cioè un enunciato valido per tutti i naturali.
La proprietà è : la somma dei primi interi positivi ha una forma chiusa.
Si applicano il passo base e il passo induttivo. Il caso iniziale è .
Quindi è vera, perché il primo membro e il secondo membro valgono entrambi .
Si assume ora vera , cioè .
Si raccoglie a fattor comune.
Si ottiene così la formula per .
La proprietà vale quindi per ogni . vera.
Errore comune: dimenticare di sostituire la formula induttiva prima di semplificare.
Dimostrare per induzione che è definita per ogni , con fissato.
Si studia una proprietà algebrica, cioè una regola valida per gli esponenti naturali.
L'enunciato si verifica nel caso base e poi si collega a .
Nel passo base, per , si ha .
Quindi è soddisfatta per ogni valore di .
Si assume ora , cioè una legge valida per .
Sostituendo l'ipotesi induttiva, si ottiene la relazione per il passo successivo.
La dimostrazione mostra la struttura ricorsiva dell'esponente. corretta.
Errore comune: confondere la definizione di potenza con il risultato dell'induzione.
Dimostrare per induzione che per e .
Si tratta di una disuguaglianza, cioè di un confronto tra due espressioni algebriche.
Il passo base si controlla con .
Il caso iniziale è quindi vero per ogni .
Si assume ora vera l'ipotesi induttiva .
Moltiplicando per e usando , si conserva il verso della disuguaglianza.
Poiché , segue .
La disuguaglianza è dimostrata per ogni . valida.
Errore comune: dimenticare che il fattore deve essere non negativo.
Verificare che ogni intero può essere scritto come prodotto di numeri primi.
Si usa l'induzione forte, cioè la variante in cui si assumono vere tutte le proprietà precedenti fino a .
Il passo base è , e è già un numero primo.
Si suppone ora vera la proprietà per ogni intero da a .
Se non è primo, allora ammette una scomposizione più piccola.
Per l'ipotesi forte, sia sia si fattorizzano in primi.
Quindi anche si fattorizza in numeri primi.
Il risultato mostra perché la versione forte è necessaria nelle scomposizioni.
Errore comune: confondere l'induzione forte con una semplice ripetizione dell'ipotesi induttiva.
Si pensa che il principio di induzione serva a verificare molti casi numerici prima di concludere.
Il principio di induzione, cioè un metodo di dimostrazione, richiede una base e un passaggio logico valido per ogni .
L’errore nasce perché si confonde l’osservazione di esempi con una prova. La verifica di molti casi non basta mai per dimostrare una proprietà per tutti i naturali.
Si scrive solo il passo base e si conclude che la proprietà vale per ogni .
Si deve dimostrare anche il passo induttivo, cioè che da segue per ogni .
Il passo base mostra soltanto l’avvio della catena. Senza il passaggio da un numero al successivo, la dimostrazione resta incompleta.
Nell’ipotesi induttiva si usa già , oppure si assume ciò che si vuole provare.
Nell’ipotesi induttiva si assume vera solo , poi si deduce con passaggi autonomi.
Questo errore rende la prova circolare. L’ipotesi induttiva serve come appoggio, non come conclusione anticipata.
Nel principio di induzione per le somme si dimentica di trasformare la formula da a .
Si parte dalla formula per e si mostra che vale anche per , aggiungendo il nuovo termine della somma.
Nelle somme l’errore tipico è non usare la struttura ricorsiva. Il controllo corretto consiste nel separare l’ultimo addendo e riscrivere l’espressione con ordine.
Si crede che il principio di induzione funzioni solo perché i naturali sono tanti, quindi la proprietà ‘si estende da sola’.
Funziona perché ogni naturale ha un successivo e perché la base, unita al passaggio , genera tutti i casi.
La giustificazione è logica, non intuitiva. La proprietà si propaga lungo la catena senza salti.
Si usa l’induzione forte come se fosse identica a quella semplice, senza dire quali casi sono assunti veri.
Nell’induzione forte, cioè la variante in cui si assumono veri tutti i casi da a , bisogna dichiarare esplicitamente l’insieme delle ipotesi.
L’errore nasce dalla somiglianza tra le due tecniche. Nella variante forte l’ipotesi è più ampia e va formulata con precisione per evitare ambiguità.
Il principio di induzione è un criterio di dimostrazione che permette di provare una proprietà per tutti i numeri naturali.
Si mostra prima che la proprietà è vera nel primo caso. Poi si prova che, se è vera per un intero , allora è vera anche per .
La dimostrazione per induzione funziona in due passaggi consecutivi.
Nel passo base si verifica la proprietà per , oppure per , se il problema parte da zero.
Nel passo induttivo si assume vera la proprietà per e si deduce la verità per .
Il passo base verifica il primo caso della proprietà, mentre il passo induttivo mostra il passaggio da un caso al successivo.
Il passo base è la verifica iniziale. L’ipotesi induttiva cioè l’assunzione che la proprietà valga per , serve per dimostrare il passo induttivo cioè la validità per .
Il principio di induzione si usa spesso per dimostrare formule di somma valide per ogni numero naturale.
Per esempio, per si ottiene , e anche .
L’induzione funziona perché collega ogni caso al successivo, creando una catena che parte dal caso iniziale.
Se il primo anello è vero e ogni anello forza il successivo, allora tutti gli anelli risultano veri. Per esempio, da segue , da segue , e così via.
L’induzione forte è una variante del principio di induzione in cui si assume vera tutta la catena delle proprietà precedenti fino a .
Si usa quando il passo da a dipende non solo da ma anche da casi precedenti. Per esempio, è utile nelle dimostrazioni sui divisori o sulle successioni ricorsive.
Un esempio classico è la formula delle potenze di 2.
Per si ha e . La verifica iniziale e il passaggio da a mostrano il meccanismo dell’induzione.
