Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 5 down vote accepted

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$

share|improve this answer
2  
It looks rock-solid to me! –  Steven Stadnicki May 20 '12 at 18:35
1  
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
1  
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
1  
... 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
1  
Now you’ve got it! –  Brian M. Scott May 21 '12 at 0:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.