Un esquema de prueba que establece una propiedad para todos los números naturales demostrando un caso base (habitualmente para 0 o 1) y un paso inductivo que muestra: si la propiedad se cumple para un n arbitrario entonces se cumple para n+1.

Principio

Transferencia local a global en N: la regla organizadora es que verificar una base y el cierre por sucesor es suficiente para propagar una propiedad a cada número natural mediante la aplicación repetida del paso inductivo.

Demostración

Para probar una fórmula P(n) para todo n∈N, muestre que P(0) es verdadera y que para un n arbitrario se cumple P(n) ⇒ P(n+1). Por ejemplo, probar por inducción que la suma de los primeros n naturales es n(n+1)/2 comprobando el caso base n=0 y el paso inductivo algebraico.

Aplicación incorrecta

Usar inducción ordinaria cuando el paso inductivo requiere suposiciones sobre varios valores menores (es decir, usar sólo P(n)⇒P(n+1) cuando la hipótesis correcta necesita conocer todos los k≤n), o no establecer un caso base válido para el dominio previsto.

Consecuencia

Proporciona un método canónico para demostrar infinitas afirmaciones con trabajo finito; subyace en definiciones recursivas, pruebas de corrección de algoritmos sobre enteros y provee una base para propiedades aritméticas.

Inversión

La inversión es mostrar que incluso con un caso base y un paso inductivo aparente la propiedad puede fallar si el paso o la base están mal; omitir el caso base o usar una regla de sucesor no estándar rompe la propagación a todos los naturales.

Límite

Se aplica a dominios bien ordenados basados en sucesor como N; no se aplica directamente a estructuras sin un sucesor claro ni a pruebas que requieren inducción transfinitas o estructurales sin la adaptación correspondiente.

Tensión semántica

Tensión con la inducción fuerte o estructural: la inducción ordinaria supone una implicación de un solo paso por sucesor, mientras que las formas fuertes o estructurales permiten premisas sobre todos los casos menores o inducen sobre la estructura en lugar del sucesor numérico.

Síntesis

La inducción matemática es la verificación finita en dos fases (caso base y paso de sucesor) que propaga la verdad a través de los números naturales, siendo el dispositivo principal para demostrar identidades aritméticas, corrección de algoritmos enteros y propiedades definidas recursivamente.