Mathematical induction - inequality

[threeder]

Homework Statement

Prove that
$$\frac{1}{n}\sum_{i=1}^n x_i\geq {(\prod_{i=1}^n x_i)}^{1/n}$$
for positive integers $n$ and positive real numbers $x_i$

Homework Equations

There is also a hint. It states that it does not seem to be possible to prove it directly so you should prove it for $n=2^m, m\geq 0$. Nonetheless, the result should follow by proving the converse of the usual inductive step: if it hold for $n=k+1$, the it also does for $n=k$

The Attempt at a Solution

I don't really understand how should I proceed. I rewrote the inequality

$$\frac{1}{2^{k+1}}\sum_{i=0}^{2^{k+1}} x_i\geq {(\prod_{i=0}^{2^{k+1}} x_i)}^{2^{-k-1}}$$

but that's it. Can't seem to understand how can we proceed from the converse using the induction principe. Any hints would be apreciated. Thanks!

 

[chiro]

Hey threeder and welcome to the forums.

Just for clarification, are the numbers x_i fixed or can than be anything that satisfies the equation? If they are fixed, then the above relationship as you have typed it is not right. (Example (1+2+3)/3 = 2: (1*2*3)^(1/3) = Cube_Root(6) Which is not 2.

So what you should do first is show that for n = 1 there exists an x₁ that satisfies this. Can you show that a real number exists that fits this description?

 

[threeder]

Checked everything number of times but still made a mistake. it was supposed to be an inequality :)

 

[chiro]

Checked everything number of times but still made a mistake. it was supposed to be an inequality :)

Ahh ok, that makes more sense.

You should look into the the idea of raising the RHS to the nth power and then compare the two equations in terms of how (x1 + x2 + ... + )^n > x1x2x3... by using the binomial theorem.

For example let's say you prove it for n = 1: Now consider (x1 + x2)^2 > x1x2: you can use the quadratic formula since x1^2 + x2^2 + 2x1x2 > x1x2 since x1^2 > 0 ad x2^2 > 0 if both are non-zero and if take the RHS to the LHS you just have to show x1^2 + x2^2 + x1x2 > 0 and you're done (since you can treat the higher order ones as letting the x1 be x1+x2 and the x2 be x3 and so on.

 

[threeder]

I think I understand what you are trying to say. though, I would like to see how to prove it using induction principle with the provided hint. I realize it is probably more difficult but I would like to see how can the induction be used in the way specified

 

[chiro]

I think I understand what you are trying to say. though, I would like to see how to prove it using induction principle with the provided hint. I realize it is probably more difficult but I would like to see how can the induction be used in the way specified

The key is that all real numbers are positive.

Use the multinomial theorem: in the expansion of (sum all x_i's)^n you have a term at the end which is in terms of the product of all the x_i's which is given in this Wikipedia reference:

http://en.wikipedia.org/wiki/Multinomial_theorem

where all the k_i's are equal to 1. You then use the fact that if you subtract the product of all the x_i's in your proof to the LHS you get a positive number and you're done.

This doesn't even require induction as the proof is very general, but the result in the wiki link probably has an element where you could use induction to show it.

But remember, since every term in the multinomial expansion is positive, then you will have a bunch of positive terms being summed so all these terms are zero which means all you have to really do is bring the RHS to the LHS and show LHS is greater than or equal to zero.

Also I forgot, you'll have to factor in the relationship between the factorial and n^n since you divide by n.

There might be a better way of doing this, but this gives you one way to look at the problem.

 

[threeder]

Thank you for the help! :)

 

[awkward]

Your text is trying to lead you to discover a famous (and beautiful) proof originally due to Cauchy (I think). If you can pull it off you can feel proud of yourself.

Try proving the cases n=1 and n=2. To get to n=4, consider choosing special values for the $x_i$'s in the n=2 case: let
$$x_1 = \frac{y_1 + y_2}{2}$$ and $$x_2 = \frac{y_3 + y_4}{2}$$
Can you prove the n=4 case from this? If so, maybe you can see how to get from n=4 to n=8...

 

[threeder]

I thought chiro explained it already?

Say $n=1 ~\Rightarrow ~ x_i \geq x_i$ is obviously correct

Say $n=2 ~\Rightarrow ~ \frac{x_1+x_2}{2} \geq \sqrt{x_1x_2}$. If we square it we get $(x_1-x_2)^2 \geq 0$ which again is true.

By constituting $x_1=y_1+y_2$ and $x_2=y_3$ we can get this inequality be true for any set of numbers. So doesn't this constitute a proof?

 

[awkward]

I thought chiro explained it already?

Say $n=1 ~\Rightarrow ~ x_i \geq x_i$ is obviously correct

Say $n=2 ~\Rightarrow ~ \frac{x_1+x_2}{2} \geq \sqrt{x_1x_2}$. If we square it we get $(x_1-x_2)^2 \geq 0$ which again is true.

By constituting $x_1=y_1+y_2$ and $x_2=y_3$ we can get this inequality be true for any set of numbers. So doesn't this constitute a proof?

This proves the inequality for the cases n=1 and n=2, but not for other values of n-- at least, not without more work.

 

[threeder]

OK, let's try to prove for n=4. say $x_1=\frac{y_1+y_2}{2}$ and $x_2=\frac{y_3+y_4}{2}$. Then, since $(x_1-x_2)^2\geq 0$ we get $$(y_1+y_2-y_3-y_4)^2= y_1^2+y_2^2+y_3^2+y_4^2+2y_1y_2+2y_3y_4-2y_1y_3-2y_1y_4-2y_2y_3$$

say $y_4\geq y_3\geq y_2\geq y_1$. then $2y_3y_4 \geq 2y_1y_4$, and $y_2^2+y_3^2 \geq 2y_2y_3$ and the rest is definitely true as well - $2y_1y_2 + y_1^2+y_4^2 \geq 2y_1y_3$

So I think it is proved for n=4. Using same path, we can prove it for n=8 as you told. But I presume something else is missing right? What exactly?

 

[awkward]

It looks like your approach will get messy if you try to apply it to larger values of n. For example, you assume $y_4\geq y_3\geq y_2\geq y_1$. What about the other possible orderings?

Here is another way.

By the n=2 case, we know
$$\frac{\frac{y_1+y_2}{2} + \frac{y_3+y_4}{2}}{2} \ge \left( \frac{y_1+y_2}{2} \frac{y_3+y_4}{2} \right)^{1/2} \ge \left((y_1 y_2)^{1/2} (y_3 y_4)^{1/2} \right) ^ {1/2} = (y_1 y_2 y_3 y_4)^{1/4}$$

so we have proved the case n=4.

See if you can use the same trick inductively to prove the inequality for $n = 2^m$. That was the hint you stated in your original post.

 

[threeder]

That is so simply elegant! I almost understand the proof now. There is only one step that bother me:

say $n=2^m$. then:

$$\frac{1}{2^m} \sum_{i=0}^{2^m} x_i \geq (\prod_{i=0}^{2^m} x_i)^\frac{1}{2^m}$$

then:
$$\frac{1}{2^{m+1}} \sum_{i=0}^{2^{m+1}} x_i = \frac{ \frac{1}{2^m} \sum_{i=0}^{2^m} x_i + \frac{1}{2^m} \sum_{i=2^m+1}^{2^{m+1}} x_i }{2}$$$$(\frac{(\sum_{i=0}^{2^m} x_i) (\sum_{i=2^m+1}^{2^{m+1}} x_i)}{2^m})^ \frac{1}{2} \geq (( \prod_{i=0}^{2^m} x_i)^{\frac{1}{2^m}}( \prod_{i=2^m+1}^{2^{m+1}} x_i)^\frac{1}{2^m})^ \frac{1}{2} = (( \prod_{i=0}^{2^{m+1}} x_i)^\frac{1}{2^m})^ \frac{1}{2} = ( \prod_{i=0}^{2^{m+1}} x_i)^\frac{1}{2^{m+1}}$$

But I don't think I can conclude that $\frac{1}{2^m} \sum_{i=2^m+1}^{2^{m+1}} x_i \geq ( \prod_{i=2^m+1}^{2^{m+1}}$ from the induction hypothesis, can I ? What do I need to do to make this this step? Prove it seperately?

 

[awkward]

But I don't think I can conclude that $\frac{1}{2^m} \sum_{i=2^m+1}^{2^{m+1}} x_i \geq ( \prod_{i=2^m+1}^{2^{m+1}}$ from the induction hypothesis, can I ? What do I need to do to make this this step? Prove it seperately?

No, you can't conclude that from the inductive hypothesis (at least, not easily).

But try proving something else. You have shown the theorem holds for all n = 2^m. If you can show that assuming the theorem holds for some n=k, then it must also hold for n=k-1, you will then know it holds for all n. (That was the hint you stated in your OP.) So that should be your next step.

 

[threeder]

I don't really understand. So you say I should try to prove it directly? presume than $n=k$ is true and then using arithmetic deduce that $n=k-1$ must be true as well? or should I somehow incorporate the idea that it is true for $n=2^m$?

 

[awkward]

I don't really understand. So you say I should try to prove it directly? presume than $n=k$ is true and then using arithmetic deduce that $n=k-1$ must be true as well? or should I somehow incorporate the idea that it is true for $n=2^m$?

Well, you will need algebra, not arithmetic. Where the n=2^m case comes in is that it allows you to conclude that the theorem is true for all n.

Let's suppose you have proved that truth of the theorem for any value of n implies it is true for n-1. We already know it is true for n = 1, 2, 4, 8, 16, ... . Can we show it is true for n = 13, for example? We know it's true for n = 16. By the n => n-1 part, we therefore know it's true for n=15. Therefore it's true for n=14. Therefore it's true for n=13. Bingo!

You should see that a similar argument can be used for any n, because for any positive integer n, there is an m such that 2^m > n. That's the whole idea of the proof.

Hint for the n => n-1 part: think about choosing a special value for $x_n$.

 

[threeder]

thank you for the help! proved it but only with few more hints that I found on the internet. it requires a little bit more of mathematical ingenuity than I currently posses :)

 

[awkward]

OK, I can see you are tired out, so I will give you the next step (but not all the way to the end-- there will still be work to do when I am finished).

Suppose we know $$\frac{1}{n} \sum_{i=0}^n a_ i \ge (a_1 a_2 \cdots a_n)^{1/n}$$
for some $n = k > 1$ and for all $a_i >= 0$.

We want to prove the inequality holds for $n = k - 1$. We are given $a_1, a_2, \dots a_{k-1}$, but we are free to choose any value for $a_k$ that we like, provided it is non-negative.

So choose $a_k$ so that
$$\frac{1}{k-1} \sum_{i=0}^{k-1} a_i = \frac{1}{k} \sum_{i=0}^{k} a_i$$
Solve this equation for $a_k$ in terms of the other variables and plug it back into the inequality for the case $n=k$. Then see if you can deduce the inequality for the case $n=k-1$.

 

[threeder]

am... maybe I was not clear enough. I found this hint, and was able to prove it using it. Indeed it was a result due to Cauchy, and it is so elegantly beautiful :)

 

[awkward]

Great!