Difference between revisions of "Newton's Inequality"

Latest revision as of 03:05, 28 January 2023

Background

For $x_1, \ldots, x_n$ , we define the symmetric sum $s_k$ to be the coefficient of $t^{n-k}$ in the polynomial $\prod_{i=1}^{n}(t+x_i)$ (see Viete's sums). We define the symmetric average $d_k$ to be $\textstyle s_k/{n \choose k}$ .

Statement

For non-negative $x_1, \ldots, x_n$ and $0 < k < n$ ,

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

with equality exactly when all the $x_i$ are equal.

Proof

Lemma. For real $x_1 , \ldots, x_m$ , there exist real $x'_1, \ldots, x'_{m-1}$ with the same symmetric averages $d_0, \ldots, d_{m-1}$ .

Proof. We consider the derivative of $P(t) = \prod_{i=1}^m (t+x_i)$ . The roots of $P$ are $-x_1, \ldots, -x_m$ . Without loss of generality, we assume that the $x_i$ increase as $i$ increases. Now for any $i \in \{1, m-1\}$ , $P'(t)$ must have a root between $x_i$ and $x_{i+1}$ by Rolle's theorem if $x_i \neq x_{i+1}$ , and if $x_i = x_{i+1} = \cdots = x_{i+k}$ , then $x_{i}$ is a root of $P$ $k+1$ times, so it must be a root of $P'$ $k$ times. It follows that $P'$ must have $m-1$ non-positive, real roots, i.e., for some non-negative reals $x'_1, \ldots, x'_{m-1}$ ,

${} P'(t) = m \prod_{i=1}^{m-1}(t+x'_i)$ .

It follows that the symmetric sum $s'_k$ for $x'_1, \ldots, x'_{m-1}$ is $\frac{m-k}{m}s_k$ , so the symmetric average $d'_k = \frac{s'_k}{{m-1 \choose k}} = \frac{m-k}{m} \cdot \frac{s_k}{{m-1 \choose k}} = \frac{s_k}{{m \choose k}} = d_k$ .

Thus to prove Newton's theorem, it is sufficient to prove

$d_{n-1}^2 \ge d_{n-2}d_n$

for any $n$ . Since this is a homogenous inequality, we may normalize it so that $d_n = \prod_{i=1}^{n}x_i = 1$ . The inequality then becomes

$(n-1)\left(\sum_{i=1}^{n}\frac{1}{x_i} \right)^2 \ge 2n \sum_{0\le i<j \le n} \frac{1}{x_ix_j}$ .

Expanding the left side, we see that this is

$(n-1)\sum_{i=1}^{n}\frac{1}{x_i^2} + (n-1)\sum_{0\le i<j \le n}\frac{2}{x_ix_j} \ge 2n \sum_{0\le i<j \le n} \frac{1}{x_ix_j}$ .

But this is clearly equivalent to

$\sum_{\rm sym}\frac{1}{x_1^2} \ge \sum_{\rm sym}\frac{1}{x_1x_2}$ ,

which holds by the rearrangement inequality.

Proof: without calculus

We will proceed by induction on $n$ .

For $n =2$ , the inequality just reduces to AM-GM inequality. Now suppose that for $n =m-1$ some positive integer $m\ge 3$ the inequality holds.

Let $x_1$ , $x_2$ , $\ldots$ , $x_m$ be non-negative numbers and $d_k$ be the symmetric averages of them. Let $d'_k$ be the symmetric averages of $x_1$ , $\ldots$ , $x_{m-1}$ . Note that $d_k = \frac{n-k}{n} {d'}_k + \frac{k}{n} {d'}_{k-1} x_m$ .

$d_{k-1}d_{k+1} = \left(\frac{n-k+1}{n} {d'}_{k-1} + \frac{k-1}{n} {d'}_{k-2} x_m \right)\left(\frac{n-k-1}{n} {d'}_{k+1} + \frac{k+1}{n} {d'}_k x_m \right)$ $= \frac{(n-k+1)(n-k-1)}{n^2} {d'}_{k-1}{d'}_{k+1} + \frac{(k-1)(n-k-1)}{n^2} {d'}_{k-2} {d'}_{k+1} x_m$ $+ \frac{(n-k+1)(k+1)}{n^2} {d'}_{k-1}{d'}_k x_m + \frac{(k-1)(k+1)}{n^2} {d'}_{k-2}{d'}_k x_m^2$ $\le \frac{(n-k+1)(n-k-1)}{n^2} {d'}_k^2 + \frac{(k-1)(n-k-1)}{n^2} {d'}_{k-2} {d'}_{k+1} x_m$ $+ \frac{(n-k+1)(k+1)}{n^2} {d'}_{k-1}{d'}_k x_m + \frac{(k-1)(k+1)}{n^2} {d'}_{k-1}^2 x_m^2$ $\le \frac{(n-k+1)(n-k-1)}{n^2} {d'}_k^2 + \frac{(k-1)(n-k-1)}{n^2} {d'}_{k-1} {d'}_{k} x_m$ $+ \frac{(n-k+1)(k+1)}{n^2} {d'}_{k-1}{d'}_k x_m + \frac{(k-1)(k+1)}{n^2} {d'}_{k-1}^2 x_m^2$ $= \frac{(n-k)^2}{n^2} {d'}_k^2 + \frac{2(n-k)k}{n^2} {d'}_k {d'}_{k-1} x_m +\frac{k^2}{n^2} {d'}_{k-1}^2 x_m^2 - \left(\frac{d_k}{n} - \frac{d_{k-1}x_m}{n}\right)^2$ $\le \left(\frac{n-k}{n} {d'}_k + \frac{k}{n} {d'}_{k-1} x_m \right)^2 = d_k^2$ By induction this completes the proof.

@@ Line 1: / Line 1: @@
 == Background ==
-For <math> x_1, \ldots, x_n </math>, we define the [[symmetric sum]] <math> \displaystyle s_k </math> to be the coefficient of <math> \displaystyle t^{n-k} </math> in the polynomial <math> \prod_{i=1}^{n}(t+x_i) </math> (see [[Viete's sums]]).  We define the ''symmetric average'' <math> \displaystyle d_k </math> to be <math> \textstyle s_k/{n \choose k} </math>.
+For <math> x_1, \ldots, x_n </math>, we define the [[symmetric sum]] <math>s_k </math> to be the coefficient of <math>t^{n-k} </math> in the polynomial <math> \prod_{i=1}^{n}(t+x_i) </math> (see [[Viete's sums]]).  We define the ''symmetric average'' <math>d_k </math> to be <math> \textstyle s_k/{n \choose k} </math>.
 == Statement ==
-For non-negative <math> x_1, \ldots, x_n</math> and <math> \displaystyle 0 < k < n </math>,
+For non-negative <math> x_1, \ldots, x_n</math> and <math>0 < k < n </math>,
 <center>
 <math>
-\displaystyle
 d_k^2 \ge d_{k-1}d_{k+1}
 </math>,
 </center>
-with equality exactly when all the <math> \displaystyle x_i </math> are equal.
+with equality exactly when all the <math>x_i </math> are equal.
 == Proof ==
@@ Line 20: / Line 20: @@
 ''Proof.''
-We consider the [[derivative]] of <math> P(t) = \prod_{i=1}^n (t+x_i) </math>.  The roots of <math> \displaystyle P </math> are <math> -x_1, \ldots, -x_n </math>.  Without loss of generality, we assume that the <math> \displaystyle x_i </math> increase as <math> \displaystyle i </math> increases.  Now for any <math> \displaystyle i \in [1, m-1] </math>, <math> \displaystyle P'(t) </math> must have a root between <math> \displaystyle x_i </math> and <math> \displaystyle x_{i+1} </math> by [[Rolle's theorem]] if <math> \displaystyle x_i \neq x_{i+1} </math>, and if <math> x_i = x_{i+1} = \cdots = x_{i+k} </math>, then <math> \displaystyle x_{i} </math> is a root of <math> \displaystyle P </math> <math> \displaystyle k+1 </math> times, so it must be a root of <math> \displaystyle P' </math> <math> \displaystyle k </math> times.  It follows that <math> \displaystyle P' </math> must have <math> \displaystyle m-1 </math> non-positive, real roots, i.e., for some non-negative reals <math> x'_1, \ldots, x'_{m-1} </math>,
+We consider the [[derivative]] of <math> P(t) = \prod_{i=1}^m (t+x_i) </math>.  The roots of <math>P </math> are <math> -x_1, \ldots, -x_m </math>.  Without loss of generality, we assume that the <math>x_i </math> increase as <math>i </math> increases.  Now for any <math>i \in \{1, m-1\} </math>, <math>P'(t) </math> must have a root between <math>x_i </math> and <math>x_{i+1} </math> by [[Rolle's theorem]] if <math>x_i \neq x_{i+1} </math>, and if <math> x_i = x_{i+1} = \cdots = x_{i+k} </math>, then <math>x_{i} </math> is a root of <math>P </math> <math>k+1 </math> times, so it must be a root of <math>P' </math> <math>k </math> times.  It follows that <math>P' </math> must have <math>m-1 </math> non-positive, real roots, i.e., for some non-negative reals <math> x'_1, \ldots, x'_{m-1} </math>,
 <center>
 <math> {}
@@ Line 26: / Line 26: @@
 </math>.
 </center>
-It follows that the symmetric sum <math> \displaystyle s'_k </math> for <math> x'_1, \ldots, x'_{m-1} </math> is <math> \frac{m-k}{m}s_k </math>, so the symmetric average <math> \displaystyle d'_k = \frac{s'_k}{{m-1 \choose k}} = \frac{m-k}{m} \cdot \frac{s_k}{{m-1 \choose k}} = \frac{s_k}{{m \choose k}} = d_k </math>.
+It follows that the symmetric sum <math>s'_k </math> for <math> x'_1, \ldots, x'_{m-1} </math> is <math> \frac{m-k}{m}s_k </math>, so the symmetric average <math>d'_k = \frac{s'_k}{{m-1 \choose k}} = \frac{m-k}{m} \cdot \frac{s_k}{{m-1 \choose k}} = \frac{s_k}{{m \choose k}} = d_k </math>.
 Thus to prove Newton's theorem, it is sufficient to prove
 <center>
 <math>
-\displaystyle
 d_{n-1}^2 \ge d_{n-2}d_n
 </math>
 </center>
-for any <math> \displaystyle n </math>.  Since this is a [[homogenous]] inequality, we may [[normalize]] it so that <math> d_n = \prod_{i=1}^{n}x_i = 1 </math>.  The inequality then becomes
+for any <math>n </math>.  Since this is a [[homogenous]] inequality, we may [[normalize]] it so that <math> d_n = \prod_{i=1}^{n}x_i = 1 </math>.  The inequality then becomes
 <center>
 <math>
@@ Line 55: / Line 55: @@
 which holds by the [[rearrangement inequality]].
-== Resources ==
+''Proof: without calculus''
+We will proceed by induction on <math>n</math>.
+For <math>n =2</math>, the inequality just reduces to AM-GM inequality.
+Now suppose that for <math>n =m-1</math> some positive integer <math>m\ge 3</math>    the inequality holds.
+Let <math>x_1</math>, <math>x_2</math>, <math>\ldots</math>, <math>x_m</math> be non-negative numbers and <math>d_k</math> be the symmetric averages of them.
+Let <math>d'_k</math> be the symmetric averages of <math>x_1</math>, <math>\ldots</math>, <math>x_{m-1}</math>.
+Note that <math>d_k = \frac{n-k}{n} {d'}_k + \frac{k}{n} {d'}_{k-1} x_m</math>.
+<cmath>
+        d_{k-1}d_{k+1} = \left(\frac{n-k+1}{n} {d'}_{k-1} + \frac{k-1}{n} {d'}_{k-2} x_m \right)\left(\frac{n-k-1}{n} {d'}_{k+1} + \frac{k+1}{n} {d'}_k x_m \right)
+</cmath>
+<cmath>
+        = \frac{(n-k+1)(n-k-1)}{n^2} {d'}_{k-1}{d'}_{k+1} + \frac{(k-1)(n-k-1)}{n^2} {d'}_{k-2} {d'}_{k+1} x_m
+</cmath>
+<cmath>
+         + \frac{(n-k+1)(k+1)}{n^2} {d'}_{k-1}{d'}_k x_m + \frac{(k-1)(k+1)}{n^2} {d'}_{k-2}{d'}_k x_m^2
+</cmath>
+<cmath>
+        \le  \frac{(n-k+1)(n-k-1)}{n^2} {d'}_k^2 + \frac{(k-1)(n-k-1)}{n^2} {d'}_{k-2} {d'}_{k+1} x_m
+</cmath>
+<cmath>
+         + \frac{(n-k+1)(k+1)}{n^2} {d'}_{k-1}{d'}_k x_m + \frac{(k-1)(k+1)}{n^2} {d'}_{k-1}^2 x_m^2
+</cmath>
+<cmath>
+        \le  \frac{(n-k+1)(n-k-1)}{n^2} {d'}_k^2 + \frac{(k-1)(n-k-1)}{n^2} {d'}_{k-1} {d'}_{k} x_m
+</cmath>
+<cmath>
+         + \frac{(n-k+1)(k+1)}{n^2} {d'}_{k-1}{d'}_k x_m + \frac{(k-1)(k+1)}{n^2} {d'}_{k-1}^2 x_m^2
+</cmath>
+<cmath>
+        = \frac{(n-k)^2}{n^2} {d'}_k^2 + \frac{2(n-k)k}{n^2} {d'}_k {d'}_{k-1} x_m +\frac{k^2}{n^2} {d'}_{k-1}^2 x_m^2 - \left(\frac{d_k}{n} - \frac{d_{k-1}x_m}{n}\right)^2
+</cmath>
+<cmath>
+        \le  \left(\frac{n-k}{n} {d'}_k + \frac{k}{n} {d'}_{k-1} x_m \right)^2        = d_k^2
+</cmath>
+By induction this completes the proof.
+== See Also ==
 * [[Inequality]]
+* [[Maclaurin's Inequality]]
+[[Category:Algebra]]
+[[Category:Inequalities]]

Page

Toolbox

Search

Difference between revisions of "Newton's Inequality"

Latest revision as of 03:05, 28 January 2023

Contents

Background

Statement

Proof

See Also