Skip to content

Chapter 10 — Induction, Recursion and Sums

10.1 — El Principio de Inducción

This content is not available in your language yet.

Los puntos suspensivos de {1,2,3,… }\{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 N={1,2,3,… }\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 N\mathbb{N} y cuáles no, y cada vez que el libro probó algo “para todo nn” pasando de nn a n+1n+1 usó una propiedad de N\mathbb{N} que nunca enunció. Esta sección define N\mathbb{N} dentro de R\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.

Definición. Un subconjunto A⊆RA\subseteq\mathbb{R} es inductivo si 1∈A1\in A y, para todo x∈Ax\in A, también x+1∈Ax+1\in A.

El propio R\mathbb{R} es inductivo, y también lo son [1,+∞)[1,+\infty), [0,+∞)[0,+\infty) y el conjunto {1}∪[2,+∞)\{1\}\cup[2,+\infty). Un conjunto inductivo contiene al 11, al 1+11+1, al (1+1)+1(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 R\mathbb{R}:

N={x∈R:x∈A para todo A⊆R inductivo}.\mathbb{N}=\{x\in\mathbb{R} : x\in A \text{ para todo } A\subseteq\mathbb{R} \text{ inductivo}\}.

Proposición. N\mathbb{N} es inductivo, y está contenido en todo subconjunto inductivo de R\mathbb{R}.

Demostración. El número 11 pertenece a todo conjunto inductivo, así que 1∈N1\in\mathbb{N}. Si x∈Nx\in\mathbb{N}, entonces xx pertenece a todo conjunto inductivo AA, y como cada uno de ellos es inductivo, también x+1∈Ax+1\in A; por lo tanto x+1∈Nx+1\in\mathbb{N}. La segunda afirmación es inmediata: si AA es inductivo, es uno de los conjuntos que se intersecan, y la intersección está contenida en cada uno de ellos. ■\blacksquare

N\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⊆NS\subseteq\mathbb{N} tal que 1∈S1\in S y, para todo n∈Sn\in S, también n+1∈Sn+1\in S. Entonces S=NS=\mathbb{N}.

Demostración. Las hipótesis dicen que SS es inductivo. Por la proposición, N⊆S\mathbb{N}\subseteq S, y como S⊆NS\subseteq\mathbb{N}, ambos conjuntos coinciden. ■\blacksquare

En la práctica el teorema se usa en la forma de propiedades. Sea P(n)P(n) una afirmación que tiene sentido para cada natural nn. Si se prueba que P(1)P(1) es verdadera, el caso base, y que para todo nn la verdad de P(n)P(n) implica la de P(n+1)P(n+1), el paso inductivo, entonces P(n)P(n) es verdadera para todo n∈Nn\in\mathbb{N}. Basta aplicar el teorema al conjunto S={n∈N:P(n) es verdadera}S=\{n\in\mathbb{N} : P(n)\text{ es verdadera}\}. En el paso inductivo, la suposición de que P(n)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)P(n) para todo nn, sino que se prueba una implicación para cada nn.

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∈Nn\in\mathbb{N} se cumple n≥1n\geq 1.

Demostración. El intervalo [1,+∞)[1,+\infty) es inductivo, así que contiene a N\mathbb{N}. ■\blacksquare

Proposición. Si m,n∈Nm,n\in\mathbb{N}, entonces m+n∈Nm+n\in\mathbb{N} y mn∈Nmn\in\mathbb{N}.

Demostración. Se fija m∈Nm\in\mathbb{N} y se prueba por inducción en nn que m+n∈Nm+n\in\mathbb{N}. Para n=1n=1, m+1∈Nm+1\in\mathbb{N} porque N\mathbb{N} es inductivo. Si m+n∈Nm+n\in\mathbb{N}, entonces m+(n+1)=(m+n)+1∈Nm+(n+1)=(m+n)+1\in\mathbb{N} por la misma razón. Para el producto, con mm fijo, m⋅1=m∈Nm\cdot 1=m\in\mathbb{N}, y si mn∈Nmn\in\mathbb{N}, entonces m(n+1)=mn+m∈Nm(n+1)=mn+m\in\mathbb{N} por lo ya probado para la suma. ■\blacksquare

Proposición. Si n∈Nn\in\mathbb{N} y n≠1n\neq 1, entonces n−1∈Nn-1\in\mathbb{N}.

Demostración. Sea S={1}∪{n∈N:n−1∈N}S=\{1\}\cup\{n\in\mathbb{N} : n-1\in\mathbb{N}\}. Contiene al 11. Si n∈Sn\in S, entonces n∈Nn\in\mathbb{N} y (n+1)−1=n∈N(n+1)-1=n\in\mathbb{N}, así que n+1∈Sn+1\in S. Por el principio de inducción, S=NS=\mathbb{N}, que es lo que se afirmaba. ■\blacksquare

Proposición. Para todo n∈Nn\in\mathbb{N}, no existe ningún natural mm con n<m<n+1n<m<n+1.

Demostración. Primero el caso n=1n=1. El conjunto {1}∪[2,+∞)\{1\}\cup[2,+\infty) es inductivo, porque si x=1x=1 entonces x+1=2x+1=2, y si x≥2x\geq 2 entonces x+1≥2x+1\geq 2. Contiene, por lo tanto, a N\mathbb{N}, y no tiene puntos en (1,2)(1,2). Supóngase ahora que la afirmación vale para nn, y que existiera m∈Nm\in\mathbb{N} con n+1<m<n+2n+1<m<n+2. Como m>2m>2, se tiene m≠1m\neq 1, y por la proposición anterior m−1∈Nm-1\in\mathbb{N}, con n<m−1<n+1n<m-1<n+1, contra la hipótesis inductiva. ■\blacksquare

Esta última proposición es la que da sentido preciso a la frase ”n+1n+1 es el siguiente de nn”. Entre dos naturales consecutivos no hay otro natural. Se sigue, en particular, que si kk y nn son naturales con k≤n+1k\leq n+1, entonces k≤nk\leq n o k=n+1k=n+1. El conjunto de los enteros se obtiene como Z=N∪{0}∪{−n:n∈N}\mathbb{Z}=\mathbb{N}\cup\{0\}\cup\{-n : n\in\mathbb{N}\}, y se escribe N0=N∪{0}\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 xx existe n∈Nn\in\mathbb{N} con n>xn>x.

Demostración. Si no fuera así, N\mathbb{N} sería un conjunto no vacío acotado superiormente por xx, y por el axioma del supremo del §1.1 tendría supremo ss. Como s−1<ss-1<s, el número s−1s-1 no es cota superior, y existe n∈Nn\in\mathbb{N} con n>s−1n>s-1. Pero entonces n+1∈Nn+1\in\mathbb{N} y n+1>sn+1>s, contra la definición de supremo. ■\blacksquare

La demostración necesita las dos mitades de la estructura de R\mathbb{R}: el axioma del supremo y el carácter inductivo de N\mathbb{N}. Sin la segunda, el argumento no puede pasar de nn a n+1n+1.

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 n0n_0). Sea n0∈Zn_0\in\mathbb{Z} y sea P(n)P(n) una afirmación para cada entero n≥n0n\geq n_0. Si P(n0)P(n_0) es verdadera y, para todo n≥n0n\geq n_0, P(n)P(n) implica P(n+1)P(n+1), entonces P(n)P(n) es verdadera para todo entero n≥n0n\geq n_0.

Demostración. Se aplica el principio de inducción a la afirmación Q(k)Q(k): ”P(n0+k−1)P(n_0+k-1) es verdadera”, para k∈Nk\in\mathbb{N}. Q(1)Q(1) es P(n0)P(n_0), y Q(k)⇒Q(k+1)Q(k)\Rightarrow Q(k+1) es el paso P(n)⇒P(n+1)P(n)\Rightarrow P(n+1) con n=n0+k−1≥n0n=n_0+k-1\geq n_0. Todo entero n≥n0n\geq n_0 es de la forma n0+k−1n_0+k-1 con k=n−n0+1∈Nk=n-n_0+1\in\mathbb{N}. ■\blacksquare

Teorema (inducción fuerte). Sea P(n)P(n) una afirmación para cada n∈Nn\in\mathbb{N}. Si, para todo n∈Nn\in\mathbb{N}, la verdad de P(k)P(k) para todos los naturales k<nk<n implica la verdad de P(n)P(n), entonces P(n)P(n) es verdadera para todo nn.

Demostración. Sea Q(n)Q(n) la afirmación ”P(k)P(k) es verdadera para todo natural k≤nk\leq n”. Para n=1n=1, no hay naturales menores que 11 (§2), de modo que la hipótesis, aplicada a n=1n=1, da P(1)P(1) sin suponer nada; como el único natural k≤1k\leq 1 es el 11, vale Q(1)Q(1). Supóngase Q(n)Q(n). Entonces P(k)P(k) vale para todo k<n+1k<n+1, porque por el §2 esos kk son exactamente los k≤nk\leq n, y la hipótesis da P(n+1)P(n+1). Por lo tanto P(k)P(k) vale para todo k≤n+1k\leq n+1, que es Q(n+1)Q(n+1). Por el principio de inducción Q(n)Q(n) vale para todo nn, y en particular P(n)P(n). ■\blacksquare

En la inducción fuerte no hay un caso base separado, pero el caso n=1n=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 N\mathbb{N} tiene un elemento mínimo.

Demostración. Sea A⊆NA\subseteq\mathbb{N} sin elemento mínimo; se prueba que AA es vacío. Sea P(n)P(n) la afirmación "n∉An\notin A". Si P(k)P(k) vale para todos los naturales k<nk<n, entonces ningún natural menor que nn está en AA. Si nn estuviera en AA, sería su mínimo, que no existe. Por lo tanto n∉An\notin A, es decir, vale P(n)P(n). Por inducción fuerte, ningún natural está en AA. ■\blacksquare

El buen orden es, a su vez, suficiente para recuperar el principio de inducción. Si S⊆NS\subseteq\mathbb{N} cumple las hipótesis del teorema del §1 y no fuera todo N\mathbb{N}, el conjunto N∖S\mathbb{N}\setminus S sería no vacío y tendría un mínimo mm. Sería m≠1m\neq 1, porque 1∈S1\in S, y entonces m−1∈Nm-1\in\mathbb{N}, con m−1∉N∖Sm-1\notin\mathbb{N}\setminus S por ser menor que el mínimo. Así, m−1∈Sm-1\in S, y por hipótesis m∈Sm\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.

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 ana^n de exponente natural se usa aquí con su definición del §1.2, “el producto de nn factores iguales a aa”, que es, en rigor, una definición por recurrencia: a1=aa^1=a y an+1=an⋅aa^{n+1}=a^n\cdot a. El §10.2 prueba que esa definición es legítima.

Proposición (desigualdad de Bernoulli). Si x≥−1x\geq -1, entonces (1+x)n≥1+nx(1+x)^n\geq 1+nx para todo n∈Nn\in\mathbb{N}.

Demostración. Para n=1n=1 la desigualdad es una igualdad. Supóngase que vale para nn. Como x≥−1x\geq -1, el factor 1+x1+x es no negativo, y multiplicar la hipótesis inductiva por él conserva la desigualdad (§1.7):

(1+x)n+1=(1+x)n(1+x)≥(1+nx)(1+x)=1+(n+1)x+nx2≥1+(n+1)x,(1+x)^{n+1}=(1+x)^n(1+x)\geq(1+nx)(1+x)=1+(n+1)x+nx^2\geq 1+(n+1)x,

donde el último paso usa que nx2≥0nx^2\geq 0. ■\blacksquare

La hipótesis x≥−1x\geq -1 se usó en un solo lugar, para multiplicar la desigualdad sin invertirla, y no puede suprimirse. Con x=−3x=-3, para n=2n=2 los miembros valen 44 y −5-5, y para n=3n=3 ambos valen −8-8, de modo que la desigualdad todavía se cumple. Pero para n=5n=5 el primer miembro vale −32-32 y el segundo −14-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 ”an<an+1a_n<a_{n+1} para todo nn” sobre las sucesiones que construyeron ee, y con las cotas de los polígonos de 2n2^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∈Nn\in\mathbb{N}, sea In={k∈N:k≤n}I_n=\{k\in\mathbb{N} : k\leq n\}, el conjunto de los primeros nn naturales.

Proposición (principio del palomar). Para todo n∈Nn\in\mathbb{N}, no existe ninguna función inyectiva de In+1I_{n+1} en InI_n.

Demostración. Para n=1n=1, toda función de I2={1,2}I_2=\{1,2\} en I1={1}I_1=\{1\} asigna a ambos elementos el valor 11 y no es inyectiva. Supóngase que no existe función inyectiva de In+1I_{n+1} en InI_n, y que existiera una función inyectiva f:In+2→In+1f:I_{n+2}\to I_{n+1}. Si el valor n+1n+1 no es imagen de ningún elemento, la restricción de ff a In+1I_{n+1} es una función inyectiva de In+1I_{n+1} en InI_n, contra la hipótesis inductiva. Si f(j)=n+1f(j)=n+1 para cierto jj, sea hh la función que coincide con ff salvo que intercambia los valores en jj y en n+2n+2. Es decir, h(j)=f(n+2)h(j)=f(n+2), h(n+2)=f(j)=n+1h(n+2)=f(j)=n+1 y h(k)=f(k)h(k)=f(k) para los demás kk. La función hh sigue siendo inyectiva y solo toma el valor n+1n+1 en n+2n+2, porque ff lo tomaba solo en jj. Su restricción a In+1I_{n+1} es, entonces, una función inyectiva de In+1I_{n+1} en InI_n, otra vez contra la hipótesis. ■\blacksquare

El nombre viene de su lectura cotidiana: si n+1n+1 palomas se acomodan en nn 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 nn.


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.