Guía de Estudio: El Principio de Inducción

Tema: Inducción Matemática (Estándar)

Definición inicial

La inducción matemática es un método de demostración que se utiliza para probar que una propiedad es verdadera para todos los números naturales (o para un conjunto infinito de números). Es una herramienta fundamental para demostrar que una afirmación se cumple universalmente.

Explicación didáctica

Imagina una fila infinita de fichas de dominó puestas una detrás de la otra. ¿Cómo podrías probar que todas las fichas van a caer si empujas la primera? No puedes empujarlas y verlas caer una por una, porque son infinitas.

En lugar de eso, solo necesitas probar dos cosas:

1. Que puedes derribar la primera ficha (esto se llama el Caso Base).
2. Que las fichas están lo suficientemente cerca como para que, si cualquier ficha (llamémosla la ficha “n”) cae, garantiza que la siguiente (la “n+1”) también caerá (esto es el Paso Inductivo).

Si logras probar esos dos puntos, has demostrado que la fila entera caerá. La inducción funciona igual: pruebas el primer caso (usualmente $n=0$ o $n=1$) y luego pruebas que la veracidad de un caso cualquiera $n$ implica la veracidad del caso $n+1$.

Definición formal

Sea $P$ una propiedad sobre los números naturales. Si se cumplen las siguientes dos condiciones:

1. Caso Base: $P$ se cumple para 0 (es decir, $P(0)$ es verdadero).
2. Caso Inductivo: Si $P$ se cumple para un número natural $n$ (esta suposición se llama “Hipótesis de Inducción”), entonces $P$ también se cumple para $n+1$ (es decir, $P(n) \Rightarrow P(n+1)$).

Si ambas condiciones son verdaderas, entonces se concluye que $P$ se satisface para todos los números naturales.

Ejemplo resuelto

Demostremos usando inducción que $2^{2n} - 1$ es divisible por 3 para todo $n \in \mathbb{N}$.

• Propiedad P(n): $2^{2n} - 1$ es divisible por 3.

• 1. Caso Base (n=0): Debemos verificar si $P(0)$ es verdadero. $2^{2 \cdot 0} - 1 = 2^0 - 1 = 1 - 1 = 0$. ¿Es 0 divisible por 3? Sí, porque $0 = 0 \cdot 3$. El caso base se cumple.

• 2. Paso Inductivo: Debemos probar que $P(n) \Rightarrow P(n+1)$.

  • Hipótesis de Inducción (P(n)): Asumimos que $P(n)$ es verdadero. Es decir, asumimos que $2^{2n} - 1$ es divisible por 3.

  • Esto significa que existe un número natural $k$ tal que $2^{2n} - 1 = 3k$.

  • Tesis (P(n+1)): Queremos demostrar que $P(n+1)$ es verdadero. Es decir, que $2^{2(n+1)} - 1$ es divisible por 3.

  • Demostración:

  • Demostración:

Comenzamos desarrollando la expresión de $P(n+1)$:

$$2^{2(n+1)} - 1 = 2^{2n+2} - 1 = 2^2 \cdot 2^{2n} - 1 = 4 \cdot 2^{2n} - 1$$

Ahora, necesitamos usar nuestra hipótesis ($2^{2n} - 1$). El truco es reescribir la expresión para que esa parte aparezca. Podemos separar $4 \cdot 2^{2n}$ en $3 \cdot 2^{2n} + 1 \cdot 2^{2n}$:

$$4 \cdot 2^{2n} - 1 = (3 \cdot 2^{2n} + 2^{2n}) - 1$$

Reagrupando, obtenemos:

$$3 \cdot 2^{2n} + (2^{2n} - 1)$$

Ahora podemos sustituir nuestra Hipótesis de Inducción ($2^{2n} - 1 = 3k$):

$$3 \cdot 2^{2n} + 3k$$

Finalmente, factorizamos el 3:

$$3 \cdot (2^{2n} + k)$$

Hemos demostrado que $2^{2(n+1)} - 1$ es igual a 3 multiplicado por otro número natural [$k' = 2^{2n} + k$]. Por lo tanto, $2^{2(n+1)} - 1$ es divisible por 3.

Como el Caso Base y el Paso Inductivo son verdaderos, concluimos que $2^{2n} - 1$ es divisible por 3 para todos los números naturales.

Resumen rápido

La inducción es una prueba en dos pasos: se demuestra el primer caso (base) y luego se demuestra la “conexión en cadena” (paso inductivo) que garantiza que si un caso $n$ es verdadero, el siguiente $n+1$ también lo será. Esto es suficiente para probar que la propiedad se cumple para todos los números.

---

Tema: Fortalecimiento de la Hipótesis de Inducción

Definición inicial

A veces, al intentar probar una afirmación por inducción, el paso inductivo falla. “Fortalecer la hipótesis” es una técnica paradójica donde, en lugar de probar la afirmación original, probamos una afirmación más fuerte o más específica. Esta nueva afirmación nos da una Hipótesis de Inducción más poderosa que, irónicamente, hace que la prueba sea más fácil de completar.

Explicación didáctica

Imagina que quieres probar por inducción que puedes subir una escalera infinita (P(n) = “puedo llegar al escalón n”). Tu paso inductivo (P(n) -> P(n+1)) falla porque no tienes suficiente equilibrio.

La solución podría ser probar una afirmación más fuerte: P’(n) = “puedo llegar al escalón $n$ y mantenerme perfectamente equilibrado”. Probar P’ es más difícil en el caso base (no solo llegas al primer escalón, sino que lo haces con equilibrio). Sin embargo, tu nueva hipótesis de inducción (asumir P’(n)) es mucho más útil. Como asumes que llegaste al escalón $n$ con equilibrio, es mucho más fácil demostrar que puedes subir al escalón $n+1$ y mantener ese equilibrio.

Probar una afirmación más fuerte nos da una hipótesis de inducción más fuerte, lo que puede hacer que un paso inductivo que antes era imposible, ahora funcione.

Definición formal

Si una demostración inductiva para una propiedad $P(n)$ falla en el paso inductivo, podemos intentar definir una nueva propiedad $P'(n)$ tal que $P'(n)$ implica $P(n)$ (es decir, $P'$ es más fuerte que $P$). Luego, intentamos demostrar $P'(n)$ para todo $n$ usando inducción. El objetivo es que la hipótesis de inducción $P'(n)$ sea lo suficientemente fuerte como para implicar $P'(n+1)$, aunque $P(n)$ no fuera suficiente para implicar $P(n+1)$.

Ejemplo resuelto

Intento Fallido: Demostrar $P(n): \sum_{i=0}^{n}r^{i}\le\frac{1}{1-r}$ para $0<r<1$.

• 1. Caso Base (n=0): $\sum_{i=0}^{0}r^{i} = 1$. Queremos probar $1 \le \frac{1}{1-r}$. Como $0 < r < 1$, entonces $0 < 1-r < 1$. Al dividir por un número menor que 1, el resultado es mayor que 1 (ej: $1 / 0.5 = 2$). Por lo tanto, $1 \le \frac{1}{1-r}$ es verdadero. El caso base funciona.

• 2. Paso Inductivo:

  • Hipótesis (P(n)): Asumimos $\sum_{i=0}^{n}r^{i}\le\frac{1}{1-r}$.

  • Tesis (P(n+1)): Queremos probar $\sum_{i=0}^{n+1}r^{i}\le\frac{1}{1-r}$.

  • Demostración (Intento):

$$\sum_{i=0}^{n+1}r^{i} = (\sum_{i=0}^{n}r^{i}) + r^{n+1}$$

Usando nuestra hipótesis:

$$\le \frac{1}{1-r} + r^{n+1}$$

Aquí nos atascamos. Queríamos llegar a $\le \frac{1}{1-r}$, pero llegamos a $\frac{1}{1-r} + r^{n+1}$. Como $r>0$, $r^{n+1}$ es un número positivo. No podemos demostrar que $\frac{1}{1-r} + r^{n+1} \le \frac{1}{1-r}$. La hipótesis fue demasiado “débil” y no nos dio la precisión que necesitábamos.

Prueba Exitosa (Fortaleciendo la Hipótesis): En lugar de eso, probemos la afirmación más fuerte $P'(n): \sum_{i=0}^{n}r^{i} = \frac{1-r^{n+1}}{1-r}$ (la diapositiva usa $\le$, pero la prueba demuestra la igualdad, que es más fuerte). Esta afirmación $P'$ implica la $P$ original, ya que $\frac{1-r^{n+1}}{1-r} \le \frac{1}{1-r}$ [porque $r^{n+1}$ es positivo].

• 1. Caso Base (n=0): $\sum_{i=0}^{0}r^{i} = 1$. El lado derecho es $\frac{1-r^{0+1}}{1-r} = \frac{1-r}{1-r} = 1$. Se cumple $1 = 1$. El caso base es verdadero.

• 2. Paso Inductivo:

  • Hipótesis (P’(n)): Asumimos $\sum_{i=0}^{n}r^{i} = \frac{1-r^{n+1}}{1-r}$.

  • Tesis (P’(n+1)): Queremos probar $\sum_{i=0}^{n+1}r^{i} = \frac{1-r^{n+2}}{1-r}$.

  • Demostración:

$$\sum_{i=0}^{n+1}r^{i} = (\sum_{i=0}^{n}r^{i}) + r^{n+1}$$

Usando nuestra nueva hipótesis fuerte:

$$= \frac{1-r^{n+1}}{1-r} + r^{n+1}$$

Ponemos todo sobre el mismo denominador:

$$= \frac{1-r^{n+1} + r^{n+1}(1-r)}{1-r}$$ $$= \frac{1-r^{n+1} + r^{n+1} - r^{n+2}}{1-r}$$ $$= \frac{1-r^{n+2}}{1-r}$$

¡Esto es exactamente lo que queríamos probar (la Tesis P’(n+1))!.

Resumen rápido

“Fortalecer la hipótesis” no es lo mismo que inducción fuerte. Es una técnica de re-formulación donde probamos una afirmación más específica. Esta afirmación más fuerte nos da una hipótesis inductiva más poderosa, que puede hacer que una prueba fallida funcione.

---

Tema: Inducción Fuerte

Definición inicial

La Inducción Fuerte es una variante del principio de inducción. En lugar de asumir que solo el caso anterior (n) es verdadero para probar (n+1), la inducción fuerte nos permite asumir que todos los casos anteriores (0, 1, 2, …, n) son verdaderos.

Explicación didáctica

Volvamos a las fichas de dominó. En la inducción estándar, para probar que la ficha #100 cae, solo podíamos usar la información de que la ficha #99 cae.

En la inducción fuerte, para probar que la ficha #100 cae, podemos usar la información de que la ficha #1, #2, #3, …, y #99 han caído todas..

Esto es útil en problemas donde el estado de $n+1$ no depende solo de $n$, sino de algún caso anterior, más pequeño. Por ejemplo, la factorización prima de 100 no depende de la de 99, sino de las de 2 y 50. La inducción fuerte nos permitiría usar la hipótesis sobre 2 y 50.

Definición formal

Sea $P$ una propiedad sobre los números naturales. Si se cumplen las siguientes dos condiciones:

1. Caso Base: $P$ se cumple para 0 (es decir, $P(0)$ es verdadero).
2. Caso Inductivo Fuerte: Si $P$ se cumple para todo $k$ tal que $0 \le k < n$ (esta es la “Hipótesis de Inducción Fuerte”), entonces $P$ también se cumple para $n$ (es decir, $(\forall k < n, P(k)) \Rightarrow P(n)$).

Si ambas condiciones son verdaderas, entonces se concluye que $P$ se satisface para todos los números naturales. (Nota: La inducción fuerte y la estándar son lógicamente equivalentes ).

Ejemplo resuelto

Demostremos que todo número natural $n \ge 8$ se puede escribir como una suma de 3s y 5s.

Usaremos inducción fuerte comenzando desde $k=8$.

• Propiedad P(n): $n$ se puede escribir como suma de 3s y 5s.

• Idea del Paso Inductivo: Si queremos probar P(n), una buena estrategia sería ver si podemos basarnos en P(n-3). Si P(n-3) es verdadero, entonces $n-3$ es una suma de 3s y 5s. Simplemente le agregamos un “+3” y ya tenemos P[n]. $n = (n-3) + 3$. Este “salto” de 3 hacia atrás nos dice dos cosas:

  1. Necesitamos Inducción Fuerte, porque $n$ no depende de $n-1$, sino de $n-3$.
  2. Nuestro paso inductivo solo funciona si $n-3$ está en el rango que ya hemos probado (es decir, $n-3 \ge 8$). Esto significa que el paso inductivo solo es válido para $n \ge 11$.
  3. Debido a esto, debemos probar manualmente todos los casos desde nuestro inicio (8) hasta que el paso inductivo funcione (10). Necesitamos múltiples casos base: $n=8, n=9, n=10$.

• 1. Casos Base:

  • P(8): $8 = 3 + 5$. Verdadero.
  • P(9): $9 = 3 + 3 + 3$. Verdadero.
  • P(10): $10 = 5 + 5$. Verdadero.

• 2. Paso Inductivo Fuerte:

  • Asumimos que $n \ge 11$.

  • Hipótesis Fuerte: Asumimos que $P(k)$ es verdadero para todo $k$ tal que $8 \le k < n$.

  • Tesis: Queremos probar $P(n)$.

  • Demostración:

Consideramos el número $k = n - 3$.

Como $n \ge 11$, sabemos que $k \ge 8$.

Como $k$ es menor que $n$, $k$ está en el rango de nuestra Hipótesis Fuerte ($8 \le k < n$).

Por lo tanto, $P(k)$ es verdadero: $k$ se puede escribir como una suma de 3s y 5s [$k = s_1 + ... + s_m$].

Ahora, veamos $n$:

$$n = (n-3) + 3 = k + 3$$

Sustituyendo $k$:

$$n = (s_1 + ... + s_m) + 3$$

Esto es una suma de 3s y 5s. Por lo tanto, P(n) es verdadero.

Como los casos base (8, 9, 10) son verdaderos y el paso inductivo fuerte (para $n \ge 11$) es verdadero, concluimos que la propiedad es verdadera para todo $n \ge 8$.

Resumen rápido

La inducción fuerte nos permite usar una hipótesis más poderosa: asumimos que todos los casos $k < n$ son verdaderos para probar $n$. Esto es ideal para problemas donde el siguiente paso no depende del anterior, sino de algún caso mucho más pequeño, como $n-3$ o $n/2$.

---

Tema: El Principio del Mínimo (Principio del Buen Orden)

Definición inicial

El Principio del Mínimo es una propiedad fundamental de los números naturales. Establece que cualquier colección de números naturales que no esté vacía, debe tener un elemento que es el “más pequeño” o el “primero” de esa colección.

Explicación didáctica

Imagina que pides a un grupo de personas (un conjunto no vacío) que escriban un número natural en un papel. No importa cuántas personas sean, ni qué números escriban, siempre que haya al menos un papel, podrás revisarlos todos y encontrar uno que tenga el número más bajo (o un empate por el más bajo). Es imposible que exista una lista infinita de números naturales que “descienda” para siempre (como 5, 4, 3, 2, 1, 0, … pero sin parar). Tarde o temprano, llegas a un mínimo.

Definición formal

Todo subconjunto no vacío $A$ de los números naturales ($\mathbb{N}$) tiene un elemento mínimo. Es decir, si $A \subseteq \mathbb{N}$ y $A \ne \emptyset$, entonces existe un elemento $a \in A$ tal que para todo $b \in A$, se cumple que $a \le b$.

Ejemplo resuelto (Equivalencia con la Inducción)

El Principio del Mínimo (PM) y el Principio de Inducción Fuerte (IF) son lógicamente equivalentes. Se pueden usar para probarse mutuamente. Aquí demostraremos que la Inducción Fuerte implica el Principio del Mínimo, usando una prueba por contradicción.

• Objetivo: Probar el Principio del Mínimo.

• Suposición (por contradicción): Asumimos que el PM es falso.

• Consecuencia de la suposición: Si el PM es falso, debe existir al menos un conjunto $A \subseteq \mathbb{N}$ que sea no vacío ($A \ne \emptyset$) y que no tenga un elemento mínimo.

• Plan: Usaremos la Inducción Fuerte para demostrar que este conjunto $A$ debe estar vacío ($A = \emptyset$). Esto creará una contradicción (dijimos que $A$ era no vacío), probando que nuestra suposición original era incorrecta.

• Definición de la Propiedad: Definamos una propiedad $P(n)$ como "$n \notin A$" [el número $n$ no pertenece al conjunto “malo”]. Vamos a probar $P(n)$ para todo $n$ usando Inducción Fuerte.

• 1. Caso Base (P(0)): Debemos probar $P(0)$, es decir, que $0 \notin A$. Si $0$ estuviera en $A$ (si $0 \in A$), como 0 es el número natural más pequeño, sería automáticamente el elemento mínimo de $A$. Pero nuestra suposición dice que $A$ no tiene mínimo. Por lo tanto, $0$ no puede estar en $A$. Concluimos que $0 \notin A$, lo que significa que $P(0)$ es verdadero.

• 2. Paso Inductivo Fuerte:

  • Hipótesis Fuerte: Asumimos que $P(k)$ es verdadero para todo $k < n$. Es decir, $k \notin A$ para todo $k < n$.
  • Tesis: Queremos probar $P(n)$, es decir, que $n \notin A$.
  • Demostración (por contradicción): Supongamos que $n$ sí está en $A$ [es decir, $n \in A$].
  • Por nuestra Hipótesis Fuerte, sabemos que ningún número $k < n$ está en $A$.
  • Si $n \in A$ y ningún número menor que $n$ está en $A$, esto haría que $n$ sea el elemento mínimo de $A$.
  • Pero, de nuevo, nuestra suposición principal es que $A$ no tiene mínimo.
  • Por lo tanto, nuestra suposición ($n \in A$) debe ser falsa. Concluimos que $n \notin A$.
  • Esto significa que $P(n)$ es verdadero.

• Conclusión de la Prueba: Hemos probado $P(0)$ y que $(\forall k < n, P(k)) \Rightarrow P(n)$. Por el Principio de Inducción Fuerte, $P(n)$ es verdadero para todos los $n \in \mathbb{N}$. Si $P(n)$ ("$n \notin A$") es verdadero para todo $n$, eso significa que $A$ es el conjunto vacío [$A = \emptyset$]. Esto es una contradicción directa con nuestra suposición inicial de que $A$ era un conjunto no vacío. La única suposición errónea fue la primera: que el Principio del Mínimo era falso. Por lo tanto, el Principio del Mínimo debe ser verdadero.

Resumen rápido

El Principio del Mínimo dice que cualquier conjunto no vacío de números naturales tiene un “primer” elemento. Es la base de por qué funciona la inducción. Demostrar que “todos los dominós caen” (Inducción) es lógicamente equivalente a demostrar que “el conjunto de dominós que no caen” debe estar vacío, porque si no lo estuviera, tendría que haber un primer dominó que no cayó (Principio del Mínimo), y eso nos lleva a una contradicción.