Let $ P(x)$ be a polynomial with real coefficients such that $ P(x) > 0$ for all $ x \geq 0.$ Prove that there exists a positive integer n such that $ (1 + x)^n \cdot P(x)$ is a polynomial with nonnegative coefficients.
Problem
Source: IMO Shortlist 1997, Q11
Tags: algebra, polynomial, coefficients, IMO Shortlist
10.08.2008 09:46
10.08.2008 12:04
Solution: Obviously,coefficient in front of $ x^n$,where $ n$ is degree of $ P$,is positive,otherwise when $ x\rightarrow\infty$ our polynomial $ P\rightarrow - \infty$.So we can divide all polynomial to this coefficient and we may assume that $ P(x)$ is of the form: \[ x^{n} + a_{n - 1}x^{n - 1} + \dots + a_0 \] We can proceed by induction on the degree of $ P(x)$ to prove the statement. We will check the base later,let's at first show how can induction be used here: Suppose that we have proved the problem for all quadratic and linear polynomials and for all polynomials of degree $ \leq n$,satisfying to the necessary conditions.We need to prove the statement for $ n + 1$. It is well-known fact that $ P(x)$ can be represented in the following form: \[ P(x) = (x + \alpha_1)(x + \alpha_2)\dots(x + \alpha_k)(x^2 - p_1x + q_1)\dots(x^2 - p_l + q_l) \] ,where $ k + 2l = n + 1$ and polynomials $ x^2 - p_ix + q_i$ are always positive. Denote \[ Q(x) = (x + \alpha_1)(x + \alpha_2)\dots(x + \alpha_k) \] \[ R(x) = (x^2 - p_1x + q_1)\dots(x^2 - p_l + q_l) \] Since $ x^2 - p_ix + q_i > 0$ for all $ x\in\mathbb{R}$,it follows that there exist some $ m_i$ for each $ x^2 + p_ix + q_i$,such that polynomial \[ (1 + x)^{m_i}(x^2 + p_ix + q_i) \] has nonnegative coefficients. On the other hand,since $ P$ has no positive roots it follows that $ \alpha_1,\alpha_2,\dots,a_k > 0$,so $ Q(x)$ has nonnegative coefficients,finally $ (1 + x)^{m_1 + m_2 + \dots + m_l}\cdot P(x)$ has nonnegative coefficients. The last step is to show why statement true for quadratic trinomials. Let $ P(x) = x^2 - bx + c$,where $ b,c > 0$.We may also assume that $ P$ has no roots,because if it has then they are negative and $ P$ has nonnegative coefficients and we will have nothing to prove. Consider polynomial $ F(x) = (1 + x)^{n}P(x)$.We can represent $ F(x)$ as follows: $ F(x) = x^{n + 2} + x^{n + 1}\cdot\left(\binom{n}{1} - b\right) + x^{n}\left(\binom{n}{2} - b\cdot\binom{n}{1} + c\right) + \dots + x^{n - k}\left(\binom{n}{k + 2} - b\cdot\binom{n}{k + 1} + c\cdot\binom{n}{k}\right) + x\left(c\cdot\binom{n}{1} - b\right) + c$ But for enough large value of $ n$ all the coefficients will be positive.So the base is checked and the proof is complete. P.S: I didn't read JoeBlow's post above and I am sorry if has the same idea I used in my proof...
07.06.2020 05:35
Since both of above proofs are not complete how to manage quadratic polynomial case, I'll prove this in detail here. Consider $$(1+x)^{m}(x^2 + bx + c)$$where $b^2 - 4c < 0$. Note that we have $c > 0$ and $|b| < 2\sqrt{c}$. Observe that $$(1 + x)^m(x^2 + bx + c)= \sum_{k=0}^{m+2}\left(\binom{m}{k-2} + \binom{m}{k-1}b + \binom{m}{k}c\right)x^k=\sum_{k=0}^{m+2}\frac{m!}{k!(m-k+2)!}f(k)x^k$$where $$f(k) = (1+c - b)\cdot k^2 - \big(m(2c - b)+3c -2b + 1\big)\cdot k+(m^2 +3m + 2)c.$$We need to show that there exists $m$ such that $f(k) \geq 0$ for all $0 \leq k \leq m + 2$. Observe that $$\bigtriangleup_f = \big( m(2c - b) + 3c - 2b + 1\big)^2 - 4(1 + c - b)(m^2 + 3m + 2)c = (b^2 -4c)m^2 + A m + B$$So $$\bigtriangleup_f \to -\infty \,\, \text{ as }\,\, m \to +\infty.$$In particular, there exists $m$ such that $\bigtriangleup_f < 0$. Since coefficient of $k^2$ in $f(k)$ is $$1 + c - b > 1+c- 2\sqrt{c} = (1 - \sqrt{c})^2 \geq 0$$we deduce that $f(k) > 0$ for all $k$.
01.10.2021 16:05
30.11.2021 04:23
The crux of the problem is the following reduction. Claim. It suffices to prove the claim for all quadratic polynomials with nonreal roots. Factor $P(x)$ into quadratics and linear terms with real coefficients by grouping its complex roots into conjugate pairs. Because the product of two polynomials with nonnegative coefficients has nonnegative coefficients, it suffices to group the $n$ extra terms throughout the quadratics. If we can guarantee that each of the resulting products has nonnegative coefficients, we are done because $P(x)$ has no nonnegative real roots. $\blacksquare$ Now the problem is a matter of computation. Scale down by the leading coefficient, which we know is positive, to obtain some quadratic $x^2+ax+b$ with $a^2>4b$. Observe $$(x+1)^n(x^2+ax+b) = \left(x^n+nx^{n-1}+{n \choose 2}x^{n-1}+\cdots+{n \choose 2}x^2+nx+1\right)(x^2+ax+b),$$and in particular the coefficient of $x^k$ for $2 \leq k \leq n$ is given by $$\left[{n \choose n-k+2} + {n \choose n-k+1} a + {n \choose n-k}b\right] = \left[{n \choose k-2} + {n \choose k-1}a + {n \choose k} b\right].$$This coefficient equals some positive factor of $$(n-k+1)(n-k+2)+bk(k-1)+ak(n-k+2)$$after expansion. From here set $a$ to be its negative, so it suffices to prove that $$ak(n-k+2) < (n-k+1)(n-k+2)+bk(k-1)$$for all $k$. This is a quadratic in $k$, and in particular, its discriminant $$\Delta = (2a+na+2n+b+3)^2-4(a+b+1)(n^2+3n+2)$$has quadratic term $$4n^2+a^2n^2-4an^2+4an^2-4bn^2-4n^2 = (a^2-4b)n^2$$has a negative coefficient. This means that by picking $n$ sufficiently large, the expression will be positive for all $k$, because the quadratic term of $k$, $a+b+1$ is positive by the $a^2>4b$ condition. Finally, the edge cases also work out; the coefficient of $x^{n+2}$ is 1, and the coefficient of $x^{n+1}$ is $n+a$ which can be positive by taking sufficiently large $n$, and similarly the constant term is $b$ and the $x$-coefficient is $bn+a$, again positive after taking sufficiently large $n$. Hence, we are done by the first claim.
01.02.2022 21:56