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"

(→‎Background)
(→‎Proof)
Line 54: Line 54:
 
</center>
 
</center>
 
which holds by the [[rearrangement inequality]].
 
which holds by the [[rearrangement inequality]].
 +
 +
"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>.
 +
 +
\begin{align*}
 +
        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
 +
    \end{align*}
  
 
== See Also ==
 
== See Also ==

Revision as of 07:22, 6 July 2018

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$.

\begin{align*} 

       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
   \end{align*}

See Also

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