Induction Proof of Inequality Involving Summation and Product

[Reckoner]

I'm reading "An Introduction to Mathematical Reasoning," by Peter Eccles. It has some interesting exercises, and right now I'm stuck on this one:

"Prove that

\[\frac1n\sum_{i=1}^nx_i \geq \left(\prod_{i=1}^nx_i\right)^{1/n}\]

for positive integers \(n\) and positive real numbers \(x_i\)."

The author notes, "It does not seem possible to give a direct proof of this result using induction on \(n\). However, it can be proved for \(n = 2^m\) for \(m\geq0\) by induction on \(m\). The general result now follows by proving the converse of the usual inductive step: if the result holds for \(n = k + 1\), where \(k\) is a positive integer, then it holds for \(n = k\)."

So, following the author's advice, I try to show that

\[\frac1{2^m}\sum_{i=1}^{2^m}x_i \geq \left(\prod_{i=1}^{2^m}x_i\right)^{1/2^m}\]

for nonnegative integers \(m\). The base case is straightforward. Here's what I've tried for the inductive step:

Assume

\[\frac1{2^k}\sum_{i=1}^{2^k}x_i \geq \left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k}\]

for some \(k \geq 0\). Then

\[\frac1{2^{k+1}}\sum_{i=1}^{2^{k+1}}x_i = \frac12\left(\frac1{2^k}\sum_{i=1}^{2^k}x_i + \frac1{2^k}\sum_{i=2^k+1}^{2^{k+1}}x_i\right).\]

Letting \(j = i - 2^k,\) we have

\[\frac12\left(\frac1{2^k}\sum_{i=1}^{2^k}x_i + \frac1{2^k}\sum_{i=2^k+1}^{2^{k+1}}x_i\right) = \frac12\left(\frac1{2^k}\sum_{i=1}^{2^k}x_i + \frac1{2^k}\sum_{j=1}^{2^k}x_{j+2^k}\right)\]

\[\geq\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{j=1}^{2^k}x_{j+2^k}\right)^{1/2^k}\mbox{ (by inductive hypothesis)}\]

\[=\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{i=2^k+1}^{2^{k+1}}x_i\right)^{1/2^k}.\]

And I'm not sure where to go from here. All that would be left is to show that

\[\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{i=2^k+1}^{2^{k+1}}x_i\right)^{1/2^k}\geq \left(\prod_{i=1}^{2^{k+1}}x_i\right)^{1/2^{k+1}},\]

but I'm not seeing it. Maybe I need to employ a different strategy altogether. Any ideas?

 

[Evgeny.Makarov]

And I'm not sure where to go from here. All that would be left is to show that

\[\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{i=2^k+1}^{2^{k+1}}x_i\right)^{1/2^k}\geq \left(\prod_{i=1}^{2^{k+1}}x_i\right)^{1/2^{k+1}},\]

Now use the base case (for two numbers) again.

This proof, along with several others, is given in Wikipedia. I am not sure about the following claim, though: 'The general result now follows by proving the converse of the usual inductive step: if the result holds for n=k+1, where k is a positive integer, then it holds for n=k."' If we denote by $P(n)$ the claim that the arithmetic mean of n numbers is >= the geometric mean of those numbers, the proof first establishes $\forall k\, P(2^k)$ by induction on k. The last part of the proof shows that $P(m)$ and $n < m$ imply $P(n)$, so, in particular, indeed $P(2^{k+1})$ implies $P(2^k)$. However, it is not necessary to go from $P(2^{k+1})$ to $P(2^k)$; rather, if $2^k<n<2^{k+1}$, one goes from $P(2^{k+1})$ to $P(n)$.

 

[Reckoner]

Now use the base case (for two numbers) again.

Wow, I completely missed that. The left-hand side is really just the mean of two positive numbers. Thanks a lot, I got it from here.

The last part of the proof shows that $P(m)$ and $n < m$ imply $P(n)$, so, in particular, indeed $P(2^{k+1})$ implies $P(2^k)$. However, it is not necessary to go from $P(2^{k+1})$ to $P(2^k)$; rather, if $2^k<n<2^{k+1}$, one goes from $P(2^{k+1})$ to $P(n)$.

Unless I misunderstand you, I believe that is exactly what the author is saying. We've shown that, \(\forall k\geq0, P(2^k),\) so to prove \(P(k)\,\forall k\geq1\) we prove that \(P(k+1)\Rightarrow P(k)\).

 

[Evgeny.Makarov]

Unless I misunderstand you, I believe that is exactly what the author is saying. We've shown that, \(\forall k\geq0, P(2^k),\) so to prove \(P(k)\,\forall k\geq1\) we prove that \(P(k+1)\Rightarrow P(k)\).

Even if we prove the converse of the usual inductive step, we don't use induction in the opposite direction. If we used such opposite induction, then we would start, say, with P(8), from there prove P(7), use it to prove P(6) and use that to prove P(5). Instead, P(5) is proved directly from P(8). Why emphasize $P(k + 1)\Rightarrow P(k)$ and create an impression that $P(2^k)\Rightarrow P(n)$ for $n < 2^k$ is proved in $2^k-n$ steps when it is proved in one step?

 

[Evgeny.Makarov]

I was looking at the Wikipedia proof, which deals with the last part in one step. I should have realized that it is indeed reasonable (and more formal) to prove $P(k + 1)\Rightarrow P(k)$ for all k and thus prove $P(n)$ from $P(2^k)$ in $2^k-n$ steps.

 

[Reckoner]

I was looking at the Wikipedia proof, which deals with the last part in one step. I should have realized that it is indeed reasonable (and more formal) to prove $P(k + 1)\Rightarrow P(k)$ for all k and thus prove $P(n)$ from $P(2^k)$ in $2^k-n$ steps.

Yes, after taking a look at that proof, I understand what you were saying - they proved the statement for a general positive integer less than \(2^k\). I believe the author of my text worded his note in a way to emphasize the induction process, because one of the preceding chapters was an introduction to induction.

Thanks for the help.