Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Newton's Inequality"

(somebody have a better proof?)
 
Line 1: Line 1:
 
== Background ==
 
== 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 ==
 
== 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>
 
<center>
 
<math>
 
<math>
−
\displaystyle
+
 
 
d_k^2 \ge d_{k-1}d_{k+1}
 
d_k^2 \ge d_{k-1}d_{k+1}
 
</math>,
 
</math>,
 
</center>
 
</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 ==
 
== Proof ==
Line 20: Line 20:
  
 
''Proof.''
 
''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}^n (t+x_i) </math>.  The roots of <math>P </math> are <math> -x_1, \ldots, -x_n </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>
 
<center>
 
<math> {}
 
<math> {}
Line 26: Line 26:
 
</math>.
 
</math>.
 
</center>
 
</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
 
Thus to prove Newton's theorem, it is sufficient to prove
 
<center>
 
<center>
 
<math>
 
<math>
−
\displaystyle
+
 
 
d_{n-1}^2 \ge d_{n-2}d_n
 
d_{n-1}^2 \ge d_{n-2}d_n
 
</math>
 
</math>
 
</center>
 
</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>
 
<center>
 
<math>
 
<math>
Line 55: Line 55:
 
which holds by the [[rearrangement inequality]].
 
which holds by the [[rearrangement inequality]].
  
−
== Resources ==
+
== See Also ==
  
 
* [[Inequality]]
 
* [[Inequality]]
 +
 +
[[Category:Inequality]]
 +
[[Category:Number Theory]]

Revision as of 22:10, 14 October 2007

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}^n (t+x_i)$. The roots of $P$ are $-x_1, \ldots, -x_n$. 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.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Newton%27s_Inequality&oldid=18059"