1.15 Demostración por inducción y por contradicción (solo NS)

Comprobar que una fórmula funciona para n = 1, n = 2 y n = 3 no demuestra que funcione siempre: detrás del cuarto caso podría esconderse el primer fallo. Una demostración es un argumento que cierra todos los casos a la vez, sin excepción posible. El subtema TANS 1.15 presenta las tres herramientas que el IB exige dominar para construir y rebatir afirmaciones matemáticas: la inducción, la contradicción y el contraejemplo.

No son piezas decorativas. La inducción reaparece al demostrar el teorema de De Moivre con números complejos, al derivar la regla de potencias o al sumar progresiones; la contradicción es la única vía limpia para probar que ciertos números son irracionales; y el contraejemplo es el modo más económico de tumbar una conjetura. Saber cuál usar, y usarla con rigor, es una competencia transversal de Nivel Superior.

Demostración por inducción matemática

La idea: una escalera infinita

Imagina una escalera con infinitos peldaños. Si sabes dos cosas —que puedes subirte al primer peldaño, y que desde cualquier peldaño puedes alcanzar el siguiente— entonces puedes llegar a cualquier peldaño, por alto que esté. La inducción matemática formaliza ese razonamiento.

Inducción para sumar una progresión

Ejemplo 1 — suma de los primeros n números impares. Demuestra que 1 + 3 + 5 + ... + (2n − 1) = n² para todo entero n ≥ 1.

1. Caso base (n = 1). El lado izquierdo tiene un solo término: 2(1) − 1 = 1. El lado derecho es 1² = 1. Como 1 = 1, P(1) es cierta.
2. Hipótesis inductiva. Suponemos que para un entero k ≥ 1:   1 + 3 + ... + (2k − 1) = k².
3. Paso inductivo. Queremos probar P(k + 1), es decir, que 1 + 3 + ... + (2k − 1) + (2(k+1) − 1) = (k + 1)².
4. Partimos del lado izquierdo y aplicamos la hipótesis a los k primeros términos:
   [1 + 3 + ... + (2k − 1)] + (2(k+1) − 1) = k² + (2k + 2 − 1) = k² + 2k + 1.
5. Y k² + 2k + 1 = (k + 1)², que es exactamente el lado derecho de P(k + 1).
6. Conclusión. P(1) es cierta y P(k) ⇒ P(k + 1); por inducción, 1 + 3 + ... + (2n − 1) = n² para todo entero n ≥ 1. ∎

Inducción para una propiedad de divisibilidad

Ejemplo 2 — divisibilidad. Demuestra que 7ⁿ − 1 es divisible entre 6 para todo entero n ≥ 1.

1. Caso base (n = 1). 7¹ − 1 = 6, que es divisible entre 6 (es 6 · 1). P(1) es cierta.
2. Hipótesis inductiva. Suponemos que 7^k − 1 es divisible entre 6, es decir, 7^k − 1 = 6m para algún entero m. De aquí: 7^k = 6m + 1.
3. Paso inductivo. Estudiamos 7^k+1 − 1 y lo reescribimos usando la hipótesis:
   7^k+1 − 1 = 7 · 7^k − 1 = 7(6m + 1) − 1 = 42m + 7 − 1 = 42m + 6 = 6(7m + 1).
4. Como 7m + 1 es un entero, 7^k+1 − 1 = 6(7m + 1) es un múltiplo de 6. Luego P(k + 1) es cierta.
5. Conclusión. P(1) es cierta y P(k) ⇒ P(k + 1); por inducción, 7ⁿ − 1 es divisible entre 6 para todo entero n ≥ 1. ∎

Demostración por contradicción y contraejemplos

La estrategia indirecta

A veces atacar una afirmación de frente es inviable —no hay fórmula que manipular, no hay escalera que subir—. La demostración por contradicción (también llamada reducción al absurdo) ataca por la espalda: supone que la afirmación es falsa y deduce de esa suposición algo lógicamente imposible. Como una premisa correcta no puede llevar a un absurdo, la suposición debía ser errónea; por tanto, la afirmación original es verdadera.

La irracionalidad de √3

Ejemplo 3 — √3 es irracional. Demuestra que √3 no puede escribirse como cociente de dos enteros.

1. Suposición (negar la tesis). Supongamos lo contrario: que √3 es racional. Entonces √3 = p/q, donde p y q son enteros, q ≠ 0, y la fracción está en su forma irreducible (p y q sin factores comunes).
2. Elevamos al cuadrado: 3 = p²/q², de donde p² = 3q².
3. Luego p² es múltiplo de 3. Como 3 es primo, si 3 divide a p² entonces 3 divide a p. Escribimos p = 3a para algún entero a.
4. Sustituimos: (3a)² = 3q² → 9a² = 3q² → q² = 3a².
5. Luego q² es múltiplo de 3, y por el mismo argumento q también es múltiplo de 3.
6. Contradicción. Hemos deducido que 3 divide a la vez a p y a q. Pero habíamos supuesto que p/q era irreducible, sin factores comunes. Eso es imposible.
7. Conclusión. La suposición de que √3 es racional lleva al absurdo. Por tanto, √3 es irracional. ∎

Racional más irracional es irracional

Ejemplo 4 — suma de un racional y un irracional. Demuestra que, si r es racional y s es irracional, entonces r + s es irracional.

1. Suposición. Supongamos lo contrario: que r + s es racional. Llamémoslo t, así que t = r + s con t racional.
2. Despejamos s: s = t − r.
3. Ahora bien, t es racional y r es racional. La diferencia de dos números racionales es racional (si t = a/b y r = c/d, entonces t − r = (ad − cb)/(bd), de nuevo un cociente de enteros).
4. Luego s = t − r sería racional.
5. Contradicción. Pero el enunciado afirma que s es irracional. No puede ser racional e irracional a la vez.
6. Conclusión. La suposición de que r + s es racional es imposible. Por tanto, r + s es irracional. ∎

Infinitos números primos: la demostración de Euclides

Ejemplo 5 — hay infinitos primos. Demuestra que el conjunto de los números primos no tiene fin.

1. Suposición. Supongamos lo contrario: que solo hay una cantidad finita de primos. Podemos entonces listarlos todos: p₁, p₂, ..., p_k.
2. Construimos el número N = (p₁ · p₂ · ... · p_k) + 1, es decir, el producto de todos los primos de la lista más 1.
3. N es un entero mayor que 1, así que tiene al menos un divisor primo; llamémoslo q. Ese q debe estar en la lista, porque la lista contenía supuestamente todos los primos.
4. Pero q divide al producto p₁·p₂·...·p_k (es uno de sus factores) y, por hipótesis, q también divide a N. Si q divide a ambos, divide a su diferencia: N − (p₁·...·p_k) = 1.
5. Contradicción. Ningún número primo divide a 1 (los primos son ≥ 2). Es imposible que q divida a 1.
6. Conclusión. La suposición de que hay un número finito de primos lleva al absurdo. Por tanto, hay infinitos números primos. ∎

El contraejemplo: cómo tumbar una afirmación

Una afirmación universal del tipo "para todo n, P(n)" se demuestra verdadera con un argumento general (inducción, contradicción...), pero se demuestra falsa con un único contraejemplo: un caso concreto que cumple las hipótesis y no la conclusión.

Ejemplo 6 — refutar con un contraejemplo. Considera la afirmación: "para todo entero positivo n, el número n² − n + 11 es primo". Decide si es cierta.

1. Probamos valores pequeños: n = 1 da 1 − 1 + 11 = 11 (primo); n = 2 da 4 − 2 + 11 = 13 (primo); n = 3 da 9 − 3 + 11 = 17 (primo). La afirmación parece prometedora.
2. Pero la fórmula no puede dar siempre primos. Probamos n = 11:   11² − 11 + 11 = 121 − 11 + 11 = 121.
3. Justificación del contraejemplo. El valor 121 = 11 · 11 no es primo: tiene un divisor distinto de 1 y de sí mismo. Por tanto, n = 11 satisface la hipótesis (es un entero positivo) pero no la conclusión (n² − n + 11 no es primo).
4. Conclusión. La afirmación es falsa. El contraejemplo n = 11 basta para refutarla. ∎