Errori e Paradossi – Il Metodo di Induzione Matematica

La matematica consiste in due principali categorie di attività: dimostrazione di teoremi e soluzione di problemi. In entrambe queste attività i matematici giustificano le loro conclusioni tramite il ragionamento deduttivo, basato sulle leggi della logica. Ad esempio la dimostrazione di un teorema è una successione di deduzioni logiche, a partire da assiomi, definizioni e altre proposizioni già dimostrate, che alla fine portano ad affermare che una certa proposizione è vera o falsa. Ricordiamo che nella logica matematica una proposizione è un’affermazione che può assumere soltanto due valori logici: vero o falso.
Il ragionamento deduttivo ha le sue regole che devono essere rispettate, altrimenti si può arrivare a delle conclusioni non valide. Purtroppo talvolta i matematici possono commettere degli errori nel ragionamento logico. Sono possibili situazioni diverse:

• la proposizione da dimostrare è vera, ma il ragionamento logico non è corretto e porta a concludere che la proposizione è falsa;
• la proposizione da dimostrare è falsa, ma il ragionamento logico non è corretto e porta ad affermare che è vera;
• la proposizione da dimostrare è vera, ma il ragionamento logico è comunque non corretto, anche se arriva alla conclusione che la proposizione è vera;
• la proposizione da dimostrare è falsa, ma il ragionamento logico è comunque non corretto, anche se porta ad affermare che è falsa.

Quando il ragionamento logico non rispetta le regole (primi due casi) e porta ad un risultato sbagliato, allora si parla di fallacia o errore nella dimostrazione.
In questo articolo presenteremo alcuni esempi di errori nelle dimostrazioni, nelle quali si utilizza il metodo di induzione matematica.

1) Il principio di induzione matematica

Il principio di induzione matematica è uno strumento utilizzato per risolvere problemi e dimostrare teoremi. L’idea fondamentale sulla quale si basa questo metodo è di ridurre la risoluzione di un problema o la dimostrazione di un teorema ad un problema o teorema di dimensioni minori. Esistono due varianti equivalenti del principio.

1.1) Principio di induzione matematica debole

Sia \(P(n)\) una proprietà relativa ai numeri interi \(n \ge n_{0}\), dove \(n_{0} \ge 0\). Consideriamo le seguenti due proposizioni.

1) \(P(n)\) è vera per \(n=n_{0}\).
2) Dato un valore qualsiasi \(n \ge n_{0}\), se \(P(n)\) è vera allora è vera anche \(P(n+1)\).

Se entrambe le proposizioni \(1,2\) sono vere, allora la proprietà \(P(n)\) è vera per tutti i numeri interi maggiori o uguali a \(n_{0}\).
In genere si assume il valore \(n_{0}\) uguale a \(0\) oppure \(1\). Tuttavia può anche essere un valore diverso.

Il principio di induzione permette di dimostrare delle proprietà per un numero infinito di casi, mediante un numero finito di passi. Il metodo di dimostrazione che si basa sul principio di induzione consiste in due passi principali:

1) il caso base o base induttiva: dimostriamo che la proposizione \(P(n)\) è vera quando \(n=n_{0}\);
2) il passo induttivo: dimostriamo che, se la proposizione \(P(n)\) è vera per un arbitrario numero intero \(n \ge n_{0}\), allora à vera anche per il numero successivo \(n+1\).

Se completiamo entrambi i due passi, allora abbiamo dimostrato che la proposizione \(P(n)\) è vera per ogni intero \(n \ge n_{0}\).
Il principio presentato sopra viene chiamato principio di induzione debole, per distinguerlo da una sua formulazione in apparenza più forte, ma in realtà equivalente, chiamato principio di induzione matematica completa o forte.

1.2) Principio di induzione matematica forte

Sia \(n_{0}\) un intero fissato. Sia \(P(n)\) una proposizione relativa ai numeri interi \(n \ge n_{0}\). Consideriamo le seguenti due proposizioni.

1) \(P(n_{0})\) è vera.
2) Se \(P(k)\) è vera per tutti i valori di \(k\), con \(n_{0}\le k \le n\), allora anche \(P(n+1)\) è vera.

Se entrambe le proposizioni \(1,2\) sono vere, allora la proprietà \(P(n)\) è vera per tutti i numeri interi maggiori o uguali a \(n_{0}\).
Per una descrizione dettagliata con vari esempi vedere l’articolo su questo sito.

1.3) Errori comuni nell’utilizzo del principio di induzione

L’utilizzo corretto del principio di di induzione matematica richiede di eseguire i seguenti passi:

• definire in modo chiaro la proposizione \(P(n)\) da dimostrare;
• definire e dimostrare il caso base;
• definire \(P(n)\) e \(P(n+1)\);
• completare il passo induttivo: cioè dimostrare che \(P(n) \implies P(n+1)\).

Gli errori più comuni fatti dagli studenti nelle dimostrazioni sono i seguenti:

• si omette di definire o dimostrare il caso base;
• si commettono errori nella dimostrazione dello step induttivo;
• si inverte la implicazione logica \(P(n) \implies P(n+1)\);
• la \(P(n)\) non è una proposizione logica.

La presenza del caso base è fondamentale. È essenziale definire e dimostrare che il caso base è vero per il valore iniziale stabilito. Chiaramente, inoltre, il caso base deve essere rilevante e consistente con il problema in esame. La dimostrazione del passo induttivo senza aver stabilito il case base non ha alcun significato.
Nel passo induttivo si deve dimostrare la validità dell’implicazione logica \(P(n) \implies P(n+1)\). Naturalmente la dimostrazione deve essere completa per ogni possibile caso.
Per quanto riguarda l’inversione della direzione dell’implicazione logica nel passo induttivo, ricordiamo una regola fondamentale della logica elementare. Siano date due proposizioni \(P,Q\). Supponiamo che se \(P\) è vera allora anche la proposizione \(Q\) è vera, cioè

\[ P \implies Q \]

Da questo non segue che \(Q \implies P\), come è facile verificare con degli esempi. Quindi anche se dimostriamo che \(P(n+1) \implies P(n)\), non possiamo dedurre che \(P(n) \implies P(n+1)\).
Infine nel definire la \(P(n)\) dobbiamo verificare che questa sia effettivamente una proposizione, cioè che esprima una proprietà che può essere vera oppure falsa. Ad esempio non ha senso definire \(P(n)\) con una formula, ad esempio \(P(n)=n^{2}+n\).

2) Esempi di errori nell’utilizzo del principio di induzione matematica

Presentiamo alcuni esempi di errato utilizzo del principio di induzione matematica. È importante capire dove sta l’errore in ognuno degli esempi.

Esempio 2.1 – Mancanza del caso base
Consideriamo la seguente proposizione:

\[ P(n): \quad 2^{n} \lt n! \ , \quad n \ge 2 \]

Dimostrazione
Supponiamo che \(P(n)\) sia vera per \(n \ge 1\). Allora \(n+1 \ge 2\) e quindi

\[ \begin{array}{l} 2^{n+1}=2(2^{n})\le 2(n!) \le (n+1)(n!)=(n+1)! \end{array} \]

Abbiamo dimostrato il passo induttivo. Però non vale il caso base; infatti si ha \( 2^{1} \not \lt 1!\) e \(2^{2} \not \lt 2!\). Quindi la dimostrazione non è corretta.
Tuttavia è facile dimostrare che vale la seguente proposizione:

\[ 2^{n} \lt n! \ , \quad n \ge 4 \]

Il ruolo fondamentale del caso base è chiarito anche dal seguente esempio. Consideriamo la seguente proposizione:

\[ P(n): \quad n^{2}+ n \quad \text{è sempre dispari per} \quad n \gt 2 \]

Saltiamo il caso base e dimostriamo lo step induttivo. Supponiamo quindi che \(P(n)\) sia vera per un dato \(n \gt 2\). Allora anche \(P(n+1)\) è vera. Infatti

\[ (n+1)^{2}+ (n+1) = n^{2}+ n +2n+2 = P(n) + 2n +2 \]

e quindi \(P(n+1)\) è vera, in quanto sommando un numero dispari ad un numero pari si ottiene un numero dispari.
Se invece supponiamo che \(n^{2}+n\) sia pari per \(n \gt 2\), allora anche il successivo è pari.
Come si vede, lo step induttivo da solo non ha alcun valore se si salta il caso base.
L’esempio in esame può essere facilmente dimostrato anche senza il metodo di induzione, e risulta che \(n^{2}+n=n(n+1)\) è sempre pari, per \(n \ge 0\).

Esempio 2.2
Consideriamo la seguente proposizione:

\[ P(n): 2^{n}=1 \ , \quad n=0,1,2,\cdots \]

Dimostrazione
Il caso base \(P(0)\) è valido in quanto \(2^{0}=1\). Applichiamo il principio di induzione forte. Supponiamo quindi che \(P(k)\) sia vero per tutti gli interi \(0 \le k \le n\). Dimostriamo che la proposizione vale anche per \(n+1\). Abbiamo

\[ \begin{array}{l} 2^{n+1}=\dfrac{2^{n}2^{n}}{2^{n-1}}= \dfrac{1 \cdot 1}{1}= 1 \end{array} \]

Quindi la \(P(n)\) è vera per ogni \(n\).
Naturalmente al posto del numero \(2\) possiamo utilizzare qualunque numero reale non nullo, diverso da \(1\).

Esempio 2.3
Consideriamo la seguente proposizione:

\[ P(n): 3n = 0 \ , \quad n=0,1,2,\cdots \]

Dimostrazione
Il caso base \(P(0)\) è vero in quanto \(3\cdot 0 =0\). Applichiamo il principio di induzione forte. Supponiamo quindi che \(P(k)\) sia vero per tutti gli interi \(0 \le k \le n\). Dimostriamo che la proposizione vale anche per \(n+1\).
Poniamo \(n+1 =i + j\) con \(0 \le i,\ j \le n\). Per l’ipotesi induttiva abbiamo \(3i=0\) e \(3j=0\). Quindi

\[ 3(n+1)= 3(i+j)=3i+3j= 0 \]

Per il principio di induzione forte quindi \(P(n)\) è vera per ogni intero \(n\) non negativo.
Per comprendere l’errore, nello step induttivo considerare il caso \(n+1=1\), cioè \(n=0\).

Esempio 2.4
Consideriamo la seguente proposizione:

\[ P(n): \frac{dx^{n}}{dx}=0 \ , \quad n=0,1,2,\cdots \]

Dimostrazione
Il caso base \(P(0)\) è vero, in quanto \(x^{0}=1\). Applichiamo il principio di induzione forte. Supponiamo quindi che \(P(k)\) sia vero per tutti gli interi \(0 \le k \le n\). Dimostriamo che la proposizione vale anche per \(n+1\).
Applichiamo la regola della derivata del prodotto di due funzioni, ponendo \(x^{n+1}=x^{1} \cdot x^{n}\). Abbiamo

\[ \begin{array}{l} \dfrac{dx^{n+1}}{dx}= x^{1} \dfrac{dx^{n}}{dx} + x^{n} \dfrac{dx^{1}}{dx}= x^{1}\cdot 0+ x^{n} \cdot 0 =0 \end{array} \]

Esempio 2.5 – Polya
Nel suo testo ^[4], Polya presenta un esempio di uso scorretto del metodo di induzione matematica, considerando la seguente proposizione:

\[ P(n): \text{In ogni insieme di numeri, tutti i numeri sono uguali.} \]

Dimostrazione
Naturalmente al posto dei numeri si può utilizzare un insieme qualunque di oggetti. Presentiamo l’esempio di Polya utilizzando i gatti al posto dei numeri. Vogliamo dimostrare che se in un gruppo di \(n\) gatti, con \(n \ge 1\), esiste un gatto nero, allora tutti i gatti sono neri.
ll caso base \(P(1)\) è chiaramente vero. Dobbiamo dimostrare il seguente passo induttivo: se un insieme qualsiasi di \(n\) gatti ha lo stesso colore, allora la stessa proprietà vale per un insieme di \(n+1\) gatti.
Illustriamo il ragionamento nel caso \(n=10\) e \(n+1=11\), che si può estendere facilmente al caso generale. Abbiamo quindi un insieme di \(10\) gatti dello stesso colore nero e un undicesimo gatto. Eliminiamo il primo gatto dell’insieme dei \(10\) e consideriamo i gatti rimanenti. Sono ancora \(10\) gatti e per l’ipotesi induttiva hanno lo stesso colore. Quindi anche l’insieme di \(11\) gatti ha lo stesso colore nero.

Esercizio 2.1
Con lo stesso ragionamento dare una dimostrazione (errata) della seguente proposizione:

\[ P(n): x_{1}^{2}+ x_{2}^{2}+ \cdots + x_{n}^{2} = y^{2} \]

dove \(x_{1},x_{2}, \cdots,x_{n},y\) sono interi.
Cioè la somma dei quadrati di un insieme qualsiasi di \(n\) interi, con \(n \ge 1\), è il quadrato di un intero.
Da questo seguirebbe in particolare, prendendo \(x_{1}=x_{2}=\cdots =x_{n}=1\), che ogni intero positivo è un quadrato.

Esempio 2.6
Consideriamo la seguente proposizione:

\[ P(n): \text{Se a,b sono due numeri naturali qualsiasi, allora } a=b. \]

Dimostrazione
Dimostriamo la proposizione precedente per ogni \(n=\max(a,b)\).
Se \(n=0\) allora \(a=b=0\). Supponiamo vera la proposizione per un dato numero naturale \(n \ge 0\) e dimostriamo che è vera anche per \(n+1\).
Siano quindi due numeri naturiali \(a,b\) tali che \(\max(a,b)=n+1\). Dobbiamo dimostrare che \(a=b\).
Poiché \(\max(a-1,b-1)=n\) abbiamo \(a-1=b-1\) e quindi \(a=b\).

Esempio 2.7
Consideriamo la seguente proposizione:

\[ \begin{array}{l} P(n): \text{È possibile tracciare una linea retta attraverso \(n \ge 1\) punti qualsiasi del piano.} \end{array} \]

Dimostrazione
Come casi base possiamo prendere \(n=1\) oppure \(n=2\). Sono di fatto assiomi della geometria euclidea.
Supponiamo ora vera \(P(n)\), con \(n \ge 2\). Dimostriamo che è vera anche \(P(n+1)\).
Consideriamo \(n+1\) punti del piano, indicati con \(x_{1},x_{2}, \cdots,x_{n},x_{n+1}\). Per l’ipotesi induttiva gli \(n\) punti \(x_{2}, \cdots,x_{n+1}\) giacciono su una retta. Lo stesso vale per gli \(n\) punti \(x_{1},x_{2}, \cdots,x_{n}\). Da questo segue che le due rette coincidono.

Esempio 2.8
Consideriamo la seguente proposizione:

\[ \begin{array}{l} P(n): \text{Un insieme qualsiasi di \(n \ge 2\) rette distinte del piano, senza nessuna coppia} \\ \text{parallela, si intersecano in un punto comune.} \\ \end{array} \]

Dimostrazione
Questo esercizio è simile al precedente (duale). Alla relazione punti che giacciono su una retta corrisponde la relazione rette che si intersecano in un punto. La dimostrazione (errata) è analoga; basta invertire le parole retta e punto.

Esempio 2.9 – Knuth
Consideriamo la seguente formula:

\[ S_{n}= \underbrace{\frac{1}{1 \cdot 2}+ \frac{1}{2 \cdot 3}+ \frac{1}{3 \cdot 4}+ \cdots }_{\text{n termini}}= \frac{3}{2}- \frac{1}{n} \ , \quad n \ge 1 \]

Dimostrazione
Per \(n=1\) la formula è vera. Supponiamola vera per \(n \ge 1\) e dimostriamo che è vera anche per \(n+1\). Abbiamo

\[ \begin{array}{l} S_{n+1}= S_{n}+ \dfrac{1}{n(n+1)}=\dfrac{3}{2}- \dfrac{1}{n} + \dfrac{1}{n}- \dfrac{1}{n+1}= \dfrac{3}{2}- \dfrac{1}{n+1} \end{array} \]

Esempio 2.10
Ricordiamo che un grafo non orientato si dice connesso se esiste almeno un cammino che collega ogni coppia dei vertici del grafo. Il grado di un vertice è il numero di archi incidenti nel vertice.
Consideriamo la seguente proposizione:

\[ \begin{array}{l} P(n): \text{Se ogni vertice di un grafo non orientato, con } n \ge 2 \text{ nodi,} \\ \text{ha grado positivo, allora il grafo è connesso.} \end{array} \]

Dimostrazione
Come casi base prendiamo \(n=1\) o \(n=2\). Chiaramente \(P(1)\) e \(P(2)\) sono vere.
Nello step induttivo dobbiamo dimostrare che, se \(P(n)\) è vera, allora lo è anche \(P(n+1)\), con \(n \ge 2\).
Consideriamo quindi un grafo di \(n\) vertici, in cui ogni vertice ha grado positivo, e supponiamo che \(P(n)\) sia vera, cioè il grafo sia connesso. Aggiungiamo un nuovo vertice \(x\) di grado positivo, ottenendo un grafo di \(n+1\) vertici. Dobbiamo dimostrare che anche il nuovo grafo ampliato è connesso. Poiché il nuovo vertice \(x\) ha grado positivo, esiste un arco che lo collega ad almeno un vertice \(y\) del grafo iniziale di \(n\) nodi. Da questo segue che qualunque vertice \(z\) del grafo può essere collegato con il vertice \(x\), collegando prima \(z\) con \(y\), e successivamente \(y\) con \(x\). Quindi anche \(P(n+1)\) è vera.

Naturalmente è facile mostrare degli esempi nei quali ogni vertice ha grado positivo, ma il grafo non è connesso.

Esempio 2.11
Consideriamo la seguente successione di numeri reali \((x_{n})\):

\[ x_{1}=2 \ , \quad x_{n+1}=4x_{n}-4x_{n-1} \ , \quad n \ge 1 \]

Consideriamo la seguente proposizione:

\[ P(n): x_{n}=2^{n} \ , \quad n \ge 1 \]

Dimostrazione
Il caso base \(x_{1}=2=2^{1}\) è soddisfatto. Applichiamo il principio di induzione forte. Dobbiamo dimostrare il passo induttivo: se \(P(k)\) è vera per \(1 \le k \le n\), con \(n \ge 1\), allora è vera anche \(P(n+1)\). Abbiamo

\[ \begin{array}{l} x_{n+1}=4x_{n}-4x_{n-1}= 4 \cdot 2^{n}- 4 \cdot 2^{n-1}= 2 \cdot 2^{n}= 2^{n+1} \end{array} \]

Esempio 2.12 – Numeri di Fibonacci
Ricordiamo la definizione dei numeri di Fibonacci \(F_{n}\):

\[ \begin{array}{l} F_{0}=0 \ , \quad F_{1}=1 \\ F_{n} = F_{n-1}+ F_{n-2} \ , \quad n \ge 2 \end{array} \]

I primi numeri di Fibonacci \(F_{n}\) a partire da \(n=0\) sono: \(0,1,1,2,3,5,8,\cdots\).
Consideriamo ora la seguente proposizione:

\[ P(n): \text{Tutti i numeri di Fibonacci } F_{3},F_{4}, \cdots \text{ sono pari.} \]

Dimostrazione
Come caso base prendiamo \(F_{3}=2\). Supponiamo ora che tutti i numeri di Fibonacci \(F_{k}, 3 \le k \le n\) siano pari. Allora poiché \(F_{n+1}=F_{n}+ F_{n-1}\) anche \(F_{n+1}\) è pari.

Esempio 2.13
Mostriamo un esempio di dimostrazione corretta, ma che non usa l’ipotesi induttiva, e quindi non è una dimostrazione per induzione.
Consideriamo la seguente proposizione:

\[ P(n): 3 | 2^{2n}-1 \ , \quad n \ge 1 \]

Coma caso base prendiamo \(P(1)\), cioè \(2^{2}-1=3\). Supponiamo ora \(P(n)\) con \(n \ge 1\) sia vera. Allora

\[ 2^{2n}-1 = 3m \]

Per completare la dimostrazione utilizziamo la seguente formula algebrica

\[ x^{n} – 1 = (x-1)(x^{n-1}+ x^{n-2}+ \cdots + x + 1) \]

Abbiamo

\[ \begin{array}{l} 2^{2(n+1)}- 1 = 4^{n+1}-1 = 3(4^{n}+4^{n-1}+ \cdots + 4 + 1) \end{array} \]

Quindi anche \(P(n+1)\) è vera.
La dimostrazione è corretta, tuttavia non abbiamo fatto uso completamente del principio di induzione. Infatti non abbiamo eseguito il passo induttivo \(P(n) \implies P(n+1)\), ma abbiamo utilizzato un metodo diretto, sfruttando la formula di fattorizzazione del polinomio \(x^{n}-1\).
Come esercizio completare la dimostrazione mediante il passo induttivo.

Conclusione

Il metodo di induzione matematica è uno strumento molto utile per dimostrare teoremi e risolvere problemi, nei quali si deve provare che una proposizione è vera per tutti i numeri naturali. Tuttavia, come abbiamo visto negli esempi di questo articolo, è molto facile dimostrare come vere proposizioni false, se non si rispettano le regole del metodo.
In successivi articoli vedremo altri esempi di errori possibili nelle dimostrazioni di teoremi e nelle soluzioni di problemi matematici, quando si utilizzano altri metodi di ragionamenti logici.

---

Bibliografia

^[1]G. Polya – How to Solve It: A New Aspect of Mathematical Method (Princeton U.P.)

^[2]D. Gunderson – Handbook of Mathematical Induction: Theory and Applications (Chapman and Hall/CRC)

^[3]Daniel J. Velleman – How to Prove It: A Structured Approach (Cambridge U.P.)

^[4]G. Polya – Mathematics and Plausible Reasoning, Volume 1/2: Induction and Analogy in Mathematics (Princeton U.P.)

^[5]M. Gardner – “The Paradox of the Unexpected Hanging” in The Unexpected Hanging and Other Mathematical Diversions (Chicago University Press)