Principio di induzione

Il principio di induzione è una tecnica per provare che una proprietà è valida per tutti i numeri di $\mathbb{N}$.

La tecnica per dimostrare la proprietà $P(x)$ consiste nel:

• Caso base, per cui si dimostra che $P(0)$ è vero
• Passo induttivo, per cui si dimostra che $P(n)\Rightarrow P(n+1)$, cioè che se $P(n)$ è dato per vero (ipotesi induttiva), anche $P(n+1)$ deve esserlo

$$P(0)\wedge (P(n)\Rightarrow P(n+1))\Rightarrow P(x),\forall x,n\in \mathbb{N}$$

Per esempio, si ha da dimostrare che con $S(n)="\text{somma dei primi }n"$, $S(x)=\frac{x(x+1)}{2}$:

• Caso base: $S(0)=0=\frac{0\cdot (0+1)}{2}$

• Passo induttivo:

  Sia l'ipotesi induttiva $S(n)=\frac{n(n+1)}{2}$ scontata, con $n\in \mathbb{N}$. $$\begin{gathered} S(n+1)=0+1+...+n+(n+1)=S(n)+(n+1)= \\ =\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}= \\ \frac{(n+2)(n+1)}{2}=\frac{(n+1)((n+1)+1)}{2} \end{gathered}$$

  E quindi è verificato che $S(n)=\frac{n(n+1)}{2}\Rightarrow S(n+1)=\frac{(n+1)((n+1)+1)}{2}$

Principio di induzione completo

Tramite il principio di induzione completo (o forte) è possibile semplificare il processo di dimostrazione visto che si considerano veri tutti i numeri dal caso base fino a $n$ nel passo induttivo.

Quindi, per dimostrare la proprietà $P(x)$ va dimostato:

• Caso base, per cui si dimostra se $P(0)$ è vero
• Passo induttivo, per cui si dimostra che se la proprietà vale per i primi $n$ numeri allora vale anche per $P(n+1)$, quindi $P(0)\wedge P(1)\wedge ...\wedge P(n)\Rightarrow P(n+1)$.

Per esempio, si ha da dimostrare che $P(x)="n\text{ eˋ scomponibile in fattori primi}"$ vale $\forall n\ge 2\in \mathbb{N}$:

• Caso base: $n=2\Rightarrow P(2)$ vale perchè $2=2$ che è primo.

• Passo induttivo:

  Si suppone che quando $n\ge 2$, tutti i numeri tra $2$ ed $n$ siano scomponibili: $$\forall x\in \mathbb{N}:2\le x\le n,P(x)$$ che è quindi l'ipotesi induttiva.

  Si vuole quindi dimostrare che la proprietà vale per $n+1$, ed esistono due casi per cui dovrebbe valere:

  • $n+1$ è primo, allora $P(n+1)$ vale perchè è già scomposto
  • $n+1$ non è primo, allora $$\exists y,z\in \mathbb{N}:n+1=y\cdot z\wedge \{y,z\}⊈\{1,n+1\}$$ per cui $2\le y\le n\wedge 2\le z\le n$.
    Per ipotesi induttiva $y$ e $z$ sono scomponibili in fattori primi e quindi lo è anche $n+1$.

Funzioni ricorsive

Oltre a dimostrare la proprietà definita dalle funzioni ricorsive, va anche dimostrato che terminano.

Per esempio, la funzione $f(n)=n!$, con $f:\mathbb{N}\to \mathbb{N}$, può essere espressa come: $$n!=\{\begin{array}{ll}1& \text{se }n=0\\ (n-1)!\cdot n& \text{se }n>0\end{array}\Rightarrow f(n)=\{\begin{array}{ll}1& \text{se }n=0\\ f(n-1)\cdot n& \text{se }n>0\end{array}$$ e si vuole dimostrare che è ben definita (cioè che trova veramente $n!$):

• Caso base: $f(0)=1=2^0$

• Passo induttivo:

  Sia $n=k-1$ con $n\ge 0\Rightarrow k\ge 1$, si assume $$f(k-1)=2^{k-1}$$ per vero e che sia quindi l'ipotesi induttiva.

  Va verificato che $$f(k)=2^k$$ quindi, $$f(k)=f(k-1)\cdot k=(k-1)!\cdot k=n!$$

Inoltre si vuole dimostrare che la funzione corrispondente $fact(n)$,

int fact(int n) {
	if (n == 0) {
		return 1;
	}
	return fact(n-1) * n;
}

termina e restituisce $n!$:

• Caso base: Con $n=0$, fact(n) restituisce $1=0!$

• Passo induttivo:

  Sia $n=k-1$ con $k\ge 1$ e si suppone che fact(n-1) termina e restituisce $(n-1)!$.

  Allora, $$\text{fact(n)}=\text{n }\ast \text{ fact(n-1)}=n\cdot (n-1)!=n!$$