Assume that every root of polynomial $P(x) = x^d - a_1x^{d-1} + ... + (-1)^{d-k}a_d$ is in $[0,1]$. Show that for every $k = 1,2,...,d$ the following inequality holds: $ a_k - a_{k+1} + ... + (-1)^{d-k}a_d \geq 0 $
Problem
Source: Simurgh 2019 - Problem 4
Tags: algebra, polynomial
25.02.2019 12:07
This is essentially equivalent to Bonferroni's inequalities.
26.02.2019 18:15
Bump Bump
27.02.2019 16:15
SchuesterCHNones wrote: Bump Bump Huh? ThE-dArK-lOrD gave a clear reference above...? In fact, this is just the Bonferroni Inequality with independent events of probabilities $x_i$ where $x_i, i=1,2,\dots,d$ are the roots of $P$.
27.02.2019 17:16
SinaQane wrote: Assume that every root of polynomial $P(x) = x^d - a_1x^{d-1} + ... + (-1)^{d}a_d$ is in $[0,1]$. Show that for every $k = 1,2,...,d$ the following inequality holds: $ a_k - a_{k+1} + ... + (-1)^{d-k}a_d \geq 0 $ In fact, it boils down to prove the following. Suppose all roots of $P(x)=a_0x^n + a_1 x^{n-1}+\dots + a_{n-1}x+a_n\,,\, a_0>0$ are in $(0,1)$. Let $a'_k := a_n+a_{n-1}+\dots+a_k\,,\,k=0,1,\dots,n$. Then $a'_0>0$ and the sequence $a'_0,a'_1,\dots,a'_n$ alternatively changes its sign. The idea is to apply a simple rational transformation which maps $(0,\infty)$ to $(0,1)$ after that the new polynomial would have all roots in $(0,\infty)$. Then to apply the Descartes rule of signs. Let us set $x=\frac{1}{t+1}$. Then all roots of the polynomial $Q(t)=a_n(t+1)^n+a_{n-1}(t+1)^{n-1}+\dots+a_1(t+1)+a_0$ are positive. The coefficient $b_k$ at $t^k$ of $Q(t)$ is: $$b_{k}= a_n\binom{n}{k}+a_{n-1}\binom{n-1}{k}+\dots+a_{k+1}\binom{k+1}{k}+ a_{k}\binom{k}{k}\,,\,k=0,1,\dots,n$$Applying the Descartes rule of signs we get $b_0,b_1,\dots,b_n$ alternatively change its sign. Since $b_0=P(1)>0$ (because $a_0>0$), it yields: $$(-1)^kb_k=(-1)^k \left[a_n\binom{n}{k}+a_{n-1}\binom{n-1}{k}+\dots+a_{k+1}\binom{k+1}{k}+ a_{k}\binom{k}{k}\right]>0\,;\,k=0,1,\dots,n.$$Obviously, adding consecutively to $(-1)^kb_k$ the terms $(-1)^{\ell}b_{\ell},\ell>k$, multiplied by some coefficients we get $(-1)^k a'_k$. That's: $$(-1)^ka'_k = (-1)^kb_k + \sum_{\ell=k+1}^n \lambda_{\ell}(-1)^{\ell} b_{\ell}.$$It remains to see $\lambda_{\ell}>0$.
05.02.2020 09:41
As suggested in @tintarn's post, regard the roots $b_1, b_2, ... , b_d$ as the probabilities of some "events". For example, assume there $d$ boxes which contains infinite number of black and white ball so that the density of white ball in $k$th box is exactly $b_k$. Then $a_i$ are the sum of all possible combination of $b_{n_1} b_{n_2}...b_{n_i}$. When all the roots are $1$ and $P(x)=(x-1)^d$. For this case, Let $c_{k,d}= a_k - a_{k+1}+...+(-1)^{d-k}a_d$ and we can easily see that $c_{k,d}$ are always non-negative. Returning back to original $a_k - a_{k+1}+...+(-1)^{d-k}a_d$ for $b_i$, the term is the weighted sum of events with at least $k$ white balls. The weight(coefficient) for each event "white balls precisely from $n_1 , n_2 , ... , n_j$" is equal to $c_k,j$ which is non-negative. Note that the possibility of event is equal to $b_{n_1}...b_{n_j}(1-b_{m_1})...(1-b_{m_{d-j}})$ where $m_1 , ... , m_{d-j}$ are the boxes with a black ball. Therefore, the weighted sum $a_k - a_{k+1}+...+(-1)^{d-k}a_d$ is also always non-negative.