Nell’ambito delle Olimpiadi della Matematica, a partire dalla gara distrettuale di febbraio, gli esercizi a risposta multipla tendono via via a lasciare spazio ad esercizi a risposta aperta la cui risoluzione richiede la stesura, da parte dello studente, di una vera e propria dimostrazione. Il principio di induzione rappresenta uno degli strumenti più potenti nella risoluzione di quesiti dimostrativi. Giova ricordare che le Indicazioni Nazionali del 2010 stabiliscono che tale principio venga presentato a scuola (è così?), in quanto costituisce un “esempio elementare del carattere non strettamente deduttivo del ragionamento matematico”. Si potrebbe discutere sull’uso della parola “elementare” riferito a questo contesto. Nel seguente articolo analizzeremo le applicazioni del principio di induzione ad esercizi per nulla banali e diversi dai classici esercizi che possono essere trovati sui libri di testo scolatici.

Nella stesura dell’articolo ho preso diversi spunti dalle ricerche fatte dall’amico e collega Antonio Veredice, un vero esperto e cultore di questo principio, che ringrazio di vero cuore.

Immagine tratta da https://it.wikipedia.org/wiki/Principio_d%27induzione

Enunciato per la prima volta in modo esplicito da Maurolico nel 1575, conosciuto ed usato da moltissimi matematici dei secoli successivi, il principio di induzione rappresenta uno degli strumenti più utilizzati per dimostrare una certa proprietà per l’insieme dei numeri naturali (o per un suo sottoinsieme infinito).

Una delle possibili formulazioni è la seguente. Sia $P(n)$ una proprietà che dipende da un certo numero naturale $n$. Se risulta che:

  1. $P(0)$ è vera (passo base);
  2. Per ogni $k \geq 0$, se $P(k)$ è vera allora $P(k+1)$ è vera (passo induttivo);

ne consegue che $P(n)$ è vera per ogni $n \in \mathbb{N}$.

Va innanzitutto detto che il passo base può iniziare da 0, da 1 oppure da un qualunque valore $n_{0} \in \mathbb{N}$, ed in quest’ultimo caso la tesi varrà per $n \geq n_{0}$. Ad esempio si può dimostrare per induzione che $n!>2^{n}$, ma ciò è possibile solo a partire dal valore $n=4$.

Il principio di induzione ha un funzionamento che ricorda il gioco del domino. Infatti affinché possano cadere tutte le tessere, disposte verticalmente una accanto all’altra, è necessario far cadere la prima e che tutte le rimanenti siano posizionate in modo tale che se cade una generica tessera $n$, allora cade anche la successiva tessera $n+1$ posta vicino ad essa.

L’esempio probabilmente più classico, che riportiamo in quanto ci permetterà di effettuare successive considerazioni, riguarda la somma dei primi $n$ numeri naturali. Si vuole dimostrare che $P(n):1+2+…+n=\frac{n \cdot (n+1)}{2}$.

  1. (passo base) $P(1):1=\frac{1 \cdot 2}{2}$;
  2. (passo induttivo) Supponiamo che $1+2+…+n=\frac{n \cdot (n+1)}{2}$. Risulta $P(n+1):1+2+…+n+(n+1)=\frac{n \cdot (n+1)}{2}+(n+1)=\frac{(n+1) \cdot (n+2)}{2}$.

Ne consegue che la relazione è vera per ogni $n \in \mathbb{N}$.

G. Hanna, nel suo articolo “Proofs that prove and proofs that explain” (1989) riporta la dimostrazione per induzione della formula di Gauss quale esempio di dimostrazione che “prova” (vale a dire che mostra che l’affermazione è vera) ma che non spiega il perchè. La classica dimostrazione attribuita a Gauss (la scrittura dei termini in ordine crescente e decrescente e le successive somme termine a termine) è senza dubbio un esempio di dimostrazione che “spiega” la validità della relazione.

Per quanto detto, si capisce che il principio di induzione risulta comodo per verificare la validità di ipotesi che però devono essere state formulate utilizzando altri metodi. A titolo di esempio, consideriamo la somma dei primi $n$ quadrati. Sappiamo che $1+4+9+…+n^{2}= \frac{n \cdot (n+1) \cdot (2n+1)}{6}$. Da dove viene questa formula? Con le differenze finite, consideriamo la successione delle somme parziali (i termini di ciascuna riga, a partire dalla seconda, sono ottenuti come differenza di due termini consecutivi della riga precedente): $$0 \hspace{1cm} 1 \hspace{1cm} 5 \hspace{1cm} 14 \hspace{1cm} 30 \hspace{1cm} 55 \hspace{1cm} 91$$ $$1 \hspace{1cm} 4 \hspace{1cm} 9 \hspace{1cm} 16 \hspace{1cm} 25 \hspace{1cm} 36$$ $$3 \hspace{1cm} 5 \hspace{1cm} 7 \hspace{1cm} 9 \hspace{1cm} 11$$ $$2 \hspace{1cm} 2 \hspace{1cm} 2 \hspace{1cm} 2$$ Si intuisce pertanto che, giungendo ad una successione costante dopo tre passaggi, la relazione cercata deve essere un polinomio di terzo grado, i cui coefficienti si ricavano, ad esempio, impostando un sistema. Scritta la formula della somma di potenze seconde, il principio di induzione può essere utilizzato per verificarne la correttezza.

Nella risoluzione di molti esercizi delle gare capita talvolta che un’apparente regolarità nello studio di una successione di termini possa portare a delle deduzioni errate se il ragionamento non è ben supportato dall’induzione. Ad esempio, si può osservare che $17+2=19$, $17+2+4=23$, $17+2+4+6=29$, $17+2+4+6+8=37$ da cui si potrebbe congetturare che se a 17 sommiamo una successione di termini pari consecutivi si ottiene sempre un numero primo. In generale si è portati a credere che $17+n \cdot (n+1)$ sia primo. Peccato che tale quantità, per $n=16$, si scompone in $17+16 \cdot 17=17^{2}$ che non è evidentemente primo.

Mostriamo di seguito alcuni esercizi che possono essere risolti con il principio di induzione.

Dimostrare che per ogni intero $n \geq 1$, $2^{2n}-1$ è divisibile per 3.

Soluzione: il passo base è banalmente verificato per $n=1$ in quanto $2^{2}-1=3$ che è chiaramente divisibile per sé stesso. Supponiamo che per un certo $n \geq 1$ la quantità $2^{2n}-1$ sia divisibile per 3. Allora $2^{2(n+1)}-1=2^{2n+2}-1=4 \cdot 2^{2n}-1=3 \cdot 2^{2n} +(2^{2n}-1)$, e poiché entrambi gli addendi sono divisibili per 3, allora anche $2^{2(n+1)}-1$ è divisibile per 3.

Osservazione: il principio di induzione chiaramente non è l’unico strumento che si può utilizzare nelle dimostrazioni. Talvolta esistono altre tecniche, anche più veloci, che permettono di dimostrare quanto enunciato. A titolo di esempio, per chi ha dimestichezza con le congruenze, quest’esercizio poteva essere risolto osservando che $2^{2n}-1 \equiv (2^{2})^{n}-1 \equiv 4^{n}-1 \equiv 1^{n}-1 \equiv 0 \hspace{0,2cm} mod \hspace{0,2cm} 3$, da cui la tesi.

Su una busta da lettere dobbiamo pagare in francobolli un costo pari a $n$ centesimi, ma disponiamo solo di una quantità (illimitata) di francobolli da 0,05€ e da 0,12€ (che per semplicità indicheremo rispettivamente con 5₵ e 12₵). Dimostrare che è sempre possibile ottenere quanto richiesto per $n \geq 44₵$.

Soluzione: procediamo per induzione. Il passo base è banalmente verificato (44₵ è possibile ottenerlo con quattro francobolli da 5₵ e due da 12₵). Supponiamo che per un certo $n \geq 44$ sia possibile usare $a$ francobolli da 5₵ e $b$ francobolli da 12₵ in modo che $n= 5a + 12b$. Notiamo che o $a \geq 7$ oppure $b \geq 2$, altrimenti se fossero contemporaneamente $a \leq 6$ e $b \leq 1$, accadrebbe che $n \leq 5 \cdot 6 + 12 \cdot 1 =42 < 44$ contro l’ipotesi che $n \geq 44$. Abbiamo due casi:

  1. se $a \geq 7$, posto $a’=a-7$ e $b’=b+3$ si ottiene $5a’ + 12b’ = 5(a-7) + 12(b+3) = 5a + 12b + 1 = n + 1$
  2. se $b \geq 2$, posto $a’=a+5$ e $b’=b-2$ si ottiene $5a’+12b’ = 5(a+5) + 12(b-2) = 5a +12b+1 = n+1$.

Variante: lasciamo al lettore dimostrare che, recandosi in una nota catena di fast food che vende bocconcini di pollo (c.d. Chicken McNuggets) in confezioni da 6, 9 e 20, per ogni intero $n \geq 44$ è possibile comprare esattamente $n$ bocconcini di pollo mediante una combinazione di tali confezioni.

Variante 2: supponiamo che la suddetta catena di fast food introduca una nuova tipologia di confezione contenete 4 bocconcini di pollo. Nonostante ciò, esistono alcuni valori di $n$ per i quali non è possibile comprare esattamente $n$ bocconcini (e.g. $n=3$). Qual è il maggiore di essi?

Si considerino tutti i possibili sottoinsiemi dell’insieme $A=\{$1,2,…,n$\}$ che non contengono elementi consecutivi. Dimostrare che la somma dei quadrati dei prodotti fra gli elementi di ciascun sottoinsieme è pari a $(n+1)!-1$. Ad esempio, se $n=3$, allora i sottoinsiemi cercati sono del tipo $\{$1$\}$, $\{$2$\}$, $\{$3$\}$, $\{$1,3$\}$ e risulta $1^{2}+2^{2}+3^{2}+(1 \cdot 3)^{2}=23=4!-1$.

Soluzione: la proposizione è banalmente verificata per $n=3$ come mostrato nell’esempio. Dividiamo ora i sottoinsiemi di $A$ in quelli che contengono $n$ e quelli che non lo contengono. Nel primo caso tali sottoinsiemi sono del tipo $\{$$a_{1}, a_{2},…, a_{k}, n$$\}$, con $a_{1}, a_{2},…, a_{k}$ non consecutivi fra loro e neanche con $n$, a cui va aggiunto il sottoinsieme $\{$$n$$\}$. Pertanto la somma dei quadrati dei prodotti fra i termini di ciascun sottoinsieme, per l’ipotesi induttiva, è pari a $n^{2} \cdot [(n-1)!-1]+ n^{2}$. Nel caso dei sottoinsiemi che non contengono $n$, sempre per l’ipotesi induttiva, la somma cercata è pari a $n!-1$. Sommando le due espressioni così ottenute si giunge alla relazione $(n+1)!-1$.

Dimostrare che ogni scacchiera $2^{n} \times 2^{n}$ a cui è stata tolta una casella, può essere ricoperta (senza sovrapposizioni) usando delle tessere a L ciascuna delle quali ricopre tre caselle.

Soluzione: si verifica banalmente che l’affermazione è vera per per $n=1$. Supponiamo di poter coprire una scacchiera $2^{n-1} \times 2^{n-1}$, mancante di una casella, con tessere a forma di L. Consideriamo ora una scacchiera $2^{n} \times 2^{n}$, mancante di una casella, e la dividiamo in 4 quadrati. Posizioniamo una tessera ad L al centro in modo che a ciascun quadrato manchi una casella, come mostrato in figura:

Per l’ipotesi induttiva, ciascun quadrato può essere ricoperto con tessere ad L. Ne consegue che a poter essere ricoperto con tessere ad L è l’intera scacchiera $2^{n} \times 2^{n}$.

Dimostrare che i numeri del tipo 12008, 120308, 1203308,… (le prime tre cifre sono sempre 120; le ultime due cifre sono sempre 08; le cifre centrali sono una stringa di 3 e ogni termine della successione possiede un 3 in più del termine precedete) sono divisibili per 19.

Soluzione: l’intero 12008 si verifica facilmente essere divisibile per 19. Se consideriamo due termini qualunque della successione, la loro differenza è pari a $1.083 \cdot 10^{k}$ con $k\geq2$. Poichè 1.083 è divisibile per 19 (e quindi lo è l’espressione $1.083 \cdot 10^{k}$), per induzione ogni termine della successione è divisibile per 19. Ogni termine della successione sarà pari, infatti, alla somma di due termini divisibili per 19.

Siano date $3^{n}$ monete, tutte uguali tranne una che è più pesante delle altre. Dimostrare che, usando una bilancia a due bracci uguali, è possibile trovare la moneta più pesante con $n$ pesate.

Soluzione: con 3 monete ($n=1$) basta una sola pesata. Infatti 2 monete vengono poste sulla bilancia (una per ciascun piatto); se i due piatti sono in equilibrio, la moneta più pesante è quella non considerata, mentre se non c’è equilibrio ho comunque trovato la più pesante. Supponiamo che con $n$ pesate si possa trovare la moneta più pesante in un mucchio di $3^{n}$ monete. Se ne considero $3^{n+1}$, posso dividerle in 3 mucchi da $3^{n}$ (in quanto $3 \cdot 3^{n} = 3^{n+1}$) e dunque mi basta una pesata per capire qual è il mucchio più pesante (si procede in modo analogo a come fatto con 3 sole monete) e ricondurmi ad un mucchio di $3^{n}$ monete per le quali, in virtù del passo induttivo, riesco a trovare la moneta più pesante con $n$ pesate.

Il principio di induzione viene frequentemente applicato nella risoluzione di un gran numero di giochi di strategia. Lasciamo al lettore la possibilità di dimostrare per induzione che il gioco delle torri di Hanoi ha soluzione (quale?) per qualsiasi numero di dischi.

Per concludere, ricordiamo che il principio di induzione può essere incontrato anche in contesti diversi dalla teoria dei numeri. A titolo di esempio, mostriamo il seguente esercizio:

Sono assegnate un insieme di rette distinte nel piano, le quali lo dividono in diverse regioni. Dimostrare che tali regioni possono essere colorate col due soli colori facendo in modo che nessuna regione confinante sia dello stesso colore.

Soluzione: dimostriamolo per induzione sul numero $n$ di rette. Per $n=1$ abbiamo solo due regioni (due semipiani) che possono essere colorate con due colori diversi (ad esempio, bianco e rosso). Supponiamo ora che le regioni di piano ottenute dopo averlo diviso con $n$ rette possano essere colorate con due soli colori (bianco e rosso) in modo che regioni confinanti non hanno lo stesso colore. Vogliamo dimostrare che anche con $n+1$ rette una simile colorazione è ancora possibile. Inseriamo la (n+1)-sima retta, la quale dividerà il piano in due semipiani, e operiamo come segue: in uno dei due semipiano lasciamo i colori come sono, mentre nel secondo semipiano li invertiamo (il bianco diventa rosso e viceversa). Pertanto, se due regioni condividono un tratto comune e si trovano nello stesso semipiano, continueranno ad avere colori diversi, mentre se si trovano su due semipiani distinti (vale a dire, sono separate dalla (n+1)-sima retta), prima dell’inserimento di quest’ultima creavano un’unica regione e avevano lo stesso colore, ma per come si è operato ora possiedono colori diversi.

Lasciamo al lettore anche il seguente esercizio di analisi matematica (tratto dal libro “Calculus” di J. Stewart):

Find expressions for the first five derivatives of $f(x)=x^{2} \cdot e^{x}$. Do you see a pattern in these expressions? Guess a formula for $f^{n}(x)$ and prove it by mathematical induction.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.