6.3: Prueba por inducción matemática II

Incluso donde no hay confusión entre la inducción matemática y la 'inducción científica', los estudiantes a menudo no logran apreciar la esencia de la “prueba por inducción”. Antes de ilustrar esto, repetimos la estructura básica de tal prueba.

Un resultado matemático, o fórmula, a menudo implica un parámetro n, donde n puede ser cualquier entero positivo. En tales casos, lo que se presenta como un solo resultado, o fórmula, es una forma corta de escribir una familia infinita de resultados. La prueba de que tal resultado es correcto, por lo tanto, requiere que probemos infinitamente muchos resultados a la vez. Repetimos que nuestra única esperanza de lograr tal hazaña alucinante es

• formular el resultado declarado para cada valor de n por separado: es decir, como una declaración P (n) que depende de n;
• luego usar las manos desnudas para verificar el “comienzo”, es decir, que el caso más simple (generalmente P (1)) es cierto;
• finalmente encontrar alguna manera de demostrar que,

— en cuanto sepamos que P (k) es cierto, para algunos (desconocido)$k\ge 1$,

— podemos probar que el siguiente resultado$\mathbf{P}(k+1)$es entonces automáticamente verdadero

Entonces podemos concluir que

“toda declaración P (n) es verdadera”,

o que

“P (n) es cierto, para todos$n\ge 1$”

Problema 229 Probar la declaración:

“5 ²ⁿ⁺² — 24n — 25 es divisible por 576, para todos$\mathit{n}⩾1$”.

Cuando se trata de construir pruebas en privado, uno es libre de escribir cualquier cosa que ayude como 'trabajo rudo'. Pero el objetivo del Problema 229 es doble:

• introducir el hábito de distinguir claramente entre

  (i) la declaración P (n) para una n particular, y

  ii) la declaración a probar — es decir, “P (n) es verdadera, para todos$n\ge 1$”; y

• llamar la atención sobre el “paso de inducción” (es decir, el tercer punto de viñeta anterior), donde

  (i) suponemos que se sabe que algún P (k) no especificado es cierto, y

  ii) procurar probar que la siguiente declaración$\mathbf{P}(k+1)$debe ser entonces cierto.

La lección central para completar el “paso de inducción” es reconocer que:

para probar que$\mathbf{P}(k+1)$es verdad, hay que empezar por mirar lo que$\mathbf{P}(k+1)$dice.

En Problem 229$\mathbf{P}(k+1)$dice que

”$5^{2(k+1)+2}-24(k+1)-25$es divisible por 576”.

De ahí que se tenga que iniciar el paso de inducción con la expresión relevante

$$\begin{array}{cc}& 5^{2(k+1)+2}-24(k+1)-25,\hfill \end{array}$$

y buscar alguna manera de reorganizar esto en una forma donde se pueda usar P (k) (que suponemos que ya se sabe que es cierto, y así son de uso gratuito).

En general es una estrategia falsa trabajar al revés —por “comenzar con P (k), y luego juguetear con él para tratar de conseguir$\mathbf{P}(k+1)$”. (Esta estrategia se puede hacer para que funcione en los casos más simples; pero no funciona en general, y así es un mal hábito en el que meterse). Entonces el paso de inducción siempre debe comenzar con la hipótesis de$\mathbf{P}(k+1)$.

El siguiente problema invita a probar la fórmula para la suma de los ángulos en cualquier polígono. El resultado es bien conocido; sin embargo, estamos bastante seguros de que el lector nunca habrá visto una prueba correcta. Entonces, la intención aquí es que reconozcas el carácter básico del resultado, identifiques las fallas en lo que hasta ahora podrías haber aceptado como prueba, y tratar de encontrar alguna manera de producir una prueba general.

Problema 230 Demostrar por inducción el enunciado:

“para cada$n\ge 3$, los ángulos de cualquier n —gon en el plano tienen una suma igual a$(n-2)\pi$radianes”.

La formulación ciertamente implica un parámetro$n\ge 3$; por lo que claramente es necesario comenzar formulando el enunciado P (n). Para que la prueba tenga la oportunidad de trabajar, ¡encontrar la formulación correcta implica un giro modesto! Entonces, si te atascas, puede valer la pena revisar el primer par de líneas de la solución.

No importa cómo se formula P (n), ciertamente debes saber cómo probar la declaración P (3) (esencialmente la fórmula para la suma de los ángulos en un triángulo). Pero está lejos de ser obvio cómo probar el “paso de inducción”:

“si sabemos que P (k) es cierto para algún particular$k\ge 1$, luego$\mathbf{P}(k+1)$también debe ser cierto”.

Al abordar el paso de inducción, ¡ciertamente no podemos comenzar con P (k)! El comunicado$\mathbf{P}(k+1)$dice algo sobre polígonos con$k+1$lados: y no hay manera de obtener una típica$(k+1)$—gon jugueteando con alguna declaración sobre polígonos con k lados. (Si comienzas con un k-gon, por supuesto puedes dibujar un triángulo en un lado para obtener un$(k+1)$—gon; pero esta es una construcción muy especial, y no hay manera fácil de saber si todos$(k+1)$—gons se pueden obtener de esta manera a partir de algunos k —gon.) Todo el empuje de la inducción matemática es que siempre debemos iniciar el paso de inducción pensando en la hipótesis de$\mathbf{P}(k+1)$— es decir, en este caso, al considerar una$(k+1)$—gon y luego encontrar alguna forma garantizada de “reducirla” para hacer uso de P (k).

Los siguientes dos problemas te invitan a probar algunas identidades algebraicas clásicas. La mayoría de estos pueden ser familiares. El desafío aquí es pensar detenidamente la forma en que presenta su prueba de inducción, aprender de los ejemplos anteriores y (más tarde) aprender de las soluciones detalladas proporcionadas.

Problema 231 Probar por inducción el enunciado:

”$1+3+5+\cdots +(2\mathit{n}-1)={\mathit{n}}^2$sostiene, para todos$\mathit{n}⩾1$”

La suma en Problema 231 era conocida por los antiguos griegos. La mística tradición pitagórica (que floreció en los siglos posteriores a Pitágoras) exploró el carácter de los enteros a través de las 'figuras espaciales' que formaron. Por ejemplo, si organizamos cada entero sucesivo como una nueva línea de puntos en el plano, entonces la suma”$1+2+3+\cdots +\mathit{n}$” se puede ver que representa un número triangular. Del mismo modo, si organizamos cada número impar$2\mathit{k}-1$en la suma”$1+2+3+\cdots +\mathit{n}$” como “k -by- k reverse L-shape”, o gnomon (palabra que todavía usamos para referirnos a la pieza en forma de L que proyecta la sombra sobre un reloj de sol), luego las formas en L acumuladas construyen un cuadrado de puntos n por n - siendo el “1” el punto en la parte superior izquierda esquina de la mano, siendo el “3” la forma de L inversa de 3 puntos que convierten este “1” inicial en un cuadrado de 2 por 2, siendo el “5” la forma de L inversa de 5 puntos lo que hace que este cuadrado de 2 por 2 en un cuadrado de 3 por 3, y así sucesivamente. De ahí la suma”$1+3+5+...+(2\mathit{n}-1)$” se puede ver que representa un número cuadrado.

Hay mucho que decir de tales ilustraciones geométricas; pero no hay escapatoria del hecho de que se esconden detrás de una elipsis (los tres puntos que insertamos en la suma entre “5” y”$2\mathit{n}-1$”, que luego se resumieron al organizar las formas de L inversas terminando con las palabras “y así sucesivamente”). La prueba por inducción matemática, y su aplicación en el Problema 231, constituyen una forma formal de evitar tanto la apelación a las imágenes, como las elipsis ocultas.

Problema 232 La secuencia

$2,5,13,35,...$

se define por sus dos primeros términos${\mathit{u}}_0=2,{\mathit{u}}_1=5$, y por la relación de recurrencia:

${\mathit{u}}_{\mathit{n}+2}=$5un+1−6un.

(a) Adivina una fórmula cerrada para el n ^º término u _n.

(b) Demostrar por inducción que su suposición en (a) es correcta para todos$$n⩾0.

Problema 233 La secuencia de los números de Fibonacci

$0,1,1,2,3,5,8,13,...$

se define por sus dos primeros términos${\mathit{F}}_0=0,{\mathit{F}}_1=1$, y por la relación de recurrencia:

${\mathit{F}}_{\mathit{n}+2}={\mathit{F}}_{\mathit{n}+1}+{\mathit{F}}_{\mathit{n}}$cuando$$n⩾0.

Demostrar por inducción que, para todos$$n⩾0,

${\mathit{F}}_{\mathit{n}}=\frac{{\alpha }^{\mathit{n}}-{\beta }^{\mathit{n}}}{\sqrt{5}},$dondeα=1+52yβ=1−52

Problema 234 Demostrar por inducción que

${}^{}$52n+1·2n+2+3n+2·22n+1

es divisible por 19, para todos$$n⩾0.

Problema 235 Utilizar la inducción matemática para demostrar que cada una de estas identidades tiene, para todos$$n⩾1:

a)$1+2+3+\cdots +\mathit{n}=\frac{\mathit{n}(\mathit{n}+1)}{2}$

b)$\frac{1}{1·2}+\frac{1}{2·3}+\frac{1}{3·4}+\cdots +\frac{1}{\mathit{n}(\mathit{n}+1)}=1-\frac{1}{\mathit{n}+1}$

c)$1+\mathit{q}+{\mathit{q}}^2+{\mathit{q}}^3+\cdots +{\mathit{q}}^{\mathit{n}-1}=\frac{1}{1-\mathit{q}}-\frac{{\mathit{q}}^{\mathit{n}}}{1-\mathit{q}}$

d)$0·0!+1·1!+2·2!+\cdots +(\mathit{n}-1)·(\mathit{n}-1)!=\mathit{n}!-1$

(e)$($cosθ+ipecadoθ)n=cosnθ+ipecadonθ.

Problema 236 Demostrar por inducción el enunciado:

”$(1+2+3+\cdots +\mathit{n}{)}^2=1^3+2^3+3^3+\cdots +{\mathit{n}}^3$, para todos$\mathit{n}⩾1$”.

Ahora sabemos que, para todos$$n⩾1:

$1+1+1+\cdots +1($ntérminos)=n.

Y si sumamos estas “salidas” (es decir, los primeros n números naturales), obtenemos el n ^º número triangular:

$1+2+3+\cdots +\mathit{n}=\frac{\mathit{n}(\mathit{n}+1)}{2}={\mathit{T}}_{\mathit{n}}$.

El siguiente problema invita a encontrar la suma de estas “salidas”: es decir, encontrar la suma de los primeros n números triangulares.

Problema 237

a) Experimentar y adivinar una fórmula para la suma de los primeros n números triangulares:

${\mathit{T}}_1+{\mathit{T}}_2+{\mathit{T}}_3+\cdots +{\mathit{T}}_{\mathit{n}}=1+3+6+\cdots +\frac{\mathit{n}(\mathit{n}+1)}{2}.$

(b) Demostrar por inducción que su fórmula adivinada es correcta para todos$$n⩾1.

A Ahora conocemos fórmulas cerradas para

”$1+2+3+\cdots +\mathit{n}$”

y para

”$1·2+2·3+3·4+\cdots +(\mathit{n}-1)\mathit{n}$”.

El siguiente problema sugiere en primer lugar que estas identidades son parte de algo más general, y en segundo lugar que estos resultados nos permiten encontrar identidades para la suma de los primeros n cuadrados:

$1^2+2^2+3^2+\cdots +{\mathit{n}}^2$

para los primeros n cubos:

$1^3+2^3+3^3+\cdots +{\mathit{n}}^3$

y así sucesivamente.

Problema 238

a) Obsérvese que$\mathrm{}$

$1·2+2·3+3·4+\cdots +\mathit{n}(\mathit{n}+1)=1·(1+1)+2·(2+1)+3·(3+1)+\cdots +\mathit{n}·(\mathit{n}+1)$.

Usa esto y el resultado del Problema 237 para derivar una fórmula para la suma:${\mathrm{}}^{}$

$1^2+2^2+3^2+\cdots +{\mathit{n}}^2$.

b) Adivina y prueba una fórmula para la suma

$1·2·3+2·3·4+3·4·5+\cdots +(\mathit{n}-2)(\mathit{n}-1)\mathit{n}$.

Use esto para derivar una fórmula cerrada para la suma:

$1^3+2^3+3^3+\cdots +{\mathit{n}}^3$.

Puede que se requiera un poco de esfuerzo para digerir la declaración en el siguiente problema. Se extiende la idea detrás del “método de coeficientes indeterminados” que se discute en la Nota 2 a la solución del Problema 237 (a).

Problema 239

a) Dado$\mathit{n}+1$números reales distintos

${\mathit{a}}_0,{\mathit{a}}_1,{\mathit{a}}_2\mathrm{,\; ...\; ,}{\mathit{a}}_{\mathit{n}}$

encontrar todos los polinomios posibles de grado n que satisfagan

$$fa0=fa1=fa2=⋯=fan−1=0,fan=b

para algún número especificado b.

b) Por cada$$n⩾1, acreditar la siguiente declaración:

Dados dos conjuntos etiquetados de$\mathit{n}+1$números reales

${\mathit{a}}_0,{\mathit{a}}_1,{\mathit{a}}_2\mathrm{,...},{\mathit{a}}_{\mathit{n}}$,

y

${\mathit{b}}_0,{\mathit{b}}_1,{\mathit{b}}_2,...,{\mathit{b}}_{\mathit{n}}$,

donde el a _i son todos distintos (pero el b no necesita serlo), existe un polinomio f _n de grado n, tal que

$$fna0=b0,fna1=b1,fna2=b2,...,fnan=bn.

Terminamos esta subsección con una bolsa mixta de tres problemas de inducción bastante diferentes. En el primer problema el paso de inducción implica una construcción sencilla de un tipo que nos encontraremos más adelante.

Problema 240 Un país tiene sólo monedas de 3 centavos y 4 centavos.

a) Experimentar para decidir cuál parece ser la mayor cantidad, N centavos, que no se puede pagar directamente (sin recibir cambio).

b) Demostrar por inducción que “n centavos pueden ser pagados directamente por cada$\mathit{n}>\mathit{N}$”.

Problema 241

a) Resolver la ecuación$\mathit{z}+\frac{1}{\mathit{z}}=1$. Calcular${\mathit{z}}^2$, y comprobar que${\mathit{z}}^2+\frac{}{}$1z2también es un número entero.

b) Resolver la ecuación$\mathit{z}+\frac{1}{\mathit{z}}=2$. Calcular${\mathit{z}}^2+\frac{}{}$1z2, y comprobar que${\mathit{z}}^2+\frac{}{}$1z2también es un número entero.

(c) Resolver la ecuación$\mathit{z}+\frac{1}{\mathit{z}}=3$. Calcular${\mathit{z}}^2+\frac{}{}$1z2, y comprobar que${\mathit{z}}^2+\frac{}{}$1z2también es un número entero.

d) Resolver la ecuación$\mathit{z}+\frac{1}{\mathit{z}}=\mathit{k}$, donde k es un número entero. Calcular z ², y comprobar que${\mathit{z}}^2+\frac{}{}$1z2también es un número entero.

(e) Demostrar que si un número z tiene el bien que$z+\frac{1}{z}$es un número entero, entonces${\mathit{z}}^{\mathit{n}}+\frac{}{}$1znes también un número entero para cada$$n⩾1.

Problema 242 Deja que p sea cualquier número primo. Utilice la inducción para probar:

”${\mathit{n}}^{\mathit{p}}-\mathit{n}$es divisible por p para todos$\mathit{n}⩾1$”.