# Backwards induction to show that $x_1\cdots x_n \leq ((x_1+\cdots+x_n)/n )^n$

This question is from "Concrete Mathematics", by Knuth.

Sometimes it's possible to use induction backwards, proving things from $n$ to $n-1$ instead of vice versa! For example, consider the statement

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

This is true when $n = 2$, since $(x_1 + x_2)^2 - 4x_1x_2 = (x_1 - x_2)^2 \geq 0$.

a. By setting $x_n = (x_1 + \cdots + x_{n-1})/(n - 1)$, prove that $P(n)$ implies $P(n-1)$ whenever $n > 1$.

b. Show that $P(n)$ and $P(2)$ imply $P(2n)$.

c. Explain why this implies the truth of $P(n)$ for all $n$.

I will post an answer to this question with my attempt at a solution. I would like to know if my solution is correct and consistent, or if there is a better way of solving it.

-
Isn't this AM GM inequality re-written in different form, i.e. $\frac{(x_1+x_2+\dots x_n)}{n} \geq (x_1 x_2 \cdots x_n)^{\frac{1}{n}}$ –  Siddhi V Iyer May 21 '12 at 12:18
@SiddhiVIyer, yes, it is. –  anonymous May 21 '12 at 15:16

## a.

The proposition $P(n-1)$ is:

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

We want to show that the inequality above follows from $P(n)$.

Setting $x_n = (x_1 + \cdots + x_{n-1})/(n - 1)$ in the proposition $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$

The right-hand side of the inequality is equal to:

$\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$

Therefore:

$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$

Dividing both sides by $\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}$

which corresponds to $P(n-1)$. $\blacksquare$

## b.

$P(n)$ is our inductive hypothesis, and we know that $P(2)$ is true. Write $P(2n)$:

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

We want to show that, under the inductive hypothesis, the expression above is true.

Rewrite like this:

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

We can apply the inductive hypothesis to both factors of the left-hand side, because both of them are products of $n$ factors:

$(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}$

We will have shown that $P(n)$ implies $P(2n)$ if we show that:

$\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}$

Taking the $n^{th}$ root of both sides:

$\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}$

After a little manipulation:

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

But, by $P(2)$, the inequality above is true. This can be seen more clearly by setting $y_1=x_1+\cdots+x_n$ and $y_2=x_{n+1}+\cdots+x_{2n}$:

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

We notice that this expression corresponds to $P(2)$, which we know is true. Therefore, it is true that $P(2)$ and $P(n)$ imply $P(2n)$. $\blacksquare$

## c.

$P(2)$ and $P(n) \rightarrow P(2n)$ show that $P(n)$ is true for 2, 4, 8, 16, etc.; in other words, $P(n)$ is true if $n\geq 2$ is a power of 2. Now, to account for all the other natural numbers, let's use the fact that $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)$

And so on.

By the reasoning above, we can see that the propositions $P(2)$, $P(n) \rightarrow P(2n)$ and $P(n) \rightarrow P(n-1)$ imply that $P(n)$ is true for all $n>1$. $\blacksquare$

-
It looks rock-solid to me! –  Steven Stadnicki May 20 '12 at 18:35
Your proof of (a) shows why it suggests setting $x_n = (x_1 + \cdots + x_{n-1})/(n - 1)$: it works! That is, that choice of $x_n$ is exactly what’s needed to let you show that $P(n)$ implies $P(n-1)$. –  Brian M. Scott May 20 '12 at 22:35
Your assumption is that the inequality holds for all choices of non-negative $x_1,\dots,x_n$. You want to show that it holds for all non-negative choices of $x_1,\dots,x_{n-1}$, so you start with any non-negative $x_1,\dots,x_{n-1}$. Then you build a particular $x_n$ from these and apply your induction hypothesis to this $x_1,\dots,x_n$ to find that the inequality holds for $x_1,\dots,x_{n-1}$. Note that you’ve proved it for every non-negative $(n-1)$-tuple. For each one of them you used a different $x_n$ to apply $P(n)$, but in order to do that, you had to know ... –  Brian M. Scott May 21 '12 at 0:00
... that the inequality holds for every non-negative $n$-tuple. The fact that you picked a particular $x_n$ to show the inequality for $x_1,\dots,x_{n-1}$ doesn’t matter, because you did it for every non-negativee $(n-1)$-tuple. The $x_n$ that you build in order to apply $P(n)$ isn’t part of $x_1,\dots,x_{n-1}$; you used it to prove something about that $(n-1)$-tuple, but it was just a disposable tool. –  Brian M. Scott May 21 '12 at 0:01
Now you’ve got it! –  Brian M. Scott May 21 '12 at 0:38