Demostración por Inducción Matemática
Introducción
Imagina una fila infinita de fichas de dominó. Si sabes que al caer una ficha, derriba a la siguiente, y además derribas la primera ficha, ¿qué sucede? Todas caen. Este es el principio de la inducción matemática, una técnica de demostración extraordinariamente poderosa que permite probar proposiciones sobre todos los números naturales, aunque sean infinitos.
¿Qué es la Inducción Matemática?
La inducción matemática es un método de demostración para probar que una proposición P(n) es verdadera para todos los números naturales n ≥ n₀ (generalmente n₀ = 1 o n₀ = 0).
El Principio de Inducción
El método se basa en dos pasos:
Paso 1: Caso Base
Demostrar que la proposición es verdadera para el primer valor, P(n₀).
"Derribamos la primera ficha de dominó."
Paso 2: Paso Inductivo
Demostrar que si la proposición es verdadera para un natural arbitrario k, entonces también es verdadera para k + 1.
"Si una ficha cae, entonces la siguiente también cae."
En símbolos: P(k) → P(k+1)
¿Por qué Funciona?
Si ambos pasos se cumplen:
- P(n₀) es verdadero (caso base)
- P(n₀) → P(n₀+1), por lo tanto P(n₀+1) es verdadero
- P(n₀+1) → P(n₀+2), por lo tanto P(n₀+2) es verdadero
- ... y así sucesivamente para todos los naturales
Terminología Importante
- Caso base: La verificación inicial para n₀
- Hipótesis de inducción: Suponer que P(k) es verdadero para algún k ≥ n₀
- Tesis inductiva: Demostrar que P(k+1) es verdadero
- Paso inductivo: La demostración de P(k) → P(k+1)
Ejemplo 1: Suma de los Primeros n Naturales
Teorema: Para todo n ≥ 1:
1 + 2 + 3 + ... + n = n(n+1)/2
Demostración por Inducción:
Caso Base (n = 1):
- Lado izquierdo: 1
- Lado derecho: 1(1+1)/2 = 2/2 = 1
✓ Ambos lados son iguales.
Paso Inductivo:
Hipótesis de inducción: Supongamos que la fórmula es verdadera para n = k:
1 + 2 + 3 + ... + k = k(k+1)/2
Tesis: Debemos probar que es verdadera para n = k + 1:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2
Demostración:
Partimos del lado izquierdo:
1 + 2 + 3 + ... + k + (k+1)
Aplicamos la hipótesis de inducción:
= k(k+1)/2 + (k+1)
Factorizamos (k+1):
= (k+1)[k/2 + 1] = (k+1)[(k + 2)/2] = (k+1)(k+2)/2
Que es exactamente lo que queríamos demostrar. ∎
Ejemplo 2: Desigualdad con Potencias
Teorema: Para todo n ≥ 5: 2ⁿ > n²
Demostración por Inducción:
Caso Base (n = 5):
- 2⁵ = 32
- 5² = 25
- 32 > 25 ✓
Paso Inductivo:
Hipótesis: 2ᵏ > k² para algún k ≥ 5
Tesis: 2ᵏ⁺¹ > (k+1)²
Demostración:
2ᵏ⁺¹ = 2 · 2ᵏ > 2k² (por la hipótesis)
Necesitamos mostrar que 2k² > (k+1)² para k ≥ 5.
2k² - (k+1)² = 2k² - k² - 2k - 1 = k² - 2k - 1
Para k ≥ 5: k² - 2k - 1 = k(k-2) - 1 ≥ 5(3) - 1 = 14 > 0
Por lo tanto, 2k² > (k+1)², y entonces:
2ᵏ⁺¹ > 2k² > (k+1)² ∎
Ejemplo 3: Suma de Cuadrados
Teorema: Para todo n ≥ 1:
1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6
Caso Base (n = 1):
- Izquierda: 1² = 1
- Derecha: 1(2)(3)/6 = 6/6 = 1 ✓
Paso Inductivo:
Hipótesis: 1² + 2² + ... + k² = k(k+1)(2k+1)/6
Tesis: 1² + 2² + ... + k² + (k+1)² = (k+1)(k+2)(2k+3)/6
Demostración:
1² + 2² + ... + k² + (k+1)² = k(k+1)(2k+1)/6 + (k+1)² = (k+1)[k(2k+1)/6 + (k+1)] = (k+1)[(2k² + k + 6k + 6)/6] = (k+1)(2k² + 7k + 6)/6 = (k+1)(2k + 3)(k + 2)/6 = (k+1)(k+2)(2k+3)/6 ∎
Variantes de la Inducción
Inducción Fuerte (o Completa)
En lugar de suponer solo P(k), suponemos P(n₀), P(n₀+1), ..., P(k) (todos los casos anteriores).
Útil cuando P(k+1) depende de varios valores anteriores, no solo del inmediato anterior.
Inducción hacia Atrás
Se usa para demostrar propiedades de conjuntos finitos, comenzando desde un caso grande y descendiendo.
Errores Comunes
- Olvidar el caso base: Sin él, la cadena nunca comienza
- No usar la hipótesis de inducción: Hay que aplicarla explícitamente
- Comenzar desde el valor equivocado: Verificar desde qué n₀ vale la propiedad
- Confundir la hipótesis con la tesis: Son proposiciones diferentes
Consejos Prácticos
- Siempre verifica el caso base primero
- Escribe claramente la hipótesis y la tesis
- Manipula la expresión para P(k+1) hasta que aparezca la forma de P(k)
- Aplica la hipótesis de inducción
- Simplifica hasta obtener lo deseado