Inducción matemática

Método de demostración de proposiciones que dependen de un número natural (denotadas mediante $P(n)$). Procede en tres pasos:

1. Caso base: comprobar que $P$ se cumple para un primer elemento --usualmente 1 o 0;
2.  Hipótesis de inducción: suponer que $P(k)$ es cierta;
3. 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.