Il principio di induzione matematica

Cosa afferma il principio di induzione matematica

Se un sottoinsieme U dell'insieme dei numeri naturali N contiene lo zero e il successivo di ogni elemento, allora il sottoinsieme U coincide con l'insieme dei numeri naturali N.

E' uno degli assiomi di Peano sui numeri naturali.

A cosa serve il principio di induzione

Il principio di induzione è alla base di un metodo di dimostrazione molto importante in matematica, la dimostrazione per induzione

Mi permette di dimostrare una proposizione o un teorema in un insieme composto da infiniti elementi nell'insieme dei numeri naturali, senza doverlo dimostrare per ogni singolo elemento.

La dimostrazione per induzione si basa sulla ricorsione matematica.

E' un po' come l'effetto domino.

Se dispongo migliaia di tavolette del domino vicine tra loro e faccio cadere la prima, tutte le altre verranno giù di conseguenza.

Non occorre che controlli le tavolette una a una.

Se sono poste alla giusta distanza costante, cadranno tutte.

Come funziona la dimostrazione per induzione

Considero una proposizione P(n) dove n ∈ N è un numero naturale e un numero iniziale n₀


• Base induttiva
  Se la proposizione P(n₀) è vera
• Tesi
  Suppongo vera per ipotesi P(n)
• Passo induttivo
  Se è vera anche la proposizione P(n+1) allora la tesi P(n) è vera per ogni numero naturale n≥n₀

Quando bisogna dimostrare una proposizione soltanto per i numeri naturali superiori o uguali a n₀, la base dell'induzione va dimostrata per n₀ anziché per 0.

$$ \begin{cases} P(n_0) \\ \\ P(n) \Rightarrow P(n+1) \end{cases} $$

Va detto che n₀ non deve essere necessariamente zero. Può anche essere n₀=1 o altro.

Di fatto n₀ è l'elemento più piccolo dell'insieme che sto considerando.

Il prossimo esempio dovrebbe chiarire del tutto l'idea.

Nota. Prima di continuare vale la pena ricordare che il metodo per induzione non trova il risultato corretto, verifica soltanto se una tesi è corretta. E' sempre il matematico a dover formulare la tesi. Inoltre, la dimostrazione per induzione è possibile soltanto se la proposizione dipende dai numeri naturali. E' bene non dimenticarlo.

Un esempio pratico

Esempio 1

Devo dimostrare che la seguente proposizione P(n) è divisibile per 6 per ogni n≥1.

Dove n è un qualsiasi numero naturale n∈N maggiore o uguale a uno.

$$ P(n) := n^3 + 5n $$

Per prima cosa verifico se la base dell'induzione è vera per l'elemento più piccolo dell'insieme.

In questo caso, l'insieme di riferimento è l'insieme dei numeri naturali (N). Quindi, n₀=1.

Sostituisco n=1 alla proposizione P(n).

$$ P(1) = (1)^3 + 5(1) \\ P(1)= 1+5 \\ P(1)=6 $$

La base dell'induzione è vera perché 6 è divisibile 6.

La prima condizione del principi di induzione è soddisfatta.

Nota. Se la base dell'induzione fosse falsa sarebbe del tutto inutile continuare la dimostrazione. Quindi, è importante dimostrare subito la veridicità della base dell'induzione prima di ogni altra cosa. Anche perché è molto più semplice da dimostrare rispetto al passo induttivo.

Ora verifico il passo induttivo.

Per ipotesi considero vera ( ossia divisibile per 6 ) la proposizione P(n).

Dove n è un generico numero naturale.

$$ P(n) := n^3 + 5n \:\: \text{ per ipotesi è divisibile per 6 } $$

Secondo il principio di induzione matematica dei numeri naturali se P(n) è vera allora anche P(n+1) è vera.

E' la tesi da dimostrare.

$$ P(n+1) := (n+1)^3 + 5(n+1) $$

Dove n+1 è il numero successivo di n.

Ora devo dimostrare che l'implicazione sia effettivamente vera.

Nota. La proposizione P(n) è considerata vera per ipotesi. Non è però detto che sia vera anche l'implicazione ossia che sia vera P(n+1). E' quello che deve dimostrare. $$ P(n) \Rightarrow P(n+1) $$

Ci sono diversi metodi per dimostrarlo.

Il più semplice è ricondurre la proposizione P(n+1) alla P(n)=n³+5n che per ipotesi so già che è vera.

$$ P(n+1) := (n+1)^3 + 5(n+1) $$

$$ P(n+1) := n^3+3n^2+3n+1 + 5n+5 $$

$$ P(n+1) := ( n^3 + 5n ) +3n^2+3n+1 +5 $$

Ho trovato la P(n) nella P(n+1).

Posso riscriverla nel seguente modo:

$$ P(n+1) := P(n) +3n^2+3n+1 +5 $$

Adesso la proposizione è scomposta in due parti.

La componente P(n) so già che è divisibile per 6 per l'ipotesi iniziale.

Devo dimostrare che lo sia anche il resto dell'espressione ossia 3n²+3n+1+5

$$ P(n+1) := P(n) +3n^2+3n+6 $$

$$ P(n+1) := P(n) +3n(n+1)+6 $$

In quest'ultima forma posso affermare che

• la seconda componente 3n(n+1) è divisibile per 6 perché n(n+1) è sicuramente superiore a 1
• la terza componente, ossia il numero +6, è ovviamente divisibile per 6.

Quindi, anche la seconda condizione del principio di induzione è soddisfatta.

Ho così dimostrato che la proposizione P(n) è divisibile per 6 per ogni n≥1.

Esempio 2

Devo dimostrare che la somma di n potenze con base 2 sia uguale a 2ⁿ-1

$$ P(n) := 2^0+2^1+2^2+2^3+...+2^{n-1}= 2^n-1 $$

Per prima cosa verifico se è vera la base induttiva per n=1

Il primo elemento della serie è 2⁰ mentre per n=1 ottengo 2¹-1

$$ P(1) := \ 2^0 = 2^1 - 1 $$

$$ P(1) := \ 1 = 2 - 1 $$

$$ P(1) := \ 1 = 1 $$

La base induttiva è vera, quindi posso procedere.

Definisco per ipotesi vera la proposizione iniziale per qualsiasi n

$$ P(n) := \ 2^0+2^1+2^2+2^3+...+2^{n-1}= 2^n-1 $$

A questo punto verifico se il passo induttivo è vero per qualsiasi n+1

$$ P(n+1) := \ 2^0+2^1+2^2+2^3+...+2^{(n+1)-1}= 2^{n+1}-1 $$

$$ P(n+1) := \ 2^0+2^1+2^2+2^3+...+2^{(n+1)-1}= 2 \cdot 2^n-1 $$

$$ P(n+1) := \ 2^0+2^1+2^2+2^3+...+2^{n}= 2 \cdot 2^n-1 $$

$$ P(n+1) := \ 2^0+2^1+2^2+2^3+...+2 \cdot 2^{n-1}= 2 \cdot 2^n-1 $$

Per la proprietà invariantiva elimino la moltiplicazione per 2 da entrambi i membri

Quello che resta è la proposizione P(n) considerata vera per ipotesi.

$$ P(n+1) := \ 2^0+2^1+2^2+2^3+...+ 2^{n-1}= 2^n-1 $$

Quindi, il passo induttivo P(n+1) è vero per il numero naturale successivo n+1.

Questo vuol dire che l'ipotesi P(n) è vera per qualsiasi numero naturale n.

E così via.