17
$\begingroup$

It is a well known fact that for positive reals $x_1, x_2, \dots, x_n$, their arithmetic mean is no less than their geometric mean:

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

and has got a multitude of proofs.

One proof approach (which I haven't seen, and what this question is about) would be to prove for the case when the numbers are positive integers. Then because of the homogenity, we can pass on to the rationals, and because rationals are dense, we move onto the reals, completing the proof.

The inequality can be rewritten as

$$ (x_1 + x_2 + \dots + x_n)^n \ge n^n x_1 x_2 \dots x_n$$

The left side can be interpreted as the number of $n$-tuples that can be formed by picking from $x_1 + x_2 + \dots + x_n$ items with replacement. So this leads to the question:

Can we give a combinatorial proof of the above (rewritten) inequality*, when the numbers involved are positive integers?

If such a proof already exists, a reference would suffice. Please feel free to add answers even if they work for specific $n \gt 1$.

*Combinatorial proofs for inequalities are not unheard of. For instance to prove that $2^n \gt n$, we count the total number of subsets of $\{1,2, \dots, n\}$ and compare with the number of subsets of size $1$.

  • 2
    Related (at least when $n = 2$): http://mathoverflow.net/questions/16129/is-there-a-combinatorial-proof-of-cauchy-schwarz2012-02-14
  • 0
    @QiaochuYuan: Thanks for the link!2012-02-14
  • 1
    I really like the footnote! :)2012-02-14
  • 0
    A better way to prove that $2^n > n$ is Cantor's diagonal argument, which applies to sets of every cardinality whereas your argument doesn't.2012-02-14
  • 0
    I like the idea of proving for natural nos. and passing to the rationals and then reals! Hope someone comes with an elegant proof for naturals!2012-02-14
  • 2
    Kiran Kedlaya gave a combinatorial proof of a more complicated inequality involving arithmetic and geometric means in Proof of a mixed arithmetic-mean, geometric-mean inequality, Amer. Math. Monthly 101 (1994), no. 4, 355–357, MR1270962 (95b:26022).2012-02-14
  • 0
    @GerryMyerson: Thanks! I think I found the tex source of that article. It seems to use AM-GM, but perhaps the ideas can be used.2012-02-14

2 Answers 2