8
$\begingroup$

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.

  • 0
    @SiddhiVIyer, yes, it is.2012-05-21

1 Answers 1

7

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$

  • 1
    Now you’ve got it!2012-05-21