Induzione

La dimostrazione per induzione si basa sul principio di induzione, secondo cui:

(...) se $\mathcal{P}$ è una proprietà che vale per $k \in \mathbb{N}$, e se $\mathcal{P}(n) \Rightarrow \mathcal{P}(n+1)$ per ogni $n \ge k$, allora $\mathcal{P}$ vale $\forall n \in \mathbb N$ con $n \ge k$.
In simboli: \[(\forall P)[P(0) \land ( \forall k \in \mathbb{N}) (P(k) \Rightarrow P(k+1))] \Rightarrow ( \forall n \in \mathbb{N} ) [ P(n) ] \] dove $k$ e $n$ sono numeri naturali.

I passi su cui si basa la dimostrazione per induzione sono quindi:

1. si dimostra che vale $P(1)$ (o $P(0)$), cioè che 1 (o 0) è nel sottoinsieme dei numeri naturali $U$ per cui vale $P(n)$;
2. si assume come ipotesi che l'asserto $P(n)$ valga per un generico $n$ e da tale assunzione si dimostra che vale anche $P(n+1)$ (cioè che $n \in U \Rightarrow n+1 \in U$) e quindi si conclude che l'insieme $U$ dei numeri per cui vale $P(n)$ coincide con tutto l'insieme dei numeri naturali.

Ed è quindi possibile dimostrare la seguente affermazione: \[2^n \geq 2n\]

1. Per $n=1$, $2 \geq 2$; per $n=2$, $4 \geq 4$;
2. $2^{n+1} = 2 \cdot 2^n = 2^n + 2^n \geq 2n + 2n \geq 2n + 1$