Método de demostración de proposiciones que dependen de un número natural (denotadas mediante $P(n)$). Procede en tres pasos:
- Caso base: comprobar que $P$ se cumple para un primer elemento --usualmente 1 o 0;
- Hipótesis de inducción: suponer que $P(k)$ es cierta;
- Paso inductivo: Demostrar $P(k+1)$ bajo la hipótesis de inducción
Ejemplo:
$1+2+3+...+n=n(n+1)/2$ (esta proposición es $P(n)$)
- Caso base: $P(1)$ es cierta pues $1=1(1+1)/2$.
- Hipótesis de inducción: Suponemos cierto que $1+2+3+...+k=k(k+1)/2$ (esta proposición es $P(k)$)
- Paso inductivo: $1+2+3+...+k+k+1=k(k+1)/2+k+1$ (aquí hemos aplicado la hipótesis de inducción); ahora aplicamos las reglas del álgebra para obtener $$1/2[k^2+k+2k+2]=1/2[k^2+3k+2]=1/2[(k+1)(k+2)],$$ y $P(n)$ queda demostrada.