Usata per provare asserzioni con dominio $\mathbb Z ^+$ della forma $\forall n \space P(n)$
L’induzione matematica consiste di due passi:
base: la proposizione $P(1)$ è vera
passo di induzione: fissato un intero positivo $n$, l’implicazione $P(n) \rightarrow P(n+1)$ è vera
l’assunzione $P(n)$ è chiamata ipotesi induttiva
Si conclude perciò che $\forall n \space P(n)$
Esempio: provare che la somma dei primi $n$ interi positivi dispari è $n^2$, cioè $1+3+5+..+(2n-1)= n^2$
dim: $P(n): 1+3+5+..+(2n-1)=n^2$
base: $P(1): 1 = 1^2$ è vera
passo di induzione: supponiamo $P(n)$ vera e mostriamo che $P(n+1)$ è vera
$1+3+5+..+(2n-1)+(2n+1)= n^2 +(2n+1) = (n+1)^2$
Esempio: proviamo che $n<2^n$ per tutti gli interi positivi $n$
dim: $P(n): n<2^n$ per ogni intero $n \geq 1$
Esempio: proviamo che $n^3 - n$ è divisibile per $3$ per ogni intero positivo $n$
dim: $P(n) : n^3-n$ è divisibile per $3$ per ogni intero $n \geq 1$