Il principio di induzione matematica è uno dei metodi dimostrativi più importanti dell'intera matematica. Esso permette di dimostrare che una proprietà vale per tutti i numeri naturali, trasformando un problema con infiniti casi in un ragionamento finito, rigoroso e controllabile.
L'idea di fondo è semplice: se una proprietà è vera all'inizio e se, ogni volta che è vera per un certo numero naturale, risulta vera anche per il successivo, allora essa è vera per tutti i numeri naturali.
Indice
- Intuizione del principio di induzione
- Enunciato del principio di induzione
- Base dell'induzione e passo induttivo
- Perché l'induzione funziona
- Induzione a partire da un valore arbitrario
- Induzione e insiemi induttivi
- Esempio 1: somma dei primi numeri naturali
- Esempio 2: una disuguaglianza esponenziale
- Principio del buon ordinamento
- Equivalenza tra induzione e buon ordinamento
- Induzione forte
- Errori comuni nelle dimostrazioni per induzione
- Induzione e definizioni ricorsive
- Conclusione
Intuizione del principio di induzione
Il principio di induzione viene spesso spiegato attraverso l'immagine delle tessere del domino.
Immaginiamo una fila infinita di tessere. Per essere certi che tutte cadano, non occorre controllare una per una tutte le tessere. È sufficiente verificare due fatti:
- la prima tessera cade;
- ogni tessera, cadendo, fa cadere la successiva.
Se entrambe le condizioni sono soddisfatte, allora tutte le tessere della fila cadranno.
In matematica accade qualcosa di analogo. Per dimostrare che una proprietà \(P(n)\) vale per ogni numero naturale \(n\), si verifica che valga per il primo valore e si dimostra che la validità per un numero qualunque implica la validità per il numero successivo.
Enunciato del principio di induzione
Sia \(P(n)\) una proprietà dipendente da un numero naturale \(n\). Il principio di induzione matematica afferma che, se valgono le due condizioni:
\[ P(1) \text{ è vera} \]
e
\[ P(n) \Rightarrow P(n+1) \quad \text{per ogni } n \geq 1, \]
allora:
\[ P(n) \text{ è vera per ogni } n\in\mathbb{N}, \ n\geq 1. \]
Se invece si adotta la convenzione secondo cui i numeri naturali iniziano da \(0\), il caso base sarà \(P(0)\) e il passo induttivo sarà:
\[ P(n) \Rightarrow P(n+1) \quad \text{per ogni } n\geq 0. \]
Base dell'induzione e passo induttivo
Una dimostrazione per induzione è composta da due momenti fondamentali.
1. Base dell'induzione
Si dimostra che la proprietà è vera per il primo valore considerato, solitamente \(n=1\) oppure \(n=0\).
Questa verifica è indispensabile: senza un punto di partenza, la catena induttiva non può iniziare.
2. Passo induttivo
Si suppone che la proprietà sia vera per un certo numero naturale \(n\). Questa supposizione prende il nome di ipotesi induttiva.
A partire da essa, si dimostra che la proprietà è vera anche per \(n+1\).
In forma simbolica:
\[ P(n)\Rightarrow P(n+1). \]
Il punto essenziale è che non si sta assumendo che la proprietà sia vera per tutti i numeri naturali. Si sta dimostrando una implicazione: se la proprietà vale in un certo punto della catena, allora vale anche nel punto successivo.
Perché l'induzione funziona
Il principio di induzione funziona perché i numeri naturali sono costruiti in modo ordinato e successivo:
\[ 1,2,3,4,\dots \]
oppure, se si parte da \(0\):
\[ 0,1,2,3,\dots \]
Una volta verificato il primo caso, il passo induttivo permette di passare dal primo al secondo, dal secondo al terzo, dal terzo al quarto, e così via.
In questo modo si genera una catena infinita di implicazioni:
\[ P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow P(4)\Rightarrow \dots \]
La forza dell'induzione consiste proprio in questo: un ragionamento finito riesce a controllare infiniti casi perché sfrutta la struttura stessa dei numeri naturali.
Induzione a partire da un valore arbitrario
Non è necessario che la catena induttiva parta sempre da \(n=1\) oppure da \(n=0\). In molte situazioni, una proprietà diventa vera soltanto a partire da un certo intero \(n_0\).
In questo caso il principio di induzione si enuncia così. Se:
\[ P(n_0) \text{ è vera} \]
e
\[ P(n)\Rightarrow P(n+1) \quad \text{per ogni } n\geq n_0, \]
allora:
\[ P(n) \text{ è vera per ogni } n\geq n_0. \]
Per esempio, dimostriamo che:
\[ 2^n>n^2 \]
per ogni \(n\geq 5\).
Base dell'induzione
Per \(n=5\), abbiamo:
\[ 2^5=32 \]
e
\[ 5^2=25. \]
Quindi:
\[ 2^5>5^2. \]
Passo induttivo
Supponiamo che, per un certo \(n\geq 5\), valga:
\[ 2^n>n^2. \]
Dobbiamo dimostrare che:
\[ 2^{n+1}>(n+1)^2. \]
Poiché:
\[ 2^{n+1}=2\cdot 2^n, \]
usando l'ipotesi induttiva otteniamo:
\[ 2^{n+1}=2\cdot 2^n>2n^2. \]
Ora osserviamo che, per ogni \(n\geq 5\),
\[ 2n^2>(n+1)^2. \]
Infatti:
\[ 2n^2-(n+1)^2 = n^2-2n-1. \]
Per \(n\geq 5\), si ha:
\[ n^2-2n-1=(n-1)^2-2\geq 4^2-2=14>0. \]
Quindi:
\[ 2n^2>(n+1)^2. \]
Combinando le due disuguaglianze, otteniamo:
\[ 2^{n+1}>2n^2>(n+1)^2. \]
Dunque:
\[ 2^{n+1}>(n+1)^2. \]
Il passo induttivo è dimostrato. Per il principio di induzione a partire da \(n_0=5\), concludiamo che:
\[ 2^n>n^2 \]
per ogni \(n\geq 5\).
La logica non cambia: la catena delle implicazioni inizia semplicemente da un punto diverso.
Induzione e insiemi induttivi
Il principio di induzione può essere espresso anche in forma insiemistica.
Un sottoinsieme \(A\subseteq\mathbb{N}\) si dice induttivo se soddisfa due condizioni:
\[ 1\in A \]
e
\[ n\in A\Rightarrow n+1\in A. \]
In altre parole, \(A\) contiene il primo numero naturale e, insieme a ogni numero, contiene anche il suo successivo.
Il principio di induzione afferma allora che:
\[ \text{se } A\subseteq\mathbb{N} \text{ è induttivo, allora } A=\mathbb{N}. \]
Questa formulazione mostra un fatto importante: l'induzione non è soltanto una tecnica per risolvere esercizi, ma una proprietà strutturale dell'insieme dei numeri naturali.
Esempio 1: somma dei primi numeri naturali
Dimostriamo per induzione che, per ogni \(n\geq 1\),
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Base dell'induzione
Per \(n=1\), il membro sinistro è:
\[ 1. \]
Il membro destro è:
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1. \]
Quindi la formula è vera per \(n=1\).
Passo induttivo
Supponiamo che la formula sia vera per un certo \(n\geq 1\), cioè supponiamo:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Dobbiamo dimostrare che allora vale anche:
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
Partiamo dal membro sinistro:
\[ 1+2+3+\dots+n+(n+1). \]
Per l'ipotesi induttiva possiamo sostituire la somma \(1+2+\dots+n\) con \(\frac{n(n+1)}{2}\):
\[ 1+2+\dots+n+(n+1)=\frac{n(n+1)}{2}+(n+1). \]
Raccogliamo \(n+1\):
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right). \]
Poiché:
\[ \frac{n}{2}+1=\frac{n+2}{2}, \]
otteniamo:
\[ (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2}. \]
Dunque:
\[ 1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}. \]
La proprietà è quindi vera per \(n+1\). Per il principio di induzione, la formula vale per ogni \(n\geq 1\).
Esempio 2: una disuguaglianza esponenziale
Dimostriamo che, per ogni \(n\in\mathbb{N}\) con \(n\geq 0\),
\[ 2^n\geq n+1. \]
Base dell'induzione
Per \(n=0\), abbiamo:
\[ 2^0=1 \]
e
\[ 0+1=1. \]
Quindi:
\[ 2^0\geq 0+1. \]
La proprietà è vera per \(n=0\).
Passo induttivo
Supponiamo che, per un certo \(n\geq 0\), valga:
\[ 2^n\geq n+1. \]
Dobbiamo dimostrare che:
\[ 2^{n+1}\geq n+2. \]
Osserviamo che:
\[ 2^{n+1}=2\cdot 2^n. \]
Usando l'ipotesi induttiva:
\[ 2\cdot 2^n\geq 2(n+1). \]
Quindi:
\[ 2^{n+1}\geq 2n+2. \]
Poiché \(n\geq 0\), abbiamo:
\[ 2n+2\geq n+2. \]
Pertanto:
\[ 2^{n+1}\geq n+2. \]
La proprietà vale anche per \(n+1\). Per induzione:
\[ 2^n\geq n+1 \]
per ogni \(n\geq 0\).
Principio del buon ordinamento
Il principio del buon ordinamento afferma che ogni sottoinsieme non vuoto di \(\mathbb{N}\) possiede un elemento minimo.
In simboli:
\[ A\subseteq\mathbb{N},\quad A\neq\varnothing \quad\Longrightarrow\quad \exists m\in A \text{ tale che } m\leq a \text{ per ogni } a\in A. \]
L'elemento \(m\) si chiama minimo di \(A\).
Attenzione: il minimo non è semplicemente un elemento piccolo. È un elemento dell'insieme che è minore o uguale di tutti gli altri elementi dell'insieme.
Per esempio, se:
\[ A=\{5,8,13,21\}, \]
allora:
\[ \min A=5. \]
Se invece:
\[ B=\{n\in\mathbb{N}\mid n\geq 10\}, \]
allora:
\[ \min B=10. \]
Il principio del buon ordinamento è una proprietà caratteristica dei numeri naturali. Non vale, ad esempio, per tutti i sottoinsiemi non vuoti di \(\mathbb{Z}\). Infatti l'insieme:
\[ \mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\} \]
non ha un minimo.
Equivalenza tra induzione e buon ordinamento
Il principio di induzione e il principio del buon ordinamento sono equivalenti: assumendo uno dei due, si può dimostrare l'altro.
Questa equivalenza è importante perché mostra che l'induzione non è un semplice artificio tecnico, ma una conseguenza profonda della struttura ordinata dei numeri naturali.
Dal buon ordinamento al principio di induzione
Supponiamo valido il principio del buon ordinamento. Vogliamo dimostrare il principio di induzione.
Sia \(P(n)\) una proprietà dei numeri naturali. Supponiamo che:
\[ P(1) \text{ sia vera} \]
e che:
\[ P(n)\Rightarrow P(n+1) \quad \text{per ogni } n\geq 1. \]
Dobbiamo dimostrare che \(P(n)\) è vera per ogni \(n\geq 1\).
Ragioniamo per assurdo. Supponiamo che esista almeno un numero naturale per cui \(P\) è falsa. Consideriamo l'insieme dei controesempi:
\[ A=\{n\in\mathbb{N}\mid P(n)\text{ è falsa}\}. \]
Per ipotesi, \(A\neq\varnothing\). Quindi, per il principio del buon ordinamento, \(A\) possiede un minimo. Indichiamolo con \(m\).
Poiché \(P(1)\) è vera, il numero \(1\) non appartiene ad \(A\). Dunque \(m\neq 1\), quindi \(m>1\).
Allora \(m-1\) è un numero naturale minore di \(m\). Poiché \(m\) è il minimo elemento di \(A\), il numero \(m-1\) non può appartenere ad \(A\).
Quindi \(P(m-1)\) è vera.
Ma, per il passo induttivo:
\[ P(m-1)\Rightarrow P(m). \]
Ne segue che \(P(m)\) è vera.
Questo è impossibile, perché \(m\in A\), e quindi \(P(m)\) dovrebbe essere falsa.
Abbiamo ottenuto una contraddizione. Dunque l'insieme dei controesempi è vuoto:
\[ A=\varnothing. \]
Pertanto \(P(n)\) è vera per ogni \(n\geq 1\). Il principio di induzione è dimostrato.
Dal principio di induzione al buon ordinamento
Supponiamo ora valido il principio di induzione. Vogliamo dimostrare il principio del buon ordinamento.
Sia \(A\subseteq\mathbb{N}\) un sottoinsieme non vuoto. Dobbiamo dimostrare che \(A\) possiede un minimo.
Ragioniamo per assurdo. Supponiamo che \(A\) non possieda alcun minimo.
Se \(1\in A\), allora \(1\) sarebbe automaticamente il minimo di \(A\), poiché nessun numero naturale positivo è minore di \(1\). Ma per ipotesi \(A\) non ha minimo. Quindi:
\[ 1\notin A. \]
Consideriamo ora la proprietà:
\[ P(n): \quad 1,2,\dots,n \notin A. \]
Cioè \(P(n)\) afferma che nessuno dei primi \(n\) numeri naturali appartiene ad \(A\).
Base dell'induzione
Abbiamo già osservato che:
\[ 1\notin A. \]
Quindi \(P(1)\) è vera.
Passo induttivo
Supponiamo vera \(P(n)\), cioè supponiamo che:
\[ 1,2,\dots,n \notin A. \]
Dobbiamo dimostrare che:
\[ 1,2,\dots,n,n+1 \notin A. \]
Sappiamo già, per ipotesi induttiva, che \(1,2,\dots,n\) non appartengono ad \(A\). Resta da mostrare che \(n+1\notin A\).
Se fosse:
\[ n+1\in A, \]
allora \(n+1\) sarebbe il minimo di \(A\), perché nessuno dei numeri naturali precedenti appartiene ad \(A\).
Ma questo contraddice l'ipotesi che \(A\) non abbia minimo.
Quindi:
\[ n+1\notin A. \]
Il passo induttivo è dimostrato.
Per il principio di induzione, \(P(n)\) è vera per ogni \(n\geq 1\). Dunque nessun numero naturale appartiene ad \(A\), cioè:
\[ A=\varnothing. \]
Ma questo è impossibile, perché avevamo supposto \(A\neq\varnothing\).
La contraddizione mostra che \(A\) deve possedere un minimo. Il principio del buon ordinamento è dimostrato.
Induzione forte
Esiste una variante del principio di induzione chiamata induzione forte.
Nell'induzione ordinaria, per dimostrare \(P(n+1)\), si assume vera soltanto \(P(n)\).
Nell'induzione forte, invece, per dimostrare \(P(n+1)\), si assume che siano vere tutte le proprietà precedenti:
\[ P(1),P(2),\dots,P(n). \]
L'enunciato è il seguente. Se:
\[ P(1) \text{ è vera} \]
e, per ogni \(n\geq 1\),
\[ P(1)\land P(2)\land \dots \land P(n) \Rightarrow P(n+1), \]
allora:
\[ P(n) \text{ è vera per ogni } n\geq 1. \]
L'induzione forte non è logicamente più potente dell'induzione ordinaria: le due forme sono equivalenti. Tuttavia, in molte dimostrazioni, l'induzione forte è più naturale e più semplice da usare.
Esempio 1: fattorizzazione in numeri primi
Un esempio classico di applicazione dell'induzione forte è la dimostrazione del fatto che ogni numero naturale maggiore di \(1\) è primo oppure può essere scritto come prodotto di numeri primi.
Sia \(n>1\). Se \(n\) è primo, non c'è nulla da dimostrare.
Se \(n\) non è primo, allora esistono due interi \(a\) e \(b\), entrambi maggiori di \(1\) e minori di \(n\), tali che:
\[ n=ab. \]
Poiché \(a<n\) e \(b<n\), l'ipotesi dell'induzione forte consente di supporre che \(a\) e \(b\) siano primi oppure prodotti di numeri primi.
Di conseguenza anche \(n=ab\) è prodotto di numeri primi.
Questo esempio mostra perché, in certi contesti, è utile poter usare non soltanto il caso immediatamente precedente, ma tutti i casi precedenti.
Esempio 2: la successione di Fibonacci
La successione di Fibonacci è definita da:
\[ F_1=1,\quad F_2=1,\quad F_n=F_{n-1}+F_{n-2} \quad \text{per ogni } n\geq 3. \]
Dimostriamo per induzione forte che, per ogni \(n\geq 1\),
\[ F_n<2^n. \]
Casi base
Per \(n=1\):
\[ F_1=1<2=2^1. \]
Per \(n=2\):
\[ F_2=1<4=2^2. \]
Sono necessari due casi base perché la relazione di ricorrenza definisce ogni termine usando i due termini precedenti.
Passo induttivo
Sia \(n\geq 3\). Supponiamo, per ipotesi di induzione forte, che la disuguaglianza valga per tutti gli indici minori di \(n\). In particolare:
\[ F_{n-1}<2^{n-1} \qquad \text{e} \qquad F_{n-2}<2^{n-2}. \]
Allora:
\[ F_n=F_{n-1}+F_{n-2} < 2^{n-1}+2^{n-2}. \]
Poiché:
\[ 2^{n-1}+2^{n-2} = 2^{n-2}(2+1) = 3\cdot 2^{n-2}, \]
e poiché \(3<4\), otteniamo:
\[ 3\cdot 2^{n-2} < 4\cdot 2^{n-2} = 2^2\cdot 2^{n-2} = 2^n. \]
Quindi:
\[ F_n<2^n. \]
Per il principio di induzione forte, \(F_n<2^n\) per ogni \(n\geq 1\).
Questo esempio illustra bene perché l'induzione forte è naturale: la relazione di ricorrenza \(F_n=F_{n-1}+F_{n-2}\) coinvolge i due termini precedenti, non soltanto l'immediato predecessore. Usare direttamente l'induzione forte rende quindi il ragionamento più lineare.
Errori comuni nelle dimostrazioni per induzione
1. Dimenticare il caso base
Senza il caso base, il passo induttivo non basta. Dimostrare soltanto:
\[ P(n)\Rightarrow P(n+1) \]
non garantisce che la proprietà sia vera per qualche numero naturale.
È come dire che ogni tessera fa cadere la successiva, senza però far cadere la prima tessera.
2. Usare male l'ipotesi induttiva
L'ipotesi induttiva deve essere usata esattamente nella forma in cui è stata assunta.
Se si vuole dimostrare una proprietà \(P(n+1)\), bisogna partire da \(P(n)\) e trasformarla correttamente nel caso successivo.
3. Dimostrare un'implicazione incompleta
Il passo induttivo deve valere per ogni valore di \(n\) appartenente al dominio considerato.
Se il ragionamento funziona solo per alcuni valori di \(n\), la dimostrazione non è valida.
Il paradosso dei cavalli
Un esempio celebre di falsa dimostrazione per induzione è il cosiddetto paradosso dei cavalli.
Si vuole dimostrare la seguente affermazione:
\[ P(n): \quad \text{in ogni insieme di } n \text{ cavalli, tutti i cavalli hanno lo stesso colore.} \]
Per \(n=1\), la proprietà è vera: in un insieme formato da un solo cavallo, tutti i cavalli hanno certamente lo stesso colore.
Consideriamo ora un insieme di \(n+1\) cavalli:
\[ \{c_1,c_2,\dots,c_n,c_{n+1}\}. \]
I primi \(n\) cavalli:
\[ \{c_1,c_2,\dots,c_n\} \]
hanno tutti lo stesso colore, per ipotesi induttiva. Anche gli ultimi \(n\) cavalli:
\[ \{c_2,c_3,\dots,c_{n+1}\} \]
hanno tutti lo stesso colore, sempre per ipotesi induttiva.
Poiché i due sottoinsiemi si sovrappongono, sembrerebbe seguire che tutti gli \(n+1\) cavalli abbiano lo stesso colore.
L'errore è nel passaggio da \(n=1\) a \(n=2\). In quel caso i due sottoinsiemi sono:
\[ \{c_1\} \qquad \text{e} \qquad \{c_2\}, \]
e non hanno alcun elemento in comune. Non esiste quindi un cavallo condiviso che permetta di collegare il colore del primo al colore del secondo.
Il passo induttivo non è valido per tutti i valori di \(n\), ma solo per \(n\geq 2\). La catena induttiva si spezza quindi proprio nel passaggio da \(P(1)\) a \(P(2)\).
4. Confondere verifica numerica e dimostrazione
Verificare una formula per \(n=1\), \(n=2\), \(n=3\) e \(n=4\) può suggerire che essa sia vera, ma non costituisce una dimostrazione.
L'induzione non consiste nel controllare molti casi iniziali, ma nel dimostrare un meccanismo generale di passaggio da \(n\) a \(n+1\).
Induzione e definizioni ricorsive
Il principio di induzione è strettamente collegato alle definizioni ricorsive.
Molti oggetti matematici vengono definiti specificando:
- uno o più valori iniziali;
- una regola che permette di costruire i termini successivi.
Per esempio, il fattoriale è definito da:
\[ 0!=1 \]
e
\[ (n+1)!=(n+1)n!. \]
La ricorsione costruisce gli oggetti passo dopo passo, mentre l'induzione permette di dimostrare proprietà valide per tutti gli oggetti costruiti in questo modo.
Ricorsione e induzione sono quindi due aspetti complementari della struttura dei numeri naturali: la ricorsione definisce, l'induzione dimostra.
Conclusione
Il principio di induzione matematica è molto più di una tecnica per dimostrare formule. Esso esprime una proprietà fondamentale dei numeri naturali: ogni numero naturale si raggiunge partendo dal primo e applicando ripetutamente l'operazione di successore.
La sua forza consiste nel trasformare un'affermazione infinita in due verifiche finite:
- una verifica iniziale;
- una regola di propagazione dal caso \(n\) al caso \(n+1\).
Inoltre, l'equivalenza con il principio del buon ordinamento mostra che l'induzione è profondamente legata alla struttura ordinata di \(\mathbb{N}\).
Per questo motivo il principio di induzione occupa un ruolo centrale in algebra, teoria dei numeri, logica, analisi discreta, informatica teorica e in molti altri ambiti della matematica.
In definitiva, l'induzione matematica mostra come sia possibile governare l'infinito attraverso un ragionamento finito, purché la struttura logica sia costruita con precisione.