Il principio di induzione
Il principio di induzione matematica è la tecnica dimostrativa fondamentale per provare che un enunciato , dipendente da un numero naturale , è vero per infiniti valori di a partire da un indice iniziale . In questa lezione introduciamo prima la notazione compatta di sommatoria , indispensabile per formulare e manipolare identità algebriche su termini, e sviluppiamo poi il principio di induzione applicandolo a somme finite, divisibilità e disuguaglianze.
Il simbolo di sommatoria
Quando dobbiamo sommare una successione di termini indicizzati da un intero che varia da un estremo inferiore a un estremo superiore (con ), usiamo la lettera greca maiuscola sigma ():
La variabile si chiama indice di sommatoria ed è un indice muto: il risultato della somma non dipende dalla lettera scelta per indicarlo, per cui
Se , la somma contiene un solo addendo: . (Per convenzione, se l’estremo superiore è minore dell’inferiore, la somma vuota vale ).
Proprietà algebriche della sommatoria
- Sommatoria di una costante : sommare la stessa costante da a significa addizionare per volte:
- Omogeneità (raccoglimento di una costante che non dipende da ):
- Additività (linearità rispetto alla somma/differenza):
- Scomposizione dell’intervallo di indici (isolamento dell’ultimo termine): fondamentale nel passo induttivo per passare da a :
- Traslazione dell’indice: se si aumenta l’indice negli estremi di un intero , occorre diminuire di l’indice all’interno del termine generale:
- Somme telescopiche: se il termine generale si scrive come differenza di due termini consecutivi , tutti i termini intermedi si elidono a coppie e sopravvivono solo il primo e l’ultimo:
L’idea intuitiva dell’induzione: l’effetto domino
Come possiamo dimostrare con un numero finito di passaggi che una proprietà vale per tutti gli infiniti numeri naturali ? Immaginiamo una fila infinita di tessere del domino numerate a partire da :
- Passo base: spingiamo con il dito la prima tessera , verificando direttamente che cada.
- Passo induttivo: dimostriamo che le tessere sono posizionate abbastanza vicine tra loro da garantire che, se una qualunque tessera cade, allora urta e fa cadere necessariamente anche la tessera successiva .
Una volta garantite queste due condizioni, si innesca una reazione a catena inarrestabile: è vera; per il passo induttivo , quindi cade ; ma allora , e così via per ogni .
Enunciato formale del principio di induzione
Sia un predicato definito per ogni numero naturale (con fissato, tipicamente oppure ). Se valgono entrambe le seguenti condizioni:
- Passo base: è vera;
- Passo induttivo: per ogni , assumendo vera (ipotesi induttiva), segue che è vera anche (tesi induttiva);
allora è vera per ogni .
In simboli logici:
Perché assumere non è un ragionamento circolare?
Nel passo induttivo non stiamo affermando gratuitamente che sia vera per ogni : stiamo dimostrando l’implicazione logica per un generico . Per dimostrare un’implicazione , la regola deduttiva standard consiste proprio nell’assumere vera la premessa (ipotesi induttiva) e dedurne la conclusione (tesi induttiva).
Schema operativo in 5 passi
Quando imposti una dimostrazione per induzione, segui sempre questa struttura ordinata:
- Enunciato e dominio: scrivi chiaramente qual è la proposizione e da quale valore parte.
- Passo base (): sostituisci nei due membri (o nella proprietà) e verifica che sia soddisfatta.
- Ipotesi induttiva (): fissa un generico e scrivi esplicitamente l’enunciato che supponi vero.
- Passo induttivo (): scrivi la tesi a cui vuoi arrivare, parti da un membro di , sostituisci al suo interno l’ipotesi induttiva e trasforma algebricamente l’espressione fino a ottenere l’altro membro di .
- Conclusione: dichiara che, per il principio di induzione, è vera per ogni .
Esempi guidati
Esempio 1: Somma dei primi numeri naturali (Formula di Gauss)
Dimostriamo che per ogni vale:
- Passo base (): il membro sinistro è ; il membro destro è . Quindi è vera.
- Ipotesi induttiva: sia e supponiamo vera :
- Passo induttivo (): dobbiamo dimostrare che . Isoliamo l’ultimo termine della sommatoria e usiamo l’ipotesi induttiva: Abbiamo ottenuto esattamente . Per il principio di induzione la formula vale per ogni .
Esempio 2: Somma dei primi numeri dispari
Dimostriamo che per ogni la somma dei primi numeri dispari è uguale a :
- Passo base (): a sinistra abbiamo , a destra . Vera.
- Ipotesi induttiva: supponiamo che per un certo valga .
- Passo induttivo (): il -esimo numero dispari è . Allora: La tesi è verificata, quindi vale per ogni .
Esempio 3: Divisibilità per induzione
Dimostriamo che per ogni il numero è divisibile per , ossia:
- Passo base (): , divisibile per .
- Ipotesi induttiva: supponiamo che per esista tale che , ovvero .
- Passo induttivo (): consideriamo e sostituiamo : Poiché , anche è multiplo di . Per induzione la proprietà vale per ogni .
Esempio 4: Disuguaglianze per induzione (Disuguaglianza di Bernoulli e )
Nelle disuguaglianze per induzione si usa una catena di maggiorazioni o minorazioni per passare da a .
4a. Disuguaglianza di Bernoulli
Sia fissato con . Dimostriamo che per ogni vale:
- Passo base (): e , quindi è vera (vale anche per : ).
- Ipotesi induttiva: supponiamo per un certo .
- Passo induttivo (): poiché per ipotesi , il fattore è strettamente positivo (). Moltiplicando ambo i membri della disuguaglianza induttiva per , il verso della disuguaglianza si conserva: dove nell’ultimo passaggio abbiamo usato il fatto che e , dunque . Ciò dimostra .
4b. Crescita esponenziale
Dimostriamo che per ogni vale .
- Passo base (): , vera (per : ).
- Ipotesi induttiva: sia per un generico .
- Passo induttivo (): moltiplicando per e usando : quindi .
Verifica empirica contro dimostrazione rigorosa, e induzione forte
Controllare che un enunciato sia vero per non costituisce una dimostrazione: esistono predicati veri per molti valori iniziali ma falsi da un certo indice in poi!
- Ad esempio, il polinomio di Eulero produce numeri primi per tutti gli interi , ma per dà , che non è primo.
- Analogamente, la congettura «ogni numero dispari maggiore di è somma di una potenza di e di un numero primo» funziona per tutti i dispari fino a , ma fallisce per (sottraendo da le potenze si ottengono , nessuno dei quali è primo).
Principio di induzione forte (o seconda forma)
Talvolta, per dimostrare non basta sapere che è vera la sola proposizione immediatamente precedente , ma serve sapere che sono vere tutte le proposizioni da fino a :
L’induzione forte è logicamente equivalente all’induzione ordinaria ed è essenziale, ad esempio, per dimostrare che ogni intero si fattorizza come prodotto di numeri primi (perché se è composto, si scrive come con , a cui si applica l’ipotesi induttiva forte) o per studiare successioni ricorsive a più passi come i numeri di Fibonacci ().
Errori frequenti
- Saltare il passo base: il solo passo induttivo non garantisce nulla se la catena non parte! Ad esempio, la proposizione falsa soddisfa il passo induttivo (aggiungendo a si ottiene ), ma è falsa per ogni perché fallisce nel passo base .
- Confondere l’ultimo termine aggiunto nel passaggio : nella somma , passando da a non si aggiunge , bensì il termine ottenuto sostituendo nella formula generale, cioè .
- Assumere direttamente la tesi e ridurla a un’identità senza verificare la reversibilità dei passaggi: è sempre preferibile partire da un membro di e arrivare all’altro attraverso una catena di uguaglianze o disuguaglianze orientate.
- Dimenticare da quale vale una disuguaglianza: alcune disuguaglianze (come ) sono false per e diventano vere solo a partire da .
Esercizi di prova
-
(Base - Somma dei quadrati) Dimostra per induzione che per ogni vale la formula per la somma dei primi quadrati perfetti:
Soluzione
- Passo base (): a sinistra ; a destra . Vera.
- Ipotesi induttiva: supponiamo vera la formula per : .
- Passo induttivo (): dobbiamo dimostrare che . Calcoliamo:
Fattorizzando il trinomio otteniamo:
che coincide esattamente con . Per il principio di induzione la formula vale per ogni .
-
(Base - Somma geometrica) Sia con . Dimostra per induzione che per ogni vale:
Soluzione
- Passo base (): a sinistra ; a destra . Vera.
- Ipotesi induttiva: supponiamo che per valga .
- Passo induttivo (): aggiungiamo il termine : Ciò dimostra , quindi l’identità vale per ogni .
-
(Intermedio - Somma di frazioni / telescopica) Dimostra per induzione che per ogni vale:
Soluzione
- Passo base (): a sinistra ; a destra . Vera.
- Ipotesi induttiva: supponiamo che per valga .
- Passo induttivo (): Questa è esattamente la formula per . (Osservazione: l’identità si può ricavare anche come somma telescopica notando che , da cui la somma vale ).
-
(Intermedio - Divisibilità) Dimostra per induzione che per ogni il numero è divisibile per (e anche per ).
Soluzione
Mostriamo la divisibilità per (che implica quella per ): .
- Passo base (): , divisibile per .
- Ipotesi induttiva: supponiamo per un certo e .
- Passo induttivo (): sviluppiamo il cubo :
Osserviamo che tra due numeri interi consecutivi e uno dei due è sempre pari, quindi il prodotto è sempre un multiplo di . Pertanto , e dunque:
che è divisibile per . Per induzione la tesi vale per ogni .
-
(Esame - Disuguaglianza con base desplazata) Dimostra per induzione che per ogni numero naturale vale la disuguaglianza:
(Suggerimento: puoi usare il fatto già noto che per vale ).Soluzione
- Passo base (): a sinistra ; a destra . Poiché , è vera. (Nota: per si ha ).
- Ipotesi induttiva: sia e supponiamo .
- Passo induttivo (): dobbiamo dimostrare che .
Osserviamo preliminarmente che per ogni vale , quindi .
Allora, partendo da e applicando prima l’ipotesi induttiva e poi la stima :
Abbiamo ottenuto . Per il principio di induzione, per ogni .
Provenienza del materiale
Sintesi ragionata ed estesa della lezione C1MAT1U2L3_Il_principio_di_induzione.pdf e degli Appunti_di_fine_Unità_2.pdf (Corso di Matematica 1, CdL in Sicurezza Informatica / SecAI - Università degli Studi di Milano), con aggiunta delle proprietà del simbolo di sommatoria , della disuguaglianza di Bernoulli e di esercizi svolti graduati.