Capítulo 10 — Inducción, Recurrencia y Sumas¶
10.1 — El Principio de Inducción¶
Los puntos suspensivos de \(\{1,2,3,\dots\}\) contienen un teorema; esta sección lo extrae.
En el §1.1 los números naturales se presentaron por extensión, como \(\mathbb{N}=\{1,2,3,\dots\}\), y la presentación descansaba en que el lector supiera continuar la lista. Para contar alcanza. Para demostrar no alcanza, porque los puntos suspensivos no dicen qué objetos pertenecen a \(\mathbb{N}\) y cuáles no, y cada vez que el libro probó algo "para todo \(n\)" pasando de \(n\) a \(n+1\) usó una propiedad de \(\mathbb{N}\) que nunca enunció. Esta sección define \(\mathbb{N}\) dentro de \(\mathbb{R}\), con los axiomas del §1.1 como único punto de partida, y demuestra a partir de esa definición el principio de inducción y sus variantes.
§1. El menor conjunto inductivo¶
Definición. Un subconjunto \(A\subseteq\mathbb{R}\) es inductivo si \(1\in A\) y, para todo \(x\in A\), también \(x+1\in A\).
El propio \(\mathbb{R}\) es inductivo, y también lo son \([1,+\infty)\), \([0,+\infty)\) y el conjunto \(\{1\}\cup[2,+\infty)\). Un conjunto inductivo contiene al \(1\), al \(1+1\), al \((1+1)+1\) y, en general, a todo lo que la lista del §1.1 pretendía enumerar, pero puede contener mucho más. Lo que se busca es el conjunto que contenga eso y nada más, y la manera de obtenerlo sin usar puntos suspensivos es tomar lo que todos los conjuntos inductivos tienen en común.
Definición. El conjunto de los números naturales es la intersección de todos los subconjuntos inductivos de \(\mathbb{R}\):
Proposición. \(\mathbb{N}\) es inductivo, y está contenido en todo subconjunto inductivo de \(\mathbb{R}\).
Demostración. El número \(1\) pertenece a todo conjunto inductivo, así que \(1\in\mathbb{N}\). Si \(x\in\mathbb{N}\), entonces \(x\) pertenece a todo conjunto inductivo \(A\), y como cada uno de ellos es inductivo, también \(x+1\in A\); por lo tanto \(x+1\in\mathbb{N}\). La segunda afirmación es inmediata: si \(A\) es inductivo, es uno de los conjuntos que se intersecan, y la intersección está contenida en cada uno de ellos. \(\blacksquare\)
\(\mathbb{N}\) es, así, el menor conjunto inductivo, en el sentido de la inclusión. De esa minimalidad sale todo lo demás, empezando por el teorema que da nombre a la sección.
Teorema (principio de inducción). Sea \(S\subseteq\mathbb{N}\) tal que \(1\in S\) y, para todo \(n\in S\), también \(n+1\in S\). Entonces \(S=\mathbb{N}\).
Demostración. Las hipótesis dicen que \(S\) es inductivo. Por la proposición, \(\mathbb{N}\subseteq S\), y como \(S\subseteq\mathbb{N}\), ambos conjuntos coinciden. \(\blacksquare\)
En la práctica el teorema se usa en la forma de propiedades. Sea \(P(n)\) una afirmación que tiene sentido para cada natural \(n\). Si se prueba que \(P(1)\) es verdadera, el caso base, y que para todo \(n\) la verdad de \(P(n)\) implica la de \(P(n+1)\), el paso inductivo, entonces \(P(n)\) es verdadera para todo \(n\in\mathbb{N}\). Basta aplicar el teorema al conjunto \(S=\{n\in\mathbb{N} : P(n)\text{ es verdadera}\}\). En el paso inductivo, la suposición de que \(P(n)\) vale se llama hipótesis inductiva. No es una petición de principio: no se supone lo que se quiere probar, que es \(P(n)\) para todo \(n\), sino que se prueba una implicación para cada \(n\).
Recordatorio. Caso base \(P(1)\); paso inductivo \(P(n)\Rightarrow P(n+1)\) para todo \(n\). Juntos implican \(P(n)\) para todo \(n\in\mathbb{N}\), porque el conjunto donde \(P\) vale es inductivo y \(\mathbb{N}\) es el menor de ellos.
§2. Lo que la definición reconstruye¶
La definición debe recuperar las propiedades que el §1.1 atribuía a la lista. Se prueban aquí las que el resto del capítulo necesita, y cada prueba es un primer ejercicio del principio.
Proposición. Para todo \(n\in\mathbb{N}\) se cumple \(n\geq 1\).
Demostración. El intervalo \([1,+\infty)\) es inductivo, así que contiene a \(\mathbb{N}\). \(\blacksquare\)
Proposición. Si \(m,n\in\mathbb{N}\), entonces \(m+n\in\mathbb{N}\) y \(mn\in\mathbb{N}\).
Demostración. Se fija \(m\in\mathbb{N}\) y se prueba por inducción en \(n\) que \(m+n\in\mathbb{N}\). Para \(n=1\), \(m+1\in\mathbb{N}\) porque \(\mathbb{N}\) es inductivo. Si \(m+n\in\mathbb{N}\), entonces \(m+(n+1)=(m+n)+1\in\mathbb{N}\) por la misma razón. Para el producto, con \(m\) fijo, \(m\cdot 1=m\in\mathbb{N}\), y si \(mn\in\mathbb{N}\), entonces \(m(n+1)=mn+m\in\mathbb{N}\) por lo ya probado para la suma. \(\blacksquare\)
Proposición. Si \(n\in\mathbb{N}\) y \(n\neq 1\), entonces \(n-1\in\mathbb{N}\).
Demostración. Sea \(S=\{1\}\cup\{n\in\mathbb{N} : n-1\in\mathbb{N}\}\). Contiene al \(1\). Si \(n\in S\), entonces \(n\in\mathbb{N}\) y \((n+1)-1=n\in\mathbb{N}\), así que \(n+1\in S\). Por el principio de inducción, \(S=\mathbb{N}\), que es lo que se afirmaba. \(\blacksquare\)
Proposición. Para todo \(n\in\mathbb{N}\), no existe ningún natural \(m\) con \(n<m<n+1\).
Demostración. Primero el caso \(n=1\). El conjunto \(\{1\}\cup[2,+\infty)\) es inductivo, porque si \(x=1\) entonces \(x+1=2\), y si \(x\geq 2\) entonces \(x+1\geq 2\). Contiene, por lo tanto, a \(\mathbb{N}\), y no tiene puntos en \((1,2)\). Supóngase ahora que la afirmación vale para \(n\), y que existiera \(m\in\mathbb{N}\) con \(n+1<m<n+2\). Como \(m>2\), se tiene \(m\neq 1\), y por la proposición anterior \(m-1\in\mathbb{N}\), con \(n<m-1<n+1\), contra la hipótesis inductiva. \(\blacksquare\)
Esta última proposición es la que da sentido preciso a la frase "\(n+1\) es el siguiente de \(n\)". Entre dos naturales consecutivos no hay otro natural. Se sigue, en particular, que si \(k\) y \(n\) son naturales con \(k\leq n+1\), entonces \(k\leq n\) o \(k=n+1\). El conjunto de los enteros se obtiene como \(\mathbb{Z}=\mathbb{N}\cup\{0\}\cup\{-n : n\in\mathbb{N}\}\), y se escribe \(\mathbb{N}_0=\mathbb{N}\cup\{0\}\).
Queda una propiedad que el libro usó desde el capítulo 1: que los naturales no están acotados.
Proposición (propiedad arquimediana). Para todo número real \(x\) existe \(n\in\mathbb{N}\) con \(n>x\).
Demostración. Si no fuera así, \(\mathbb{N}\) sería un conjunto no vacío acotado superiormente por \(x\), y por el axioma del supremo del §1.1 tendría supremo \(s\). Como \(s-1<s\), el número \(s-1\) no es cota superior, y existe \(n\in\mathbb{N}\) con \(n>s-1\). Pero entonces \(n+1\in\mathbb{N}\) y \(n+1>s\), contra la definición de supremo. \(\blacksquare\)
La demostración necesita las dos mitades de la estructura de \(\mathbb{R}\): el axioma del supremo y el carácter inductivo de \(\mathbb{N}\). Sin la segunda, el argumento no puede pasar de \(n\) a \(n+1\).
§3. Variantes del principio¶
Muchas afirmaciones valen solo a partir de cierto número, y muchos pasos inductivos necesitan más que el caso inmediatamente anterior. Ambas situaciones se reducen al principio básico.
Proposición (inducción desde \(n_0\)). Sea \(n_0\in\mathbb{Z}\) y sea \(P(n)\) una afirmación para cada entero \(n\geq n_0\). Si \(P(n_0)\) es verdadera y, para todo \(n\geq n_0\), \(P(n)\) implica \(P(n+1)\), entonces \(P(n)\) es verdadera para todo entero \(n\geq n_0\).
Demostración. Se aplica el principio de inducción a la afirmación \(Q(k)\): "\(P(n_0+k-1)\) es verdadera", para \(k\in\mathbb{N}\). \(Q(1)\) es \(P(n_0)\), y \(Q(k)\Rightarrow Q(k+1)\) es el paso \(P(n)\Rightarrow P(n+1)\) con \(n=n_0+k-1\geq n_0\). Todo entero \(n\geq n_0\) es de la forma \(n_0+k-1\) con \(k=n-n_0+1\in\mathbb{N}\). \(\blacksquare\)
Teorema (inducción fuerte). Sea \(P(n)\) una afirmación para cada \(n\in\mathbb{N}\). Si, para todo \(n\in\mathbb{N}\), la verdad de \(P(k)\) para todos los naturales \(k<n\) implica la verdad de \(P(n)\), entonces \(P(n)\) es verdadera para todo \(n\).
Demostración. Sea \(Q(n)\) la afirmación "\(P(k)\) es verdadera para todo natural \(k\leq n\)". Para \(n=1\), no hay naturales menores que \(1\) (§2), de modo que la hipótesis, aplicada a \(n=1\), da \(P(1)\) sin suponer nada; como el único natural \(k\leq 1\) es el \(1\), vale \(Q(1)\). Supóngase \(Q(n)\). Entonces \(P(k)\) vale para todo \(k<n+1\), porque por el §2 esos \(k\) son exactamente los \(k\leq n\), y la hipótesis da \(P(n+1)\). Por lo tanto \(P(k)\) vale para todo \(k\leq n+1\), que es \(Q(n+1)\). Por el principio de inducción \(Q(n)\) vale para todo \(n\), y en particular \(P(n)\). \(\blacksquare\)
En la inducción fuerte no hay un caso base separado, pero el caso \(n=1\) debe tratarse de todos modos, porque para él la hipótesis no ofrece nada que usar.
Teorema (principio del buen orden). Todo subconjunto no vacío de \(\mathbb{N}\) tiene un elemento mínimo.
Demostración. Sea \(A\subseteq\mathbb{N}\) sin elemento mínimo; se prueba que \(A\) es vacío. Sea \(P(n)\) la afirmación "\(n\notin A\)". Si \(P(k)\) vale para todos los naturales \(k<n\), entonces ningún natural menor que \(n\) está en \(A\). Si \(n\) estuviera en \(A\), sería su mínimo, que no existe. Por lo tanto \(n\notin A\), es decir, vale \(P(n)\). Por inducción fuerte, ningún natural está en \(A\). \(\blacksquare\)
El buen orden es, a su vez, suficiente para recuperar el principio de inducción. Si \(S\subseteq\mathbb{N}\) cumple las hipótesis del teorema del §1 y no fuera todo \(\mathbb{N}\), el conjunto \(\mathbb{N}\setminus S\) sería no vacío y tendría un mínimo \(m\). Sería \(m\neq 1\), porque \(1\in S\), y entonces \(m-1\in\mathbb{N}\), con \(m-1\notin\mathbb{N}\setminus S\) por ser menor que el mínimo. Así, \(m-1\in S\), y por hipótesis \(m\in S\), una contradicción. Las dos formulaciones son, en este sentido, equivalentes. La del buen orden es la que usan las demostraciones por descenso, en las que se supone un contraejemplo y se construye otro menor, lo que es imposible si se partió del mínimo.
Recordatorio. Inducción desde \(n_0\): caso base \(P(n_0)\). Inducción fuerte: \(P(n)\) puede usar todos los casos anteriores, no solo \(P(n-1)\). Buen orden: todo subconjunto no vacío de \(\mathbb{N}\) tiene mínimo. Las tres se reducen al principio de inducción.
§4. Dos aplicaciones¶
La primera aplicación salda una deuda del capítulo 4, cuya prueba de unicidad de la exponencial se apoyó en una desigualdad de Bernoulli. La potencia \(a^n\) de exponente natural se usa aquí con su definición del §1.2, "el producto de \(n\) factores iguales a \(a\)", que es, en rigor, una definición por recurrencia: \(a^1=a\) y \(a^{n+1}=a^n\cdot a\). El §10.2 prueba que esa definición es legítima.
Proposición (desigualdad de Bernoulli). Si \(x\geq -1\), entonces \((1+x)^n\geq 1+nx\) para todo \(n\in\mathbb{N}\).
Demostración. Para \(n=1\) la desigualdad es una igualdad. Supóngase que vale para \(n\). Como \(x\geq -1\), el factor \(1+x\) es no negativo, y multiplicar la hipótesis inductiva por él conserva la desigualdad (§1.7):
donde el último paso usa que \(nx^2\geq 0\). \(\blacksquare\)
La hipótesis \(x\geq -1\) se usó en un solo lugar, para multiplicar la desigualdad sin invertirla, y no puede suprimirse. Con \(x=-3\), para \(n=2\) los miembros valen \(4\) y \(-5\), y para \(n=3\) ambos valen \(-8\), de modo que la desigualdad todavía se cumple. Pero para \(n=5\) el primer miembro vale \(-32\) y el segundo \(-14\), y la desigualdad falla.
Los otros argumentos de los capítulos 4 y 5 que pasaban de un término al siguiente tenían la misma estructura. Así ocurre con las afirmaciones del tipo "\(a_n<a_{n+1}\) para todo \(n\)" sobre las sucesiones que construyeron \(e\), y con las cotas de los polígonos de \(2^n\) lados que construyeron \(\pi\). Todos son aplicaciones del principio que esta sección acaba de demostrar, y quedan justificados sin cambiar una línea.
La segunda aplicación es un principio de conteo que el §10.4 va a necesitar. Para \(n\in\mathbb{N}\), sea \(I_n=\{k\in\mathbb{N} : k\leq n\}\), el conjunto de los primeros \(n\) naturales.
Proposición (principio del palomar). Para todo \(n\in\mathbb{N}\), no existe ninguna función inyectiva de \(I_{n+1}\) en \(I_n\).
Demostración. Para \(n=1\), toda función de \(I_2=\{1,2\}\) en \(I_1=\{1\}\) asigna a ambos elementos el valor \(1\) y no es inyectiva. Supóngase que no existe función inyectiva de \(I_{n+1}\) en \(I_n\), y que existiera una función inyectiva \(f:I_{n+2}\to I_{n+1}\). Si el valor \(n+1\) no es imagen de ningún elemento, la restricción de \(f\) a \(I_{n+1}\) es una función inyectiva de \(I_{n+1}\) en \(I_n\), contra la hipótesis inductiva. Si \(f(j)=n+1\) para cierto \(j\), sea \(h\) la función que coincide con \(f\) salvo que intercambia los valores en \(j\) y en \(n+2\). Es decir, \(h(j)=f(n+2)\), \(h(n+2)=f(j)=n+1\) y \(h(k)=f(k)\) para los demás \(k\). La función \(h\) sigue siendo inyectiva y solo toma el valor \(n+1\) en \(n+2\), porque \(f\) lo tomaba solo en \(j\). Su restricción a \(I_{n+1}\) es, entonces, una función inyectiva de \(I_{n+1}\) en \(I_n\), otra vez contra la hipótesis. \(\blacksquare\)
El nombre viene de su lectura cotidiana: si \(n+1\) palomas se acomodan en \(n\) nidos, algún nido recibe al menos dos. Parece demasiado obvio para necesitar una prueba, y sin embargo la prueba no es trivial, porque "obvio" significaba aquí "evidente para los primeros casos que uno imagina". El principio de inducción es exactamente lo que convierte esa evidencia local en un enunciado para todo \(n\).
El principio de inducción permite demostrar afirmaciones sobre todos los naturales. La sección siguiente prueba su contraparte constructiva: que una regla que dice cómo obtener cada término a partir del anterior define, efectivamente, una única sucesión.