Cálculo de Spivak - Capítulo 1 Pregunta 1.5 - Demostración por Inducción

Question

En la cuarta edición de Cálculo de Spivak, capítulo 1, la pregunta 1.5 es la siguiente:

Prueba $x^n - y^n = (x - y)(x^{n-1}+x^{n-2}y+ \cdots + xy^{n-2}+y^{n-1})$ utilizando sólo las siguientes propiedades:

Para mí es bastante fácil utilizar P9 para ampliar el lado derecho:

$$ \begin{array} { c l } (x - y)(x^{n-1}+x^{n-2}y+ \cdots + xy^{n-2}+y^{n-1}) & \text{Given} \\ x^{n-1}(x - y)+x^{n-2}y(x - y)+ \cdots + xy^{n-2}(x - y)+y^{n-1}(x - y) & \text{P9} \\ x^n - yx^{n-1} + x^{n-1}y - x^{n-2}y^2 + \cdots + xy^{n-1} - xy^{n-2}y^2 + xy^{n-1} - y^n & \text{P9} \end{array} $$

Finalmente, todos los términos excepto el primero y el último se anulan por P3.

Tengo la sensación de que este último paso debería demostrarse por inducción. Si es así ¿cómo se escribiría eso?

( Además, me he dado cuenta de que mucha gente escribe la aplicación de P9 a los polinomios de forma diferente a como lo hago yo cuando estoy trabajando en el Cálculo de Spivak. ¿Por qué lo hacen? ¿Cómo se vería aquí? )

Answer 1

Si estás planeando hacer una prueba por inducción, el primer paso es escribir tu hipótesis inductiva, típicamente expresada como una proposición como " $P(n): (x^n - y^n) = (x-y) \sum_{i=0}^{n-1} x^i y ^ {n-1-i}$ .

Entonces establece la verdad de $P(0)$ o $P(1)$ o algún otro punto de partida útil. Entonces se dice "Supongamos que $P(1), P(2), \ldots, P(k)$ son todos verdaderos. Mostraremos $P(k+1)$ que establece que [escriba aquí los detalles]". Y ese es el punto en el que comenzó su prueba. Pero no hay mucho que puedas hacer porque no tienes $P(1)$ y $P(2)$ y demás por escrito. De hecho, probablemente sólo necesite $P(n-1)$ y unos cuantos axiomas para demostrar $P(n)$ .

Pero los argumentos "y demás" como el tuyo son exactamente inducciones ocultas, por lo que tu prueba no es realmente una solución al problema planteado.

Por mucho que me guste la obra de Spivak Cálculo En mi opinión, este es uno de los peores problemas pedagógicos del libro. Parte de la dificultad es que los poderes no han sido definidos, y la afirmación no es cierta cuando $x$ o $y$ es cero y $n = 0$ porque $0^0$ es indefinido. Dejando todo esto de lado, y aceptando que la afirmación se aplica a todos los $x$ y $y$ y que para estos, $x^0 = 1$ sigamos adelante y escribamos una prueba.

Antes de poder hacer esa demostración, necesito un lema, también demostrado por inducción: Para cualquier $n \ge 1$ y cualquier $x$ y $y$ y cualquier $s$ , $$ s\sum_{i=0}^n x^i y^{n-1-i} = \sum_{i=0}^n s (x^i y^{n-1-i}). $$ Puede que incluso escriba una prueba de esto más abajo, pero por ahora, sigamos con ello.

Para demostrarlo: para todo número entero positivo $n$ y para todo lo que no sea cero $x$ y $y$ la declaración $P(n): (x^n - y^n) = (x-y) \sum_{i=0}^{n-1} x^i y ^ {n-1-i}$ es cierto.

Prueba:

Primer paso: caso base.

Para $n = 1$ La declaración afirma que $(x^1 - y^1) = (x-y)(x^0y^0)$ . Debemos demostrar que esto es cierto.

Ya que para cualquier número no nulo $a$ , $a^0 = 1$ podemos reescribir $P(1)$ como \begin{align} (x^1 - y^1) &= (x-y)(1\cdot 1) \end{align}

Para demostrar esta afirmación, empecemos por el lado derecho y convirtámoslo en el lado izquierdo: \begin{align} (x-y)(1 \cdot 1) &= (x-y) \cdot 1, & \text{because of P6, applied to $a = 1$} \\ &= (x-y), & \text{because of P6, applied to $a = 1$}. \end{align} Por lo tanto, el lado derecho es igual al lado izquierdo, y hemos establecido $P(1)$ .

Segundo paso: paso inductivo (siguiendo el enfoque de @BrebiusB.Brebs)

Nosotros suponga que para algunos $k \ge 1$ que $P(k)$ es verdadera, es decir, que $$x^k - y^k = (x-y) \sum_{i=0}^{k-1} x^i y ^ {k-1-i}$$ para todo lo que no sea cero $x$ y $y$ .

Utilizando esta hipótesis, demostraremos $P(k+1)$ es verdadera, es decir, que $$x^{k+1} - y^{k+1} = (x-y) \sum_{i=0}^{k} x^i y ^ {k-i}$$ para todo lo que no sea cero $x$ y $y$ .

Para ello, dejemos que $x$ y $y$ sean dos valores fijos no nulos. Modifiquemos gradualmente el lado derecho de la ecuación mostrada arriba en un intento de convertirla en el lado izquierdo. Para cada paso en la izquierda, proporcionaré una razón en la derecha. \begin{align} (x-y) \sum_{i=0}^{k} x^i y ^ {k-i} &= \sum_{i=0}^{k} (x-y) (x^i y ^ {k-i}), & \text{Lemma applied to $s = (x-y)$}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i y ^ {k-i}) \right) + (x-y)(x^k y^{k-k}), & \text{The sum from 0 to $k$ is the sum from $0$ to $k-1$ plus the $k$th term; this is a hidden definition of the summation symbol}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i y ^ {k-i}) \right) + (x-y)(x^k y^{0}), & \text{P3, definition of subtraction}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i y ^ {k-i}) \right) + (x-y)(x^k \cdot 1), & \text{$y^0 = 1$ because $y$ is nonzero. }\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i y ^ {k-i}) \right) + (x-y)(x^k), & \text{P6 applied to last product }\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i (y \cdot y ^ {(k-i) - 1}) \right) + (x-y)(x^k), & \text{Property of exponents: $y^a \cdot y^b = y^(a+b)$, which also must be proved by induction! }\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i (y \cdot y ^ { ((k+ (-i)) + (- 1)}) \right) + (x-y)(x^k), & \text{Definition of subtraction, twice}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i (y \cdot y ^ { ((k+ (-1)) + (- i)}) \right) + (x-y)(x^k), & \text{P1, applied within exponent}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i (y \cdot y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{Definition of subtraction}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (x^i y) ( y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{P5, applied within summation -- which is another hidden induction!}\\ &= \left(\sum_{i=0}^{k-1} (x-y) (y x^i) ( y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{P8, applied within summation -- which is another hidden induction!}\\ &= \left(\sum_{i=0}^{k-1} ((x-y) y) x^i ( y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{P5, again induction}\\ &= ((x-y)y)\left(\sum_{i=0}^{k-1} x^i ( y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{Lemma,applied to $s = (x-y)y$}\\ &= (y(x-y))\left(\sum_{i=0}^{k-1} x^i ( y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{P8}\\ &= y\cdot \left( (x-y))\sum_{i=0}^{k-1} x^i ( y ^ { (k -1) - i)}) \right) + (x-y)(x^k), & \text{P5}\\ &= y\cdot \left(x^k - y^k\right) + (x-y)(x^k), & \text{Inductive hypothesis, applied to middle summation}\\ &= (y\cdot x^k - y \cdot y^k) + (x\cdot x^k -y \cdot x^k), & \text{P9, twice ,with the definition of subtraction used as well. }\\ &= (y\cdot x^k + (- y) \cdot y^k) + (x\cdot x^k + (-y) \cdot x^k), & \text{Defn of subtraction, twice }\\ &= ((-y) \cdot y^k + y\cdot x^k ) + x^{k+1}) + (-y) \cdot x^k)), & \text{P4, definition of exponentiation }\\ &= ((-y) \cdot y^k + (y\cdot x^k + x^{k+1})) + (-y) \cdot x^k)), & \text{P1}\\ &= (((-y) \cdot y^k + x^{k+1}) +y\cdot x^k)) + (-y) \cdot x^k)), & \text{P1}\\ &= ((-y) \cdot y^k + x^{k+1}) +(y\cdot x^k + (-y) \cdot x^k), & \text{P1}\\ &= ((-y) \cdot y^k + x^{k+1}) +((y+ (-y)) \cdot x^k), & \text{P9}\\ &= ((-y) \cdot y^k + x^{k+1}) +(0 \cdot x^k), & \text{P3}\\ &= ((-y) \cdot y^k + x^{k+1}) +0, & \text{Lemma to be proved: $0 \cdot a = 0$ for every $a$}\\ &= (x^{k+1} + (-y) \cdot y^k ) , & \text{P4, P2}\\ &= (x^{k+1} + (-1\cdot y) \cdot y^k ) , & \text{Lemma to be proved: $-1 \cdot a = -a$ for any $a$. }\\ &= (x^{k+1} + (-1)\cdot (y \cdot y^k ) , & \text{P5}\\ &= (x^{k+1} + (-1)\cdot (y^{k+1} ) , & \text{Defn of exponent, P4 (to turn $ 1+k$ into $k+1$)}\\ &= (x^{k+1} + (-y^{k+1} ) , & \text{Most recent to-be-proved lemma again}\\ &= x^{k+1} -y^{k+1} , & \text{Def of subtraction}. \end{align} Y con esto (¡una vez que probamos todos esos lemas ocultos!) hemos demostrado que $P(k+1)$ es cierto.

(Me disculpo: tengo algunos paréntesis de sobra colgando en ese desorden, y no tengo el corazón para volver a encontrar/corregir cada uno de ellos...)

Ahora, presumiblemente, ves por qué creo que este es uno de los peores ejercicios de Spivak. No se ha dado la definición inductiva del símbolo de la suma, ni la definición de la exponentación para números reales y exponentes enteros no negativos, ni propiedades como $a^{n+m} = a^n \cdot a^m$ se ha demostrado. Es simplemente un viejo dolor de cabeza. Por otro lado, muestra que puedes hacer estas cosas, y que una vez que has tomado una manipulación algebraica y la has escrito de esta manera, (a) no quieres volver a hacerlo, y (b) estás seguro de que puedes hacerlo de nuevo si te lo piden.

Answer 2

A veces, para demostrar algo por inducción es útil hacer un esquema al revés. Tomemos la expresión $x^{n}-y^{n}$ y desmontarlo para intentar encajar la expresión $(x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1})$ en alguna parte.

Otro truco útil es sumar y restar lo mismo, ya que $a+b=a+0+b=a+c-c+b.$ Obviamente, la cantidad $c$ elegido debe ser útil cuando se manipula la expresión original.

Estoy bastante seguro de que esta estrategia funciona aquí, pero ahora mismo no estoy muy seguro de lo que $c$ para elegir... Puede que me equivoque pero creo que hacer $x^{n}-y^{n}=x^{n}+x^{n-1}y-x^{n-1}y+y^{n}$ funciona.

Voy a hacer un boceto rápido a ver si es eso. Y

Edición: Sí. Funciona. Terminarás con algo como $$x^{n+1}-y^{n-1}=x^n(x-y)+y(x^n-y^n)=(x-y)(x^n+y(x^{n-1}+x^{n-2}y+\cdots+y^{n-1})). $$ Después de un poco de trabajo, esto se reduce a la expresión que quieres probar.

Answer 3

Los pasos básicos de la prueba por inducción son:

1. Identificar la hipótesis de inducción

   En este caso, es $P(n) : x^n - y^n = (x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1})$

   Tenga en cuenta que a menudo es una buena idea escribir la Hipótesis de Inducción utilizando operadores iterativos, como $\sum$ y $\prod$ hacer esto suele facilitar el análisis.

   $$P(n) : x^n - y^n = (x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i$$

   El $P(n) : $ aquí dice "La proposición sobre $n$ que lo siguiente es cierto".

2. Identificar el valor más pequeño de $n$ para los que la hipótesis de inducción es verdadera.

   En este caso, $n = 1$

3. Supongamos que la Hipótesis de Inducción es verdadera.

4. Adopta el llamado "paso de inducción". Es decir, incrementar $n$ de la Hipótesis de Inducción una vez--y mostrar que la proposición resultante sigue siendo verdadera.

¿Qué se consigue con esto?

Los pasos anteriores son simplemente una manera formal de decir: "Si el paso 3 es cierto, el paso 4 muestra que podemos incrementar $n$ tanto como queramos y el paso 3 seguirá siendo cierto. Porque podemos empezar con algún valor mínimo de $n$ e incrementarlo hasta que hayamos visitado cada posible valor de $n$ --y porque ya hemos demostrado que el paso 2 ( el valor mínimo de $n$ ) es verdadera, sabemos que el paso 3 es verdadero para todos los $n$

Aplicando estos pasos a la pregunta original

Paso 1:

$$P(n) : x^n - y^n = (x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i$$

Paso 2:

$$P(1) : x^1 - y^1 = (x-y)\sum_{i=0}^{1-1}x^{1-1-i}y^i$$ $$P(1) : x - y = (x-y)\sum_{i=0}^{0}x^{-i}y^i$$ $$P(1) : x - y = (x-y)(x^{-0}y^0)$$

Tenga en cuenta que $x^{-0}$ es definido y $x^{-0} = x^0 = 1$ . Entonces, por sustitución:

$$ P(1) : x - y = (x-y)(1 \cdot 1) \\ P(1) : x - y = (x-y)(1) \\ P(1) : x - y = (x-y) \\ P(1) : true \\ $$

Paso 3:

$$P(n) : x^n - y^n = (x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i \text{ is true by assumption.}$$

Paso 4:

$$P(n+1) : x^{n+1} - y^{n+1} = (x-y)\sum_{i=0}^{n+1-1}x^{n+1-1-i}y^i \text{ By Induction Hypothesis}$$ $$P(n+1) : x^{n+1} - y^{n+1} = (x-y)\sum_{i=0}^{n}x^{n-i}y^i$$ $$P(n+1) : x^{n+1} - y^{n+1} = (x-y)(x^n+x^{n-1}y+x^{n-2}y^2+\cdots+x^2y^{n-2}+xy^{n-1}+y^n)$$ $$P(n+1) : x^{n+1} - y^{n+1} = x^n(x-y)+x^{n-1}y(x-y)+x^{n-2}y^2(x-y)+\cdots+x^2y^{n-2}(x-y)+xy^{n-1}(x-y)+y^n(x-y)$$ $$P(n+1) : x^{n+1} - y^{n+1} = x^{n+1} - y^{n+1}$$ $$QED$$

Cada una de las operaciones de la prueba anterior puede justificarse mediante P1 a P12.