# A proof of Muirhead’s Inequality

I’ve been reading Thomas Mildorf’s Olympiad Inequalities, and trying to prove the 12 Theorems stated at the beginning. I’m recording my proof of Muirhead’s Inequality below. Although it is probably known to people working in this area, I could not find it on the internet.

Muirhead’s Inequality states the following: if the sequence $a_1,\dots,a_n$ majorizes the sequence $b_1,\dots,b_n$, then for nonnegative numbers $x_1,\dots,x_n$, we have the following inequality

$\sum\limits_{\text{sym}} x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}\geq \sum\limits_{\text{sym}}x_1^{b_1}x_2^{b_2}\dots x_n^{b_n}$

We will derive it as an easy consequence of the fact that for a convex function $f$, if the sequence $\{a_i\}$ majorizes the sequence $\{b_j\}$, then $f(a_1)+\dots f(a_n)\geq f(b_1)+\dots+f(b_n)$. This is theorem 9 in Mildorf’s document (the Majorization Theorem).

We will prove the Muirhead Inequality by induction on the number of $x_i$‘s. For just one such $x_i$, this is true by the Majorization Inequality. Now assume that it is true for $(n-1)$ number of $x_i$‘s. Then the statement of Muirhead’s Inequality is equivalent to the statement

$(x_1^{a_1}+x_1^{a_2}+\dots x_1^{a_n})(x_2^{a_1}+x_2^{a_2}+\dots x_2^{a_n})\dots (x_n^{a_1}+x_n^{a_2}+\dots x_n^{a_n})\geq (x_1^{b_1}+x_1^{b_2}+\dots x_1^{b_n})(x_2^{b_1}+x_2^{b_2}+\dots x_2^{b_n})\dots (x_n^{b_1}+x_n^{b_2}+\dots x_n^{b_n})$

The above is true because $f_i(y)=x_i^y$ is a convex function, as it is an exponential function. Hence, $f_i(a_1)+\dots f_i(a_n)\geq f_i(a_1)+\dots+f_i(a_n)$. Therefore, $x_i^{a_1}+\dots x_i^{a_n}\geq x_i^{b_1}+\dots x_i^{b_n}$.

It follows that

$(x_1^{a_1}+x_1^{a_2}+\dots x_1^{a_n})(x_2^{a_1}+x_2^{a_2}+\dots x_2^{a_n})\dots (x_n^{a_1}+x_n^{a_2}+\dots x_n^{a_n})\geq (x_1^{b_1}+x_1^{b_2}+\dots x_1^{b_n})(x_2^{b_1}+x_2^{b_2}+\dots x_2^{b_n})\dots (x_n^{b_1}+x_n^{b_2}+\dots x_n^{b_n})$

A note on the induction: Consider the base case, where we just have $x_1$. Then the inequality is equivalent to proving that

$x_1^{a_1}+x_1^{a_2}+\dots+x_1^{a_n}\geq x_1^{b_1}+x_1^{b_2}+\dots+x_1^{b_n}$, which is true by Muirhead inequality.

Now if we have two $x_i$‘s, say $x_1$ and $x_2$, then this is equivalent to the inequality $(x_1^{a_1}+\dots+x_1^{a_n})(x_2^{a_1}+\dots+x_2^{a_n})\geq (x_1^{b_1}+\dots+x_1^{b_n})(x_2^{b_1}+\dots+x_2^{b_n})$.

We get the above inequality + terms of the form $(xy)^{a_1}+\dots+(xy)^{a_n}$, which we know from the Majorization Inequality is $\geq (xy)^{b_1}+\dots+(xy)^{b_n}$

The induction will work similarly for higher numbers of $x_i$‘s.