Symmetric Inequalities

Symmetric Sums: Let x_1,x_2, \ldots, x_n be n real numbers. We define symmetric sum s_k as the coefficient of x^{n-k} in the polynomial

P(x)=(x_1+x)(x_2+x)(x_3+x)\cdots (x_n+x)

 

and symmetric average is defined by d_k=\frac{s_k}{\binom{n}k}. For example for 4 variables we have

s_1=x_1+x_2+x_3+x_4
s_2=x_1x_2+x_2x_3+x_3x_4+x_4x_1+x_1x_3+x_2x_4
s_3=x_2x_3x_4+x_1x_3x_4+x_1x_2x_4+x_1x_2x_3
s_4=x_1x_2x_3x_4

 

\boxed{1} Newton’s Inequality: Let x_1,x_2,\cdots,x_n be n non-negative reals. Then for all k \in \{1,2,\cdots,n-1\} we have

d_k^2 \ge d_{k-1}d_{k+1}

Proof: See http://www.artofproblemsolving.com/Wiki/index.php/Newton%27s_Inequality

\boxed{2} Maclaurin’s Inequality: Let x_1,x_2,\ldots,x_n be n nonnegative reals. Let their symmetric averages be d_1,d_2,\ldots,d_n. Then we have

d_1 \ge \sqrt{d_2} \ge \sqrt[3]{d_3} \ge \cdots \ge \sqrt[n]{d_n}

Proof: We will use induction and Newton’s Inequality. Let us prove that d_1\ge \sqrt{d_2} holds. This inequality is equivalent to

\displaystyle (x_1+x_2+\cdots+x_n)^2 \ge \frac{2n}{n-1}\underset{i<j}{\sum_{i=1}^n\sum_{j=1}^n} x_ix_j

\displaystyle \Longleftrightarrow (n-1)\left[\sum_{i=1}^n x_i^2+2\underset{i<j}{\sum_{i=1}^n\sum_{j=1}^n} x_ix_j\right] \ge 2n\underset{i<j}{\sum_{i=1}^n\sum_{j=1}^n} x_ix_j

\displaystyle \Longleftrightarrow (n-1)\sum_{i=1}^n x_i^2 \ge 2\underset{i<j}{\sum_{i=1}^n\sum_{j=1}^n} x_ix_j

\displaystyle \Longleftrightarrow \underset{i<j}{\sum_{i=1}^n\sum_{j=1}^n} (x_i-x_j)^2 \geq 0

which is obvious.

Suppose the chain of inequalities is true upto \sqrt[k-1]{d_{k-1}} \ge \sqrt[k]{d_k}. Then by applying Newton’s inequality we have

d_{k-1}^k \ge d_k^{k-1} \ge \left[\sqrt{d_{k-1}d_{k+1}}\right]^{k-1}\implies d_{k-1}^{2k} \ge d_{k-1}^{k-1}d_{k+1}^{k-1} \implies d_{k-1}^{k+1} \ge d_{k+1}^{k-1}

Hence

d_k^{2(k+1)} \ge d_{k-1}^{k+1}d_{k+1}^{k+1} \ge d_{k+1}^{k-1+k+1} \implies \sqrt[k]{d_k} \ge \sqrt[k+1]{d_{k+1}}

 Thus by induction the proof is complete.

\boxed{3} (own): Let s_k denote the arithmetic mean of k-th degree symmetric sum of n (positive) variables. If k \ge 2 and m+1 > k for B and m+k-1 \le n for A we have the following inequalities:

s_m^k \ge s_{m-1}^{k-1}s_{m+k-1} \ \ \ \left[A_{(k,m)}\right], \ \ \ s_m^k \ge s_{m+1}^{k-1}s_{m-k+1} \ \ \ \left[B_{(k,m)}\right]

Proof: To prove this we use induction on k.
For k=2, both inequalities are equivalent to s_m^2 \ge s_{m-1}s_{m+1} which is Newton’s inequality. Let us suppose both holds for all k \le t
Then for k=t+1

s_m^{t} \stackrel{A_{(t,m)}}{\ge} s_{m-1}^{t-1}s_{m+t-1} = s_{m-1}^{t-1}\sqrt[t]{s_{m+t-1}^t} \stackrel{B_{(t,m+t-1)}}{\ge} s_{m-1}^{t-1}\sqrt[t]{s_{m+t}^{t-1}s_m}

\implies s_m^{t+1} \ge s_{m-1}^ts_{m+t} \ \ \ (A_{(t+1,m)})

And

s_m^t \stackrel{B_{(t,m)}}{\ge} s_{m+1}^{t-1}s_{m-t+1}=s_{m+1}^{t-1}\sqrt[t]{s_{m-t+1}^t} \stackrel{A_{(t,m-t+1)}}{\ge} s_{m+1}^{t-1}\sqrt[t]{s_{m-t}^{t-1}s_{m}}

\implies s_m^{t+1} \ge s_{m+1}^ts_{m-t} \ \ \ (B_{(t+1, m)})

Hence by induction the two inequalities are true.

\boxed{4} (Lastnightstar): If x_1,x_2,\ldots,x_n\in\mathbb{R}^{+} such that \displaystyle \frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_n}=n then

x_1+x_2+\cdots+x_n\leq nx_1x_2{\cdots}x_n

Proof: We use the same notations as used in \boxed{3}. The condition is equivalent to s_{n-1}=s_n
Hence the inequality after homogenization becomes

s_1 \le s_n\left(\frac{s_{n-1}}{s_n}\right)^{n-1} \iff s_{n-1}^{n-1} \ge s_n^{n-2}s_1

which is B_{(n-1,n-1)}

\boxed{5} (Lastnightstar): If x_1,x_2,\ldots,x_n\in\mathbb{R}^+ then

\left(\sum\limits_{i=1}^n x_i \right)^{n+2}\ge n^{n+1}\prod\limits_{i=1}^n x_i\sum\limits_{i=1}^n x_i^2

Proof: Using the same notations by AM-GM

\left(\sum\limits_{i=1}^n x_i\right)^2=\sum\limits_{i=1}^n x_i^2+ n(n-1)s_2 \ge n\sqrt[n]{\left(ns_2\right)^{n-1}\sum\limits_{i=1}^n x_i^2}

Thus

\displaystyle n^{2n}s_1^{2n} \ge n^n\cdot n^{n-1}s_2^{n-1}\sum_{i=1}^n x_i^2

Again by A_{(n-1, 2)} we have s_2^{n-1} \ge s_1^{n-2}s_n. Using this we have

\displaystyle n^{2n}s_1^{2n} \ge n^n\cdot n^{n-1}s_2^{n-1}\sum_{i=1}^n x_i^2 \ge n^{n-1}s_1^{n-2}s_n\sum_{i=1}^n x_i^2 \implies ns_1^{n+2} \ge s_n\sum_{i=1}^n x_i^2

which is equivalent to

\displaystyle (x_1+x_2+\cdots+x_n)^{n+2} \ge n^{n+1}\prod_{i=1}^n x_i \sum_{i=1}^n x_i^2

which is precisely what we want to show. Hence the proof is complete. \square

Note that \boxed{5} for three variables becomes

(x_1+x_2+x_3)^5 \ge 81x_1x_2x_3(x_1^2+x_2^2+x_3^2)

which is the well-known Vasc inequality.

Let us use the notations used by Lastnightstar from here.

Let x_1,x_2,\ldots, x_n be nonnegative reals. Let

\displaystyle \nu_{(m,r)}=\frac{1}{\binom{n}{m}}\sum_{1\leq{ i_1}<{i_2}<{\cdots}<{i_{m}}\leq{ n}}{(x_{i_1}x_{i_2}{\cdots}x_{i_m})^r}

denote the general arithmetic mean of the symmetric sum of variables.

Then maclaurin’s inequality is equivalent to \displaystyle \nu_{(1,1)}\ge \sqrt{\nu_{(2,1)}} \ge \sqrt[3]{\nu_{(3,1)}} \ge \cdots \ge \sqrt[n]{\nu_{(n,1)}} and Newton’s inequality is equivalent to \displaystyle \nu_{(k,1)}^2 \ge \nu_{(k+1,1)}\nu_{(k-1,1)}.

Under this notations the two inequalities in \boxed{3} become \displaystyle \nu_{(m,1)}^k \ge \nu_{(m-1,1)}^{k-1}\nu_{(m+k-1,1)} and \displaystyle \nu_{(m,1)}^k \ge \nu_{(m+1,1)}^{k-1}\nu_{(m-k+1,1)} respectively.

\boxed{6}: Let \displaystyle x_1,x_2,\ldots, x_n\in\mathbb{R}^+, n\geq m+k-1\geq m\geq 1 and \displaystyle n,m,k\in\mathbb{N}, then show that

\displaystyle\nu_{(1,m-1)}^{k-1}\nu_{(1,m+k-1)}-\nu_{(1,m)}^k\geq 0

Proof: The inequality is equivalent to

\displaystyle\left(\sum_{i=1}^n x_i^{m-1}\right)^{k-1}\left(\sum_{i=1}^n x_i^{m+k-1}\right) \geq \left(\sum_{i=1}^n x_i^m\right)^k

Which is true because by Holder:

\displaystyle\begin{aligned}\left(\sum_{i=1}^n x_i^{m-1}\right)^{k-1} \left(\sum_{i=1}^n x_i^{m+k-1}\right) & \ge \left(\sum_{i=1}^n x_i^{\frac{(m-1)(k-1)+m+k-1}{k}}\right)^k \\ & = \left(\sum_{i=1}^n x_i^m\right)^k \end{aligned}

Similarly we can prove:

\boxed{7}: If x_1,x_2,\ldots, x_n\in\mathbb{R}^+, n\geq m\geq m-k+1\geq 0; n,m,k\in\mathbb{N}, then

\displaystyle \nu_{(1,m+1)}^{k-1}\nu_{(1,m-k+1)}-\nu_{(1,m)}^k\geq 0

\boxed{8} Show that \displaystyle \nu_{(1,p-1)}\nu_{(1,q+1)}+\nu_{(1,p+1)}\nu_{(1,q-1)}\geq 2\nu_{(1,p)}\nu_{(1,q)} for suitable values of p,q.

Proof:  By AM-GM and Cauchy Schwarz we have

\displaystyle\begin{aligned}\nu_{(1,p-1)}\nu_{(1,q+1)}+\nu_{(1,p+1)}\nu_{(1,q-1)} & \ge 2\sqrt{\nu_{(1,p-1)}\nu_{(1,q+1)}\nu_{(1,p+1)}\nu_{(1,q-1)}} \\ & \ge 2\sqrt{\nu_{(1,p)}^2\nu_{(1,q)}^2} \\ & = 2\nu_{(1,p)}\nu_{(1,q)} \end{aligned}

\boxed{9} (Lastnightstar): Let f_{(3,1)}=\nu_{(1,3)}-\nu_{(1,2)}\nu_{(1,1)}, \ \ \ f_{(3,2)}=\nu_{(2,1)}\nu_{(1,1)}-\nu_{(3,1)} and let g_{(3,1)}=2f_{(3,1)}-(n-1)f_{(3,2)}. Show that g_{(3,1)} \ge 0

Proof: Let us prove for 3 variables. For 3 variables the inequality is equivalent to

\displaystyle 2\left(\frac13\sum_{cyc} x^3 -\frac19\sum_{cyc} x^2\sum_{cyc} x\right) \ge 2\left(\frac19\sum_{cyc} xy\sum_{cyc} x -xyz\right)

\displaystyle\iff 2(2\sum_{cyc} x^3 -\sum_{cyc} xy(x+y)) \ge 2(\sum_{cyc} xy(x+y) -6xyz)

\displaystyle\iff \sum_{cyc} x^3 +3xyz \ge \sum_{cyc} xy(x+y)

which Schur’s inequality of 3 degree.

For n > 3 variables,

\displaystyle 2\left(\frac1n\sum_{i=1}^n x_i^3 - \frac1{n^2}\sum_{i=1}^n x_i^2\sum_{i=1}^n x_i\right)

\displaystyle \ge (n-1)\left(\frac{1}{n}\sum_{i=1}^n x_i\frac{1}{\binom{n}{2}}\sum_{1\le i<j\le n} x_i x_j - \frac{1}{\binom{n}{3}}\sum_{1\le i<j<k\le n} x_i x_j x_k\right)

\displaystyle\iff 2\left(n\sum_{i=1}^n x_i^3-\sum_{i=1}^n x_i^2\sum_{i=1}^n x_i\right) \ge \left(2\sum_{i=1}^n x_i\sum_{1\le i<j\le n} x_i x_j - \frac{6n}{n-2}\sum_{1\le i<j<k\le n} x_i x_j x_k\right)

\displaystyle (n-2)\left(n\sum_{i=1}^n x_i^3-\sum_{i=1}^n x_i^2\sum_{i=1}^n x_i\right) \ge \left((n-2)\sum_{i=1}^n x_1\sum_{1\le i<j\le n} x_i x_j - 3n\sum_{1\le i<j<k \le n} x_i x_j x_k\right)

Let us simplify the left side:

\displaystyle (n-2)\left(n\sum_{i=1}^n x_i^3 -\sum_{i=1}^n x_i^2\sum_{i=1}^n x_i\right)= \sum_{i=1}^n x_i^2(n-2)(nx_i-\sum_{i=1}^n x_i)

Note that

\displaystyle \begin{aligned}\underset{i\neq k, j \neq k}{\sum_{1\le i<j\le n}} (2x_k-x_i-x_j) & = 2\binom{n-1}2 x_k - (n-2){\sum_{i=1, i \neq k}^n} x_i \\ & = (n-2)((n-1)x_k-\sum_{i=1, i \neq k}^n x_i) \\ & = (n-2)(nx_k -\sum_{i=1}^n x_i) \end{aligned}

Hence

\displaystyle\begin{aligned}(n-2)\left(n\sum_{i=1}^n x_i^3 -\sum_{i=1}^n x_i^2\sum_{i=1}^n x_1\right) & = \sum_{k=1}^n x_k^2\left(\underset{i\neq k, j \neq k}{\sum_{1\le i<j\le n}} (2x_k-x_i-x_j)\right) \\ & = \sum_{1\le i <j < k\le n} A_{(i,j,k)} \end{aligned}

where

\displaystyle A_{(i.j,k)}=x_i^2(2x_i-x_j-x_k)+x_j^2(2x_j-x_k-x_i)+x_k^2(2x_k-x_i-x_j)

Now let us simplify the right side:

\displaystyle (n-2)\sum_{k=1}^n x_k\sum_{1\le i<j\le n} x_i x_j - 3n\left[\sum_{1\le i<j<k\le n} x_i x_j x_k\right]

Note that

\displaystyle\begin{aligned}& \sum_{k=1}^n x_k\sum_{1\le i<j\le n} x_i x_j \\ & = \frac1{n-2}\sum_{\ell=1}^n x_{\ell}\left[\sum_{1\le i<j<k\le n}(x_i x_j+x_j x_k+x_k x_i)\right] \\ & = \frac1{n-2}\left[\sum_{1 \le i<j<k\le n}(x_i+x_j+x_k)(x_i x_j+x_j x_k+x_k x_i)+\sum_{1 \le i<j<k\le n} \underset{\ell \neq i,\ell \neq j , \ell \neq k}{\sum_{\ell=1}^n}x_{\ell}(x_i x_j+x_j x_k+x_k x_i)\right] \\ & = \frac1{n-2}\left[\sum_{1 \le i<j<k\le n}(x_i+x_j+x_k)(x_i x_j+x_j x_k+x_k x_i)+3(n-3)\sum_{1 \le i<j<k\le n} x_i x_j x_k\right] \end{aligned}

Therefore

\displaystyle\begin{aligned} & (n-2)\sum_{k=1}^n x_k\sum_{1\le i<j\le n} x_i x_j - 3n\left[\sum_{1\le i<j<k\le n} x_i x_j x_k\right] \\ & = \left[\sum_{1\le i<j<k\le n} \{(x_i+x_j+x_k)(x_i x_j+x_j x_k+x_k x_i) - 9x_i x_j x_k \}\right] \\ & = \sum_{1\le i<j<k\le n} B_{(i,j,k)} \end{aligned}

Note that A_{(i,j,k)} \ge B_{(i,j,k)} Since it is exactly equivalent to g_{(3,1)} \ge 0 for 3 variables namely i,j,k, i.e., Schur’s inequality of 3 degree.
Hence we have

\displaystyle g_{(3,1)}=\sum_{1\le i<j<k\le n}\left[A_{(i,j,k)}-B_{(i,j,k)}\right] \ge 0

\boxed{10} Show that

\displaystyle 3n\cdot\nu_{(1,1)}(\nu_{(2,1)}\nu_{(1,1)}-\nu_{(3,1)})\geq 2(n-1)(\nu_{(3,1)}\nu_{(1,1)}-\nu_{(4,1)})

Proof: It can be proved similarly like the last one.

To be expanded…..

The full thing is already available in my old blog:

http://www.artofproblemsolving.com/community/c2426h1043311_symmetric_n_variable_inequalities

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s