MHB Induction Proof of Inequality Involving Summation and Product

AI Thread Summary
The discussion revolves around proving the inequality involving the arithmetic and geometric means for positive real numbers using induction. The initial challenge is to establish the result for \(n = 2^m\) through induction on \(m\), starting with a straightforward base case. The inductive step involves manipulating the means and applying the inductive hypothesis, leading to the conclusion that if the inequality holds for \(n = k + 1\), it also holds for \(n = k\). A key insight is that the proof can be simplified by recognizing that the inequality for non-powers of two can be derived directly from the established case for powers of two. Ultimately, the discussion emphasizes the importance of understanding the induction process and its implications for broader cases.
Reckoner
Messages
45
Reaction score
0
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?
 
Physics news on Phys.org
Reckoner said:
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)$.
 
Evgeny.Makarov said:
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.

Evgeny.Makarov said:
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)\).
 
Reckoner said:
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?
 
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.
 
Evgeny.Makarov said:
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.
 
Back
Top