Inducción Matemática
La inducción matemática es una técnica de demostración para enunciados sobre todos los números naturales, que funciona demostrando un caso base y un paso inductivo.
Formula
\text{Prove } P(1); \text{ prove } P(k) \text{ implies } P(k+1)
Definition
La inducción matemática es un método de demostración para mostrar que algo es verdadero para todo número natural; tiene dos pasos: mostrar que es verdadero para el primer caso, luego mostrar que si es verdadero para un número, debe ser verdadero para el siguiente. Formalmente, para demostrar $P(n)$ para todo $n \ge n_0$: demuestra el caso base $P(n_0)$, luego asume $P(k)$ (la hipótesis inductiva) y demuestra $P(k+1)$. Esto es equivalente al principio de buen orden de $\mathbb{N}$ (todo subconjunto no vacío tiene un elemento mínimo) y al quinto axioma de Peano; la inducción transfinita extiende la técnica a los ordinales, añadiendo un caso límite donde que $P$ se cumpla para todo $\beta < \lambda$ implica $P(\lambda)$.
Example
Para demostrar que los primeros $n$ enteros positivos suman $n(n+1)/2$: el caso base $n=1$ da $1 = 1(2)/2 = 1$, y el paso inductivo asume que se cumple para $k$, suma $(k+1)$ a ambos lados, y simplifica para mostrar que se cumple para $k+1$. Para demostrar $2^n > n$ para $n \ge 1$: caso base $2^1 = 2 > 1$, y suponiendo $2^k > k$, entonces $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$. La inducción transfinita demuestra el teorema de Cantor-Bendixson, que todo subconjunto cerrado de $\mathbb{R}$ es la unión de un conjunto perfecto y un conjunto numerable, procediendo a través de etapas ordinales de eliminación de puntos aislados.
Key Insight
Piensa en fichas de dominó: demuestra que la primera cae (caso base), y demuestra que cada ficha que cae derriba a la siguiente (paso inductivo), entonces todas las fichas caen. La inducción es razonamiento deductivo, no inductivo, ya que usas una cadena de implicaciones demostrada en lugar de adivinar patrones; el nombre es históricamente desafortunado. La inducción estructural en ciencias de la computación demuestra propiedades de estructuras de datos recursivas (árboles, listas) usando el mismo principio aplicado a la estructura recursiva en lugar de a los números naturales.