Combinatorial proof of arithmetic geometric mean inequality
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$.
Solution 1:
I'm not completely sure this is what you're looking for, but after playing a bit with the suggested inequality, I think I have found a combinatorial way of thinking about it. In fact, we shall prove the following inequality of which the inequality we are interested in is a special case (in fact, they are equivalent):
Inequality. Let $m,n\in\mathbb{N}$ and let $k_1,k_2,\cdots k_n\in\mathbb{N}$ (yes, this is the same $n$) be natural numbers such that $k_1+k_2+\cdots+k_n=mn$. Then the following inequality holds: $$m^n \geq k_1k_2\cdots k_n\qquad(*)$$
(Taking $m=x_1+x_2+\cdots+x_n$ and $k_i = nx_i$ yields the inequality in the question.)
We shall proceed by a constructiong a sequence of injections. The following lemma is easy to see. (It is basically just the combinatorial interpretation of the inequality $k l\leq (k+1)(l-1)$ which holds for natural numbers $k<l$.)
Lemma. Let $k,l\in\mathbb{N}$ be numbers such that $k<l$. Let $A,B$ be sets such that $|A|=k$ and $|B|=l$ and let $b\in B$. Then there is an injection $\phi:A\times B\to (A\cup\lbrace b\rbrace)\times(B\setminus\lbrace b\rbrace)$.
Proof. Since $k<l$, we have $k\leq l-1$, which means that there is an injection $\psi:A\to B\setminus\lbrace b\rbrace$, so we can define $\phi$ by $$\phi(x,y)=\begin{cases}(x,y);&\textrm{if }y\neq b,\\(b,\psi(x));&\textrm{if }y=b.\end{cases}$$ It is straightforward to verify that this is indeed an injection, so we are done.
From this lemma we get the following proposition, which is the inequality $(*)$ interpreted combinatorially.
Proposition. Let $m,n\in\mathbb{N}$ and let $A_1,A_2,\cdots,A_n$ be disjoint finite sets such that $\sum_{i=1}^n|A_n|=nm$. Let $B$ be a set such that $|B|=m$. Then there is an injection $\phi:A_1\times A_2\times\cdots\times A_n\to B^n$. ($B^n$ denotes $n$-tuples of elements from $B$, as usual.)
Proof. If $|A_i|=m$ for each $i$, there is not much to prove. Otherwise, there are indices $i_1$ and $i_2$ such that $|A_{i_1}|<m$ and $|A_{i_2}|>m$. Now choose some $c\in A_{i_2}$ and define a new partition of $\bigcup_{i=1}^n A_i$ as follows: $A_i^{(1)} = A_i$ for $i\neq i_1,i\neq i_2$ and $A_{i_2}^{(1)}=A_{i_2}\setminus\lbrace c\rbrace$, $A_{i_1}^{(1)}=A_{i_1}\cup\lbrace c\rbrace$. The above lemma allows us to construct an injection $\phi_1:A_1\times A_2\times\cdots\times A_n\to A_1^{(1)}\times A_2^{(1)}\times\cdots\times A_n^{(1)}$.
If now $|A_i^{(1)}|=m$ for each $i$, we are done, otherwise, repeat the same procedure, to obtain a partition $(A_{i}^{(2)})_i$ and an injection $\phi_2:A_1^{(1)}\times A_2^{(1)}\times\cdots\times A_n^{(1)}\to A_1^{(2)}\times A_2^{(2)}\times\cdots\times A_n^{(2)}$.
The procedure will terminate after finitely many steps, since at each step $j$ the sum $\sum_{i=1}^{n}|k_i^{(j)}-m|$ decreases so it will eventually reach zero at some step $r$. (Here we define $k_i^{(j)}=|A_i^{(j)}|$.) But this implies $k_i^{(r)} = m$ for each $i$, so $|A_i^{(r)}|=|B|$ for each $i$, so there is a bijection $\psi:A_1^{(r)}\times A_2^{(r)}\times\cdots\times A_n^{(r)}\to B^n$.
This means we have found a sequence of injections: $$A_1\times A_2\times\cdots\times A_n\overset{\phi_1}{\to}A_1^{(1)}\times A_2^{(1)}\times\cdots\times A_n^{(1)}\overset{\phi_2}{\to}\cdots\overset{\phi_r}{\to}A_1^{(r)}\times A_2^{(r)}\times\cdots\times A_n^{(r)}\overset{\psi}{\to}B^n$$ and the proof is complete.
Conclusion. We have constructed a sequence of injections that proves $(*)$, thus proving the A-G inequality in a combinatorial fashion. The combinatorial meaning of the proof is basically something like this: suppose we have a set $A$ and we partition it into $n$ non-empty parts. Then the number of ways to choose a single element from each set of the partition will be the greatest when the partition is into sets of equal size.
Solution 2:
For $n=2$, the inequality is $(x_1+x_2)^2\ge2^2x_1x_2$. Instead of thinking about $x_1,x_2$ as arbitrary positive integers, suppose WLOG that $x_2$ has $b$ more than $x_1$, and we write $x_1=a$, $x_2=a+b$ for $b\ge0$. (Note that this change in perspective can be thought of combinatorially by separating out the first $a$ things inside the box with more items.) Then the statement becomes $(a+(a+b))^2\ge2^2a(a+b)=2^2a^2+2^2ab$.
We can prove this directly, using the "select with replacement" idea: If we select two items from the three "boxes" (two with $a$ items and one with $b$ items), then we can do it in three main sorts of ways:
- Restrict ourselves to the $a$ boxes: then we have to choose twice which box to pick, so $a^2$ is multiplied by $2^2$ for the box-choosing.
- Pick the $b$ box exactly once: Then the $b$ box can be first or second, and we can choose wither of the $a$ boxes, for an answer of $2*2*ab$.
- Pick from the $b$ box twice: The above two cases cover the right hand side of the inequality, so since this can be done in a nonnegative number of ways, we have the desired result.
In theory, something resembling this method of solution could be used for any particular $n$, but it's more arbitrary. e.g. For $n=3$, we have leftover like $$\left((a+b+c)+(a+b)+a\right)^3-27\left((a+b+c)*(a+b)*a\right)$$ $$=c^3+c^2(9a+6b)+cb(9a+12b)+b^2(9a+8b)$$
Admittedly, the exact form of leftover doesn't matter, but the issue is that while $27a^3$ and $27a^2c$ may be natural terms for the right hand side, $27ab^2$ is not - if you choose two $b$'s and one $a$, you should expect $4*3*3*ab^2$ and have to artificially ignore some case like "both $b$ items from the first box" (that's where the $b^2*9a$ comes from in the above).