6.10: Comentarios y soluciones

Nota: Es importante separar la idea subyacente de “inducción” de la forma formal que hemos elegido para presentar pruebas. Como siempre en matemáticas, las ideas son lo que más importa. Pero el proceso de luchar con (y poco a poco llegar a entender por qué necesitamos) la estructura formal detrás de las pruebas escritas es parte de la forma en que se doman y organizan las ideas.

Los lectores no deben dejarse intimidar por la extensión física de las soluciones a este capítulo. Como se explica en el texto principal, es importante que todos los lectores revisen la forma en que abordan las pruebas de inducción: así nos hemos equivocado a favor de la integridad —sabiendo que a medida que cada lector se vuelve más seguro, va a comprimir cada vez más, o abreviar, algunos de los pasos.

228.

a) Sí.

b) Sí.

$$2\times 3\times 5\times 7\times 11+1=2311,y$ \sqrt{2311}=48.07...$,\; por\; lo\; que\; solo\; necesitamos\; verificar\; los\; factores\; primos\; hasta$ 47$.$$

c) No.

$$2\times 3\times 5\times 7\times 11\times 13+1=30031,$$

y$\sqrt{30031}=173.29...$así que tal vez tengamos que verificar todos$40$posibles factores primos hasta$173$. Sin embargo, sólo tenemos que empezar en$17$[¿Por qué?] , y verificar con una calculadora es muy rápido. De hecho$30031$factoriza bastante bonitas como$59\times 509$.

229. Nota: El enunciado en el problema incluye el cuantificador “para todos$n\ge 1$”.

Lo que hay que probar es la declaración compuesta

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

Por el contrario, cada declaración individual$P(n)$se refiere a un único valor de n.

Es esencial tener claro cuando se trata de la declaración compuesta, y cuando se está refiriendo a alguna declaración en particular$P(1)$, o$P(n)$, o$P(k)$.

Let$P(n)$ser la declaración:

”$5^{2n+2}-24n-25$es divisible por$576$”.

•$P(1)$es la declaración:

”$5^4-24\times 1-25$es divisible por$576$”.

Es decir:

”$625-49=576$es divisible por$576$”,

lo que evidentemente es cierto.

• Ahora supongamos que sabemos$P(k)$es cierto para algunos$k\ge 1$. Debemos demostrar que$P(k+1)$es entonces también cierto.

Para probar que$P(k+1)$es verdad, tenemos que considerar la afirmación$P(k+1)$. No sirve de nada comenzar con$P(k)$. Sin embargo, ya que sabemos que$P(k)$) es verdad, somos libres de usarlo en cualquier etapa si resulta útil.

Para probar que$P(k+1)$es verdad, tenemos que demostrar que

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

Entonces debemos comenzar con$5^{2(k+1)+2}-24(k+1)-25$y tratar de “simplificarlo” (sabiendo que “simplificar” en este caso significa “reescribirlo de una manera que implique${}^{}$52k+2−24k−25”).

$\begin{array}{c}{5}^{2(k+1)+2}-24(k+1)-25\hfill \\ \hfill & =\left[5^{2k+4}\right]-24k-24-25\hfill \\ \hfill & =[5^2(5^{2k+2}-24k-25)+5^2\cdot \left(24k\right)+5^2\cdot 25]\hfill \\ \hfill & -24k-(24+25)\hfill \\ \hfill & =5^2(5^{2k+2}-24k-25)+[(5^2-1)\times \left(24k\right)]\hfill \\ \hfill & +[5^2\times 25-24-25]\hfill \\ \hfill & =5^2(5^{2k+2}-24k-25)+24^{2}k+[5^2\times 25-24-25]\hfill \\ \hfill & =5^2(5^{2k+2}-24k-25)+24^{2}k+[5^4-24-25].\hfill \end{array}$

El primer término en el RHS es un múltiplo de$({}^{}$52k+2−24k−25), por lo que es divisible por$576$(ya que sabemos que P (k) es cierto); el segundo término sobre el RHS es un múltiplo de 24 ² = 576; y el tercer término sobre el RHS es la expresión que surge en P (1), que vimos es igual a 576.

$\equiv$todo el RHS es divisible por$576$

$\equiv$el LHS es divisible por$576$, entonces$P(k+1)$es verdad.

De ahí

• $P(1)$es verdad; y
• siempre que$P(k)$es cierto para algunos$k\ge 1$, hemos demostrado que$P(k+1)$debe ser verdad.

$\equiv$ $P(n)$es cierto para todos$n\ge 1$.

230. Let$P(n)$ser la declaración:

“los ángulos de cualquier p -gon, para cualquier valor de p con$3\le p\le n$, tienen suma exactamente$(p-2)\pi$radianes”.

1. $P(3)$es la declaración:

   “los ángulos de cualquier triángulo tienen suma$\pi$radianes”.

   Esto es un hecho conocido: dado triángulo ΔABC, dibujar la línea$$XAYa través de A paralelo a$BC$, con X en el mismo lado de$AC$como B e Y en el mismo lado de$AB$como C. Entonces$\angle XAB=\angle CBA$y$\angle YAC=\angle BCA$(ángulos alternos), entonces

   $$\angle B+\angle A+\angle C=\angle XAB+\angle A+\angle YAC=\angle XAY=\pi .$$
2. Ahora suponemos que$P(k)$se sabe que es cierto para algunos$k\ge 3$. Debemos demostrar que$P(k+1)$es entonces necesariamente cierto.

Para probar que$P(k+1)$es verdad, tenemos que considerar la afirmación$P(k+1)$: es decir,

“los ángulos de un p -gon, para cualquier valor de p con$3\le p\le k+1$, tienen suma exactamente$(p-2)\pi$radianes”

Esto se puede reformular dividiéndolo en dos partes:

“los ángulos de cualquier p -gon para$3\le p\le k$tener suma exactamente$(p-2)\pi$radianes;”

y

“los ángulos de cualquier (k + 1) -gon tienen suma exactamente$((k+1)-2)\pi$radianes”.

La primera parte de esta versión revisada es precisamente la declaración$P(k)$, lo que suponemos se sabe que es cierto. Entonces el quid de la materia es probar la segunda parte —es decir, que los ángulos de cualquier (k + 1) -gon tienen suma$(k-1)\pi$.

Let$A_0{A}_1{A}_2\cdots A_k$ser cualquier (k + 1) -gon.

[Nota: El movimiento habitual en este punto es decir “dibujar el acorde$$AkA1para cortar el polígono en el triángulo$$AkA1A0(con suma de ángulo$\pi$(por$P(3)$), y el k -gon$A_1{A}_2\cdots A_k$(con suma de ángulo$(k-2)\pi$(por$P(k)$), de donde podemos agregar para ver que$A_0{A}_1{A}_2\cdots A_k$tiene suma de ángulo$((k+1)-2)\pi$. Sin embargo, esto solo funciona

• si el triángulo$$AkA1A0“sobresale” en lugar de entrar, y

Entonces, lo que suele presentarse como una “prueba” no funciona en general.

Si queremos probar el resultado general —para polígonos de todas las formas— tenemos que sortear esta suposición injustificada. Experimento puede persuadirte de que “siempre hay algún vértice que sobresale y que se puede “cortar” con seguridad; pero no está nada claro cómo probar este hecho (no conocemos ninguna prueba simple). Entonces tenemos que encontrar otra manera.]

Considera el vértice$A_1$, y sus dos vecinos$A_0$y$A_2$.

Imagina cada media línea, que comienza en$A_1$, y que se desencadene en el interior del polígono. Debido a que el polígono es finito, cada media línea define un segmento de línea$\underset{¯}{A_{1}X}$, donde X es el siguiente punto del polígono que golpea la media línea (es decir, X es uno de los vértices$A_m$, o un punto en uno de los lados$\underset{}{}$AmAm+1¯).

Considere el lugar geométrico de todos los puntos X ya que la media línea oscila desde$\underset{¯}{A_1{A}_0}$(producido) a$\underset{¯}{A_1{A}_2}$(producido). Hay dos posibilidades:

(a) todos estos puntos X pertenecen a un solo lado del polígono; o

(b) no lo hacen.

(a) En el primer caso ninguno de los vértices o lados del polígono$A_0{A}_1{A}_2\cdots A_k$entrometerse en el interior del triángulo$$A0A1A2, por lo que el acorde$\underset{¯}{A_0{A}_2}$separa el (k + 1) -gon$A_0{A}_1{A}_2\cdots A_k$en un triángulo$$A0A1A2y a k -gon$A_0{A}_2{A}_3\cdots A_k$. La suma del ángulo de$A_0{A}_1{A}_2\cdots A_k$es entonces igual a la suma de (i) la suma del ángulo del triángulo$$A0A1A2y ii) la suma angular de$A_0{A}_2{A}_3\cdots A_k$— que son iguales a$\pi$y$(k-2)\pi$respectivamente (por$P(k)$). Entonces, la suma del ángulo del (k + 1) -gon$A_0{A}_2{A}_3\cdots A_k$es igual a$((k+1)-2)\pi$según sea necesario.

b) En el segundo caso, como la media línea$$A1Xgira desde$$A1A0a$$A1A2, el punto X debe cambiar en algún instante de estar acostado en un lado del polígono a estar en otro lado; en el mismo instante en que X cambia de lado,$X=A_m$debe ser un vértice del polígono.

Por la forma en que se eligió el punto X, el acorde$\underset{¯}{A_{1}X}=\underset{¯}{A_1{A}_m}$no cumple con ningún otro punto del (k + 1) -gon$A_0{A}_1{A}_2\cdots A_k$, y así divide el (k + 1) -gon en un m -gon$A_1{A}_2{A}_3\cdots A_m$(con suma de ángulo$(m-2)\pi$por$P(k)$) y a (k - m + 3) -gon$$AmAm+1Am+2⋯AkA0A1(con suma de ángulo$(k-m+1)\pi$por$P(k)$). Entonces el (k + 1) -gon$A_0{A}_1{A}_2\cdots A_k$tiene suma de ángulo$((k+1)-2)\pi$según sea necesario.

De ahí$P(k+1)$es verdad.

$\therefore$ $P(n)$es cierto para todos$n\ge 3$.

231. Let$P(n)$ser la declaración$$1$$$$+3+5+\cdots +(2n-1)=n^2$$

• LHS de$P(1)=1$; RHS de$P(1)=1^2$. Dado que estos dos son iguales,$P(1)$es verdad.
• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

  $$1+3+5+\cdots +(2k-1)=k^2$$.

  Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

  Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$:

  $\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & 1+3+5+...+\left(2\right(k+1)-1)\hfill \\ \hfill & =\hfill & (1+3+5+...+(2k-1\left)\right)+(2k+1).\hfill \end{array}$

  Si ahora usamos$P(k)$, lo que suponemos que es cierto, entonces el primer paréntesis es igual a k ², por lo que esta suma es igual a:

  $\begin{array}{ccc}\hfill & =\hfill & k^2+(2k+1)\hfill \\ \hfill & =\hfill & {(k+1)}^2\hfill \\ \hfill & =\hfill & \text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$

  De ahí$P(k+1)$sostiene.

Combinar estas dos viñetas muestra entonces que”$P(n)$sostiene, para todos$n\ge 1$”.

232.

(a) La única manera de aprender es intentando y fallando; luego intentándolo de nuevo y fallando un poco mejor! Así que no te rindas demasiado rápido. Es natural tratar de relacionar cada término con el anterior. Entonces podrá notar que cada término es ligeramente inferior a 3 veces el término anterior.

b) Nota: La relación de recurrencia para$u_n$involucra los dos términos anteriores. Entonces, cuando asumimos que$P(k)$se sabe que es verdad y tratar de probar$P(k+1)$, la relación de recurrencia para$u_{k+1}$implicará$u_k$y$u_{k-1}$, entonces$P(n)$necesita ser formulado para asegurar que podamos usar expresiones cerradas para ambos términos. Por la misma razón, la prueba de inducción tiene que comenzar demostrando que ambos$P(0)$y$P(1)$son ciertas.

Let$P(n)$ser la declaración:

”$u_m=2^m+3^m$para todos los m,$0\le m\le n$”.

• LHS de$P(0)=u_0=2$; RHS de$P(0)=2^0+3^0=1+1$. Dado que estos dos son iguales,$P(0)$es verdad.

  $P(1)$combina$P(0)$, y la igualdad de$u_1=5$y$2^1+3^1$; dado que estos dos son iguales,$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

  ”$u_m=2^m+3^m$para todos los m,$0\le m\le k$.”

  Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

  Ahora$P(k+1)$requiere que probemos que

  ”$u_m=2^m+3^m$para todos los m,$0\le m\le k+1$.”

  La mayor parte de esto está garantizado por$P(k)$, lo que suponemos que es cierto. Nos queda comprobar que la igualdad se mantiene para$u_{k+1}$. Sabemos que

  $$u_{k+1}=5u_k-6u_{k-1}.$$

  Y podemos usar$P(k)$), lo que suponemos que es cierto, para concluir que:

  $\begin{array}{ccc}{u}_{k+1}\hfill & =\hfill & 5(2^k+3^k)-6(2^{k-1}+3^{k-1})\hfill \\ \hfill & =\hfill & (10-6)2^{k-1}+(15-6)3^{k-1}\hfill \\ \hfill & =\hfill & 2^{k+1}+3^{k+1}.\hfill \end{array}$

  De ahí$P(k+1)$sostiene.

Combinar estas dos viñetas muestra entonces que”$P(n)$sostiene, para todos$n\ge 0$”.

233. Let$P(n)$ser la declaración:

”$F_m=\frac{{\alpha }^m-{\beta }^m}{\sqrt{5}}$para todos los m,$0\le m\le n$”,

donde$\alpha =\frac{1+\sqrt{5}}{2}$y$\beta =\frac{1-\sqrt{5}}{2}$.

• LHS de$P(0)=F_0=0$; RHS de$P(0)=\frac{1-1}{\sqrt{5}}=0$. Dado que estos dos son iguales,$P(0)$es verdad.

  LHS de$P(1)=F_1=1$; RHS de$P(1)=\frac{\alpha -\beta }{\sqrt{5}}=1$. Dado que estos dos son iguales,$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

  ”$F_m=\frac{{\alpha }^m-{\beta }^m}{\sqrt{5}}$para todos los m,$0\le m\le k$.”

  Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

  Ahora$P(k+1)$requiere que probemos que

  ”$F_m=\frac{{\alpha }^m-{\beta }^m}{\sqrt{5}}$para todos los m,$0\le m\le k+1$.”

  La mayor parte de esto está garantizado por$P(k)$, lo que suponemos que es cierto. Queda por verificar esto para$F_{k+1}$. Sabemos que

  $$F_{k+1}=F_k+F_{k-1}.$$

  Y podemos usar$P(k)$, lo que suponemos que es cierto para concluir que:

  $\begin{array}{ccc}{F}_{k+1}\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{{\alpha }^k-{\beta }^k}{\sqrt{5}}+\genfrac{}{}{0.1ex}{}{{\alpha }^{k-1}-{\beta }^{k-1}}{\sqrt{5}}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{{\alpha }^k+{\alpha }^{k-1}}{\sqrt{5}}-\genfrac{}{}{0.1ex}{}{{\beta }^k+{\beta }^{k-1}}{\sqrt{5}}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{{\alpha }^{k+1}-{\beta }^{k+1}}{\sqrt{5}}\hfill \end{array}$

  (ya que$\alpha$y$\beta$son las raíces de la ecuación$x^2-x-1=0$) Por lo tanto$P(k+1)$sostiene.

Combinar estas dos viñetas muestra entonces que”$P(n)$sostiene, para todos$n\ge 1$”.

Nota: Puede comprender la solución anterior y, sin embargo, preguntarse cómo podría descubrirse tal fórmula. La respuesta es bastante simple. Existe una teoría general sobre las relaciones de recurrencia lineal que garantiza que el conjunto de todas las soluciones de una recurrencia de segundo orden (es decir, una recurrencia en la que cada término depende de los dos términos anteriores) es “bidimensional” (es decir, es igual que el plano 2D familiar, donde cada vector (p , q) es una combinación de los dos “vectores base” (1, 0) y (0, 1):

$$(p,q)=p(1,0)+q(0,1)).$$

Una vez que sabemos esto, queda:

• para encontrar dos soluciones especiales (como los vectores (1, 0) y (0, 1) en el plano), lo que hacemos aquí buscando secuencias de la forma”$1,x,x^2,x^3,...$” que satisfagan la recurrencia, lo que implica que$1+x=x^2$, entonces$x=\alpha$, o$x=\beta$;
• a continuación, elegir una combinación lineal$F_m=$pαm+qβmde estas dos soluciones de potencia para dar los primeros dos términos correctos:$0=F_0=p+q$,$1=F_1=p\alpha +q\beta$, entonces$p=\frac{1}{\sqrt{5}}$,$q=-\frac{1}{\sqrt{5}}$.

234. Let$P(n)$ser la declaración:

”$5^{2n+1}·2^{n+2}+3^{n+2}·2^{2n+1}$es divisible por$19$”.

• $P(0)$es la declaración:”$5\times 4+9\times 2$es divisible por 19”, lo cual es cierto.
• Ahora supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 0$. Debemos demostrar que$P(k+1)$es entonces también cierto.
• Para probar que$P(k+1)$es verdad, tenemos que demostrar que

  ”$5^{2k+3}·2^{k+3}+3^{k+3}·2^{2k+3}$es divisible por$19$”.

  $\begin{array}{ccc}{5}^{2k+3}\cdot 2^{k+3}+3^{k+3}\cdot 2^{2k+3}\hfill & =\hfill & 5^2\cdot 2(5^{2k+1}\cdot 2^{k+2}+3^{k+2}\cdot 2^{2k+1})\hfill \\ \hfill & \hfill & -5^2\cdot 2\cdot 3^{k+2}\cdot 2^{2k+1}+3^{k+3}\cdot 2^{2k+3}\hfill \\ \hfill & =\hfill & 5^2\cdot 2\cdot (5^{2k+1}\cdot 2^{k+2}+3^{k+2}\cdot 2^{2k+1})\hfill \\ \hfill & \hfill & -(5^2-3\cdot 2)3^{k+2}\cdot 2^{2k+2}.\hfill \end{array}$

  El paréntesis en el primer término sobre el RHS es divisible por 19 (por$P(k)$), y el paréntesis en el segundo término es igual a 19. De ahí que ambos términos en el RHS sean divisibles por 19, por lo que el RHS es divisible por 19. Por lo tanto, el LHS también es divisible por 19, entonces$P(k+1)$es verdad.

$\therefore$ $P(n)$es cierto para todos$n\ge 0$.

235.

Nota: Las pruebas de identidades como las del Problema 235., que se dan en muchos textos introductorios, ignoran las lecciones de los dos problemas anteriores. En particular,

• a menudo no logran distinguir entre

— la declaración única$P(n)$para una n particular, y

— el resultado “cuantificado” a probar (“para todos$n\ge 1$”),

y

• proceden en la dirección “equivocada” (por ejemplo, comenzando con la identidad$P(n)$y “añadiendo lo mismo a ambos lados”).

Esta última estrategia es psicológica y didácticamente engañosa —aunque puede justificarse lógicamente a la hora de demostrar identidades muy simples. En estos casos muy sencillos, cada enunciado$P(n)$a probar es inusual en el sentido de que se refiere exactamente a una configuración, o ecuación, para cada$n$. Y como hay exactamente una configuración por cada n, la configuración o identidad para$k+1$a menudo se puede obtener jugueteando con la configuración para k. En contraste, en el Problema 230., para cada valor de n, existe una desconcertante variedad de posibles polígonos con n vértices, que van desde polígonos regulares hasta las formas reentrantes más enrevesadas: la declaración$P(n)$hace una afirmación sobre todas esas configuraciones, y no hay manera de saber si podemos obtener todas esas configuraciones para$k+1$de manera uniforme jugueteando con alguna configuración para k.

Los lectores deben tratar de escribir cada prueba con el espíritu pretendido, y aprender de las soluciones —ya que este estilo ha sido elegido para resaltar de qué se trata realmente la inducción matemática, y es este enfoque el que se necesita en aplicaciones serias.

(a) Dejar$P(n)$ser la declaración:

”$1+2+3+\cdots +n=\frac{n(n+1)}{2}$”.

• LHS de$P(1)=1$; RHS de$P(1)=\frac{1·(1+1)}{2}=1$. Dado que estos dos son iguales,$P(1)$es verdad.
• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

  ”$1+2+3+\cdots +k=\frac{k(k+1)}{2}$”.

  Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

  Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$):

  $\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & 1+2+3+\cdots +k+(k+1)\hfill \\ \hfill & =\hfill & (1+2+3+\cdots +k)+(k+1).\hfill \end{array}$

  Si ahora usamos$P(k)$, lo que suponemos que es cierto, entonces el primer paréntesis es igual a$\frac{k(k+1)}{2}$, por lo que la suma completa es igual a:

  $\begin{array}{ccc}\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{k(k+1)}{2}+(k+1)\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{(k+1)(k+2)}{2}\hfill \\ \hfill & =\hfill & \text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$

  De ahí$P(k+1)$sostiene.

  Si combinamos estas dos viñetas, entonces hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

b) Dejar$P(n)$ser la declaración:

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

• LHS de$P(1)=\frac{1}{1·2}=\frac{1}{2}$; RHS de$P(1)=1-\frac{1}{2}=\frac{1}{2}$. Dado que estos dos son iguales,$P(1)$es verdad.
• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

  ”$\frac{1}{1·2}+\frac{1}{2·3}+\frac{1}{3·4}+\cdots +\frac{1}{k·(k+1)}=1-\frac{1}{k+1}$”.

  Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

  Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$:

  $\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1\cdot 2}+\genfrac{}{}{0.1ex}{}{1}{2\cdot 3}+\genfrac{}{}{0.1ex}{}{1}{3\cdot 4}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(k+1)(k+2)}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{1\cdot 2}+\genfrac{}{}{0.1ex}{}{1}{2\cdot 3}+\genfrac{}{}{0.1ex}{}{1}{3\cdot 4}+\genfrac{}{}{0.1ex}{}{1}{k(k+1)}]\hfill \\ \hfill & \hfill & +\genfrac{}{}{0.1ex}{}{1}{(k+1)(k+2)}.\hfill \end{array}$

  Si ahora usamos$P(k)$, que suponemos que es cierto, entonces el primer paréntesis es igual a$1-\frac{1}{k+1}$, por lo que la suma completa es igual a:

  $\begin{array}{ccc}\hfill & =\hfill & [1-\genfrac{}{}{0.1ex}{}{1}{k+1}]+\genfrac{}{}{0.1ex}{}{1}{(k+1)(k+2)}\hfill \\ \hfill & =\hfill & 1-[\genfrac{}{}{0.1ex}{}{1}{k+1}-\genfrac{}{}{0.1ex}{}{1}{(k+1)(k+2)}]\hfill \\ \hfill & =\hfill & 1-\genfrac{}{}{0.1ex}{}{1}{k+2}\hfill \\ \hfill & =\hfill & \text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$

  De ahí$P(k+1)$sostiene.

  Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

c) Nota: Si$q=1$, entonces el LHS es igual a n, pero el RHS no tiene sentido. Entonces asumimos$q\ne 1$.

Let$P(n)$ser la declaración:

”$1+q+q^2+q^3+\cdots +q^{n-1}=\frac{1}{1-q}-\frac{q^n}{1-q}$”.

• LHS de$P(1)=1$; RHS de$P(1)=\frac{1}{1-q}-\frac{q}{1-q}=1$. Dado que estos dos son iguales,$P(1)$es verdad.
• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

  ”$1+q+q^2+q^3+\cdots +q^{k-1}=\frac{1}{1-q}-\frac{q^k}{1-q}$”.

  Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$:

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & 1+q+q^2+q^3+\cdots +q^k\hfill \\ \hfill & =\hfill & (1+q+q^2+q^3+\cdots +q^{k-1})+q^k.\hfill \end{array}$

Si ahora usamos$P(k)$, que suponemos que es cierto, entonces el primer paréntesis es igual a

$$\frac{1}{1-q}-\frac{q^k}{1-q}$$

por lo que la suma completa es igual a:

$\begin{array}{ccc}\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1-q}-[\genfrac{}{}{0.1ex}{}{q^k}{1-q}-q^k]\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1-q}-\genfrac{}{}{0.1ex}{}{q^{k+1}}{1-q}\hfill \\ \hfill & =\hfill & \text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$

De ahí$P(k+1)$sostiene.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

d) Nota: La declaración a probar inicia con un término que involucra “¡0!”. La definición

$$n!=1\times 2\times 3\times \cdots \times n$$

no nos dice de inmediato cómo interpretar”$0!$”. La correcta interpretación surge del hecho de que varios pensamientos diferentes apuntan todos en la misma dirección.

(i) Cuando$n>0$, luego para obtener de$n!$a$(n+1)!$multiplicamos por (n + 1). Si extendemos esto a$n=0$, luego “para obtener de$0!$a$1!$, tenemos que multiplicar por 1” — lo que sugiere que$0!=1$.

ii) Cuando$n>0$,$n!$cuenta el número de permutaciones de n símbolos, o el número de diferentes órdenes lineales de n objetos (es decir, cuántas formas diferentes se pueden organizar en una línea). Si extendemos esto a$n=0$, vemos que solo hay una manera de organizar 0 objetos (es decir, sentarse apretado y no hacer nada).

iii) La definición de$n!$como un producto sugiere que$0!$implica un “producto sin términos” en absoluto. Ahora cuando “no sumamos términos juntos” tiene sentido interpretar el resultado como “= 0” (quizás porque si esta “suma de no términos” se agregara a alguna otra suma, no haría ninguna diferencia). En el mismo espíritu, el producto de ningún término debe tomarse como “= 1” (ya que si este producto vacío se incluyera al final de algún otro producto, no haría diferencia en el resultado).

Let$P(n)$ser la declaración:

”$0·0!+1·1!+2·2!+\cdots +(n-1)·(n-1)!=n!-1$”.

• LHS de$P(1)=0·0!=0$; RHS de$P(1)=1!-1=0$. Dado que estos dos son iguales,$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

”$0·0!+1·1!+2·2!+\cdots +(k-1)·(k-1)!=k!-1$”.

Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$):

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & 0\cdot 0!+1\cdot 1!+2\cdot 2!+\cdots +k\cdot k!\hfill \\ \hfill & =\hfill & [0\cdot 0!+1\cdot 1!+2\cdot 2!+\cdots +(k-1)\cdot (k-1)!]+k.k!.\hfill \end{array}$

Si ahora usamos$P(k)$, que suponemos que es cierto, entonces el primer paréntesis es igual a$k!-1$, por lo que la suma completa es igual a:$\begin{array}{ccc}\hfill & =\hfill & (k!-1)+k\cdot k!\hfill \\ \hfill & =\hfill & (k+1)\cdot k!-1\hfill \\ \hfill & =\hfill & (k+1)!-1=\text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$De ahí$P(k+1)$sostiene.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

e) Dejar$P(n)$ser la declaración:

”${(}^{}$cosθ+ipecadoθ)n=cosnθ+ipecadonθ”

• LHS de$P(1)={(}^{}$cosθ+ipecadoθ)1; RHS de$P(1)=$cosθ+ipecadoθ. Dado que estos dos son iguales,$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

”${(}^{}$cosθ+ipecadoθ) k =coskθ+ipecadokθ”.

Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$:$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & {(\cos \theta +i\mathrm{pecado}\theta )}^{k+1}\hfill \\ \hfill & =\hfill & {(\cos \theta +i\mathrm{pecado}\theta )}^k(\cos \theta +i\mathrm{pecado}\theta ).\hfill \end{array}$Si ahora usamos$P(k)$, que suponemos que es cierto, entonces el primer paréntesis es igual a$($coskθ+ipecadokθ), por lo que la expresión completa es igual a:

$\begin{array}{cc}=\hfill & (\cos k\theta +i\mathrm{pecado}k\theta )(\cos \theta +i\mathrm{pecado}\theta )\hfill \\ =\hfill & [\cos k\theta \cdot \cos \theta -\mathrm{pecado}k\theta \cdot \mathrm{pecado}\theta ]+i[\cos k\theta \cdot \mathrm{pecado}\theta +\mathrm{pecado}k\theta \cdot \cos \theta ]\hfill \\ =\hfill & \cos (k+1)\theta +i\mathrm{pecado}(k+1)\theta =\text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$De ahí$P(k+1)$sostiene.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

236. Let$P(n)$ser la declaración:

”${(1+2+3+\cdots +n)}^2=1^3+2^3+3^3+\cdots +n^3$”.

• LHS de$P(1)=1^2$; RHS de$P(1)=1^3$. Dado que estos dos son iguales,$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

”${(1+2+3+\cdots +k)}^2=1^3+2^3+3^3+\cdots +k^3$”.

Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Ahora$P(k+1)$es una ecuación, así que empezamos con un lado de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el otro lado de$P(k+1)$. En esta instancia, el RHS de$P(k+1)$es el punto de partida más prometedor (porque conocemos una fórmula para${}^{}$kthnúmero triangular, y así se puede ver cómo simplificarlo):$\begin{array}{ccc}\text{RHS de}\mathbf{P}(k+1)\hfill & =\hfill & 1^3+2^3+3^3+\cdots +k^3+{(k+1)}^3\hfill \\ \hfill & =\hfill & [1^3+2^3+3^3+\cdots +k^3]+{(k+1)}^3.\hfill \end{array}$

Si ahora usamos$P(k)$, que suponemos que es cierto, entonces el primer paréntesis es igual a

$${(1+2+3+\cdots +k)}^2,$$

por lo que el RHS completo es:$\begin{array}{cc}=\hfill & {(1+2+3+\cdots +k)}^2+{(k+1)}^3\hfill \\ =\hfill & {\left[\genfrac{}{}{0.1ex}{}{k(k+1)}{2}\right]}^2+{(k+1)}^3\hfill \\ =\hfill & \genfrac{}{}{0.1ex}{}{1}{4}{(k+1)}^2[k^2+4k+4]\hfill \\ =\hfill & {\left[\genfrac{}{}{0.1ex}{}{(k+1)(k+2)}{2}\right]}^2\hfill \\ =\hfill & {(1+2+3+\cdots +(k+1\left)\right)}^2\hfill \\ =\hfill & \text{LHS de}\mathbf{P}(k+1).\hfill \end{array}$De ahí$P(k+1)$sostiene.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

Nota: A veces puede ser útil una forma ligeramente diferente de organizar la prueba. Denote los dos lados de la ecuación en la declaración$P(n)$por$f(n)$y$g(n)$respectivamente. Entonces

•$f(1)=1^2=1^3=g(1)$; y

• álgebra simple permite verificar eso, para cada$k\ge 1$,

$$f(k+1)-f(k)={(k+1)}^3=g(k+1)-g(k).$$

A continuación se deduce (por inducción) que$f(n)=g(n)$para todos$n\ge 1$.

237.

(a)$T_1=1$,$T_1+T_2=1+3=4$,$T_1+T_2+T_3=1+3+6=10$. Estos pueden no ser muy sugerentes. Pero

$$T_1+T_2+T_3+T_4=20=5\times 4,$$ $$T_1+T_2+T_3+T_4+T_5=35=5\times 7,$$

y

$$T_1+T_2+T_3+T_4+T_5+T_6=56=7\times 8$$

eventualmente puede llevar a uno a adivinar que

$$T_1+T_2+T_3+\cdots +T_n=\frac{n(n+1)(n+2)}{6}.$$

Nota 1: Esto sin duda será más fácil de adivinar si recuerdas lo que encontraste en Problema 17. y Problema 63.

Nota 2: Hay otra manera de ayudar en ese tipo de adivinanzas. Supongamos que nota que

— agregar valores para$k=1$hasta$k=n$de un polinomio de grado 0 (como$p(x)=1$) da una respuesta que es un “polinomio de grado 1”,

$$1+1+\cdots +1=n,$$

y

— agregar valores para$k=1$hasta$k=n$de un polinomio de grado 1 (como$p(x)=x$) da una respuesta que es un “polinomio de grado 2”,

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

Entonces podrías adivinar que la suma

$$T_1+T_2+T_3+\cdots +T_n$$

dará una respuesta que es un polinomio de grado 3 en n. Supongamos que

$$T_1+T_2+T_3+\cdots +T_n=$$An3+Bn2+Cn+D.

Entonces podemos usar pequeños valores de n para establecer ecuaciones que deben ser satisfechas por A, B, C, D y resolverlas para encontrar A, B, C, D:

— cuando$n=0$, obtenemos$D=0$;

— cuando$n=1$, obtenemos$A+B+C=1$;

— cuando$n=2$, obtenemos$8A+4B+2C=4$;

— cuando$n=3$, obtenemos$$27A+9B+3C=10.

Este método supone que sabemos que la respuesta es un polinomio y que conocemos su grado: se le llama “el método de coeficientes indeterminados”.

Existen diversas formas de mejorar el método básico (como escribir el polinomio$$An3+Bn2+Cn+Den la forma

$$Pn(n-1)(n-2)+Qn(n-1)+Rn+S,$$

que lo adapta a los valores$n=0,1,2,3$que se pretende sustituir).

b) Dejar$P(n)$ser la declaración:

”$T_1+T_2+T_3+\cdots +T_n=\frac{n(n+1)(n+2)}{6}$”.

• LHS de$P(1)=T_1=1$; RHS de$P(1)=\frac{1\times 2\times 3}{6}=1$. Dado que estos dos son iguales,$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular,

$$T_1+T_2+T_3+\cdots +T_k=\frac{k(k+1)(k+2)}{6}.$$

Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Ahora$P(k+1)$es una ecuación, así que empezamos con el LHS de$P(k+1)$y tratar de simplificarlo de manera adecuada para obtener el RHS de$P(k+1)$:$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & T_1+T_2+T_3+\cdots +T_k+T_{k+1}\hfill \\ \hfill & =\hfill & [T_1+T_2+T_3+\cdots +T_k]+T_{k+1}.\hfill \end{array}$Si ahora usamos$P(k)$, que suponemos que es cierto, entonces el primer paréntesis es igual a

$$\frac{k(k+1)(k+2)}{6}.$$

por lo que la suma completa es igual a:$\begin{array}{cc}=\hfill & \genfrac{}{}{0.1ex}{}{k(k+1)(k+2)}{6}+\genfrac{}{}{0.1ex}{}{(k+1)(k+2)}{2}\hfill \\ =\hfill & \genfrac{}{}{0.1ex}{}{(k+1)(k+2)(k+3)}{6}\hfill \\ =\hfill & \text{RHS de}\mathbf{P}(k+1).\hfill \end{array}$

De ahí$P(k+1)$sostiene.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

Nota: Los números triangulares$T_1,T_2,T_3,...,T_k,...T_n$también son iguales a los coeficientes binomiales$k+$1choose2. Y la suma de estos coeficientes binomiales es otro coeficiente binomial$n+$2choose3, por lo que el resultado en Problema 237. se puede escribir como:

$$\left(\begin{array}{c}2\\ 2\end{array}\right)+\left(\begin{array}{c}3\\ 2\end{array}\right)+\left(\begin{array}{c}4\\ 2\end{array}\right)+\cdots +\left(\begin{array}{c}n+1\\ 2\end{array}\right)=\left(\begin{array}{c}n+2\\ 3\end{array}\right).$$

Te podría interesar interpretar el Problema 237. en el lenguaje de los coeficientes binomiales, y probarlo mediante el uso repetido de la relación básica del triángulo Pascal (Pascal (1623—1662)):

$$\left(\begin{array}{c}k\\ r\end{array}\right)+\left(\begin{array}{c}k\\ r+1\end{array}\right)=\left(\begin{array}{c}k+1\\ r+1\end{array}\right).$$

Comience por reescribir

$$\left(\begin{array}{c}n+2\\ 3\end{array}\right)=\left(\begin{array}{c}n+1\\ 2\end{array}\right)+\left(\begin{array}{c}n+1\\ 3\end{array}\right).$$

238.

(a) Sabemos por el Problema 237. b) que

$$1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n(n+1)=\frac{n(n+1)(n+2)}{3}.$$

También

$\begin{array}{ccc}1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n(n+1)\hfill & =\hfill & 1\cdot (1+1)+2\cdot (2+1)+3\cdot (3+1)\hfill \\ \hfill & \hfill & +\cdots +n\cdot (n+1)\hfill \\ \hfill & =\hfill & (1^2+1)+(2^2+2)+(3^2+3)\hfill \\ \hfill & \hfill & +\cdots +(n^2+n)\hfill \\ \hfill & =\hfill & (1^2+2^2+3^2+\cdots +n^2)\hfill \\ \hfill & \hfill & +(1+2+3+\cdots +n).\hfill \end{array}$

Por lo tanto

$\begin{array}{ccc}{1}^2+2^2+3^2+\cdots +n^2\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{n(n+1)(n+2)}{3}-\genfrac{}{}{0.1ex}{}{n(n+1)}{2}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{n(n+1)(2n+1)}{6}.\hfill \end{array}$

b) Adivina:

$$1\cdot 2\cdot 3+2\cdot 3\cdot 4+3\cdot 4\cdot 5+\cdots +n(n+1)(n+2)=\frac{n(n+1)(n+2)(n+3)}{4}.$$

La prueba por inducción es totalmente rutinaria, y se deja para el lector.

$\begin{array}{ccc}1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n(n+1)(n+2)\hfill & =\hfill & 1\cdot (1+1)(1+2)+2\cdot (2+1)(2+2)\hfill \\ \hfill & \hfill & +\cdots +n\cdot (n+1)(n+2)\hfill \\ \hfill & =\hfill & (1^3+3\cdot 1^2+2\cdot 1)\hfill \\ \hfill & \hfill & +(2^3+3\cdot 2^2+2\cdot 2)\hfill \\ \hfill & \hfill & +\cdots +(n^3+3n^2+2n)\hfill \\ \hfill & =\hfill & (1^3+2^3+\cdots +n^3)\hfill \\ \hfill & \hfill & +3(1^2+2^2+\cdots +n^2)\hfill \\ \hfill & \hfill & +2(1+2+\cdots +n).\hfill \end{array}$

Por lo tanto

$\begin{array}{ccc}{1}^3+2^3+3^3+\cdots +n^3\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{n(n+1)(n+2)(n+3)}{4}\hfill \\ \hfill & \hfill & -3\left[\genfrac{}{}{0.1ex}{}{n(n+1)(2n+1)}{6}\right]\hfill \\ \hfill & \hfill & -n(n+1)\hfill \\ \hfill & =\hfill & {\left[\genfrac{}{}{0.1ex}{}{n(n+1)}{2}\right]}^2.\hfill \end{array}$

239.

(a) Dejar$f(x)$ser cualquiera de tales polinomios. Si$f(a_k)=0$, entonces sabemos (por el Teorema del Resto) que$f(x)$tiene$(x-a_k)$como factor. Desde el$a_k$son todos distintos, y$f(a_k)=0$por cada k,$0\le k\le n-1$, tenemos

$$f(x)=(x-a_0)(x-a_1)(x-a_2)\cdots (x-a_{n-1})\cdot g(x)$$

para algunos polinomios$g(x)$. Y ya que nos dicen que$f(x)$tiene grado n,$g(x)$tiene grado 0, así es una constante. De ahí que cada polinomio de grado n tenga la forma

$$C\cdot (x-a_0)(x-a_1)(x-a_2)\cdots (x-a_{n-1}).$$

Desde$f(a_n)=b$, podemos sustituir para encontrar C:

$$C=\frac{b}{(a_n-a_0)(a_n-a_1)(a_n-a_2)\cdots (a_n-a_{n-1})}.$$

b) Dejar$P(n)$ser la declaración:

“Dado cualquiera de dos conjuntos etiquetados de$n+1$números reales$a_0,a_1,a_2,...,a_n$, y$b_0,b_1,b_2,...,b_n$, donde el$a_i$son todos distintos (pero el$b_i$no necesita ser), existe un polinomio$f_n$de grado n, tal que$f_n(a_0)=b_0$,$f_n(a_1)=b_1$,$f_n(a_2)=b_2$,...,$f_n(a_n)=b_n$.”

• Cuando$n=0$, podemos elegir$f_0(x)=b_0$ser el polinomio constante. De ahí$P(0)$es verdad.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 0$; es decir, sabemos que, para esta k en particular:

“Dado cualquiera de dos conjuntos etiquetados de$k+1$números reales$a_0,a_1,a_2,...,a_k$, y$b_0,b_1,b_2,...,b_k$, donde el$a_i$son todos distintos (pero el$b_i$no necesita ser), existe un polinomio$f_k$de grado k, tal que$f_k(a_0)=b_0$,$f_k(a_1)=b_1$,$f_k(a_2)=b_2,...,f_k(a_k)=b_k$.”

Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Ahora$P(k+1)$es la declaración:

“Dado cualquiera de dos conjuntos etiquetados de$(k+1)+1$números reales$a_0,a_1,...,a_{k+1}$, y$b_0,b_1,b_2,...,b_{k+1}$, donde el$a_i$son todos distintos (pero el$b_i$no necesita ser), existe un polinomio$f_{k+1}$de grado$k+1$, de tal manera que$f_{k+1}(a_0)=b_0$,$f_{k+1}(a_1)=b_1$,$f_{k+1}(a_2)=b_2$,...,$f_{k+1}(a_{k+1})=b_{k+1}$.”

Así que para probar que$P(k+1)$sostiene, debemos comenzar por considerar

cualesquiera dos conjuntos etiquetados de$(k+1)+1$números reales$$a_0,a_1,a_2,...,a_{k+1},\text{y}{b}_0,b_1,b_2,...,b_{k+1},$$donde el$a_i$son todos distintos (pero el$b_i$no necesita ser).

Debemos entonces de alguna manera construir una función polinómica$f_{k+1}$de grado$k+1$con la propiedad requerida.

Porque estamos suponiendo que$P(k)$se sabe que es verdad, podemos enfocarnos en la primera$k+1$números en cada una de las dos listas —$a_0,a_1,a_2,...,a_k$, y$b_0,b_1,b_2,...,b_k$— y entonces podemos estar seguros de que hay un polinomio$f_k$de grado k tal que

$$f_k(a_0)=b_0,f_k(a_1)=b_1,f_k(a_2)=b_2,...,f_k(a_k)=b_k.$$

El siguiente paso es ligeramente indirecto: hacemos uso del polinomio$f_{k+1}$que todavía estamos tratando de construir, y enfocarnos en el polinomio

$$f(x)=f_{k+1}(x)-f_k(x)$$

satisfaciendo

$$f(a_0)=f(a_1)=...=f(a_k)=0,f(a_{k+1})=b_{k+1}-f_k(a_{k+1})=b(\text{decir}).$$

La parte (a) garantiza la existencia de tal polinomio$f(x)$de grado$k+1$y nos dice exactamente lo que esta función polinómica$f(x)$es igual a. De ahí que podamos construir el polinomio requerido$f_{k+1}(x)$) al establecerlo igual a$f(x)+f_k(x)$, lo que demuestra que$P(k+1)$es verdad.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”.

240.

a) No se pueden hacer 5 centavos;$6=3+3$;$7=3+4$;$8=4+4$;$9=3+3+3$; etc.

Adivina: Cada cantidad > N = 5 se puede pagar directamente (sin recibir cambio).

b) Dejar$P(n)$ser la declaración:

“n centavos se pueden pagar directamente (sin cambio) utilizando monedas de 3 centavos y 4 centavos”.

—$P(6)$es la declaración: “6 centavos se pueden pagar directamente”. Y$6=3+3$, entonces$P(6)$es verdad.

— Ahora supongamos que sabemos$P(k)$es cierto para algunos$k\ge 6$. Debemos demostrar que$P(k+1)$debe ser entonces cierto.

Para acreditar$P(k+1)$consideramos la declaración$P(k+1)$:

”$k+1$centavos se pueden pagar directamente”.

Sabemos que$P(k)$es cierto, entonces sabemos que “k centavos se pueden pagar directamente”.

— Si un método directo de pagar k centavos implica al menos una moneda de 3 centavos, entonces podemos reemplazar una moneda de 3 centavos por una moneda de 4 centavos para producir una forma de pagar$k+1$centavos.

De ahí que solo tengamos que preocuparnos por una situación en la que la única forma de pagar k centavos directamente no implica nada de monedas de 3 centavos —es decir, pagar k centavos usa solo monedas de 4 centavos. Pero entonces debe haber al menos dos monedas de 4 centavos (ya que$k\ge 6$), y podemos reemplazar dos monedas de 4 centavos por tres monedas de 3 centavos para producir una forma de pagar$k+1$centavos directamente.

De ahí

•$P(6)$es verdad; y

• siempre que$P(k)$es cierto para algunos$k\ge 6$, sabemos que$P(k+1)$también es cierto.

$\therefore$ $P(n)$es cierto para todos$n\ge 6$.

241.

(a)$z^2-z+1=0$, entonces$z=\frac{1\pm \sqrt{-3}}{2}$(estas son las dos sextas raíces primitivas de la unidad).

$\therefore$ $z^2=\frac{-1\pm \sqrt{-3}}{2}$(los dos primitivos cubos toots de la unidad), y

$$z^2+$$1z2=−1.

b)$z^2-2z+1=0$, entonces$z=1$(raíz repetida).$\propto$ $z^2=1$y$z^2+\frac{}{}$1z2=2.

c) d$z^2-3z+1=0$, entonces$z=\frac{3\pm \sqrt{5}}{2}$.

Tan pronto como uno comience a calcular z ² y$\frac{}{}$1z2, queda claro que es hora de p-a-u-s-e y pensar.

$${\left(z+\frac{1}{z}\right)}^2=(z^2+$$1z2)+2,

así que cuando$z+\frac{1}{z}=k$es un número entero,

$$z^2+{\left(\frac{1}{z}\right)}^2=k^2-2$$

también es un número entero.

e) Dejar$P(n)$ser la declaración:

“si z tiene la propiedad que$z+\frac{1}{z}$es un número entero, entonces$z^m+\frac{}{}$1zmes también un número entero para todos los m,$0\le m\le n$”.

•$P(0)$y$P(1)$son claramente ambas verdaderas; y$P(2)$se probó en la parte d) anterior.

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 2$; es decir, sabemos que, para esta k en particular:

“si z tiene la propiedad que$z+\frac{1}{z}$es un número entero, entonces$z^m+\frac{}{}$1zmes también un número entero para todos los m,$0\le m\le k$”.

Deseamos demostrar que$P(k+1)$debe ser entonces cierto.

Si$z+\frac{1}{z}$es un número entero, entonces, por$P(k)$,

”$z^m+\frac{}{}$1zmes también un número entero para todos los m,$0\le m\le k$”.

Así que para probar que$P(k+1)$sostiene, solo necesitamos demostrar que

”$z^{k+1}+\frac{}{}$1zk+1es un entero”.

Por el Teorema Binomial:$\begin{array}{ccc}{(z+\genfrac{}{}{0.1ex}{}{1}{z})}^{k+1}\hfill & =\hfill & (z^{k+1}+\genfrac{}{}{0.1ex}{}{1}{z^{k+1}})+\left(\genfrac{}{}{0ex}{}{k+1}{1}\right)(z^{k-1}+\genfrac{}{}{0.1ex}{}{1}{z^{k-1}})\hfill \\ \hfill & \hfill & +\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)(z^{k-3}+\genfrac{}{}{0.1ex}{}{1}{z^{k-3}})+\cdots \hfill \end{array}$

El LHS es un entero (ya que$z+\frac{1}{z}$es un número entero), y (por$P(k)$) cada término en el RHS es un número entero excepto posiblemente el primero. De ahí que el primer término sea la diferencia de dos enteros, por lo que también debe ser un entero.

De ahí$P(k+1)$es verdad.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”. QED

Nota: Si$k+1=2m$es parejo, la expansión de${\left(z+\frac{1}{z}\right)}^{k+1}$tiene un número impar de términos, por lo que el RHS de la expansión reagrupada anterior termina con el término$(\begin{array}{}\end{array}$2mm)·zm·(1z)m, que también es un número entero.

242.

Nota: En la solución al Problema 241. incluimos la condición en z como parte de la declaración$P(n)$.

En Problema 242. el resultado a probar tiene una hipótesis de fondo similar — “Let p be a prime number”. Puede hacer más clara la inducción si, como en el enunciado del Problema, esta hipótesis se plantea antes de iniciar la prueba de inducción.

Que p sea cualquier número primo. Dejamos$P(n)$ser la declaración:

”$n^p-n$es divisible por p”.

•$P(1)$es cierto (ya que$1^p-1=0=0\times p$, que es divisible por p).

• Supongamos que$P(k)$es cierto para algunos particulares (no especificados)$k\ge 1$; es decir, sabemos que, para esta k en particular:

”$k^p-k$es divisible por p”.

Deseamos probar$P(k+1)$— es decir,

”${(k+1)}^p-(k+1)$es divisible por p”

debe ser entonces cierto. Usando de nuevo el Teorema Binomial vemos que

$$\begin{array}{lll}{(k+1)}^p-(k+1)\hfill & =\hfill & \left[k^p+\left(\begin{array}{c}p\\ p-1\end{array}\right)k^{p-1}+\left(\begin{array}{c}p\\ p-2\end{array}\right)k^{p-2}+\cdots +\left(\begin{array}{c}p\\ 1\end{array}\right)k+1\right]\hfill \\ \hfill & \hfill & -(k+1)\hfill \\ \hfill & =\hfill & (k^p-k)+\left[\left(\begin{array}{c}p\\ p-1\end{array}\right)k^{p-1}+\left(\begin{array}{c}p\\ p-2\end{array}\right)k^{p-2}+\cdots +\left(\begin{array}{c}p\\ 1\end{array}\right)k\right].\hfill \end{array}$$

Por$P(k)$, el primer paréntesis en el RHS es divisible por p; y en cada uno de los otros términos cada uno de los coeficientes binomiales$\left(\begin{array}{c}p\\ r\end{array}\right)$,$0<r<p$,

• es un número entero, y

• tiene un factor “p” en el numerador y no tal factor en el denominador.

De ahí que cada término en el segundo paréntesis sea un múltiplo de p. Entonces el RHS (y por lo tanto el LHS) es divisible por p.

De ahí$P(k+1)$es verdad.

Si combinamos estas dos viñetas, hemos demostrado que”$P(n)$sostiene para todos$n\ge 1$”. QED

243.

$$0.037037037...\text{(para siempre)}=\frac{37}{1000}+\frac{37}{1000000}+\frac{37}{1000000000}+\cdots \text{(para siempre)}.$$

Se trata de una serie geométrica con primer término$a=\frac{37}{1000}$y relación común$r=\frac{1}{1000}$, y también lo ha hecho la suma

$$\frac{a}{1-r}=\frac{37}{999}=\frac{1}{27}.$$

244.

a) Cada persona recibe en total:

$$\frac{1}{4}+{\left(\frac{1}{4}\right)}^2+{\left(\frac{1}{4}\right)}^3+{\left(\frac{1}{4}\right)}^4+\cdots \text{(para siempre)}=\frac{1}{3}$$

(aquí$a=\frac{1}{4}=r$).

(b) Tiene

$$1-\frac{1}{2}+\frac{1}{4}-\frac{1}{8}+\cdots \text{(para siempre)}=\frac{2}{3}$$

(aquí$a=1$,$r=-\frac{1}{2}$); tengo

$$\frac{1}{2}-\frac{1}{4}+\frac{1}{8}-\cdots \text{(para siempre)}=\frac{1}{3}$$

(aquí$a=\frac{1}{2}$,$r=-\frac{1}{2}$).

245. Los trenes están a 120 km de distancia, y la mosca viaja a 50 km/h hacia el Tren B, que inicialmente se encuentra a 120 km de distancia y viaja a 30 km/h.

La velocidad relativa de la mosca y del Tren B es de 80 km/h, por lo que toma$\genfrac{}{}{0.1ex}{}{3}{2}$horas antes de que se reúnan. En este tiempo el Tren A y el Tren B han recorrido cada uno 45 km, por lo que ahora están a 30 km de distancia. Luego, la mosca gira a la derecha y vuela de regreso al Tren A.

La velocidad relativa de la mosca y del Tren A es entonces también de 80 km/h, por lo que toma solo$\genfrac{}{}{0.1ex}{}{3}{8}$horas (o 22.5 minutos) para que el vuelo regrese al Tren A. El tren A y el tren B han viajado cada uno$\genfrac{}{}{0.1ex}{}{45}{4}$km en este tiempo, por lo que son ahora$\genfrac{}{}{0.1ex}{}{30}{4}$km de distancia. Luego, la mosca gira y vuela directamente de regreso al Tren B.

El tren B es$\genfrac{}{}{0.1ex}{}{30}{4}$km de distancia y la velocidad relativa de la mosca y el Tren B vuelve a ser de 80 km/h, por lo que el trayecto dura$\genfrac{}{}{0.1ex}{}{3}{32}$horas (o 5.625 minutos).

Continuando de esta manera, vemos que la mosca lleva

$$\frac{3}{2}+\frac{3}{8}+\frac{3}{32}+\frac{3}{128}+\cdots \text{(para siempre)}=2\text{horas}.$$De ahí que la mosca recorra 100 km antes de ser aplastada.

Nota: Los dos trenes se acercan entre sí a 60 km/h, por lo que chocan exactamente en 2 horas —tiempo durante el cual la mosca recorre 100 km.

246.

a) i$3^2>2^2$; por lo tanto

$$\frac{1}{3^2}<\frac{1}{2^2},$$

por lo

$$\frac{1}{2^2}+\frac{1}{3^2}<\frac{2}{2^2}=\frac{1}{2}.$$

ii)$7^2>6^2>5^2>4^2$; por lo tanto

$$\frac{1}{7^2}<\frac{1}{6^2}<\frac{1}{5^2}<\frac{1}{4^2},$$

por lo

$$\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}<\frac{4}{4^2}=\frac{1}{4}.$$

b) El argumento de la parte (a) da un límite superior para cada expresión entre corchetes en la suma

$$\left(\frac{1}{1^2}\right)+\left(\frac{1}{2^2}+\frac{1}{3^2}\right)+\left(\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}\right)+\left(\frac{1}{8^2}+\cdots +\frac{1}{{15}^2}\right)+\cdots$$

Sustituyendo cada corchete por su límite superior, vemos que la suma es

$\begin{array}{ccc}\hfill & <\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{2}{2^2}+\genfrac{}{}{0.1ex}{}{4}{4^2}+\genfrac{}{}{0.1ex}{}{8}{8^2}+\cdots \hfill \\ \hfill & =\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{2}+\genfrac{}{}{0.1ex}{}{1}{4}+\genfrac{}{}{0.1ex}{}{1}{8}+\cdots \text{(para siempre)}\hfill \\ \hfill & =\hfill & 2.\hfill \end{array}$

c) Las sumas parciales finitas

$$S_n=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{}{}$$1n2

• aumentar constantemente a medida que tomamos más y más términos, y

• cada suma parcial$S_n$es menor que$2$. Es claro que estas sumas parciales forman una secuencia

$$1=S_1<S_2<S_3<...<S_n<S_{n+1}<...<2.$$

De ello se deduce que hay algún número (desconocido)$S\le 2$a la que convergen las sumas parciales como$n\to \infty$, y tomamos este valor exacto (desconocido) S como el valor exacto de la suma interminable

$$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{}{}$$1n2+⋯(para siempre)

Para ver, por ejemplo, que$S>\frac{17}{12}$, observe que

$\begin{array}{ccc}S\hfill & >\hfill & S_4\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\genfrac{}{}{0.1ex}{}{1}{4^2}\hfill \\ \hfill & =\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{4}+\genfrac{}{}{0.1ex}{}{1}{9}+\genfrac{}{}{0.1ex}{}{1}{16}\hfill \\ \hfill & >\hfill & \genfrac{}{}{0.1ex}{}{17}{12}.\hfill \end{array}$

Nota 1: La afirmación de que

“una secuencia creciente de sumas parciales$S_n$, todos menos de 2, deben converger a algún número$S\le 2$”

es una propiedad fundamental de los números reales — llamada integridad.

Nota 2: Así como uno puede obtener mejores y mejores límites inferiores para S, como”$\frac{17}{12}<S$”, así se puede mejorar el límite superior”$S<2$”. Por ejemplo, si en la parte (b) evitamos sustituir el tercer término$\genfrac{}{}{0.1ex}{}{1}{9}$por$\genfrac{}{}{0.1ex}{}{1}{4}$, obtenemos un mejor límite superior”$S<\frac{67}{36}$”, que es$\genfrac{}{}{0.1ex}{}{5}{36}$menos de 2.

247.

(a) Dejar$P(n)$ser la declaración:

”$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{1}{n^2}\le 2-\frac{1}{n}$”.

• Luego LHS de$P(1)=\frac{1}{1^2}=1$, y RHS de$P(1)=2-1=1$. De ahí$P(1)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 1$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k^2}+\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k^2}]+\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}\hfill \\ \hfill & \le \hfill & [2-\genfrac{}{}{0.1ex}{}{1}{k}]+\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}\hfill \\ \hfill & =\hfill & 2-[\genfrac{}{}{0.1ex}{}{1}{k}-\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}]\hfill \\ \hfill & <\hfill & 2-\genfrac{}{}{0.1ex}{}{1}{k+1}.\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\equiv$ $P(1)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 1$. QED

b) Dejar$P(n)$ser la declaración:

”$\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots +\frac{}{}$1n2<1.68−1n”.

• Luego

$$\text{LHS de}P(4)=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}=1.423611111\cdots ,$$

y RHS de$P(4)=1.43$. De ahí$P(4)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 4$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k^2}+\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}\hfill \\ \hfill & =\hfill & (\genfrac{}{}{0.1ex}{}{1}{1^2}+\genfrac{}{}{0.1ex}{}{1}{2^2}+\genfrac{}{}{0.1ex}{}{1}{3^2}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k^2})+\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}\hfill \\ \hfill & <\hfill & [1.68-\genfrac{}{}{0.1ex}{}{1}{k}]+\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}\hfill \\ \hfill & =\hfill & 1.68-[\genfrac{}{}{0.1ex}{}{1}{k}-\genfrac{}{}{0.1ex}{}{1}{{(k+1)}^2}]\hfill \\ \hfill & <\hfill & 1.68-\genfrac{}{}{0.1ex}{}{1}{k+1}.\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\therefore$ $P(1)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 1$.

248.

a) i$n!=n\times (n-1)\times (n-2)\times \cdots \times 3\times 2\times 1\ge 2\times 2\times 2\times \cdots \times 2\times 1=2^{n-1}$siempre que$n\ge 1$.

$\therefore$ $\frac{1}{n!}\le {\left(\frac{1}{2}\right)}^{n-1}$para todos$n\ge 1$.

$\therefore$ $\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le 1+\left[1+\frac{1}{2}+{\left(\frac{1}{2}\right)}^2+\cdots +{\left(\frac{1}{2}\right)}^{n-1}\right]<3$para todos$n\ge 0$.

(ii) A medida que vamos añadiendo más y más términos, cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}$$

es mayor que la suma anterior. Desde cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}<3,$$

las sumas aumentan, pero nunca llegan a 3, por lo que se acumulan cada vez más cerca de un valor “e”$\le 3$. Además, este valor “e” es ciertamente mayor que la suma de los dos primeros términos$\frac{1}{0!}+\frac{1}{1!}=2$, entonces$2<e\le 3$.

b) i) Dejar$P(n)$ser la declaración:

”$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le 3-\frac{1}{n\cdot n!}$”.

•$\text{LHS de}P(1)=2=\text{RHS de}P(1)$. De ahí$P(1)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 1$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k!}]+\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & \le \hfill & 3-\genfrac{}{}{0.1ex}{}{1}{k\cdot k!}+\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & =\hfill & 3-\genfrac{}{}{0.1ex}{}{1}{k(k+1)!}\hfill \\ \hfill & <\hfill & 3-\genfrac{}{}{0.1ex}{}{1}{(k+1)\cdot (k+1)!}\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\therefore$ $P(1)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 1$.

ii) [El razonamiento aquí utiliza la constante “3” al tiempo que ignora el refinamiento”$3-\frac{1}{n.n!}$”, y así suena exactamente como la parte (a) (ii).] A medida que agregamos más términos, cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}$$

es mayor que la suma anterior. Desde cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}<3,$$

las sumas parciales aumentan, pero nunca llegan a 3; así se acumulan cada vez más cerca de un valor “e”$\le 3$. Además, este valor “e” es ciertamente mayor que la suma de los tres primeros términos$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}=2.5$, entonces$2.5<e\le 3$.

c) Nota: Examinar cuidadosamente el papel desempeñado por el número “3” en la prueba de inducción anterior en el inciso b) ii). Se necesita precisamente para validar el enunciado$P(1)$: desde$\frac{1}{0!}+\frac{1}{1!}=3-\frac{1}{1\times 1!}$”. Pero el número “3” no juega ningún papel activo en el segundo paso de inducción, y podría ser reemplazado por cualquier otro número que elijamos.

El valor exacto “e” de la serie infinita no se ve realmente afectado por lo que sucede cuando$n=1$. Supongamos que preguntamos: “Qué número$C_2$debería sustituir a “3” si sólo queremos demostrar que

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le C_2-\frac{1}{n\cdot n!},\text{para todos}n\ge 2?$$

La única parte de la prueba de inducción donde$C_2$entonces importa es cuando tratamos de verificar que$P(2)$sostiene; por lo que debemos elegir el más pequeño posible$C_2$para satisfacer

$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}\le C_2-\frac{1}{2.2!}:$

es decir,$C_2=2.75$.

(i) Dejar$P(n)$ser la declaración:

”$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le 2.75-\frac{1}{n\cdot n!}$”.

• LHS de$P(2)=2.5$; RHS de$P(2)=2.75-\frac{1}{4}$. De ahí$P(2)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\le 2$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k!}]+\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & \le \hfill & 2.75-\genfrac{}{}{0.1ex}{}{1}{k\cdot k!}+\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & =\hfill & 2.75-\genfrac{}{}{0.1ex}{}{1}{k(k+1)!}\hfill \\ \hfill & <\hfill & 2.75-\genfrac{}{}{0.1ex}{}{1}{(k+1)(k+1)!}\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\therefore$ $P(2)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 2$. QED

(ii) A medida que añadimos más términos, cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}$$

es mayor que la suma anterior.

Desde cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}<2.75,$$

las sumas finitas aumentan, pero nunca llegan a 2.75, por lo que se acumulan cada vez más cerca de un valor “e”$\le 2.75$. Además, este valor “e” es ciertamente mayor que la suma de los primeros cuatro términos

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}>2.66,$$

entonces$2.66<e\le 2.75$.

d) i) Dejar$P(n)$ser la declaración:

”$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le 2.7222\cdots (\text{para siempre)}-\frac{1}{n.n!}$”.

•$\text{LHS de}P(3)=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}=2.666\cdots \text{(para siempre)}$;$\text{RHS de}P(3)=2.7222\cdots \text{(para siempre)}-\frac{1}{18}=2.666\cdots \text{(para siempre)}$. De ahí$P(3)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 3$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & =\hfill & [\genfrac{}{}{0.1ex}{}{1}{0!}+\genfrac{}{}{0.1ex}{}{1}{1!}+\genfrac{}{}{0.1ex}{}{1}{2!}+\cdots +\genfrac{}{}{0.1ex}{}{1}{k!}]+\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & \le \hfill & 2.7222\cdots \left(\text{para siempre}\right)-\genfrac{}{}{0.1ex}{}{1}{k\cdot k!}+\genfrac{}{}{0.1ex}{}{1}{(k+1)!}\hfill \\ \hfill & =\hfill & 2.7222\cdots \left(\text{para siempre}\right)-\genfrac{}{}{0.1ex}{}{1}{k(k+1)!}\hfill \\ \hfill & <\hfill & 2.7222\cdots \left(\text{para siempre}\right)-\genfrac{}{}{0.1ex}{}{1}{(k+1)(k+1)!}\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\equiv$ $P(3)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\equiv$ $P(n)$es verdad, para todos$n\ge 3$.

(ii) A medida que añadimos más términos, cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}$$

es mayor que la suma anterior.

Desde cada suma finita

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}<2.7222\cdots \text{(para siempre)},$$

las sumas finitas aumentan, pero nunca alcanzan$2.7222\cdots$(para siempre), por lo que se acumulan cada vez más cerca de un valor “e”$\le 2.7222\cdots$(para siempre). Además, este valor “e” es ciertamente mayor que la suma de los cinco primeros términos

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}>2.708,$$

entonces$2.708<e\le 2.7222\cdots \text{(para siempre)}$.

Nota: Este proceso de refinamiento puede continuar indefinidamente. Pero sólo tenemos que dar un paso más para precisar el valor de “e” con sorprendente precisión.

El siguiente paso utiliza la misma prueba para demostrar que

”$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le 2.7185-\frac{1}{n\cdot n!}$, para todos$n\ge 4$”,

y para concluir que la suma sin fin

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}+\cdots (\text{para siempre})$$

tiene un valor definido “e” que se encuentra en algún lugar entre$2.716$y$2.71875$.

Entonces podríamos repetir la misma prueba para demostrar que

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}\le 2.718333\cdots (\text{para siempre})-\frac{1}{n\cdot n!},\text{para todos}n\ge 5,$$

y usar el límite inferior$2.7177...$desde los primeros siete términos para concluir que la suma sin fin

$$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots +\frac{1}{n!}+\cdots \text{(para siempre)}$$

tiene un valor definido “e” que se encuentra en algún lugar entre$2.7177$y$2.718333\cdots$(para siempre). Y así sucesivamente.

249. Let$P(n)$ser la declaración:

”$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{n}}\ge \sqrt{n}$”.

• LHS de$P(1)=1=$RHS de$P(1)$. De ahí$P(1)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 1$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & \genfrac{}{}{0.1ex}{}{1}{\sqrt{1}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{2}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{3}}+\cdots +\genfrac{}{}{0.1ex}{}{1}{\sqrt{k+1}}\hfill \\ \hfill & =\hfill & (\genfrac{}{}{0.1ex}{}{1}{\sqrt{1}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{2}}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{3}}+\cdots +\genfrac{}{}{0.1ex}{}{1}{\sqrt{k}})+\genfrac{}{}{0.1ex}{}{1}{\sqrt{(k+1)}}\hfill \\ \hfill & \ge \hfill & \sqrt{k}+\genfrac{}{}{0.1ex}{}{1}{\sqrt{k+1}}\hfill \\ \hfill & \ge \hfill & \sqrt{k+1}(\text{desde}\genfrac{}{}{0.1ex}{}{1}{\sqrt{k+1}}\ge \genfrac{}{}{0.1ex}{}{1}{\sqrt{k+1}+\sqrt{k}}).\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\therefore$ $P(1)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 1$. QED

250. Que a, b sean números reales tales que$a\ne b$, y$a+b>0$.

Uno de a, b es entonces el mayor, y podemos suponer que esto es a — así que$a>b$. Si$a>b>0$, luego$a^n>b^n>0$para todo n; si$b<0$, luego$a+b>0$implica que$a=\left|a\right|>\left|b\right|$, entonces$a^n>b^n$para todos n.

Let$P(n)$ser la declaración:

”$\frac{a^n+b^n}{2}\ge {\left(\frac{a+b}{2}\right)}^n$”.

• LHS de$P(1)=\frac{a+b}{2}=\text{RHS de}P(1)$. De ahí$P(1)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 1$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{RHS de}\mathbf{P}(k+1)\hfill & =\hfill & {\left(\genfrac{}{}{0.1ex}{}{a+b}{2}\right)}^{k+1}\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{a+b}{2}\cdot {\left(\genfrac{}{}{0.1ex}{}{a+b}{2}\right)}^k\hfill \\ \hfill & \le \hfill & \genfrac{}{}{0.1ex}{}{a+b}{2}\cdot \genfrac{}{}{0.1ex}{}{a^k+b^k}{2}\left(\text{por}\mathbf{P}\right(k\left)\right)\hfill \\ \hfill & =\hfill & \genfrac{}{}{0.1ex}{}{a^{k+1}+b^{k+1}}{4}+\genfrac{}{}{0.1ex}{}{a{b}^k+b{a}^k}{4}\hfill \\ \hfill & <\hfill & \genfrac{}{}{0.1ex}{}{a^{k+1}+b^{k+1}}{2}\left(\text{desde}\right(a^k-b^k\left)\right(a-b)>0).\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\therefore$ $P(1)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 1$.

251. Sea x cualquier número real$\ge -1$.

Si$x=-1$, luego${(1+x)}^n=0\ge 1-n=1+nx$, para todos$n\ge 1$.

Por lo tanto, podemos suponer que$x>-1$, entonces$1+x>0$.

Let$P(n)$sea la declaración:”${(1+x)}^n\ge 1+nx$”.

• LHS de$P(1)=1+x=\text{RHS de}P(1)$. De ahí$P(1)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 1$. Queremos demostrar que$P(k+1)$sostiene.

$\begin{array}{ccc}\text{LHS de}\mathbf{P}(k+1)\hfill & =\hfill & {(1+x)}^{k+1}\hfill \\ \hfill & =\hfill & (1+x)\cdot {(1+x)}^k\hfill \\ \hfill & \ge \hfill & (1+x)\cdot (1+kx)\left(\text{por}\mathbf{P}\right(k),\text{desde}1+x>0)\hfill \\ \hfill & =\hfill & 1+(k+1)x+k{x}^2\hfill \\ \hfill & \ge \hfill & 1+(k+1)x\hfill \end{array}$

De ahí$P(k+1)$sostiene.

$\therefore$ $P(1)$sostiene; y siempre que$P(k)$se sabe que es verdad,$P(k+1)$también es cierto.

$\therefore$ $P(n)$es verdad, para todos$n\ge 1$.

252. El problema se discute después de la declaración del Problema 252. en el texto principal.

253.

a) i$3>2$, entonces$\frac{1}{3}<\frac{1}{2}$.$\therefore$ $\frac{1}{2}+\frac{1}{3}<\frac{1}{2}+\frac{1}{2}=1$.

ii)$5,6,7>4$; por lo tanto$\frac{1}{5},\frac{1}{6},\frac{1}{7}$son todos$<\frac{1}{4}$.$⦁$ $\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}<\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}=1$.

iii) Dejar$P(n)$ser la declaración:

”$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{2^n-1}<n$”.

Entonces

•$P(2)$es cierto por (i), ya que

$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}<1+\left(\frac{1}{2}+\frac{1}{2}\right)=2.$$

• Supongamos que$P(k)$es cierto para algunos$k\ge 2$.

$$\begin{array}{lll}\text{LHS de}P(k+1)\hfill & =\hfill & \left[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{2^k-1}\right]\hfill \\ \hfill & \hfill & +\left[\frac{1}{2^k}+\cdots +\frac{1}{2^{k+1}-1}\right].\hfill \end{array}$$

El primer soporte es$<k$(por$P(k)$); y cada uno de los$2^k$términos en el segundo paréntesis es$\le \frac{1}{2^k}$, por lo que todo el soporte es$\le 1$.

De ahí el LHS de$P(k+1)<k+1$, entonces$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

iv) En la primera etapa (parte (i)) sustituimos$\frac{1}{2}+\frac{1}{3}$por$\frac{1}{2}+\frac{1}{2}=1$. De ahí cuando$n\ge 2$, sabemos que los dos lados de$P(n)$difieren por al menos$\frac{1}{2}-\frac{1}{3}$. Esta diferencia es mayor que$\frac{}{}$12ncuando$n\ge 3$, por lo que sigue el inciso iv).

b)

(i)$3<4$, entonces$\frac{1}{3}>\frac{1}{4}$.

$\therefore$ $\frac{1}{3}+\frac{1}{4}>\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$.

ii)$5,6,7<8$; por lo tanto$\frac{1}{5},\frac{1}{6},\frac{1}{7}$son todos$>\frac{1}{8}$.

$\therefore$ $\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}>\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=\frac{1}{2}$.

iii) Dejar$P(n)$ser la declaración:

”$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{}{}$12n>1+n2”.

Entonces

•$P(2)$es cierto por (i), ya que

$\begin{array}{ccc}\genfrac{}{}{0.1ex}{}{1}{1}+\genfrac{}{}{0.1ex}{}{1}{2}+\genfrac{}{}{0.1ex}{}{1}{3}+\genfrac{}{}{0.1ex}{}{1}{4}\hfill & =\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{2}+(\genfrac{}{}{0.1ex}{}{1}{3}+\genfrac{}{}{0.1ex}{}{1}{4})\hfill \\ \hfill & >\hfill & 1+\genfrac{}{}{0.1ex}{}{1}{2}+(\genfrac{}{}{0.1ex}{}{1}{4}+\genfrac{}{}{0.1ex}{}{1}{4})\hfill \\ \hfill & =\hfill & 1+2\times \genfrac{}{}{0.1ex}{}{1}{2}.\hfill \end{array}$

• Supongamos que$P(k)$es cierto para algunos$k\ge 2$.

LHS de$P(k+1)=\left[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{}{}\right]$12k+12k+1+⋯+12k+1.

El primer soporte es$>1+\frac{k}{2}$(por$P(k)$); y cada uno de los$2^k$términos en el segundo paréntesis es$\ge \frac{1}{2^{k+1}}$, por lo que todo el soporte es$\ge \frac{1}{2}$. De ahí el LHS de$P(k+1)>1+\frac{k+1}{2}$, entonces$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

254.

(a) Utilizamos inducción. Let$P(n)$ser la declaración:

“n tiras rectangulares idénticas de longitud 2 se equilibran exactamente en el borde de una mesa si las distancias sucesivas de protrusión (primero más allá del borde de la mesa, luego más allá del borde de ataque de la tira inmediatamente debajo, y así sucesivamente) son los términos$\frac{1}{n},\frac{1}{n-1},\frac{1}{n-2},...,\frac{1}{3},\frac{1}{2},\frac{1}{1}$de la serie armónica finita en orden inverso”.

• Cuando$n=1$, una sola tira que sobresale la distancia 1 más allá del borde de la mesa tiene su centro de gravedad exactamente sobre el borde de la mesa. De ahí$P(1)$es verdad.

• Supongamos que sabemos que$P(k)$es cierto para algunos$k\ge 1$.

Let$k+1$tiras idénticas se dispongan como se describe en la declaración$P(k+1)$.

El comunicado$P(k)$garantiza que las tiras k superiores se equilibrarían exactamente si el borde delantero de la tira inferior fuera de hecho el borde de la mesa; de ahí que el centro de gravedad combinado de las tiras k superiores se posicione exactamente sobre el borde delantero de la tira inferior.

Deje que M sea la masa de cada tira; ya que el borde delantero de la tira inferior es la distancia$\frac{1}{k+1}$más allá del borde de la mesa, las tiras k superiores producen un momento combinado alrededor del borde de la mesa igual a$$kM×1k+1.

El centro de gravedad de la tira inferior es la distancia$1-\frac{1}{k+1}=\frac{k}{k+1}$desde el borde de la mesa en sentido contrario; de ahí aporta un momento alrededor del borde de la mesa igual a$M\times \left(-\frac{k}{k+1}\right)$.

$\propto$el momento total de toda la pila alrededor del borde de la mesa es igual a cero, por lo que el centro de gravedad de la pila combinada de$k+1$tiras se encuentra exactamente sobre el borde de la mesa. De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 1$.

b) Problema 253. b) iii) ahora garantiza que una pila de$2^n$las tiras pueden sobresalir una distancia$>1+\frac{n}{2}$más allá del borde de la mesa.

Nota: El blog Matemático Turístico de Ivars Petersen contiene una entrada en 2009

http://mathtourist.blogspot.com/2009/01/overhang.html

que explora cómo se pueden obtener voladizos grandes con menos tiras si se le permite usar tiras para contrarrestar las que sobresalen más allá del borde de la mesa.

255.

a) i) Dejar$P(n)$ser la declaración:

”$s_{2p-2}<{}_{}$s2p<s2q+1<s2q−1para todos$p,q$tal que$1\le p,q\le n$”.

•$P(1)$es cierto (ya que$s_0$es la suma vacía, entonces

$$0=s_0<s_2=\frac{1}{2}<s_3=\frac{5}{6}<s_1=1.$$

• Supongamos que$P(k)$es cierto para algunos$k\ge 1$. Entonces la mayor parte de las desigualdades en el comunicado$P(k+1)$forman parte de la declaración$P(k)$; las únicas desigualdades pendientes que quedan por demostrar son:

$${}_{}$$s2k<s2k+2<s2k+3<s2k+1.

que son ciertos, ya que

$${}_{}$$s2k+3=s2k+2+12k+3=s2k+1−12k+2+12k+3

y

$${}_{}$$s2k+2=s2k+12k+1−12k+2.

De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

ii) Las “sumas pares”$s_0,s_2,s_4,...$están aumentando, pero todos son menores que$s_1=1$, por lo que se acercan a algún valor$s_{even}\le 1$.

Las “sumas impares”$s_1,s_3,s_5,...$están disminuyendo, pero todos son mayores que$s_2=\frac{1}{2}$, por lo que se acercan a algún valor$s_{odd}\ge \frac{1}{2}$.

Las “sumas pares”$s_0,s_2,s_4,...$están aumentando, pero todos son menores que$s_5=\frac{47}{60}$, por lo que se acercan a algún valor$s_{even}\le \frac{47}{60}$.

Las “sumas impares”$s_1,s_3,s_5,...$están disminuyendo, pero todos son mayores que$s_6=\frac{37}{60}$, por lo que se acercan a algún valor$s_{odd}\ge \frac{37}{60}$.

Además, la diferencia entre sumas sucesivas es$\frac{1}{n}$, y esto tiende hacia cero, por lo que la diferencia entre cada “suma impar” y la siguiente “suma par” tiende a cero, por lo que$s_{even}={}_{}$sodd.

b) La prueba de la parte a) lleva palabra por palabra, con”$\frac{1}{k}$” reemplazado en cada etapa por”$a_k$”.

256. Let$P(n)$ser la declaración:

”$f_k$tiene al menos k factores primos distintos”.

•$f_1=2$tiene exactamente 1 factor primo, entonces$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos$k\ge 1$.

Entonces$f_{k+1}=f_k(f_k+1)$. El primer factor$f_k$tiene al menos k factores primos distintos.

Y el segundo factor$f_k+1>f_k>1$, por lo que tiene al menos un factor primo.

Por otra parte$$HCF(fk,fk+1)=1, por lo que el segundo soporte no tiene factor en común con$f_k$.

De ahí$f_{k+1}$tiene al menos$k+1$distintos factores primos, por lo$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 1$.

Nota: Este problema [sugerido por Serkan Dogan] da una prueba diferente del resultado (Problema 76. d)) que la lista de números primos continúe para siempre.

257.

(a) Dejar$P(n)$ser la declaración: “n puntos distintos en una línea recta dividen la línea en$n+1$intervalos”.

• 0 puntos dejan la línea en condiciones prístinas, es decir, un solo intervalo, entonces$P(0)$es verdad.

• Supongamos que$P(k)$es cierto para algunos$k\ge 0$.

Considere una línea recta arbitraria dividida por$k+1$puntos$A_0,A_1,...,A_k$.

Entonces los k puntos$A_1,...,A_k$dividir la línea en$k+1$intervalos (por$P(k)$).

El punto adicional$A_0$es distinto de$A_1$,...,$A_k$y así debe estar dentro de uno de estos$k+1$intervalos, y lo divide en dos — dando$(k+1)+1=k+2$intervalos en conjunto.

De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 0$.

(b) (i) Queremos una función R satisfactoria

$R_0=1,R_1=2,R_2=4,R_3=7.$

Si observamos que en la parte (a)$n+1=1+\left(\begin{array}{c}n\\ 1\end{array}\right),$entonces podríamos adivinar que

$$R_n=1+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right).$$

ii) Dejar$P(n)$ser la declaración:

“n líneas rectas distintas en el plano dividen el plano en como máximo$f(n)=1+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)$regiones”.

• 0 líneas dejan el avión en condiciones prístinas, es decir, una sola región, por lo que$P(0)$es cierto, siempre que

$$1+\left(\begin{array}{c}0\\ 1\end{array}\right)+\left(\begin{array}{c}0\\ 2\end{array}\right)=1.$$

• Supongamos que$P(k)$es cierto para algunos$k\ge 0$.

Considera el plano dividido por$k+1$líneas rectas$m_0,m_1,...,m_k$.

Entonces las k líneas$m_1,...,m_k$dividir el avión en como máximo

$$R_k=1+\left(\begin{array}{c}k\\ 1\end{array}\right)+\left(\begin{array}{c}k\\ 2\end{array}\right)$$

regiones (por$P(k)$).

La línea adicional$m_0$es distinto de$m_1,...,m_k$y así cumple cada una de estas líneas en un solo punto como máximo, dando como máximo k puntos en la línea$m_0$. Estos puntos dividen$m_0$en a lo sumo$k+1$intervalos, y cada uno de estos intervalos corresponde a una línea de corte, donde la línea$m_0$corta una de las regiones creadas por las líneas$m_1,m_2,...,m_k$en dos piezas, dando como máximo

$\begin{array}{ccc}{R}_k+(k+1)\hfill & =\hfill & 1+\left(\genfrac{}{}{0ex}{}{k}{1}\right)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)+k+1\hfill \\ \hfill & =\hfill & 1+\left(\genfrac{}{}{0ex}{}{k+1}{1}\right)+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)\hfill \\ \hfill & =\hfill & R_{k+1}\hfill \end{array}$

regiones en conjunto.

De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 0$.

(c) (i) Queremos que una función S satisfaga

$$S_0=1,S_1=2,S_2=4,S_3=8,S_4=15,...$$

Después de pensar en las diferencias entre términos sucesivos en la parte (b), podríamos adivinar que

$$S_n=\left(\begin{array}{c}n\\ 0\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\left(\begin{array}{c}n\\ 3\end{array}\right).$$

ii) Dejar$P(n)$ser la declaración:

“n planos distintos en 3 espacios dividen el espacio en como máximo

$S_n=\left(\begin{array}{c}n\\ 0\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\left(\begin{array}{c}n\\ 3\end{array}\right)$

regiones”.

• 0 aviones dejan nuestro espacio 3D en perfectas condiciones, es decir, una sola región, por lo que$P(0)$es cierto, siempre que

$$\left(\begin{array}{c}0\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ 1\end{array}\right)+\left(\begin{array}{c}0\\ 2\end{array}\right)+\left(\begin{array}{c}0\\ 3\end{array}\right)=1.$$

• Supongamos que$P(k)$es cierto para algunos$k\ge 0$.

Considere 3D dividido por$k+1$aviones$m_0,m_1,...,m_k$.

Entonces los k aviones$m_1,...,m_k$dividir 3D en como máximo

$$S_k=\left(\begin{array}{c}k\\ 0\end{array}\right)+\left(\begin{array}{c}k\\ 1\end{array}\right)+\left(\begin{array}{c}k\\ 2\end{array}\right)+\left(\begin{array}{c}k\\ 3\end{array}\right)$$

regiones (por$P(k)$).

El avión adicional$m_0$es distinto de$m_1,...,m_k$y así se reúne cada uno de estos planos en (a lo sumo) una línea, dando lugar a como máximo k líneas en el avión$m_0$. Esta disposición de líneas en el plano$m_0$divide$m_0$en a lo sumo

$R_k=1+\left(\begin{array}{c}k\\ 1\end{array}\right)+\left(\begin{array}{c}k\\ 2\end{array}\right)$

regiones, y cada una de estas regiones en el plano$m_0$es el “corte” donde el avión$m_0$corta una región existente en dos pedazos, dando lugar a como máximo

$\begin{array}{ccc}{S}_k+R_k\hfill & =\hfill & [\left(\genfrac{}{}{0ex}{}{k}{0}\right)+\left(\genfrac{}{}{0ex}{}{k}{1}\right)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)+\left(\genfrac{}{}{0ex}{}{k}{3}\right)]+[1+\left(\genfrac{}{}{0ex}{}{k}{1}\right)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)]\hfill \\ \hfill & =\hfill & \left(\genfrac{}{}{0ex}{}{k+1}{0}\right)+\left(\genfrac{}{}{0ex}{}{k+1}{1}\right)+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)+\left(\genfrac{}{}{0ex}{}{k+1}{3}\right)\hfill \\ \hfill & =\hfill & S_{k+1}\hfill \end{array}$

regiones en conjunto. (Aquí no hay necesidad de álgebra: solo se necesita usar la condición del triángulo Pascal).

De ahí$P(k+1)$es cierto siempre que$P(k)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 0$.

258. Observe que, dada una disección de un cuadrado en k cuadrados, siempre podemos cortar un cuadrado en cuatro cuartos (por líneas a través del centro, y paralelas a los lados), y así crear una disección con$k+3$cuadrados.

Let$P(n)$ser la declaración:

“Cualquier cuadrado dado se puede cortar en m (no necesariamente congruentes) cuadrados más pequeños, por cada m,$6\le m\le n$”.

• Dejar$n=6$. Dado cualquier cuadrado de lado s (digamos). Podemos cortar un cuadrado de lado$\frac{}{}$2s3desde una esquina, dejando una tira en forma de L de ancho$\frac{s}{3}$, que luego podemos cortar en 5 cuadrados más pequeños, cada uno de lado$\frac{s}{3}$. De ahí$P(6)$es verdad.

Let$n=7$. Dado cualquier cuadrado, podemos dividir el cuadrado primero en cuatro cuartos; luego dividir uno de estos cuadrados más pequeños en cuatro cuartos para obtener una disección en 7 cuadrados más pequeños. De ahí$P(7)$es verdad.

Let$n=8$. Dado un cuadrado de lado s (digamos). Podemos cortar un cuadrado de lado$\frac{}{}$3s4desde una esquina, dejando una tira en forma de L de ancho$\frac{s}{4}$, que luego podemos cortar en 7 cuadrados más pequeños, cada uno de lado$\frac{s}{4}$. De ahí$P(8)$es verdad.

• Supongamos que$P(k)$es cierto para algunos$k\ge 8$.

Entonces$k-2\ge 6$, por lo que cualquier cuadrado dado se puede diseccionar en$k-2$cuadrados más pequeños (por$P(k)$). Tomando esta disección y dividiendo uno de los cuadrados más pequeños en cuatro cuartos da una disección del cuadrado inicial en$k-2+3$cuadrados. De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 6$.

259. Let$P(n)$ser la declaración:

“Cualquier árbol con n vértices tiene exactamente$n-1$bordes”.

• Un árbol con 1 vértice es simplemente un vértice con 0 bordes (ya que cualquier borde tendría que ser un bucle, y luego crearía un ciclo). De ahí$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos$k\ge 1$.

Considere un árbol arbitrario T con$k+1$vértices.

[Idea: Necesitamos encontrar alguna manera de reducir T a un árbol$T^{\prime }$con k vértices. Esto sugiere “eliminar un vértice final”. Entonces primero debemos probar que “cualquier árbol T tiene un vértice final”.]

Definición El número de bordes incidentes con un vértice dado v se denomina valencia de v.

Lema Let S sea un árbol finito con$s>1$vértices. Entonces S tiene un vértice de valencia 1 —es decir, un “vértice final”.

Prueba Elige cualquier vértice$v_0$. Entonces$v_0$debe estar conectado con el resto del árbol, por lo que$v_0$tiene valencia por lo menos 1.

Si$v_0$es un “vértice final”, luego deténgase; si no, elija un vértice$v_1$que es adyacente a$v_0$.

Si$v_1$es un “vértice final”, luego deténgase; si no, elija un vértice$v_2\ne v_0$que es adyacente a$v_1$.

Si$v_2$es un “vértice final”, luego deténgase; si no, elija un vértice$v_3\ne v_1$que es adyacente a$v_2$.

Continuar de esta manera.

Todos los vértices$v_0,v_1,v_2,v_3,...$debe ser diferente (ya que cualquier repetición$v_m=v_n$con$m<n$definiría un ciclo

$$v_m,v_{m+1},v_{m+2},...,v_{n-1},v_n=v_m$$

en el árbol S). Como sabemos que el árbol es finito (teniendo precisamente s vértices), el proceso debe terminar en alguna etapa. El vértice final$v_e$es entonces un “vértice final”, de valencia 1.

Si aplicamos el Lema a nuestro árbol arbitrario T con$k+1$vértices, podemos elegir un “vértice final” v y eliminarlo tanto como el borde e incidente con él para obtener un árbol$T^{\prime }$teniendo k vértices. Por$P(k)$sabemos que$T^{\prime }$tiene exactamente$k-1$bordes, así que cuando restablecimos el borde e, vemos que T tiene exactamente$(k-1)+1$bordes, entonces$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 1$.

260.

Nota: Todos los poliedros descritos en esta solución son “esféricos” en virtud de tener sus vértices ubicados en la esfera unitaria.

(a) (i) Un tetraedro regular.

(ii) Una pirámide cuadrada con su ápice en el polo Norte.

(b) Si un poliedro esférico tiene V vértices, bordes E y caras F, entonces

$$V-E+F=2.$$

Ahora cada borde tiene exactamente dos vértices finales, por lo que$2E$cuenta el número exacto de pares ordenados (v, e), donde e es un borde, y v es un vértice “incidente con e”.

Por otra parte, en un poliedro esférico, cada vértice v tiene valencia al menos 3; por lo que cada vértice v ocurre en al menos 3 pares (v, e) de este tipo. De ahí$2E\ge 3V$.

De la misma manera, cada borde e se encuentra en el límite de exactamente 2 caras, por lo que$2E$cuenta el número exacto de pares ordenados (f, e), donde e es un borde de la cara f.

Por otra parte, en un poliedro esférico, cada cara f tiene al menos 3 bordes; así cada cara f se presenta en al menos 3 pares (f, e) de este tipo. De ahí$2E\ge 3F$.

Si$E=7$, luego$14\ge 3V$, y$14\ge 3F$; ahora V y F son números enteros, entonces$V\le 4$y$F\le 4$. De ahí$V+F\le 8$. Sin embargo$V+F=E+2=9$. Esta contradicción demuestra que no existe tal poliedro.

(c) Mostramos por inducción cómo construir ciertos poliedros “esféricos”, con como máximo una cara no triangular. Let$P(n)$ser la declaración:

“Existe un poliedro esférico con como máximo una cara no triangular, y con bordes e para cada$e,$ $8\le e\le n$”.

• Sabemos que existe un poliedro tan esférico con$n=6$bordes — es decir, el tetraedro regular (con cuatro caras, que son todos triángulos equiláteros).

Sabemos que no existe tal poliedro con$n=7$aristas (por parte (b)).

Cuando$n=8$, no hay poliedro esférico con$n=8$aristas y todas las caras triangulares (ya que entonces tendríamos$16=2E=3F$, como en la parte b)). Sin embargo, existe un poliedro esférico con$n=8$bordes y una sola cara no triangular, es decir, la pirámide de base cuadrada con su vértice en el polo norte.

Cuando$n=9$, podemos unir tres puntos en el ecuador a los polos Norte y Sur para producir una bi-pirámide triangular (la dual de un prisma triangular), con todas las caras triangulares, y con$n=9$bordes.

Cuando$n=10$, no hay poliedro esférico con$n=10$aristas y con todas las caras triángulos (ya que entonces tendríamos que tener$20=2E=3F$, como en la parte b)); pero existe un poliedro esférico con$n=10$bordes y una sola cara que no es un triángulo equilátero, es decir, la pirámide pentagonal con su ápice en el polo norte.

Esto nos proporciona un punto de partida para la construcción inductiva. En particular$P(8)$,$P(9)$, y$P(10)$son todas ciertas.

• Supongamos que$P(k)$es cierto para algunos$k\ge 10$. La única parte de la declaración$P(k+1)$que queda por demostrar es la existencia de un poliedro adecuado con$k+1$bordes.

Desde$k\ge 10$, sabemos que$k-2\ge 8$, so (por$P(k)$) existe un poliedro con todos sus vértices en la esfera unitaria, con como máximo una cara no triangular, y con$e=k-2$bordes. Toma este poliedro y quita una cara triangular$ABC$. Ahora agrega un nuevo vértice X en la esfera, interno al triángulo esférico$ABC$, y añadir los bordes$XA$,$XB$,$XC$y las tres caras triangulares$$XAB,$$XBC,$$XCA, para producir un poliedro esférico con$e=(k-2)+3=k+1$bordes, y con como máximo una cara no triangular. De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 8$.

261. Para probar un resultado que se da en forma de declaración de “si y solo si”, tenemos que probar dos cosas: “si” y “solo si”.

Comenzamos por probar la parte “sólo si”:

“un mapa se puede colorear correctamente con dos colores sólo si cada vértice tiene valencia par”.

Que M sea un mapa que pueda ser coloreado correctamente con dos colores. Que v sea cualquier vértice del mapa M.

Los bordes$e_1,e_2,e_3,...$incidente con v forman partes de los límites de la secuencia de regiones alrededor del vértice v (con$e_1$,$e_2$limítrofes con una región;$e_2$,$e_3$bordeando el siguiente; y así sucesivamente). Dado que estamos asumiendo que las regiones del mapa M pueden ser “correctamente coloreadas” con dos colores, la sucesión de regiones alrededor del vértice v se puede colorear adecuadamente con solo dos colores. De ahí que los colores de las regiones alrededor del vértice v deban alternarse (digamos negro-blanco-negro-...). Y como el mapa es finito, esta secuencia debe volver al inicio —por lo que el número de tales regiones en el vértice v (y de ahí el número de aristas incidentes con v — es decir, la valencia de v) debe ser par.

Ahora probamos la parte “si”:

“un mapa se puede colorear correctamente con dos colores si cada vértice tiene valencia par”.

Supongamos que tenemos un mapa M en el que cada vértice tiene valencia par. Debemos probar que cualquier mapa M de este tipo puede ser coloreado correctamente usando solo dos colores.

Let$P(n)$ser la declaración:

“cualquier mapa con m bordes, en el que cada vértice tenga valencia uniforme, puede colorearse adecuadamente con dos colores siempre que m satisfaga$1\le m\le n$,”.

• Si$n=1$, un mapa en el que cada vértice tiene valencia uniforme, y que tiene un solo borde$e$, debe consistir en un solo vértice v, con$e$como un bucle de$v$a$v$(entonces$v$tiene valencia 2, ya que el borde$e$es incidente con$v$dos veces). Esto crea un mapa con dos regiones: la “isla” dentro del bucle, y el “mar” afuera; para que podamos darle color a la “isla” de negro y al “mar” de blanco. De ahí$P(1)$es verdad.

• Supongamos que$P(k)$es cierto para algunos$k\ge 1.$

La mayor parte del contenido de la declaración$P(k+1)$ya están garantizados por$P(k)$. Para probar que$P(k+1)$es verdad, todo lo que queda por probar es que

cualquier mapa con$k+1$Los bordes, en los que cada vértice tiene valencia uniforme, pueden colorearse adecuadamente usando solo dos colores.

Considera un mapa arbitrario M con$k+1$bordes, en los que cada vértice tiene valencia uniforme.

[Idea: Necesitamos encontrar alguna manera de reducir el mapa M a un mapa$M^{\prime }$con$\le k$bordes, en los que cada vértice todavía tiene valencia par.]

Desde$k\ge 1$, el mapa M tiene al menos 2 bordes. Elija cualquier borde e de M, con (digamos) vértices$u_1$,$u_2$como sus puntos finales, y con las regiones R, S a cada lado de e.

Supongamos primero que$u_1=u_2$, por lo que el límite de la región R (digamos) consiste únicamente en el borde e. Por lo tanto e es un bucle, y S es la única región vecina R. El borde e aporta 2 a la valencia de$u_1$; así que si eliminamos el borde e, obtenemos un mapa$M^{\prime }$en el que cada vértice vuelve a tener valencia uniforme, en la que las regiones R y S se han amalgamado en una región$S^{\prime }$. Desde$M^{\prime }$tiene solo k bordes,$M^{\prime }$puede ser coloreado correctamente con solo dos colores. Si ahora restablecemos el borde e y la región R, podemos darle a S el mismo color que$S^{\prime }$(en la coloración adecuada de$M^{\prime }$) y dar a R el color opuesto a$S^{\prime }$para obtener una coloración adecuada del mapa M con solo dos colores.

De ahí que podamos suponer que$u_1\ne u_2$, por lo que e no es el límite completo de R. Luego podemos reducir lentamente el borde e hasta un punto, finalmente fusionando los viejos vértices$u_1$,$u_2$juntos para formar un nuevo vértice$u^{\prime }$, donde dos nuevas regiones$R^{\prime }$,$S^{\prime }$conocer. El resultado es entonces un nuevo mapa$M^{\prime }$, en el que todos los demás vértices están inalterados (y por lo tanto tienen valencia uniforme), y en el que

$$\text{valencia}(u^{\prime })=(\text{valencia}(u_1)-1)+(\text{valencia}(u_2)-1)$$

que también es parejo.

De ahí cada vértice del nuevo mapa$M^{\prime }$tiene incluso valencia. Además,$M^{\prime }$tiene a lo sumo k bordes, así que (por$P(k)$) sabemos que el mapa$M^{\prime }$puede ser coloreado correctamente con solo dos colores. Y en esta coloración de$M^{\prime }$, hay un número impar de cambios de color a medida que uno va de$R^{\prime }$a$S^{\prime }$a través de las otras regiones que se encuentran alrededor del viejo vértice$u_1$de M, entonces$S^{\prime }$recibe el color opuesto a$R^{\prime }$. El adecuado bicolor garantizado de$M^{\prime }$por lo tanto, se extiende hacia atrás para dar una adecuada bicoloración del mapa original M. De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 1$.

262. Let$P(n)$ser la declaración:

“El$2^n$las secuencias de longitud n que consisten en 0s y 1s pueden organizarse en una lista cíclica de tal manera que dos secuencias vecinas cualesquiera (incluyendo la última y la primera) difieran exactamente en una posición de coordenadas.”

• Cuando$n=2$, el ciclo requerido es obvio:

$$00\to 10\to 11\to 01(\to 00).$$Entonces$P(2)$es verdad.

• La construcción general tal vez se ilustra mejor mostrando primero cómo$P(2)$lleva a$P(3)$.

El ciclo anterior para secuencias de longitud 2 da lugar a dos ciclos disjuntos para secuencias de longitud 3:

— primero agregando una tercera coordenada “0”:

$$000\to 100\to 110\to 010(\to 000)$$

— luego añadiendo una tercera coordenada “1”:

$$001\to 101\to 111\to 011(\to 001).$$

Ahora elimina el join final en cada ciclo ($010\to 000$y$011\to 001$) y en su lugar vincular los dos ciclos juntos invirtiendo primero el orden del primer ciclo y luego insertando las uniones$000\to 001$y$011\to 010$para formar un solo ciclo.

En general, supongamos que$P(k)$es cierto para algunos$k\ge 1$. Luego construimos un solo ciclo para el$2^{k+1}$secuencias de longitud$k+1$de la siguiente manera:

Toma el ciclo del$2^k$secuencias de longitud k garantizadas por$P(k)$, y formar dos ciclos disjuntos de longitud$2^k$

• primero agregando una coordenada final “0”

• luego agregando una coordenada final “1”.

Luego vincula los dos ciclos en un solo ciclo de duración$2^{k+1}$, eliminando el paso final

$$v_1{v}_2\cdots v_{k}0\to 00\cdots 00$$en el primer ciclo, y$v_1{v}_2\cdots v_{k}1\to 00\cdots 01$

en el segundo ciclo, invirtiendo el primer ciclo e insertando las juntas

$$00\cdots 00\to 00\cdots 01\text{y}{v}_1{v}_2\cdots v_{k}1\to v_1{v}_2\cdots v_{k}0$$

para producir un solo ciclo del tipo requerido uniendo todos$2^{k+1}$secuencias de longitud$k+1$. De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

Nota: La significación de lo que llamamos códigos Gray fue resaltada en una patente de 1953 por el ingeniero Frank Gray (1887-1969) —donde fueron llamados códigos binarios reflejados (ya que el paso crucial en su construcción anterior implica tomar dos copias de los ciclos anteriores, revertir uno de los ciclos, y luego producir la mitad del ciclo requerido atravesando la primera copia antes de regresar hacia atrás a lo largo de la segunda copia). Su uso más básico es volver a codificar la secuencia habitual de conteo binario

$$1\to 10\to 11\to 100\to 101\to 110\to 111\to 1000\to 1001\to 1010\to \cdots ,$$

donde un solo paso puede llevar a la necesidad de cambiar arbitrariamente muchos dígitos binarios (por ejemplo, el paso de$3=\text{“}11$” a$4=\text{“}100$” cambia 3 dígitos, y el paso de$7=\text{“}111$” a$8=$“1000” cambia 4 dígitos, etc.) —requisito que es ineficiente en términos de “conmutación” electrónica, y que aumenta la probabilidad de errores. Por el contrario, la secuencia de código Gray cambia un solo dígito binario en cada paso. Sin embargo, la energía física que se ahorra mediante la reducción de la cantidad de “conmutación” en los circuitos corresponde a un aumento en la necesidad de fórmulas matemáticas desconocidas, que reinterpretan cada vector en el código Gray como el entero ordinario en la secuencia de conteo a la que se corresponde.

263.

(a) Toda la construcción es inductiva (cada etiqueta deriva de una etiqueta anterior). Así que vamos$P(n)$ser la declaración:

“si$$HCF(r,s)=1y$2\le r+s\le n$, luego el positivo racional$\frac{r}{s}$ocurre una vez y sólo una vez como etiqueta, y ocurre en sus términos más bajos”.

• Por construcción se le da la etiqueta a la raíz$\genfrac{}{}{0.1ex}{}{1}{1}$, entonces$\genfrac{}{}{0.1ex}{}{1}{1}$ocurre. Y no puede volver a ocurrir, ya que el numerador y denominador de cada vértice padre son ambos positivos, ni i ni j pueden ser nunca 0. De ahí$P(2)$es verdad.

Observe que la construcción básica:

“si$\frac{i}{j}$es un vértice `parent', luego etiquetamos a su `descendiente izquierdo' como$\frac{i}{i+j}$, y su `descendiente derecho'$\frac{i+j}{j}$”

garantiza que, desde que empezamos etiquetando la raíz con el racional positivo$\genfrac{}{}{0.1ex}{}{1}{1}$, todos los “descendientes” posteriores son positivos.

Además, si algún `descendiente' apareciera repentinamente no “en términos más bajos”, entonces tampoco

—$$HCF(i,i+j)>1, en cuyo caso$$HCF(i,i+j)=HCF(i,j), entonces$$HCF(i,j)>1en la etapa anterior; o

—$$HCF(i+j,j)>1, en cuyo caso$$HCF(i+j,j)=HCF(i,j), entonces$$HCF(i,j)>1en la etapa anterior.

Desde que comenzamos por etiquetar la raíz$\genfrac{}{}{0.1ex}{}{1}{1}$, donde$$HCF(1,1)=1, se deduce que todas las etiquetas posteriores son racionales positivos en términos más bajos.

• Supongamos que$P(k)$es cierto a partir de algunos$k\ge 2$.

La mayoría de las partes de la declaración$P(k+1)$están garantizados por$P(k)$. Para demostrar que$P(k+1)$es cierto, queda por considerar casos en los que$$HCF(r,s)=1y$r+s=k+1$($\ge 3$). O bien (i)$r>s$, o ii)$s>r$.

i) Supongamos que$r>s$. Entonces$\frac{r}{s}$surge en esta forma (totalmente cancelada) solo como descendiente directo (derecho) de$\frac{r-s}{s}$. Entonces$\frac{r}{s}$ocurre. Además, cada etiqueta se presenta en sus términos más bajos, por lo que$\frac{r}{s}$no puede volver a ocurrir.

ii) Supongamos que$s>r$. Entonces$\frac{r}{s}$surge en esta forma (totalmente cancelada) solo como descendiente directo (izquierdo) de$\frac{r}{s-r}$. Entonces$\frac{r}{s}$ocurre. Además, cada etiqueta se presenta en sus términos más bajos, por lo que$\frac{r}{s}$no puede volver a ocurrir.

De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

b) El hecho de que las etiquetas sean simétricas izquierda-derecha también es un fenómeno inductivo. Observamos que la única etiqueta completamente “simétrica izquierda-derecha”, a saber$\genfrac{}{}{0.1ex}{}{1}{1}$, ocurre en la única posición completamente “simétrica izquierda-derecha”, es decir, en la raíz.

Todas las demás etiquetas aparecen en pares recíprocos:$\frac{r}{s}$y$\frac{s}{r}$, donde podemos suponer que$r>s$. El hecho de que estos ocurran como etiquetas de vértices “simétricos izquierda-derecha” deriva del hecho de que

$\frac{r}{s}$es el `descendiente derecho' de$\frac{r-s}{s}$y

$\frac{s}{r}$es el `descendiente izquierdo' de$\frac{s}{r-s}$.

Entonces, si sabemos que el par recíproco anterior par recíproco$\frac{r-s}{s}$y$\frac{s}{r-s}$ocurren como etiquetas de vértices posicionados simétricamente, entonces se deduce que lo mismo es cierto para el par recíproco descendiente$\frac{r}{s}$y$\frac{s}{r}$. Dejamos al lector escribir la prueba por inducción — por ejemplo, usando el enunciado

”$P(n)$: si$r,s>0$, y$2\le r+s\le n$, luego el par recíproco$\frac{r}{s}$,$\frac{s}{r}$ocurren como etiquetas de vértices al mismo nivel por debajo de la raíz, siendo los dos vértices etiquetados imágenes especulares entre sí alrededor del espejo vertical a través del vértice raíz”.

264. Los intervalos en este problema pueden ser de cualquier tipo (incluyendo finitos o infinitos). Cada intervalo tiene dos “puntos finales”, que son números reales ordinarios, o$\pm \infty$(lo que significa que el intervalo va al infinito en una o ambas direcciones).

Let$P(n)$ser la declaración:

“si una colección de n intervalos en el eje x tiene la propiedad de que dos intervalos cualesquiera se superponen en un intervalo (de posiblemente longitud cero, es decir, un punto), entonces la intersección de todos los intervalos en la colección es un intervalo no vacío”.

Cuando$n=2$, la hipótesis de$P(2)$es lo mismo que la conclusión. Entonces$P(2)$es verdad.

Supongamos que$P(k)$es cierto para algunos$k\ge 2$. Buscamos demostrar que$P(k+1)$es verdad.

Así que considere una colección de$k+1$intervalos con la propiedad que dos intervalos cualesquiera de la colección se cruzan en un intervalo no vacío. Si esta colección incluye un intervalo que se enumera más de una vez, entonces la conclusión requerida se desprende de$P(k)$. Entonces podemos suponer que los intervalos en nuestra colección son todos diferentes.

Entre los$k+1$intervalos, considere primero aquellos con el punto final más grande a la derecha. Si solo hay uno de esos intervalos, denotarlo por$I_0$; si hay más de un intervalo con el mismo punto final más grande a la derecha, deje$I_0$ser el intervalo entre aquellos con el punto final más grande a la derecha que tiene el punto final más grande a la izquierda. En cualquier caso, ponga$I_0$aparte por el momento, dejando una colección S de k intervalos con la propiedad requerida.

Por$P(k)$sabemos que los intervalos en la colección S se cruzan en un intervalo no vacío I, con el punto final izquierdo a y el extremo derecho b (digamos).

Tenemos que demostrar que la intersección$I\cap I_0$no está vacío.

La prueba que sigue funciona si el punto final b está incluido en el intervalo I. El ligero ajuste necesario si b no está incluido en el intervalo I se deja al lector.

Desde el punto final derecho de$I_0$es el mayor posible, y dado que los puntos entre a y b pertenecen a todos los intervalos de S, podemos estar seguros de que el punto final derecho de$I_0$es$\ge b$.

Además, para cada punto$x>b$, sabemos que debe haber algún intervalo$I_x$en la colección S que no se estira tan a la derecha como x. Dado que, por hipótesis, la intersección$I_0\cap I_x$no está vacío, el extremo izquierdo de$I_0$yace a la izquierda de cada uno de esos puntos x, así$I_0$debe superponerse al intervalo I, de donde se deduce que$I\cap I_0$es un intervalo no vacío según sea necesario.

De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

265. Si uno experimenta un poco, debería quedar claro

• que si tanque$T_2$contiene más de tanque$T_1$y luego vincular el tanque T a$T_2$conduce a un mejor resultado inmediato (es decir, una cantidad mayor en el tanque T) que vincular T a$T_1$;

• que si, en alguna etapa de la secuencia de enlace, el tanque T contiene una cantidad provisional de a litros, y está a punto de vincularse sucesivamente a un tanque que contiene b litros, y luego al tanque que contiene c litros, este par ordenado de cambios altera la cantidad en el tanque T a$\frac{a+b+}{}$2c4litros; así que para un mejor resultado final siempre debemos elegir la secuencia para que$b<c$;

• una vez que se ha abierto el grifo que une el tanque T a otro tanque, de modo que los dos niveles se igualan, no hay beneficio de abrir el grifo que une estos dos tanques nunca más, por lo que el tanque T debe vincularse entre sí a lo sumo una vez.

Estas tres observaciones determinan esencialmente la respuesta, es decir, que el tanque T debe unirse a los otros tanques en orden creciente de su contenido inicial.

Para una prueba por inducción, deje$P(n)$ser la declaración:

“dado n tanques que contienen$a_1,a_2,a_3,...,a_n$litros respectivamente, donde

$a_1<a_2<a_3<...<a_n,$

si T es el tanque que contiene la cantidad más pequeña$a_1$litros, luego la secuencia óptima para unir el otro$n-1$tanques a tanque T (óptimo en el sentido de que transfiere la cantidad máxima de agua al tanque T) es la secuencia que une T sucesivamente a los otros tanques en orden creciente de su contenido inicial”.

• Cuando$n=2$, sólo hay una secuencia posible, que es la descrita, por lo que$P(2)$es verdad.

• Supongamos que$P(k)$es cierto para algunos$k\ge 2$, y considerar una colección desconocida de$k+1$tanques que contienen$a_1,a_2,a_3,...,a_{k+1}$litros respectivamente, donde

$$a_1<a_2<a_3<...<a_{k+1},$$

y donde T es el tanque que inicialmente contiene$a_1$litros.

Supongamos que en la secuencia óptima de k uniones sucesivas a los otros k tanques (es decir, que transfiere la mayor cantidad posible de agua al tanque T), la sucesión de uniones es unir T primero al tanque$T_2$, luego al tanque$T_3$, y así sucesivamente hasta el tanque$T_{k+1}$(donde tanque$T_m$no es necesariamente el tanque que contiene$a_m$litros). Ahora hay dos posibilidades: ya sea

(i)$T_{k+1}$es el tanque que contiene$a_{k+1}$litros, o

ii)$T_{k+1}$contiene menos de$a_{k+1}$litros.

(i) Supongamos tanque$T_{k+1}$es el tanque que contiene$a_{k+1}$litros. Luego la primera$k-1$las juntas involucran los k tanques que contienen$a_1,a_2,a_3,...,a_k$litros. Y sabemos (por el primer punto de viñeta anterior) que, para maximizar la cantidad final en el tanque T, la cantidad en el tanque T después de vincularlo al tanque$T_k$debe ser “lo más grande que pueda ser”. Por lo tanto, por$P(k)$, la primera$k-1$une el enlace T sucesivamente a los otros tanques en orden creciente de su contenido, antes de finalmente vincularlo al tanque que contiene$a_{k+1}$litros. De ahí la conclusión de$P(k+1)$sostiene.

(ii) Ahora supongamos que ese tanque$T_{k+1}$contiene$a_m<a_{k+1}$litros.

Por el primer punto de viñeta, con el fin de garantizar el resultado global óptimo de la vinculación final con tanque$T_{k+1}$la cantidad en el tanque T después de que se haya vinculado al tanque$T_k$debe ser “tan grande como sea posible” (dadas las cantidades en los tanques$T,T_2,T_3,...,T_k$). De ahí declaración$P(k)$se aplica a la secuencia inicial de$k-1$se une (de T a$T_2$, luego a$T_3$, y así sucesivamente hasta$T_k$), y garantiza que estos tanques deben estar en orden creciente de su contenido inicial. En particular, el último tanque de esta secuencia,$T_k$, debe ser el que contenga$a_{k+1}$litros. Pero si denotamos por litros la cantidad en el tanque T justo antes de que se vincule con el tanque$T_k$(que contiene$a_{k+1}$litros), luego los dos últimos enlaces, con$b=a_{k+1}$y$c=a_m$contradecir el segundo punto de viñeta al inicio de esta solución. De ahí que el caso (ii) no pueda ocurrir.

De ahí$P(k+1)$es verdad.

De ahí$P(n)$es cierto para todos$n\ge 2$.

266.

Nota: Como todos los problemas prácticos, éste requiere de un elemento de “modelización” inicial para que la situación sea susceptible de análisis matemático.

El `residuo' se adhiere a las superficies; por lo que la cantidad total de `residuo' dependerá de

a) la viscosidad del producto químico (qué tan “gruesa” o “adhesiva” es), y

(b) la superficie total del interior del matraz.

Dado que no se nos da información sobre las cantidades, podemos fijar la cantidad de residuo que queda en el matraz `vacío' en “1 unidad”, y la cantidad de solvente en el otro matraz como “s unidades”.

Si agregamos el solvente, obtenemos una cantidad combinada de$1+s$unidades de solución — que podemos suponer (después de sacudidas adecuadas) que son homogéneas, con la concentración química reducida a “1 parte en$1+s$”.

El primer desafío de modelización surge cuando tratamos de darle sentido matemático a lo que queda en cada etapa después de vaciar el frasco. Se fija la superficie interna del matraz, a la que se pueda adherir cualquier residuo diluido. Si cometemos el error de pensar en el químico original como “espeso y pegajoso” y el solvente como “delgado”, entonces la viscosidad del residuo diluido cambiará con relación al original, y lo hará de formas que no podemos saber. De ahí que la única suposición razonable (que puede o no ser válida en un caso particular) es asumir que la viscosidad del producto químico original es aproximadamente la misma que la viscosidad de la mezcla químico-disolvente. Esto sugiere entonces que, al vaciar la mezcla diluida, aproximadamente la misma cantidad (1 unidad) de mezcla diluida permanecerá adheridas a las paredes del matraz. Entonces nos quedaremos con 1 unidad de residuo, con una concentración de$\frac{1}{1+s}$. En particular, si$s=1$, usando todo el solvente a la vez reduce la cantidad de residuo químico tóxico a$\genfrac{}{}{0.1ex}{}{1}{2}$unidad (con la otra$\genfrac{}{}{0.1ex}{}{1}{2}$unidad que consiste en disolvente).

Pero, ¿y si primero usamos solo la mitad del solvente, vaciamos el matraz y luego usamos la otra mitad? Añadiendo$\frac{s}{2}$unidades de solvente (y agitando a fondo) produce$1+\frac{s}{2}$unidades de mezcla homogénea, con una concentración de 1 parte por$1+\frac{s}{2}$. Cuando vaciamos el matraz, esperamos aproximadamente 1 unidad de residuo con esta concentración, así que solo$\frac{2}{2+s}$unidades del químico, con$\frac{s}{2+s}$unidades de solvente.

Si luego agregamos el otro$\frac{s}{2}$unidades de solvente, esto produce$1+\frac{s}{2}$unidades de mezcla con una concentración de 1 parte por${\left(1+\frac{s}{2}\right)}^2$. Cuando vaciamos el matraz, esperamos aproximadamente 1 unidad de residuo con concentración 1 parte por${\left(1+\frac{s}{2}\right)}^2$. En particular, si$s=1$, esta estrategia reduce la cantidad de sustancia química tóxica en la 1 unidad de residuo a$\genfrac{}{}{0.1ex}{}{4}{9}$unidades. Desde$\frac{4}{9}<\frac{1}{2}$esta estrategia de dos etapas parece más efectiva que la anterior estrategia “todo a la vez”.

Supongamos que usamos una estrategia de cuatro etapas, usando primero un cuarto del solvente, luego otro cuarto, y así sucesivamente. Luego aterrizamos con aproximadamente 1 unidad de residuo con concentración 1 parte por${\left(1+\frac{s}{4}\right)}^4$. En particular, si$s=1$, aterrizamos con la cantidad de químico tóxico en la 1 unidad de residuo igual a$\genfrac{}{}{0.1ex}{}{256}{625}$unidades, y$\frac{256}{625}<\frac{4}{9}$. De manera más general, si usamos$\left(\frac{1}{n}\right)$th del solvente, n veces, la cantidad final de químico tóxico en la 1 unidad de residuo es igual a${\left(1+\frac{s}{n}\right)}^{-n}$. Y a medida que n se hace cada vez más grande, esta expresión se acerca cada vez más a$e^{-s}$. En particular, cuando$s=1$, esta estrategia deja una cantidad final de sustancia química en la 1 unidad de residuo aproximadamente igual a$\frac{1}{e}=0.367879\cdots$.

Nota: La situación aquí es similar a la que enfrenta un diseñador de lavadoras, que desea eliminar restos de detergente de los artículos que han sido lavados, sin usar cantidades ilimitadas de agua. La idea de tener una “cantidad fija de disolvente” corresponde al objetivo de un enjuague “eficiente en el agua”. Sin embargo, el ciclo de la lavadora, o programa, claramente no puede repetir el enjuague indefinidamente (como se requeriría en el caso limitante anterior).

267.

i) Si$\sqrt{2}=\frac{m}{n}$, luego

$$$$2n2=m2

De ahí que m ² sea parejo.

De ello se deduce que m debe ser parejo.

Nota: Es un hecho que, si$m=2k$es parejo, entonces$m^2=$4k2también es parejo. Pero esto es completamente irrelevante aquí. Para concluir que “m debe ser parejo”, tenemos que demostrar:

Reclamar m no puede ser impar.

Prueba Supongamos que m es impar.

$\therefore$ $m=2k+1$para algunos enteros k.

Pero entonces

$$m^2={(2k+1)}^2=4k^2+4k+1$$

sería impar, contrario a “m ² debe ser par”.

De ahí que m no pueda ser impar.

(ii) Como m es parejo, podemos escribir$m=2m^{\prime }$para algún número entero$m^{\prime }$. La ecuación (*) en (i) anterior entonces se convierte$n^2=2{(m^{\prime })}^2$, por lo que n ² es par. De ahí que, como en la Nota anterior, n debe ser parejo, para que podamos escribir$n=2n^{\prime }$para algún número entero$n^{\prime }$.

iii) Si$\sqrt{2}=\frac{m}{n}$, luego$m=2m^{\prime }$, y$n=2n^{\prime }$son ambos parejos.

$\therefore$ $\sqrt{2}=\frac{m}{n}=\frac{2m^{\prime }}{2n^{\prime }}=\frac{m^{\prime }}{n^{\prime }}$.

De la misma manera, se deduce que$m^{\prime }$y$n^{\prime }$son ambos parejos, así que podemos escribir$m^{\prime }=2m\text{'}\text{'}$,$n^{\prime }=2n\text{'}\text{'}$para algunos enteros$m\text{'}\text{'}$,$n\text{'}\text{'}$.

Continuando de esta manera produce entonces una interminable secuencia decreciente de denominadores positivos

$$n>n^{\prime }>n\text{'}\text{'}>...>0.$$

contrariamente al hecho de que tal secuencia puede tener longitud como máximo$n-1$(o de hecho, a lo sumo$1+$registro2n).

268.

i) Si$a<b$y$c>0$, luego$ac<bc$.

Si$0<\sqrt{2}\le 1$, luego (multiplicando por$\sqrt{2}$) se deduce que$2\le \sqrt{2}\le 1$, que es falso. De ahí$\sqrt{2}>1$.

Ahora sabemos que$1<\sqrt{2}$, multiplicando así por$\sqrt{2}$da$\sqrt{2}<2$. De ahí$1<\sqrt{2}<2$. En particular,$\sqrt{2}$no se puede escribir como una fracción con denominador 1, entonces$P(1)$es verdad.

(ii) Supongamos$P(k)$es cierto para algunos$k\ge 1$. La mayor parte de la declaración$P(k+1)$está implícito por$P(k)$: todo lo que queda por probar es que$\sqrt{2}$no se puede escribir como una fracción con denominador$n=k+1$.

Supongamos$\sqrt{2}=\frac{m}{n}$, donde$n=k+1$y m son números enteros positivos.

Entonces$m=2m^{\prime }$y$n=2n^{\prime }$ambos son parejos (como en el Problema 267).

Entonces$\sqrt{2}=\frac{m^{\prime }}{n^{\prime }}$con$n^{\prime }\le k$, contrario a$P(k)$. De ahí$P(k+1)$sostiene.

$\equiv$ $P(n)$es cierto para todos$n\ge 1$.

269.

(a) Supongamos que S no está vacío. Entonces por el Principio de Elemento Mínimo el conjunto S debe contener un elemento mínimo k: es decir, un entero más pequeño k que no está en el conjunto T. Entonces$k\ne 1$(ya que se nos dice que T contiene el entero 1). De ahí$k>1$.

Por lo tanto$k-1$es un número entero positivo que es menor que k. Entonces$k-1$no es un elemento de S, y por lo tanto debe ser un elemento de T. Pero si$k-1$es un elemento de T, entonces se nos dice que$(k-1)+1$también debe ser miembro de T. Esta contradicción muestra que S debe estar vacío, por lo que T contiene todos los enteros positivos.

b) Supongamos que T no tiene un elemento más pequeño. Claramente 1 no pertenece al conjunto T (o sería el elemento más pequeño de T). De ahí que 1 debe ser un elemento del conjunto S.

Ahora supongamos que, para algunos$k\ge 1$, todos los enteros positivos$1,2,3,...,k$son elementos de S, pero$k+1$no es un elemento de S. Entonces$k+1$sería un elemento de T, y sería el elemento más pequeño de T, lo cual no es posible. De ahí que S tenga la propiedad que

“siempre que$k\ge 1$es un elemento de S, podemos estar seguros de que$k+1$es también un elemento de S”.

El Principio de Inducción Matemática garantiza entonces que estas dos observaciones (que 1 es un elemento de S, y que siempre que k es un elemento de S, así es$k+1$) implican que S contiene todos los enteros positivos, de manera que el conjunto T debe estar vacío —contrario a lo que se supone.

De ahí que T deba tener un elemento más pequeño.

270.

i) Triángulo$O{P}^{\prime }{Q}^{\prime }$es un triángulo en ángulo recto con$\angle P^{\prime }O{Q}^{\prime }={45}^{°}$. De ahí que los dos ángulos de base (en O y en$Q^{\prime }$) son iguales, por lo que el triángulo es isósceles:$\underset{\_}{P^{\prime }{Q}^{\prime }}=\underset{\_}{P^{\prime }O}$.

ii) Triángulos$Q{Q}^{\prime }{P}^{\prime }$y$Q{Q}^{\prime }R$son congruentes por RHS (ya que comparten la hipotenusa$\underset{\_}{Q{Q}^{\prime }}$, y tienen lados iguales ($\underset{\_}{Q{P}^{\prime }}=\underset{\_}{QP}=\underset{\_}{QR}$). De ahí$\underset{\_}{Q^{\prime }{P}^{\prime }}=\underset{\_}{Q^{\prime }R}$.

iii) Si$\underset{\_}{OQ}:\underset{\_}{OP}=m:n$, podemos elegir una unidad para que$\underset{\_}{OQ}$tiene longitud m unidades y$\underset{\_}{OP}$tiene longitud n unidades. Entonces

$$\underset{\_}{O{P}^{\prime }}=\underset{\_}{OQ}-\underset{\_}{Q{P}^{\prime }}=\underset{\_}{OQ}-\underset{\_}{QP}=m-n,$$

y

$$\underset{\_}{O{Q}^{\prime }}=\underset{\_}{OR}-\underset{\_}{Q^{\prime }R}=\underset{\_}{OR}-\underset{\_}{Q^{\prime }{P}^{\prime }}=\underset{\_}{OR}-\underset{\_}{O{P}^{\prime }}=n-(m-n).$$

iv)$\underset{\_}{OP}<\underset{\_}{OQ}<\underset{\_}{OP}+\underset{\_}{PQ}$, entonces$n<m<n+n$. De ahí$0<m-n<n$, y$0<2n-m$.

v) En la plaza$O{P}^{\prime }{Q}^{\prime }{R}^{\prime }$, la relación “diagonal: lado”$=\underset{\_}{O{Q}^{\prime }}:\underset{\_}{O{P}^{\prime }}=\sqrt{2}:1$. Si la relación$\underset{\_}{OQ}:\underset{\_}{OP}=m:n$, con m, n enteros positivos, entonces la construcción aquí reemplaza los enteros positivos m, n por enteros positivos más pequeños$2n-m$y$m-n$, con$m-n<n$. Y el proceso puede repetirse indefinidamente para generar una secuencia interminable de enteros positivos decrecientes

$$n>m-n>(2n-m)-(m-n)=3n-2m>...>0.$$

La última y más vital lección de Zaratustra: “Ahora hazlo sin mí”.

George Steiner (1929-)