Hacia atrás de la inducción para demostrar que $x_1\cdots x_n \leq ((x_1+\cdots+x_n)/n )^n$

Question

Esta pregunta es de "Concreto de las Matemáticas", por Knuth.

A veces, es posible el uso de la inducción hacia atrás, probando cosas de $n$ $n-1$en lugar de viceversa! Por ejemplo, considere la declaración

$P(n)$: $\displaystyle x_1x_2\cdots x_n \leq \left( \dfrac{x_1+x_2+\cdots+x_n}{n} \right)^n$, si $x_1,\cdots,x_n\geq 0$.

Esto es cierto cuando se $n = 2$, ya que el $(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$.

una. Mediante el establecimiento $x_n = (x_1 + \cdots + x_{n-1})/(n - 1)$, demuestran que, a $P(n)$ implica $P(n-1)$ siempre $n > 1$.

b. Mostrar que $P(n)$ $P(2)$ implican $P(2n)$.

c. Explique por qué esto implica la verdad de $P(n)$ todos los $n$.

Voy a publicar una respuesta a esta pregunta con mi intento por llegar a una solución. Me gustaría saber si mi solución es correcta y consistente, o si hay una mejor forma de resolverlo.

Answer 1

una.

La proposición $P(n-1)$ es:

$P(n-1): x_1\cdots x_{n-1} \leq \left( \dfrac{ x_1+\cdots+x_{n-1} }{n-1} \right)^{n-1}$

Queremos mostrar que la desigualdad anterior se sigue de $P(n)$.

Establecimiento $x_n = (x_1 + \cdots + x_{n-1})/(n - 1)$ en la proposición $P(n)$:

$x_1\cdots x_{n-1} \dfrac{x_1 + \cdots + x_{n-1}}{n-1} \leq \left( \dfrac{x_1+\cdots+x_{n-1}+\dfrac{x_1 + \cdots + x_{n-1}}{n-1}}{n} \right)^n$

$x_1\cdots x_{n-1} \dfrac{x_1 + \cdots + x_{n-1}}{n-1} \leq \left( \dfrac{ \dfrac{ (n-1)(x_1+\cdots+x_{n-1})+(x_1 + \cdots + x_{n-1}) }{n-1} }{n} \right)^n$

El lado derecho de la desigualdad es igual a:

$ \left( \dfrac{ \dfrac{ (n)(x_1+\cdots+x_{n-1}) }{n-1} }{n} \right)^n = \left( \dfrac{ x_1+\cdots+x_{n-1} }{n-1} \right)^n$

Por lo tanto:

$x_1\cdots x_{n-1} \dfrac{x_1 + \cdots + x_{n-1}}{n-1} \leq \left( \dfrac{ x_1+\cdots+x_{n-1} }{n-1} \right)^n$

Dividir ambos lados por $\dfrac{x_1 + \cdots + x_{n-1}}{n-1}$:

$x_1\cdots x_{n-1} \leq \left( \dfrac{ x_1+\cdots+x_{n-1} }{n-1} \right)^{n-1}$

que corresponde a $P(n-1)$. $\blacksquare$

b.

$P(n)$ es nuestra hipótesis inductiva, y sabemos que $P(2)$ es cierto. Escribir $P(2n)$:

$x_1\cdots x_{2n} \leq \left( \dfrac{x_1+\cdots+x_{2n}}{2n} \right)^{2n}$

Queremos mostrar que, bajo la hipótesis inductiva, la expresión anterior es cierto.

Reescribir así:

$(x_1\cdots x_{n})(x_{n+1}\cdots x_{2n}) \leq \left( \dfrac{x_1+\cdots+x_{2n}}{2n} \right)^{2n}$

Podemos aplicar la hipótesis inductiva para ambos factores de la mano izquierda, ya que ambos de ellos son productos de $n$ factores:

$(x_1\cdots x_{n})(x_{n+1}\cdots x_{2n}) \leq \left( \dfrac{x_1+\cdots+x_{n}}{n} \right)^{n} \left( \dfrac{x_{n+1}+\cdots+x_{2n}}{n} \right)^{n} $

Nos han demostrado que $P(n)$ implica $P(2n)$ si se demuestra que:

$\left( \dfrac{x_1+\cdots+x_{n}}{n} \right)^{n} \left( \dfrac{x_{n+1}+\cdots+x_{2n}}{n} \right)^{n} \leq \left( \dfrac{x_1+\cdots+x_{2n}}{2n} \right)^{2n}$

Tomando el $n^{th}$ raíz de ambos lados:

$\left( \dfrac{x_1+\cdots+x_{n}}{n} \right) \left( \dfrac{x_{n+1}+\cdots+x_{2n}}{n} \right) \leq \left( \dfrac{x_1+\cdots+x_{2n}}{2n} \right)^{2}$

Después de un poco de manipulación:

$(x_1+\cdots+x_n)(x_{n+1}+\cdots+x_{2n}) \leq \left( \dfrac{x_1+\cdots+x_{2n}}{2} \right) ^2$

Pero, por $P(2)$, la desigualdad anterior es cierto. Esto puede verse más claramente mediante el establecimiento $y_1=x_1+\cdots+x_n$$y_2=x_{n+1}+\cdots+x_{2n}$:

$y_1 y_2 \leq \left( \dfrac{y_1+y_2}{2} \right)^2$

Nos damos cuenta de que esta expresión corresponde a $P(2)$, que sabemos que es verdadero. Por lo tanto, es cierto que $P(2)$ $P(n)$ implica $P(2n)$. $\blacksquare$

c.

$P(2)$ $P(n) \rightarrow P(2n)$ muestran que $P(n)$ es cierto para 2, 4, 8, 16, etc.; en otras palabras, $P(n)$ es verdadera si $n\geq 2$ es una potencia de 2. Ahora, a cuenta de todos los otros números naturales, vamos a utilizar el hecho de que $P(n)\rightarrow P(n-1)$:

$P(2) \rightarrow P(1)$

$P(4) \rightarrow P(3)$

$P(8) \rightarrow P(7) \rightarrow P(6) \rightarrow P(5)$

$P(16) \rightarrow P(15) \rightarrow \cdots \rightarrow P(9)$

Y así sucesivamente.

Por el razonamiento anterior, podemos ver que las proposiciones $P(2)$, $P(n) \rightarrow P(2n)$ y $P(n) \rightarrow P(n-1)$ implica que $P(n)$ es cierto para todos $n>1$. $\blacksquare$