Non-negative coefficients polynomials

Question

Let $n \in \mathbb N$ and $P,Q \in \mathbb R_+[x]$.

Is it true that $(x+1)^n\neq (x-2)^2 \times P(x)+(x-4)^2 \times Q(x)$ ?

I have asked, this question here (*), two weeks ago, but no answers.

(*) : https://artofproblemsolving.com/community/c6h3449999

Answer 1

This is true for all $n\le31$ and false for all $n\ge32$. Note that if $P$ and $Q$ have nonnegative coefficients, then this is true also for $(1+x)^kP$ and $(1+x)^kQ$ for all $k\ge0$. So we need to show our claim only for the separating cases $n=32$ and $n=31$.

First we provide polynomials $P$ and $Q$ for the case $n=32$. As they are somewhat messy, it is possibly best to let the SageMath code verify the example:

R.<x> = QQ[]
n = 32
Q = x^22 * (x^8 + 40*x^7 + 800*x^6 + 10720*x^5
            + 108920*x^4 + 901216*x^3
            + 6373200*x^2 + 275225453226539/8388608*x
            + 167518566127061/16777216)
F = (1+x)^n - (x-4)^2*Q
print(F%((x-2)^2) == 0)
P = F//(x-2)^2
print(min(P.coefficients()) >= 0)

There are also examples where all the coefficients of $P$ and $Q$ are positive (in fact $\ge1/20$).

Now to the nonexistence of the polynomials $P$ and $Q$ for $n=31$. Suppose there are such polynomials, and let $p_0,\ldots,p_{n-2}$ and $q_0,\ldots,q_{n-2}$ be the coefficients of $P$ and $Q$. In particular, we have \begin{equation} (i-2)^2P(i)+(i-4)^2Q(i)=(1+i)^n \text{ for } i=0,1,\ldots,n. \end{equation} This gives a system of linear equations in the $p_i$ and $q_i$ with the constraints $p_i\ge0$, $q_i\ge0$. We expect that there is no solution. So by the duality theorem of linear programming, there should be a linear combination of these $n+1$ equations such that the coefficients of the $p_i$ and $q_i$ are all nonnegative, while the right hand side is negative. So providing such linear combination is a certificate of non-solvability. The following SageMath code provides and verifies such a certificate.

l = [-2108040331336548903403960,
     130698500541766244133725308,
     24430791984013543095814146195,
     -18951282578251718561418168740,
     66329489023372568852805416120,
     -238786160482366171485193599300,
     776055021562094319447240570732,
     -2217300061590472940868232520100,
     5543250153938554385007326392200,
     -12142357479975883554109755230100,
     23374038148804080911943087039150,
     -39665034434087870104738057305780,
     59497551650772955930444514662200,
     -79052691004060346653718195898900,
     93169242968540743250901681491700,
     -97469361874241850537601512246900,
     90507264597023562135452452319640,
     -74535394373629681240190077346700,
     54348725063828618063890118909025,
     -34998559793252130830241927230700,
     19832517216080766528228824308200,
     -9841700272595492742977438511180,
     4249825117692316966085705978100,
     -1583785758139175841822283502700,
     503931832133014267534086888600,
     -134966090692447793799632424540,
     29848270056861219503789362302,
     -5306359121198562627384997820,
     728895483678281479887347240,
     -72610278067292472590710620,
     4667803590022941066421100,
     -145382091791068044379772]
n = 31
for k in range(n-1):
    s = sum(b*(i-2)^2*i^k for i, b in enumerate(l))
    print(s >= 0)
    s = sum(b*(i-4)^2*i^k for i, b in enumerate(l))
    print(s >= 0)
s = sum(b*(1+i)^n for i, b in enumerate(l))
print(s < 0)

Note: These linear programs were handled with SageMath using the backend ppl which does exact arithmetic.