Inicio · Parte 04 — Matemática discreta para computación

091 — Inducción matemática

intermedio clase 11 de 20 4 horas demostración induction

La inducción demuestra infinitos casos con un caso base y un paso que hereda la propiedad.

Fórmulas

base: P(1) es cierta
paso: P(k) ⟹ P(k+1)
conclusión: P(n) para todo n ≥ 1

Desarrollo

La inducción resuelve un problema que parece imposible: demostrar algo sobre infinitos números en dos pasos. El caso base establece que la propiedad vale en el primer valor; el paso inductivo demuestra que si vale en k, entonces vale en k+1. La combinación de ambos hace caer todas las fichas de dominó.

La analogía con un bucle es exacta: el caso base es la inicialización y el paso inductivo es el invariante que se mantiene en cada iteración. Demostrar la corrección de un bucle es demostrar por inducción que su invariante se preserva, y esa es la base de la verificación formal de programas.

El paso inductivo es donde vive la demostración, y su estructura es siempre la misma: escribir P(k+1), identificar dentro de ella la parte que es P(k), aplicar la hipótesis y simplificar. Para la suma de Gauss: S(k+1) = S(k) + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, que es exactamente la fórmula con k+1.

Es importante no confundir inducción con verificación. Comprobar los primeros 50 casos no demuestra nada, como la clase 019 mostró con el polinomio de Euler. La verificación empírica es un control de sanidad previo a la demostración, no un sustituto.

Ejemplo trabajado

Demostrar la suma de Gauss por inducción.

Proposición: 1 + 2 + ... + n = n(n+1)/2

Caso base (n=1):
  izquierda = 1
  derecha   = 1·2/2 = 1              ✓

Paso inductivo: suponemos S(k) = k(k+1)/2
  S(k+1) = S(k) + (k+1)
         = k(k+1)/2 + (k+1)
         = (k+1)(k/2 + 1)
         = (k+1)(k+2)/2              ✓ es la fórmula con k+1

Verificación empírica (control de sanidad):
  50 valores comprobados, 0 contraejemplos
  → NO es la demostración, es una comprobación previa

Qué calcula el laboratorio

Inducción: caso base, paso inductivo y verificación empírica.

python classes/part-04-matematica-discreta-para-computacion/091-induccion-matematica/lab.py
compmath run 091

Salidas del laboratorio (6)

proposicion
caso_base_n=1
paso_inductivo
verificado_hasta
contraejemplos
la_verificacion_no_es_demostracion

Muestra de la ejecución real

{
  "proposicion": "1+2+…+n = n(n+1)/2",
  "caso_base_n=1": true,
  "paso_inductivo": "S(k)+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2",
  "verificado_hasta": 50,
  "contraejemplos": [],
  "la_verificacion_no_es_demostracion": true
}

Errores comunes

Omitir el caso base: sin él, el paso inductivo no arranca.
Usar la conclusión como hipótesis dentro del paso inductivo.
Confundir verificar los primeros n casos con demostrar.

Dónde se usa

Corrección de algoritmos recursivos, invariantes de bucle, análisis de estructuras de datos y demostración de cotas de complejidad.

Idea rectora de la parte

Una demostración por inducción es un bucle `for` con garantía.

Error a evitar

Confundir implicación con equivalencia lógica.

Conexión con IA

Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.

Bibliografía de la clase

Velleman, D. How to Prove It, 3ª ed., Cambridge, 2019, cap. 6 — Lógica y demostración: el tema de esta clase · ISBN-13 9781108539890 verificado en International ISBN Agency (2026-08-19).
Gries, D. The Science of Programming. Springer, 1981 — Lógica y demostración: el tema de esta clase · ISBN-13 9781461259831 verificado en International ISBN Agency (2026-08-19).

Archivos de la clase

← 090 Principio del palomar 092 Recurrencias →