Inducción matemática
“La inducción es el truco de derribar infinitas fichas de dominó con solo dos comprobaciones.”
La fórmula
[ P(1) ∧ ( P(k) ⟹ P(k+1) ) ] ⟹ ∀n ≥ 1, P(n)Cómo leerla: si el primer caso es verdadero y que cada caso sea verdadero obliga al siguiente, entonces el enunciado es verdadero para todo número natural
- P(n)
- — el enunciado que se debe probar para un número natural n
- P(1)
- — el caso base—tirar la primera ficha de dominó
- P(k) ⟹ P(k+1)
- — el paso inductivo—cada ficha tira a la siguiente
- ∀n ≥ 1
- — por lo tanto se cumple para todos los números naturales
El gancho
Demuestra infinitos casos en solo dos líneas—tira la primera ficha de dominó, muestra que cada ficha derriba a la siguiente, y listo.
En palabras simples
La inducción matemática demuestra enunciados verdaderos 'para todo número natural n'. (1) Muestra que se cumple en n=1 (la base), y (2) muestra que si se cumple en n=k debe cumplirse en n=k+1 (el paso); como fichas de dominó, todas caen.
La intuición
Imagina una fila interminable de fichas de dominó. No puedes derribar cada una a mano. Pero solo necesitas comprobar dos cosas—la primera cae, y 'siempre que una ficha cae, su vecina también cae'. Entonces la primera derriba a la segunda, la segunda a la tercera… para siempre, así que todas caen. El infinito se conquista con dos comprobaciones finitas.
Cómo se construye
Dos partes—el caso base y el paso inductivo. La base comprueba directamente que el punto de partida (usualmente n=1) se cumple. El paso usa la hipótesis inductiva 'P(k) es verdadero' para derivar P(k+1). Necesitas ambos: sin la primera ficha nada cae, y sin la cadena solo cae una.
Ejemplo
Demuestra 1+2+⋯+n = n(n+1)/2. Base n=1: el lado izquierdo es 1 = 1·2/2 = 1 ✓. Paso: supón 1+⋯+k = k(k+1)/2, entonces 1+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, que coincide con la fórmula en n=k+1 ✓. Así que se cumple para todo n.
Error común
La hipótesis inductiva 'supón que P(k) es verdadero' parece razonamiento circular—asumir lo que quieres probar—pero no lo es. No estás afirmando que P(k) sea realmente verdadero; solo estás probando el vínculo condicional 'si es verdadero, también lo es el siguiente' (el hueco entre fichas de dominó).
Dónde se usa
Probar fórmulas de sumas y desigualdades, verificar la corrección de algoritmos (recursión y bucles), probar la corrección de estructuras de datos y compiladores, incontables teoremas en teoría de números y combinatoria—está en todas partes donde aparecen casos infinitos en matemáticas e informática.
De dónde viene
Pascal la usó explícitamente en el siglo XVII trabajando con el triángulo de Pascal, y en el siglo XIX Peano la incorporó a los axiomas de los números naturales, convirtiéndola en un pilar de la lógica.
Requisitos previos
Comprobación rápida
Además del caso base, ¿qué debes probar en la inducción matemática?
- que si P(k) es verdadero entonces P(k+1) es verdadero✓
- que P(n) es verdadero para algún n grande
- que P(n) nunca es falso
- no se necesita nada más
Práctica
Usa la fórmula 1+2+⋯+n = n(n+1)/2 para calcular 1+2+⋯+10.
Respuesta: 55
- sustituye n=10: 10·11/2
- = 110/2 = 55
Idea clave: Una vez que la inducción prueba una fórmula, solo sustituyes.
Calcula 1+2+⋯+100.
Respuesta: 5050
- 100·101/2
- = 10100/2 = 5050
Idea clave: La misma suma que, según cuenta la historia, el joven Gauss resolvió en segundos.
La suma de los primeros n números impares es 1+3+5+⋯+(2n−1) = n². Halla su valor para n=5.
Respuesta: 25
- 1+3+5+7+9 = 25
- = 5² = 25
Idea clave: Los números impares suman un cuadrado perfecto—un ejemplo clásico de inducción.
Demuestra 1+2+⋯+n = n(n+1)/2 por inducción (escribe la base y el paso inductivo).
Respuesta: undefined
- base n=1: 1 = 1·2/2 = 1 ✓
- supón: 1+⋯+k = k(k+1)/2
- suma (k+1): k(k+1)/2 + (k+1) = (k+1)(k+2)/2, la fórmula en n=k+1 ✓
Idea clave: Base + paso = una prueba completa para infinitos casos.