Principio di induzione

Quando dobbiamo fare una dimostrazione possiamo seguire una via costruttiva cercando di far vedere che ciò che asseriamo è vero, oppure ragionando per assurdo assumendo come vero il contrario e arrivando, appunto, ad un assurdo, oppure attraverso il principio di induzione.

E’ abbastanza semplice capire questo principio, ma la sua applicazione può risultare piuttosto difficile, occorre un po’ di pratica, quindi esercitarsi molto. Daremo l’enunciato attraverso un esempio in modo da vedere subito come procedere.

Vogliamo dimostrare una certa proprietà P(n) che dipende da un indice n $\displaystyle{\in\mathbb{N}}$

Ad esempio vogliamo dimostrare che

P(n) : n²+ n è pari $\displaystyle{\forall n \in \mathbb{N} , n \geq 1}$ .

Il principio di induzione si basa su due passi

Passo base
Passo induttivo

Passo base : esprimiamo la proprietà P(n) con il valore iniziale di n, che, nel nostro caso è 1 e verifichiamo se la proprietà vale per questo valore di n

Per n = 1 → n²+ n =2 ed è pari

Il passo zero, base dell’induzione è vero.

Passo induttivo : supponiamo P(n) vera, non dobbiamo dimostrare che è vera ! La supponiamo tale. Ora scriviamo la proprietà per n + 1, ossia P(n + 1) che, per il nostro esempio sarà

$\displaystyle{(n+1)^2 + (n+1)}$

e dimostriamo che l’ipotesi che P(n) è vera implica che anche P(n + 1) è vera ∀n ≥ n₀, dove n₀è il valore iniziale di n, quello usato nel passo base. Se P(n) vera implica P(n + 1) vera allora P(n) è vera .

Riprendiamo l’esempio , abbiamo trovato che P(n) è vera per n = 1 (passo base), poi abbiamo scritto la proprietà che vogliamo dimostrare per n + 1, ora dobbiamo lavorare su questa

$\displaystyle{(n+1)^2 + (n+1)}$ .

Supponendo che n²+ n è vera, ossia è pari.

$\displaystyle{(n+1)^2 + (n+1)= n^2+1+2n+n+1=n^2+n+2(n+1)}$ .

n²+ n è pari per ipotesi (passo induttivo) , 2(n + 1) è sicuramente pari. Dato che la somma di due numeri pari è un numero pari abbiamo dimostrato che

P(n) : n²+ n è pari $\displaystyle{\forall n \in \mathbb{N} , n \geq 1}$ .

e lo abbiamo fatto utilizzando il passo induttivo, ossia ammettendo vero che P(n) è vera.

Vediamo subito altri esempi.

Vogliamo dimostrare che ∀n ≥ 1 , la somma dei primi n numeri naturali S(n) = 1 , 2 , .. , n può essere scritta come :

$\displaystyle{\sum_{k=1}^n K =\frac{n(n+1)}{2}}$ .

Passo base, poniamo n = 1 e vediamo se la proprietà è vera

$\displaystyle{\sum_{k=1}^1 K =\frac{1(1+1)}{2} \Longrightarrow 1 = 1 }$ .

il passo base dell’induzione è vero.

Applichiamo ora il passo induttivo, supponiamo P(n) vera

$\displaystyle{\sum_{k=1}^n K =\frac{n(n+1)}{2} \> vera \> per \> n> n_0}$ .

dobbiamo far vedere che questo implica che è vera anche la proprietà P(n + 1)

$\displaystyle{\sum_{k=1}^{n+1}=\frac{(n+1)[(n+1)+1]}{2}}$ .

P(n) ⇒ P(n + 1)

Dobbiamo lavorare su P(n + 1) in modo da far comparire P(n) che supponiamo vera.

Dividiamo in due la sommatoria

$\displaystyle{\sum_{k=1}^{n} K + \sum_{k=n+1}^{n+1} K =\frac{(n+1)(n+2)}{2}}$ .

Abbiamo fatto comparire P(n). Dimostriamo che il primo membro dell’equazione è uguale al secondo utilizzando l’ipotesi P(n) vera.

$\displaystyle{\sum_{k=1}^{n} K =\frac{n(n+1)}{2}}$ .

Questa la supponiamo vera.

$\displaystyle{\sum_{k=n+1}^{n+1} K=n+1}$ .

Il primo membro diventa

$\displaystyle{\sum_{k=1}^{n} K +\sum_{k=n+1}^{n+1} K =\frac{n(n+1)}{2}+n+1 =\frac{n(n+1)+2(n+1)}{2}=(n+1)\frac{n+2}{2}=\frac{(n+1)(n+2)}{2}}$ .

Che è proprio quello che volevamo dimostrare.

Altro esempio

Vogliamo dimostrare che

$\displaystyle{11^n -1 , \forall n\in\mathbb{N} , n \geq 1}$

è divisibile per 10.

Passo base n = 1

$\displaystyle{11^1-1 =10}$

è vero che è divisibile per 10.

Passo induttivo

Dobbiamo far vedere che 11ⁿ⁺¹-1 è divisibile per 10 sapendo che 11ⁿ– 1 lo è (lo supponiamo). Lavoriamo su P(n + 1)

$\displaystyle{(11)^{(n+1)}-1 =11^n \cdot 11 -1 =11^n (10+1) -1 = 11^n \cdot 10 +11^n -1 }$ .

Quello che abbiamo ottenuto è divisibile per 10 ?

11ⁿ– 1 lo è perché è P(n) che supponiamo vera nel passo induttivo.

11ⁿ• 10 è sicuramente divisibile per 10

Abbiamo dimostrato che 11ⁿ– 1 è divisibile per 10 ∀n ≥ 1.