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

  1. Sommatoria di una costante : sommare la stessa costante da a significa addizionare per volte:
  2. Omogeneità (raccoglimento di una costante che non dipende da ):
  3. Additività (linearità rispetto alla somma/differenza):
  4. Scomposizione dell’intervallo di indici (isolamento dell’ultimo termine): fondamentale nel passo induttivo per passare da a :
  5. Traslazione dell’indice: se si aumenta l’indice negli estremi di un intero , occorre diminuire di l’indice all’interno del termine generale:
  6. 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 :

  1. Passo base: spingiamo con il dito la prima tessera , verificando direttamente che cada.
  2. 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 .

Il principio di induzione rappresentato come una catena di tessere del domino

Enunciato formale del principio di induzione

Sia un predicato definito per ogni numero naturale (con fissato, tipicamente oppure ). Se valgono entrambe le seguenti condizioni:

  1. Passo base: è vera;
  2. 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:

  1. Enunciato e dominio: scrivi chiaramente qual è la proposizione e da quale valore parte.
  2. Passo base (): sostituisci nei due membri (o nella proprietà) e verifica che sia soddisfatta.
  3. Ipotesi induttiva (): fissa un generico e scrivi esplicitamente l’enunciato che supponi vero.
  4. 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 .
  5. 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

  1. (Base - Somma dei quadrati) Dimostra per induzione che per ogni vale la formula per la somma dei primi quadrati perfetti:

  2. (Base - Somma geometrica) Sia con . Dimostra per induzione che per ogni vale:

  3. (Intermedio - Somma di frazioni / telescopica) Dimostra per induzione che per ogni vale:

  4. (Intermedio - Divisibilità) Dimostra per induzione che per ogni il numero è divisibile per (e anche per ).

  5. (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 ).

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.