1
$\begingroup$

I am studying computer science in the first term.

I have to proof the following inequality:

$$ \frac {x_1 + \cdots+ x_n}{n} \ge \sqrt[n]{x_1 x_2 \cdots x_n}$$

$x$ can be any positive real Number: $ x \in \mathbb{R},x \gt0 $

I try to bring it in a form that is like Bernoulli's Inequality, but then realized that this is pretty much nonsense.

So now I am having a hard time to prove it through induction.

Beginning of the induction is clear: $n \rightarrow 1$

$ \large\frac {x_1}{1} \ge x_1$

Next Step: $n \rightarrow n+1$

For the start, lets write the left side of the inequality as $$x_a(n) = \frac{1}{n} \sum_{k=1}^n x_k$$ $$x_g(n) = \prod_{k=1}^n x_k^\frac{1}{n}$$

So now we have to prove:

$$x_a(n+1) = \frac{1}{n+1} \sum_{k=1}^{n+1} x_k$$ $$x_g(n+1) = \prod_{k=1}^{n+1} x_k^\frac{1}{n+1}$$

$x_a(n+1) \ge x_g(n+1)$

Can you just give me a strategy on that?

Thanks.

$\endgroup$
8
  • 1
    $\begingroup$ This is famous inequality. Proofs are everywhere: Books, google, here, there, in your notes, etc, etc, etc $\endgroup$
    – user139708
    Nov 6 '14 at 10:25
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – user99914
    Nov 6 '14 at 10:28
  • 2
    $\begingroup$ The standard way of proof is to first prove it when $n$ is a power of $2$ by induction. Then show that any other case follows from the next power of two (e.g. the case $n = 5$ follows from the case $n = 8$). Search around for "Arithmetic mean geometric mean" or "AM-GM". $\endgroup$
    – Arthur
    Nov 6 '14 at 10:29
  • $\begingroup$ One (my favourite, in fact) way to realize this inequality is by noting that the minimization of the $\Bbb R$-perimeter (total length of the edges) of a hypercuboid in $\Bbb R^n$ with fixed volume is a hypercube in $\Bbb R^n$. $\endgroup$ Nov 6 '14 at 10:31
  • $\begingroup$ It is known as AM-GM Inequality.. It's an important and famous inequality.. $\endgroup$
    – Argha
    Nov 6 '14 at 10:38
3
$\begingroup$

Many ways, here is another one:

Note that the inequality is homogeneous, (we can scale all variables by any positive value and the inequality remains unchanged). So WLOG we can set $x_1 x_2\dots x_n = 1$. Then we need to show only that $x_1+x_2 + \dots + x_n \ge n$ under this condition.

Consider the function $f(t) = t-1-\log t$. Note that our inequality is the same as $f(x_1)+f(x_2)+\dots + f(x_n)\ge 0$, so it is enough to show $f(t)\ge 0$ for positive $t$. This is easily done using one variable calculus or if you know the series expansion of $\log (1+t)$ or $e^t$.

$\endgroup$
3
$\begingroup$

Hints: The standard way to solve this: Put $f(x) = x_1 x_2 ... x_n $. Let

$$ D = \{ x \in \mathbb{R}^n: x_1 + ... + x_n = n , x_i \geq 0 \}$$

Now, use LAgrange multipliers to find the max of $f$ on the set $D$.

Conclude.

$\endgroup$
1
$\begingroup$

I think the easiest way to prove this is to use the concavity of ln:

$(ln(x))" = -\frac{1}{x^2} < 0$ => ln concave

Then you know that if: $\sum_{k=1}^n a_k = 1$ : $ln(\sum_{k=1}^n a_k*x_k) \geq \sum_{k=1}^n a_k*ln(x_k)$

Now set: $a_k =\frac{1}{n}$ for $k=1..n$, and see what you get, knowing that: $ a*ln(x)=ln(x^a)$ and $\sum_{k=1}^n ln(x_k) = ln(x_1*x_2*...*x_n) $

$\endgroup$
1
$\begingroup$

An elementary way:
By squaring both relations on the left side of the implication, it's easy to see this holds: $$x+y=x'+y', |x-y|\ge|x'-y'|\implies x'y'\ge xy.$$ Now set $a=(x_1+\ldots+x_n)/n$. Find $x_i\ne a$ so that $|x_i-a|$ is the smallest possible. If $x_i>a$, take any $x_j<a$, then by using the above inequality you can replace $x_i$ by $a$ and $x_j$ by $x_j{+}(x_i{-}a)\le a$; similarly for $x_i<a$. Repeat until all $x_i = a$.

$\endgroup$
0
$\begingroup$

Another Solution:

First, a result: for any $x,y$ non-negative reals, $\alpha + \beta = 1 $, then

$$ x^{\alpha}y^{\beta} \leq \alpha x + \beta y $$

To show this, put $f(t) = (1 - \beta) + \beta t - t^{\beta} $. Show this function decreases on $[0,1]$ and then replace $t$ with $\frac{y}{x}$. . Now, as for your problem, we use induction on $n$. The base case is Young, and now let us suppose result holds for $n$, we show it holds for the case $n+1$. Indeed,

$$x_1^{\alpha_1}...x_{n+1}^{\alpha_{n+1}} = [ x_1^{ \frac{\alpha_1}{\alpha_1 + ... + \alpha_n}}...x_n^{ \frac{\alpha_n}{\alpha_1 + ... + \alpha_n}} ]^{\alpha_1 + ... + \alpha_n}x_{n+1}^{\alpha_{n+1}} \leq (\alpha_1 + ... + \alpha_n )x_1^{ \frac{\alpha_1}{\alpha_1 + ... + \alpha_n}}...x_n^{ \frac{\alpha_n}{\alpha_1 + ... + \alpha_n}} + \alpha_{n+1}x^{n+1}$$

$$ \leq (\alpha_1 + .... + \alpha_n)[ \frac{\alpha_1}{\alpha_1 + ... + \alpha_n}x_1 + ... + \frac{\alpha_n}{\alpha_1 + ... + \alpha_n}x_n] + x_{n+1}\alpha_{n+1}$$

By induction hypothesis. But, the the above is obviously equal to

$$ = \alpha_1 x_1 + .... + \alpha_{n+1}x_{n+1} $$

Hence, your result follows by math induction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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