La inducción matemática es un método de demostración que generalmente se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones. El método es bastante natural para usarse en una variedad de situaciones en ciencias de la computación. Algunas aplicaciones tienen un sabor muy matemático, tal como verificar que todo entero positivo satisface cierta formula. Otra utilización frecuente es la de mostrar que un programa de computación o que un algoritmo con ciclos funciona como se espera.

Primer principio de inducción matemática
Sea m un entero y sea p(n) un predicado de un argumento sobre el universo de discurso {n ∈Z:n ≥m}.
(B) p(m)
(I) ∀n≥m [p(n) → p(n + 1)] .
∀n≥m p(n)

En el paso inductivo (I), cada proposición es verdadera siempre que la proposición inmediatamente anterior sea verdadera. Para utilizar este principio como marco de una demostración constructiva, necesitamos revisar que p(m) es verdadera y que cada proposición constructiva es verdadera suponiendo que la proposición inmediatamente anterior es verdadera. Es este privilegio de suponer el caso inmediatamente anterior es lo que hace que el método de demostración por inducción sea tan poderoso. Resulta que de hecho está permitido suponer todos los casos anteriores. Esta afirmación aparentemente más fuerte es una consecuencia del siguiente principio cuya demostración discutimos al final de esta sección.

Segundo principio de inducción matemática
Sea m un entero y sea p(n) un predicado de un argumento sobre el universo de discurso {n ∈ Z: n≥ m}.
(B) p(m)
(I) ∀n≥m [p(n) → p(n + 1)] .
∀n≥m p(n)
Las primeras tres implicaciones en (I) correspondientes a n= m + 1, m + 2 y m + 3, son
p(m) → p(m + 1)
p(m) ᴧ p(m +1) → p(m+2)
p(m) ᴧ p(m + 1) ᴧ p(m + 2) →p(m + 3)

Para verificar (I) en general debemos considerar una n > m y suponer que las proposiciones p(k) son verdaderas para m ≤ k < n y mostramos que p(n) es verdadera. El segundo principio de inducción matemática es la versión apropiada para utilizarse cuando la veracidad de las proposiciones se sigue predecesores distintos de los predecesores inmediatos.

Ejemplo

Todo entero n ≥ 2 puede escribirse como un producto de primos.
Demostración: nótese que si n es primo el “producto de primos” es el primo mismo. Para n ≥ 2 sea p(n) la proposición. (“n puede escribirse como producto de primos”)