Principio di induzione

Analisi #Completo

Il principio di induzione è una tecnica di dimostrazione che consente di dimostrare la validità di una tesi dalla verifica di due condizioni: la validità del passo zero e la validità del passo induttivo

Va praticamente sempre nel caso in cui abbiamo un enunciato del genere

$$\text{Dimostrare che per ogni }n\in \mathbb{N}\text{ vale ...}$$

Funzionamento

Il principio di induzione stabilisce che, se valgono le seguenti condizioni:

1. Passo zero - $P(n)$ è vera per $n=0$, cioè $P(0)$ è vera
2. Passo induttivo - supponendo che $P(n)$ sia vera, ne consegue che $P(n+1)$ è vera allora $P(n)$ è vera per tutti gli $n\in \mathbb{N}$

Spiegazione

YouMath: Distacchiamoci dal formalismo matematico, anzi dimentichiamo per un momento che stiamo facendo Matematica, e supponiamo di aver costruito un robot privo di intelligenza in grado di eseguire tutti i nostri comandi vocali. Vogliamo far costruire al robot una casa di due piani fatta di mattoni.

Gli daremo le seguenti istruzioni:

• costruisci il piano terra assemblando sei pezzi: uno per il pavimento, quattro per i muri laterali ed uno per il solaio;

• partendo dal solaio del piano terra assembla altri sei pezzi: uno per il pavimento, quattro per i muri laterali ed uno per il solaio;

Fine, la casa a due piani è stata costruita.

Supponiamo ora di voler far costruire al robot un palazzo di dieci, cento, mille… infiniti piani. Come nel caso precedente potremmo metterci a spiegargli come costruire il palazzo, piano dopo piano, impiegandoci però un sacco di tempo… In alternativa potremmo:

• spiegargli come costruire il piano terra (passo zero);

• dirgli come costruire un piano qualsiasi a partire dal precedente (passo induttivo).

A questo punto il nostro lavoro è terminato. Il robot, sapendo costruire il piano terra e qualsiasi altro piano a partire dal precedente, riuscirà a costruire il palazzo in totale autonomia. Se questo (stupido) esempio vi è chiaro, tra poco sarà chiara anche la logica del principio di induzione. Considerate le seguenti analogie, e pensate:

• al palazzo di infiniti piani da costruire come alla proposizione $P(n)$ di cui vogliamo dimostrare la validità per ogni $n\in \mathbb{N}$

• alla costruzione del piano terra come alla verifica della base di induzione, cioè alla verifica della validità di $P(0)$

• all’ipotesi di avere costruito un generico piano come all’ipotesi induttiva, ossia all’ipotesi secondo cui $P(n)$ è vera;

• alla costruzione del piano successivo partendo dal precedente come alla verifica del passo induttivo, ossia alla verifica della validità dell’implicazione $P(n)⟹P(n+1)$.

Questa è la logica che regola il principio di induzione. Niente di più e niente di meno. :)

Come usare il principio di induzione

Supponiamo di dover dimostrare che una proprietà $P(n)$ vale per ogni $n\in \mathbb{N}$, oppure per ogni $n\ge k$ con $k$ un certo numero naturale.

1) Base di induzione

Si esprime la proprietà $P(n)$ da dimostrare con il valore iniziale $n=k$ e si verifica che la proprietà ottenuta è vera

2) Paso induttivo

1. Si suppone che la proprietà sia vera $P(n)$
2. Si considera la proprietà per $P(n+1)$, e si dimostra che l’ipotesi per cui $P(n)$ è vera implica anche che $P(n+1)$ è vera.

Warning

Per il primo punto del passo induttivo non c’è bisogno di dimostrare che la proprietà sia vera

Dimostrazione

$$\begin{array}{rl}& S(n)=1+2+3+4+\cdots +n\\ & S(n)=\frac{n(n+1)}{2}\forall n\ge 1\end{array}$$

vogliamo dimostrare che:

$$P(n)\text{ eˋ vera per ogni }n{\ge }_1$$

1)Base di induzione: verifichiamo che la proprietà $P(n)$ vale per il valore iniziale, che in questo caso è $k=1$

$$S(1)=\frac{1\ast (1+1)}{2}=\frac{2}{2}=1$$

2)Passo induttivo supponiamo che $P(n)$ sia vera per $n$, quindi:

$$S(n)=\frac{n(n+1)}{2}$$

dimostriamo che l’ipotesi induttiva rende vera la proprietà per $n+1$

$$S(n+1)+\frac{(n+1)[(n+1)+1]}{2}$$

Per dimostrare che $P(n)⟹P(n+1)$ cerchiamo di esprimere $S(n+1)$ in termini di $S(n)$. Questo la parte più difficile perché bisogna cercare di scrivere $S(n+1)$ in funzione di $S(n)$.

$$S(n+1)=\frac{(n+1)[(n+1)+1]}{2}=\frac{(n+1)(n+2)}{2}=\frac{n^2+3n+2}{2}$$

Ricordiamoci che $S(n+1)$ è la somma dei primi $n+1$, cioè: $1+2+3+4+5+\cdots +n$ Quindi possiamo vederla anche cosi:

$$S(n+1)=S(n)+(n+1)$$

Ora non ci resta che sostituire $S(n)$ con la sua espressione e usare l’ipotesi induttiva.

$$\begin{array}{rl}& S(n+1)=S(n)+(n+1)=\text{[ipotesi induttiva]}\\ & =\frac{n(n+1)}{2}+(n+1)\\ & =\frac{n(n+1)+2(n+1)}{2}\\ & =n^2+3n+2=\text{[Ipotesi induttiva]}\end{array}$$

Come dimostrato l’ipotesi induttiva segue la validità del passo induttivo. Quindi per il principio di induzione possiamo affermare che la proprietà $P(n)$ è vera per ogni $n\ge 1$, ossia che la formula vale $\forall n\ge 1$