Suma de los n primeros enteros positivos

Demuestra que $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ para todo $n \ge 1$.

Caso base: comprueba $n = 1$: Lado izquierdo: $1$. Lado derecho: $\dfrac{1 \cdot 2}{2} = 1$ = $P(1)$ es verdadera

Hipótesis de inducción: supón $P(k)$ para algún $k \ge 1$: Supongamos que $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ = Podemos usar esta igualdad

Paso inductivo: suma el siguiente término $k+1$ a ambos lados: $1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ = $= \dfrac{(k+1)(k+2)}{2}$

Compara con $P(k+1)$: $P(k+1)$ dice que la suma es igual a $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ = $P(k+1)$ es verdadera

Answer: Por inducción, $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ para todo $n \ge 1$. Por ejemplo, $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$.

Suma de los n primeros números impares

Demuestra que $1 + 3 + 5 + \dots + (2n-1) = n^2$ para todo $n \ge 1$.

Caso base: comprueba $n = 1$: Lado izquierdo: $1$. Lado derecho: $1^2 = 1$ = $P(1)$ es verdadera

Hipótesis de inducción: Supongamos que $1 + 3 + \dots + (2k-1) = k^2$ para algún $k \ge 1$ = Podemos usar esta igualdad

Encuentra el siguiente número impar: El número impar después de $2k-1$ es $2(k+1) - 1 = 2k + 1$ = Sumamos $2k + 1$

Paso inductivo: $1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1$ = $= (k+1)^2$, así que $P(k+1)$ es verdadera

Answer: Por inducción, la suma de los $n$ primeros números impares es $n^2$. Comprobación: $1 + 3 + 5 + 7 + 9 = 25 = 5^2$.

Suma de potencias de 2

Demuestra que $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ para todo $n \ge 0$.

Caso base: aquí el primer valor es $n = 0$: Lado izquierdo: $2^0 = 1$. Lado derecho: $2^{1} - 1 = 1$ = $P(0)$ es verdadera

Hipótesis de inducción: Supongamos que $1 + 2 + \dots + 2^k = 2^{k+1} - 1$ para algún $k \ge 0$ = Podemos usar esta igualdad

Paso inductivo: suma el siguiente término $2^{k+1}$: $1 + 2 + \dots + 2^k + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1}$ = $= 2 \cdot 2^{k+1} - 1$

Simplifica y compara con $P(k+1)$: $2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 = 2^{(k+1)+1} - 1$ = $P(k+1)$ es verdadera

Answer: Por inducción, $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ para todo $n \ge 0$. Comprobación para $n = 6$: $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 2^7 - 1$.

Una demostración de divisibilidad

Demuestra que $n^3 - n$ es divisible entre $3$ para todo $n \ge 1$. (La lección Demostración directa lo probó factorizando; ahora usamos inducción.)

Caso base: comprueba $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$ = $P(1)$ es verdadera

Hipótesis de inducción: Supongamos que $k^3 - k = 3m$ para algún entero $m$ = $k^3 - k$ es múltiplo de $3$

Desarrolla la expresión para $k+1$: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$ = $= (k^3 - k) + 3k^2 + 3k$

Usa la hipótesis de inducción: $(k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k)$ = $= 3(m + k^2 + k)$

Concluye: $m + k^2 + k$ es un entero, así que la expresión es múltiplo de $3$ = $P(k+1)$ es verdadera

Answer: Por inducción, $3$ divide a $n^3 - n$ para todo $n \ge 1$. Comprobación para $n = 5$: $125 - 5 = 120 = 3 \cdot 40$.

Una desigualdad: 2 elevado a n es mayor que n

Demuestra que $2^n > n$ para todo $n \ge 1$.

Caso base: comprueba $n = 1$: $2^1 = 2$ y $2 > 1$ = $P(1)$ es verdadera

Hipótesis de inducción: Supongamos que $2^k > k$ para algún $k \ge 1$ = Podemos usar esta desigualdad

Escribe $2^{k+1}$ usando $2^k$: $2^{k+1} = 2 \cdot 2^k > 2 \cdot k$ = $2^{k+1} > 2k$

Compara $2k$ con $k+1$: $2k = k + k \ge k + 1$, porque $k \ge 1$ = $2k \ge k + 1$

Encadena las desigualdades: $2^{k+1} > 2k \ge k + 1$ = $2^{k+1} > k + 1$, así que $P(k+1)$ es verdadera

Answer: Por inducción, $2^n > n$ para todo $n \ge 1$. Por ejemplo, $2^{10} = 1024 > 10$.

Mistake: Saltarse el caso base

Why: El paso inductivo solo no demuestra nada: solo dice que SI cae una ficha, también cae la siguiente. Ejemplo: la afirmación falsa $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ tiene un paso inductivo que funciona, pero para $n = 1$ el lado izquierdo es $1$ y el derecho es $2$.

Correct: Comprueba siempre el primer caso de forma explícita. Sin una primera ficha que caiga, no cae nada.

Mistake: Suponer lo que quieres demostrar

Why: Escribir "supongamos que $P(n)$ es verdadera para todo $n$" o "supongamos $P(k+1)$" es un razonamiento circular: supone la conclusión.

Correct: Supón $P(k)$ para UN valor $k$ (la hipótesis de inducción) y demuestra $P(k+1)$ a partir de ella.

Mistake: Álgebra incorrecta en el paso inductivo

Why: Un despiste frecuente es sumar el término siguiente equivocado, por ejemplo $2k - 1$ en lugar de $2k + 1$ en la suma de impares, u olvidar sumar el nuevo término en un lado.

Correct: Escribe primero $P(k+1)$ completa (cambia cada $n$ por $k+1$) y después trabaja hasta llegar exactamente a esa expresión.

Mistake: Creer que comprobar muchos casos es una demostración

Why: La expresión $n^2 + n + 41$ da números primos para $n = 0, 1, \dots, 39$, pero para $n = 40$ da $1681 = 41^2$, que no es primo.

Correct: Los ejemplos ayudan a adivinar una fórmula. Solo el caso base junto con el paso inductivo la demuestran para todo $n$.

Verificar programas informáticos

Los programadores usan la inducción para demostrar que un bucle da la respuesta correcta tras cualquier número de vueltas: si es correcta tras $k$ vueltas, es correcta tras $k+1$ vueltas.

Un bucle suma $1, 2, 3, \dots$ a un total acumulado. La inducción demuestra que tras $n$ vueltas el total es $\dfrac{n(n+1)}{2}$.

Las Torres de Hanói

En este rompecabezas mueves una pila de discos a otra varilla, un disco cada vez, sin poner nunca un disco grande sobre uno más pequeño. La inducción demuestra que $n$ discos necesitan $2^n - 1$ movimientos.

Para mover $k+1$ discos, apartas los $k$ discos de arriba, mueves el disco más grande y vuelves a poner los $k$ discos encima: $2(2^k - 1) + 1 = 2^{k+1} - 1$ movimientos.

Granos de arroz en el tablero de ajedrez

Una antigua leyenda: pon $1$ grano de arroz en la primera casilla, $2$ en la segunda, $4$ en la tercera, duplicando cada vez. La suma de potencias de 2 te da el total.

En las $3$ primeras casillas hay $1 + 2 + 4 = 7 = 2^3 - 1$ granos.

Q: ¿Por qué la inducción demuestra de verdad la afirmación para TODO n?

A: El caso base da $P(1)$. El paso con $k = 1$ da $P(2)$, con $k = 2$ da $P(3)$, y así sucesivamente. Cada entero positivo se alcanza tras un número finito de pasos, así que ningún $n$ se queda fuera.

Q: ¿El caso base tiene que ser siempre n = 1?

A: No. Empieza en el primer valor a partir del cual debe cumplirse la afirmación. La suma de potencias de 2 empieza en $n = 0$. La afirmación $2^n > n^2$ es falsa para $n = 2, 3, 4$ (por ejemplo, $2^4 = 16 = 4^2$) y se cumple para todo $n \ge 5$, así que esa demostración usa el caso base $n = 5$.

Q: ¿La inducción matemática es lo mismo que el razonamiento inductivo de las ciencias?

A: No. El razonamiento inductivo adivina una regla general a partir de ejemplos y puede equivocarse. La inducción matemática es una demostración deductiva: una vez demostrados el caso base y el paso inductivo, el resultado es seguro.

Q: ¿Qué es la inducción fuerte?

A: En la inducción fuerte la hipótesis supone que $P(1), P(2), \dots, P(k)$ son todas verdaderas, no solo $P(k)$. Es útil cuando $P(k+1)$ depende de varios casos anteriores, por ejemplo en demostraciones sobre la descomposición en factores primos.