Assume that every root of polynomial P(x)=xd−a1xd−1+...+(−1)d−kad is in [0,1]. Show that for every k=1,2,...,d the following inequality holds: ak−ak+1+...+(−1)d−kad≥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 xi where xi,i=1,2,…,d are the roots of P.
27.02.2019 17:16
SinaQane wrote: Assume that every root of polynomial P(x)=xd−a1xd−1+...+(−1)dad is in [0,1]. Show that for every k=1,2,...,d the following inequality holds: ak−ak+1+...+(−1)d−kad≥0 In fact, it boils down to prove the following. Suppose all roots of P(x)=a0xn+a1xn−1+⋯+an−1x+an,a0>0 are in (0,1). Let a′k:=an+an−1+⋯+ak,k=0,1,…,n. Then a′0>0 and the sequence a′0,a′1,…,a′n alternatively changes its sign. The idea is to apply a simple rational transformation which maps (0,∞) to (0,1) after that the new polynomial would have all roots in (0,∞). Then to apply the Descartes rule of signs. Let us set x=1t+1. Then all roots of the polynomial Q(t)=an(t+1)n+an−1(t+1)n−1+⋯+a1(t+1)+a0 are positive. The coefficient bk at tk 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,nApplying 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 kth 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.