Demostración por inducción

Elige una afirmación sobre todos los números enteros n. Cada dominó de abajo representa una n y su color indica si la afirmación es cierta en ese punto tras comprobarla directamente. La flecha que sale de un dominó es el paso inductivo de n a n + 1. Solo un dominó base verdadero seguido de una cadena ininterrumpida de flechas constituye una demostración, y los dominós que alcance esa cadena caerán.

Ejemplo resuelto — Demostración por inducción

Paso de 1 a 2	falla
Demostrado, para n hasta 12	1
Primer n falso, hasta 12	2

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Demostración por inducción

La demostración por inducción demuestra un enunciado P(n) para cada número entero n a partir de algún n₀, en dos partes: el caso base, donde se comprueba P(n₀) directamente, y el paso inductivo, un argumento en el que P(k) fuerza P(k + 1) para cada k ≥ n₀. Juntos alcanzan cada n, al igual que cada dominó que cae derriba al siguiente.

Qué significa cada símbolo

P(n): el enunciado sobre n; en cada n es simplemente verdadero o falso
n₀: el caso base, donde comienza la demostración, comprobado a mano
k: una n general dentro del paso: el argumento asume P(k) y debe llegar a P(k + 1)

De dónde viene la fórmula

Por qué las dos partes son suficientes. Supongamos que el caso base se cumple y el paso funciona para cualquier k ≥ n₀, pero P es falsa en algún lugar a partir de n₀. Entre las n donde es falsa hay una que es la menor; llamémosla m. No es n₀, porque ya comprobaste P(n₀), así que m − 1 ≥ n₀, y P(m − 1) es verdadera porque m era el menor fallo. El paso entonces te da P(m), lo cual contradice que P(m) sea falsa. Por tanto, no hay ningún fallo. Ambas partes son necesarias: sin la base, m podría ser n₀; si el paso falta en un solo k, m podría ser k + 1.
Por qué n² + n + 41 tenía que fallar. En n = 40 los dos primeros términos se combinan, 40² + 40 = 40 × 41, así que 40² + 40 + 41 = 40 × 41 + 41 = 41 × 41. En n = 41 cada término es un múltiplo de 41 y el valor es 41 × 43. La idea va más allá: ningún polinomio con coeficientes enteros que no sea constante puede dar únicamente primos, sin importar cuántos dé al principio (Lehman, Leighton y Meyer lo demuestran en el Problema 1.25). Por lo que nunca podría haber existido un paso inductivo para esta afirmación.
2ⁿ > n² para todo n ≥ 5, hecho correctamente. Caso base: 2⁵ = 32 > 25 = 5². Paso: sea k ≥ 5 y supongamos que 2ᵏ > k². Entonces 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k². Dado que k ≥ 5, k² ≥ 5k = 2k + 3k > 2k + 1, así que 2k² > k² + 2k + 1 = (k + 1)², y 2ᵏ⁺¹ > (k + 1)², que es P(k + 1). El paso en sí solo necesita que k ≥ 3. La base tenía que ser 5 porque P(2), P(3) y P(4) son falsas.

Cuarenta casos verdaderos, luego 41 × 41 🖖

Pulsa n² + n + 41. Los valores 41, 43, 47, 53, 61, … son primos para cualquier n del 0 al 39, cuarenta seguidos, y en n = 40 el valor es 1.681 = 41 × 41. Puedes preverlo en cuanto lo analizas: 40² + 40 + 41 = 40 × 41 + 41. El gráfico no tiene flechas porque no hay paso. Saber que p(39) = 1.601 es primo no dice nada sobre p(40), que es p(39) + 80. De los primeros mil valores 581 son primos, razón por la cual el patrón resulta tan convincente.

El paso para 2ⁿ > n² funciona desde k = 3; la afirmación solo desde n = 5 🖖

Pulsa 2ⁿ > n² desde 1. El caso base se cumple, ya que 2 > 1. El paso dice que si 2ᵏ > k², entonces 2ᵏ⁺¹ > 2k², y 2k² ≥ (k + 1)² exactamente cuando k² ≥ 2k + 1, lo cual es cierto desde k = 3. Así que desde n₀ = 1 las flechas que salen del 1 y del 2 están rotas, y la afirmación es falsa en 2, 3 y 4. Las flechas que salen del 3 y del 4 funcionan mientras que P(3) y P(4) son ambas falsas: un paso correcto con un dominó falso detrás no empuja nada. Pulsa 2ⁿ > n² desde 5 y las mismas flechas demuestran cada n de 5 en adelante.

El argumento de los caballos es correcto en todos los pasos excepto en uno 🖖

Pulsa Los caballos. El paso toma n + 1 caballos, aplica la afirmación a los primeros n y a los últimos n, y los une a través de los caballos que comparten ambos grupos. Desde n = 2 en adelante eso funciona, y cada flecha a partir del 2 es sólida. Del 1 al 2 los grupos son de un caballo cada uno y no comparten ninguno, así que el argumento no demuestra nada en el único lugar donde hace falta. Pon la base en el 5 y cada paso funciona, pero P(5) es falsa y la cadena no tiene nada que empujar.

Problema resuelto al detalle

¿A partir de qué valor 2ⁿ se mantiene por encima de n³? 4 pasos
Demuestra que 2ⁿ > n³ para cualquier n lo bastante grande. El paso es fácil de escribir. ¿Dónde empieza a funcionar y dónde debe estar el caso base?

Abre este problema en la herramienta
1. Supongamos P(k): 2ᵏ > k³. Duplicar es el único movimiento disponible:
  
  $2^{k} > k^{3} \Rightarrow 2^{k + 1} = 2 \cdot 2^{k} > 2 k^{3}$
2. Así que el paso funciona cuando 2k³ ≥ (k + 1)³. Divide ambos lados entre k³:
  
  $2 k^{3} \geq (k + 1)^{3} ⟺ (1 + \frac{1}{k})^{3} \leq 2 ⟺ k \geq \frac{1}{3 2 - 1} = 3.847$
3. El paso funciona desde k = 4, no desde 3:
  
  $k = 3 : 2 \cdot 27 = 54 < 64 = 4^{3}, k = 4 : 2 \cdot 64 = 128 \geq 125 = 5^{3}$
4. Pero la afirmación en sí es falsa desde n = 2 hasta n = 9. El caso base es la primera n donde vuelve a cumplirse:
  
  $2^{9} = 512 < 729 = 9^{3}, 2^{10} = 1, 024 > 1, 000 = 1 0^{3}$
Respuesta

2ⁿ > n³ se cumple para todo n ≥ 10, y en n = 0 y 1. El paso funciona desde k = 4, así que para k del 4 al 9 un paso correcto se apoya en una afirmación falsa, al igual que hace 2ⁿ > n² en el 3 y el 4 de esta página. Pulsa 2ⁿ > n² desde 5 para comparar.

$2^{n} > n^{3} for every n \geq 10 (and n = 0, 1); step from k = 4, base n_{0} = 10$

Ruta de aprendizaje

Métodos de demostración

Referencias (3)

Both of this page's broken arguments, worked through: n² + n + 41 prime through n = 39 and 41·41 at n = 40 (§1.1), and the horses, whose failure the text pins to the one step P(1) → P(2) (§5.1): E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §1.1 and §5.1.
The primes n² + n + 41 takes, with the forty consecutive prime values from n = 0 to 39: OEIS Foundation, "A005846: Primes of the form k² + k + 41", The On-Line Encyclopedia of Integer Sequences.
Where the horses come from: George Pólya posed the argument as an induction exercise in 1954: ProofWiki, "All Horses are the Same Colour/Historical Note", citing G. Pólya, Induction and Analogy in Mathematics (Princeton University Press, 1954).

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.