Induzione matematica

L’induzione matematica è un metodo di dimostrazione molto usato in matematica, soprattutto quando lavoriamo con i numeri naturali o con un’altra successione.

Il principio

Il principio di base è che dimostriamo l’affermazione per un primo elemento; nei numeri naturali è spesso n = 1. Lo dimostriamo con una semplice sostituzione. Nel passo successivo, quello induttivo, dimostriamo l’implicazione «se l’affermazione vale per n = a, allora vale anche per n = a + 1».

Da questi due passi possiamo dedurre che l’espressione vale per ogni n (di un certo insieme, quello con cui stiamo lavorando). Perché è così? All’inizio dimostriamo che l’espressione vale per n = 1. Sappiamo inoltre che, se l’espressione vale per n = a, vale anche per n = a + 1. Scegliamo quindi a = 1. Sappiamo che per a = 1 l’espressione vale e sappiamo anche che vale per a + 1 = 2. A questo punto sappiamo che l’espressione vale per a = 2. Ma poiché vale anche per a + 1, deve valere anche per 2 + 1 = 3. E così via.

Primo esempio

Il primo esempio sarà banale. Dimostriamo che, se a un numero pari qualsiasi aggiungiamo due, otteniamo di nuovo un numero pari. Poiché ci muoviamo nei numeri naturali non nulli, scriviamo in generale un numero pari come 2n, dove n è un numero naturale non nullo. Se al posto di n sostituiamo un numero naturale qualsiasi, otteniamo come risultato un numero pari: si vede a colpo d’occhio. La divisibilità si scrive con una barra verticale così:

$$2\mid 2n$$

Questa scrittura significa che il due divide senza resto l’espressione 2n. Ora che sappiamo scrivere la divisibilità, possiamo scrivere anche ciò che dobbiamo dimostrare per induzione matematica.

$$2\mid 2n+2;n\in {\mathbb{N}}^{\ast }$$

Nel primo esempio dobbiamo dimostrare questo, cioè che il due divide l’espressione 2n + 2: corrisponde esattamente all’enunciato a parole di partenza «se a un numero pari qualsiasi aggiungiamo due, otteniamo di nuovo un numero pari».

Nel passo base dell’induzione lo dimostriamo per il primo elemento, per l’uno. Sostituiamo nell’espressione n = 1:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Il due divide il quattro senza resto, quindi per il primo elemento l’affermazione vale. Ora tocca al passo induttivo, in cui dobbiamo dimostrare che, se l’affermazione vale per l’elemento a-esimo, allora vale anche per l’elemento (a + 1)-esimo. All’inizio supponiamo che valga la nostra ipotesi, cioè n = a:

$$2\mid 2a+2$$

Supponiamo che questa espressione sia vera: la useremo nella costruzione della dimostrazione. Vogliamo ora dimostrare che

$$2\mid 2(a+1)+2.$$

Che cosa abbiamo fatto? Al posto di a abbiamo scritto (a + 1). Le parentesi sono importanti; questa espressione sarebbe sbagliata: 2a + 1 + 2. Non aggiungiamo uno all’intera espressione, ma trasformiamo davvero a in un’espressione più grande di un’unità, cioè (a + 1). Modifichiamo l’espressione svolgendo la parentesi.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Ora una piccola digressione sulla divisibilità. Se abbiamo due numeri, diciamo p e q, divisibili per un certo numero, per esempio r, allora anche la loro somma è divisibile per r. Vale quindi:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Possiamo sostituire, per esempio, i numeri p = 8, q = 20 e r = 4. Vediamo che il quattro divide sia l’otto sia il venti. E divide anche la loro somma 8 + 20 = 28.

Come lo usiamo nel nostro esempio? Scomponiamo il membro di destra nella somma dei numeri p e q così:

$$p=2a+2;q=2$$

Il numero q, cioè il due, è banalmente divisibile per due. E anche l’espressione p è divisibile per due, perché ce lo dice l’ipotesi. L’espressione p corrisponde esattamente alla nostra ipotesi, che supponiamo vera. E se p è divisibile per due e allo stesso tempo q è divisibile per due, allora anche la loro somma è divisibile per due.

Torniamo ancora un momento sull’ipotesi. All’inizio abbiamo detto di supporre che valga

$$2\mid 2a+2.$$

Perciò, quando durante la costruzione della dimostrazione ci siamo imbattuti nell’espressione 2a + 2, abbiamo potuto dire che è divisibile per due, proprio perché è la nostra ipotesi. Di solito questo è il passo più difficile dell’induzione matematica: capire quando e perché si può usare l’ipotesi induttiva.

Con questo l’induzione è conclusa, la dimostrazione è stata svolta con successo, il teorema vale.

Se volessi, potresti scomporre in un altro modo e non dovresti usare l’ipotesi: p = 2n e q = 2 + 2. Il numero q = 4 è banalmente divisibile per due e lo stesso vale per p = 2n, perché dividendo per due ci resta il numero n, che è naturale, cioè intero. Abbiamo di nuovo due espressioni entrambe divisibili per due, quindi anche la loro somma è divisibile per due.

In entrambi i casi abbiamo però dimostrato che

1. l’espressione data vale per n = 1,
2. se l’espressione vale per n, allora vale anche per n + 1.

Da qui possiamo dedurre:

• Sappiamo che l’espressione vale per n = 1.
• Se vale per n, deve valere anche per n + 1, cioè anche per 1 + 1, quindi l’espressione vale anche per n = 2.
• Se vale per n, deve valere anche per n + 1, cioè anche per 2 + 1, quindi l’espressione vale anche per n = 3.
• Se vale per n, deve valere anche per n + 1, cioè anche per 3 + 1, quindi l’espressione vale anche per n = 4.
• Se vale per n, deve valere anche per n + 1, cioè anche per 4 + 1, quindi l’espressione vale anche per n = 5.
• …

Secondo esempio

Dimostriamo ora per induzione matematica una semplice affermazione:

$$2^n\ge 2n;n\in {\mathbb{N}}^{\ast }.$$

Prima il passo base: verifichiamo se l’affermazione vale per n = 1, in quanto primo elemento dei numeri naturali non nulli da cui scegliamo n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Vale banalmente. Passiamo ora al passo induttivo, in cui dobbiamo verificare se, quando vale per n = a, vale anche per n = a + 1. La nostra ipotesi è quindi che valga

$$2^a\ge 2a$$

e vogliamo dimostrare:

$$2^{a+1}\ge 2(a+1)$$

Scriviamo prima il membro di sinistra con le regole di calcolo con le potenze e nel membro di destra semplicemente svolgiamo la parentesi.

$$2\cdot 2^a\ge 2a+2$$

Nel membro di sinistra al posto della moltiplicazione usiamo l’addizione, il membro di destra lo lasciamo invariato.

$$2^a+2^a\ge 2a+2$$

Ora sfruttiamo l’ipotesi. L’ipotesi è un enunciato che supponiamo vero. Nella disuguaglianza abbiamo in entrambi i membri una somma di due termini. Sappiamo però anche che

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

La prima riga ce la dà l’ipotesi e il secondo enunciato è banale (il valore minimo di 2^a si ha per a = 1 ed è proprio uguale a due). Sappiamo quindi che nel membro di sinistra entrambi i termini sono maggiori o uguali ai corrispondenti termini del membro di destra. Abbiamo così dimostrato per induzione che, se l’espressione vale per a, allora vale anche per (a + 1), e poiché l’espressione vale anche per uno, l’espressione data è vera.

Terzo esempio

Proviamo a dimostrare l’affermazione seguente:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{N}}^{\ast }$$

A parole: se n è divisibile per tre, allora anche n² è divisibile per tre. Se n non è divisibile per tre, l’espressione vale banalmente (per la definizione di implicazione), quindi ci occupiamo dei casi in cui n è divisibile per tre. Questo ci genera la successione di numeri naturali a_i=3, 6, 9, 12, 15… D’ora in poi ci muoveremo in questa successione a_i.

La dimostrazione per induzione comincia con il passo base, cioè verificando se l’affermazione vale per il primo elemento. Ricorda che ci muoviamo nella successione a_i, quindi prendiamo il primo elemento di questa successione, cioè a₁, che è il tre. Per il tre l’espressione vale:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Passiamo ora al passo induttivo. Vediamo che la successione a_i si può scrivere come 3n, dove n è un numero naturale non nullo. Quindi ogni elemento supera di tre il precedente, e così via. Supponiamo ora che l’espressione valga per n e dobbiamo dimostrare che vale anche per (n + 3), che è la regola che genera il successivo elemento della successione in cui ci muoviamo. Scriviamo prima l’ipotesi:

$$3\mid n\Rightarrow 3\mid n^2$$

e poi ciò che vogliamo dimostrare

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Sviluppiamo la parentesi a destra dell’implicazione con la formula:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

E siamo ormai quasi al traguardo. A sinistra dell’implicazione abbiamo un’espressione sicuramente divisibile per tre, perché n per ipotesi è divisibile per tre (ci muoviamo solo tra i numeri della successione a_i) e anche il tre è divisibile per tre. A destra abbiamo prima n², che per ipotesi è divisibile per tre. Sappiamo infatti che n è divisibile per tre e l’ipotesi dice che, se n è divisibile per tre, allora anche n² è divisibile per tre:

$$3\mid n\Rightarrow 3\mid n^2$$

Segue poi l’espressione 6n, che è banalmente divisibile per tre. Puoi pensarla come una semplificazione di frazione:

$$\frac{6n}{3}=2n$$

La variabile n è un numero naturale, quindi anche il prodotto 2n sarà un numero naturale: dividendo per tre abbiamo ottenuto un numero naturale e l’espressione 6n deve perciò essere divisibile per tre. E il nove alla fine è di nuovo divisibile per tre. L’espressione vale per il primo elemento e per il passo induttivo, quindi è vera.

Numero di parentesi in un’espressione

L’ultimo esempio sarà un po’ atipico. Proviamo a dimostrare l’affermazione che il numero di parentesi in un’espressione semplice è sempre pari, per farti vedere che l’induzione matematica si può usare anche in un contesto del tutto diverso dai soli numeri naturali. All’inizio dobbiamo definire che cos’è un’espressione semplice. Un’espressione semplice è:

• un numero naturale,
• se p è un’espressione semplice, allora anche (p²) è un’espressione semplice,
• se p e q sono espressioni semplici, allora anche (p + q) è un’espressione semplice.

Ecco dunque che cosa sono espressioni semplici: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). E invece queste non sono espressioni semplici:

• 1 + 2 → mancano le parentesi esterne,
• (1 + 2 → manca la parentesi destra,
• 13² → mancano le parentesi esterne,
• (1 + 2 + 3) → mancano delle parentesi, la scrittura corretta dovrebbe essere (1 + (2 + 3))

Un’espressione semplice può nascere, per esempio, così. All’inizio scegliamo l’espressione semplice (a + b). Ora al posto di a sostituiamo l’espressione semplice a = (c + d), così otteniamo ((c + d) + b), e al posto di b sostituiamo il tre: ((c + d) + 3). Al posto di c sostituiamo il dieci: ((10 + d) + 3) e infine al posto di d sostituiamo (5²): ((10 + (5²)) + 3). È importante rispettare le parentesi, altrimenti non funziona.

Dimostriamo ora che un’espressione semplice contiene un numero pari di parentesi (tra i numeri pari rientra anche lo zero).

Nel passo base dell’induzione scegliamo un primo elemento. In questo caso il primo elemento sarà l’espressione semplice più banale, cioè un qualsiasi numero naturale. Poniamo quindi

$$j=n;n\in {\mathbb{N}}^{\ast }.$$

Per l’espressione j il numero di parentesi è zero, quindi il primo elemento va bene. Nel passo induttivo supponiamo di avere due espressioni semplici p e q e che entrambe abbiano un numero pari di parentesi. Dobbiamo allora dimostrare che anche le espressioni semplici (p + q) e (p²) hanno un numero pari di parentesi.

Prima l’addizione. Definiamo anche la funzione z(q), che restituisce il numero di parentesi dell’espressione q. Allora l’espressione (p + q) ha z(p) + z(q) + 2 parentesi. Ha quindi due parentesi in più della somma delle parentesi delle espressioni p e q. Per ipotesi sia z(p) sia z(q) sono pari, quindi sommando tre numeri pari otteniamo di nuovo un numero pari. In questo caso l’affermazione vale.

Ora la potenza. Vale ancora l’ipotesi che l’espressione semplice p contenga un numero pari di parentesi. L’espressione (p²) contiene allora z(p) + 2 parentesi, cioè di nuovo due parentesi in più rispetto all’espressione p. Anche in questo caso sommiamo numeri pari, quindi il risultato è pari.

L’affermazione vale per il primo elemento e vale anche nel passo induttivo, perciò è vera.