Verified: no
Verdicts: PASS + FAIL
Solve time: 33m09s
Source on kvant.digital

Problem

1. $f(x)$ is a nonzero polynomial of even degree. Prove that there exists a natural number $k$ such that the polynomial $$f(x)+f(x+1)+\ldots+f(x+k)$$ has no real roots.
2. $f(x)$ is a polynomial of odd degree. Prove that there exists a natural number $k$ such that the polynomial $$f(x)+f(x+1)+\ldots+f(x+k)$$ has exactly one real root.

S. Berlov, K. P. Kokhas

Saint Petersburg City Mathematical Olympiad (1995)

Solution

Let $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ with $a_n\ne 0$, and define for a natural number $k$

$F_k(x)=\sum_{j=0}^k f(x+j),\qquad G_k(y)=\frac{F_k(ky)}{k^{n+1}}.$

Then for $0\le j\le k$ and bounded $y$,

$f(ky+j)=a_n(ky+j)^n+O(k^{n-1})$

uniformly, since the lower-degree terms contribute $O(k^{n-1})$. Summing over $j=0,\dots,k$ gives

$F_k(ky)=a_n\sum_{j=0}^k(ky+j)^n+O(k^n),$

and dividing by $k^{n+1}$ yields

$G_k(y)=a_n\frac1k\sum_{j=0}^k\left(y+\frac jk\right)^n+O!\left(\frac1k\right).$

The first term is a Riemann sum for the integral of $(y+t)^n$ over $t\in[0,1]$, so uniformly on compact intervals

=\frac{a_n}{n+1}\bigl((y+1)^{n+1}-y^{n+1}\bigr).$$### Part 1 Assume $n$ is even. Then $n+1$ is odd. If $H(y)=0$, then (y+1)^{n+1}=y^{n+1}. Since $t\mapsto t^{n+1}$ is strictly monotone on $\mathbb R$, this is impossible. Thus $H$ has no real roots. Let $R>0$ be arbitrary. Since $H$ is continuous and never vanishes, there exists $c>0$ such that $|H(y)|\ge c$ for all $y\in[-R,R]$. Uniform convergence of $G_k$ to $H$ on $[-R,R]$ guarantees that there exists $k_0$ such that for all $k\ge k_0$, |G_k(y)-H(y)|<\frac c2 for all $y\in[-R,R]$, which implies that $G_k$ has no roots in $[-R,R]$. To control roots for $|y|>R$, write G_k(y)=a_n\frac1k\sum_{j=0}^k\left(y+\frac jk\right)^n+P_k(y), where $P_k(y)$ is a polynomial of degree at most $n-1$. The coefficient of $y^n$ in the first term equals a_n\frac1k\sum_{j=0}^k1 =a_n\frac{k+1}{k},$$hence$$ G_k(y)=a_n\frac{k+1}{k}y^n+Q_k(y), where $\deg Q_k\le n-1$. Fix $k$. Since $\deg Q_k\le n-1$, there is a constant $C_k>0$ such that |Q_k(y)|\le C_k|y|^{,n-1} \qquad (|y|\ge1). $$Choose$$ R_k=\max!\left(1,\frac{2C_k}{|a_n|(k+1)/k}\right). Then for $|y|\ge R_k$, |Q_k(y)| \le C_k|y|^{n-1} \le \frac{|a_n|(k+1)}{2k}|y|^n. $$Consequently,$$ |G_k(y)| \ge \frac{|a_n|(k+1)}{k}|y|^n-|Q_k(y)| \ge \frac{|a_n|(k+1)}{2k}|y|^n>0. $$Moreover,$$

\operatorname{sgn} G_k(y)

\operatorname{sgn}!\left(a_n y^n\right) \qquad (|y|\ge R_k). Since $n$ is even, $a_n y^n$ has the same sign for all sufficiently large positive and negative $y$. Thus $G_k$ has no real roots with $|y|\ge R_k$. Now choose $R=R_k$. The preceding compact-interval argument shows that for all sufficiently large $k$, $G_k$ has no roots in $[-R_k,R_k]$, while the estimate above shows that there are no roots outside this interval. Hence, for sufficiently large $k$, $G_k$ has no real roots. Since $G_k(y)=0$ if and only if $F_k(ky)=0$, the polynomial $F_k$ also has no real roots. ### Part 2 Assume $n$ is odd. Then $n+1$ is even, and H(y)=0 \iff (y+1)^{n+1}=y^{n+1} \iff |y+1|=|y|. $$The unique solution is$$ y_0=-\frac12. $$Compute the derivative$$ H'(y)=a_n\bigl((y+1)^n-y^n\bigr), $$and$$

H'!\left(-\frac12\right)

a_n\left(\left(\frac12\right)^n-\left(-\frac12\right)^n\right)

2a_n\left(\frac12\right)^n \ne0, so $y_0$ is a simple root. Choose $\varepsilon>0$ such that the interval I=\left[y_0-\varepsilon,;y_0+\varepsilon\right] contains no other roots of $H$. Since $H'$ is continuous and $H'(y_0)\neq0$, shrinking $\varepsilon$ if necessary, there exists $m>0$ such that |H'(y)|\ge m \qquad (y\in I). Hence $H$ is strictly monotone on $I$. Let \delta=\frac12\min\bigl(|H(y_0-\varepsilon)|,;|H(y_0+\varepsilon)|\bigr)>0. Then $H(y_0-\varepsilon)$ and $H(y_0+\varepsilon)$ have opposite signs, and |H(y_0\pm\varepsilon)|\ge2\delta. Uniform convergence on $I$ yields a number $k_1$ such that for all $k\ge k_1$, |G_k(y)-H(y)|<\delta \qquad (y\in I). For such $k$, G_k(y_0-\varepsilon) $$has the same sign as$$ H(y_0-\varepsilon), $$and$$ G_k(y_0+\varepsilon) $$has the same sign as$$ H(y_0+\varepsilon). Since these signs are opposite, the intermediate value theorem gives at least one root of $G_k$ in $I$. To prove uniqueness, suppose $u,v\in I$ are roots of $G_k$. Then H(u)=H(u)-G_k(u), \qquad H(v)=H(v)-G_k(v), $$so$$ |H(u)|<\delta,\qquad |H(v)|<\delta. By the mean value theorem and the bound $|H'|\ge m$ on $I$, |H(u)-H(v)|\ge m|u-v|. $$Also,$$ |H(u)-H(v)| \le |H(u)|+|H(v)| <2\delta. $$Hence$$ |u-v|<\frac{2\delta}{m}. Choosing $\delta$ smaller if necessary, this forces any two roots in $I$ to coincide. Thus $G_k$ has exactly one root in $I$. On $\mathbb R\setminus I$, the continuous function $H$ has no zeros. Hence there exists $\delta_1>0$ such that |H(y)|\ge2\delta_1 \qquad (y\notin I). Uniform convergence on every compact interval containing all possible real roots of $G_k$ then gives |G_k(y)-H(y)|<\delta_1, so $G_k(y)\neq0$ on $\mathbb R\setminus I$. Thus there are no additional roots outside $I$. Hence for sufficiently large $k$, $G_k$ has exactly one real root. Rescaling $x=ky$ shows that $F_k$ also has exactly one real root. Both statements are established. ∎