Kvant Math Problem 1563
For $n=0$, the condition is
Verified: yes
Verdicts: PASS + PASS
Solve time: 8m28s
Source on kvant.digital
Problem
Prove that if the numbers $a_1$, $a_2$, $\ldots$, $a_m$ are nonzero and for every integer $k=0$, 1, $\ldots$, $n$ ($n\lt m-1$) $$a_1+a_2\cdot2^k+a_3\cdot3^k+\ldots+a_m\cdot m^k=0,$$, then the sequence $a_1$, $a_2$, $\ldots$, $a_m$ contains at least $n+1$ pair of adjacent numbers with opposite signs.
O. R. Musin
All-Russian Mathematical Olympiad for School Students (1996)
Exploration
For $n=0$, the condition is
$$a_1+a_2+\cdots+a_m=0.$$
Since all $a_i\neq0$, not all terms have the same sign, hence there is at least one sign change between adjacent terms. The statement is true.
For $n=1$, we have
$$\sum a_i=0,\qquad \sum i,a_i=0.$$
Take $m=3$. Then
$$a_1+ a_2+a_3=0,\qquad a_1+2a_2+3a_3=0.$$
Subtracting gives $a_2+2a_3=0$, so
$$(a_1,a_2,a_3)=(a,-2a,a).$$
There are exactly two adjacent sign changes, which equals $n+1$.
The conditions
$$\sum_{i=1}^m a_i i^k=0,\qquad k=0,\dots,n,$$
say that the signed discrete measure
$$\mu=\sum_{i=1}^m a_i\delta_i$$
annihilates every polynomial of degree at most $n$.
The desired conclusion concerns the number of sign changes of the sequence $(a_i)$. This strongly suggests a discrete version of the classical fact that a nontrivial signed measure orthogonal to all polynomials of degree $\le n$ must have at least $n+1$ sign changes.
Suppose there are only $r\le n$ adjacent sign changes. Then the indices $1,\dots,m$ split into at most $r+1\le n+1$ consecutive blocks on each of which all $a_i$ have the same sign.
Let
$$t_1<t_2<\cdots<t_r$$
be the positions where the sign changes occur, so $a_{t_j}$ and $a_{t_j+1}$ have opposite signs.
Consider
$$P(x)=\prod_{j=1}^{r}(x-t_j).$$
Its degree is $r\le n$.
For every integer $i$, the sign of $P(i)$ changes exactly when $i$ crosses one of the numbers $t_j$. Hence the sign pattern of $P(i)$ along $i=1,\dots,m$ alternates from block to block. Since the signs of the $a_i$ also alternate from block to block, multiplying $P$ by an overall constant makes
$$a_iP(i)>0$$
for every $i$.
Then
$$\sum_{i=1}^m a_iP(i)>0.$$
But $P$ has degree at most $n$, so orthogonality implies this sum must be $0$, a contradiction.
This appears to be the whole argument. The only delicate point is proving carefully that one may choose the overall sign of $P$ so that $a_iP(i)$ is positive for every index.
Problem Understanding
We are given nonzero real numbers $a_1,\dots,a_m$ satisfying
$$\sum_{i=1}^m a_i i^k=0$$
for every $k=0,1,\dots,n$, where $n<m-1$.
We must prove that the sequence $a_1,\dots,a_m$ contains at least $n+1$ pairs of adjacent terms with opposite signs.
This is a Type B problem. The statement itself is given and must be proved.
The core difficulty is to convert the algebraic conditions
$$\sum a_i i^k=0$$
into information about the sign pattern of the coefficients $a_i$. The natural bridge is to regard the conditions as orthogonality to all polynomials of degree at most $n$ and then construct a polynomial whose values have the same sign pattern as the sequence $(a_i)$.
Proof Architecture
Assume that the sequence has only $r\le n$ adjacent sign changes and derive a contradiction.
Let $t_1<\cdots<t_r$ be the positions of the sign changes; then the polynomial
$$P(x)=\prod_{j=1}^{r}(x-t_j)$$
has degree $r\le n$.
The values $P(i)$ change sign exactly when the index $i$ passes a sign-change position $t_j$, so the sign pattern of $P(i)$ alternates from block to block in exactly the same way as the sign pattern of $a_i$.
After multiplying $P$ by $-1$ if necessary, one obtains
$$a_iP(i)>0$$
for all $i$.
Hence
$$\sum a_iP(i)>0.$$
Since $\deg P\le n$, write
$$P(x)=c_0+c_1x+\cdots+c_rx^r.$$
Using the given equalities for $k=0,\dots,n$, we obtain
$$\sum a_iP(i)=0,$$
a contradiction.
The most delicate lemma is the statement that $P(i)$ and $a_i$ have the same sign on every block between consecutive sign changes.
Solution
Assume, for contradiction, that the sequence $a_1,\dots,a_m$ contains only $r$ pairs of adjacent terms with opposite signs, where
$$r\le n.$$
Let
$$t_1<t_2<\cdots<t_r$$
be all indices such that $a_{t_j}$ and $a_{t_j+1}$ have opposite signs.
Define
$$P(x)=\prod_{j=1}^{r}(x-t_j).$$
Its degree equals $r$, hence
$$\deg P=r\le n.$$
The numbers
$$1,\dots,m$$
are divided by the points $t_1,\dots,t_r$ into consecutive blocks. Since there are no sign changes inside a block, all coefficients $a_i$ in a fixed block have the same sign. Passing from one block to the next, the sign of $a_i$ changes.
Now consider the signs of $P(i)$ for integer values $i=1,\dots,m$.
For a fixed integer $i$, the sign of $P(i)$ is determined by the number of factors $i-t_j$ that are negative. When $i$ passes from a block to the next one, exactly one additional factor changes sign, namely the factor corresponding to the separating point $t_j$. Hence the sign of $P(i)$ also alternates from block to block.
Thus the sign pattern of the sequence
$$P(1),P(2),\dots,P(m)$$
alternates from block to block in exactly the same way as the sign pattern of
$$a_1,a_2,\dots,a_m.$$
Multiplying $P$ by $-1$ if necessary, we may arrange that on the first block the signs of $P(i)$ and $a_i$ coincide. Since both sign patterns alternate at every boundary between blocks, they then coincide on every block. Therefore
$$a_iP(i)>0$$
for all $i=1,\dots,m.
]
Consequently,
$$\sum_{i=1}^{m} a_iP(i)>0. \tag{1}$$
On the other hand, write
$$P(x)=c_0+c_1x+\cdots+c_rx^r.$$
Since $r\le n$, the given conditions imply
$$\sum_{i=1}^{m} a_i i^s=0 \qquad (s=0,1,\dots,r).$$
Hence
$$\sum_{i=1}^{m} a_iP(i) =\sum_{i=1}^{m} a_i \sum_{s=0}^{r} c_s i^s =\sum_{s=0}^{r} c_s \sum_{i=1}^{m} a_i i^s =0. \tag{2}$$
Statements (1) and (2) contradict each other.
The assumption $r\le n$ is impossible. Therefore
$$r\ge n+1.$$
Thus the sequence $a_1,a_2,\dots,a_m$ contains at least $n+1$ pairs of adjacent terms with opposite signs.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the comparison of sign patterns.
Let the sign-change positions be $t_1,\dots,t_r$. For an integer $i$ lying in the block
$$t_j<i\le t_{j+1},$$
with the conventions $t_0=0$ and $t_{r+1}=m$, exactly $j$ factors among
$$i-t_1,\dots,i-t_r$$
are positive and $r-j$ are negative. Hence
$$\operatorname{sgn} P(i)=(-1)^{,r-j}.$$
Moving from one block to the next increases $j$ by $1$, so the sign is multiplied by $-1$. Thus $P(i)$ changes sign at every boundary and nowhere else. This matches exactly the behavior of the sequence $(a_i)$.
The second delicate step is the deduction
$$\sum a_iP(i)=0.$$
The argument uses only linearity. Since $P$ has degree at most $n$, it is a linear combination of the monomials $1,x,\dots,x^n$. Each corresponding moment
$$\sum a_i i^k$$
vanishes by hypothesis. Therefore the same holds for every polynomial of degree at most $n$.
A careless argument might overlook the necessity of proving $\deg P\le n$. This follows from the assumption that there are only $r\le n$ sign changes, giving exactly $r$ roots $t_1,\dots,t_r$ and hence degree $r$.
Alternative Approaches
The proof is a discrete analogue of the classical variation-diminishing principle. One may formulate the hypothesis as saying that the signed measure
$$\mu=\sum_{i=1}^{m} a_i\delta_i$$
annihilates every polynomial of degree at most $n$. If $\mu$ had at most $n$ sign changes, one could construct a polynomial of degree at most $n$ whose sign agrees everywhere with the sign of $\mu$. Integrating that polynomial against $\mu$ would then give a positive value, contradicting orthogonality.
Another approach uses finite differences. The conditions imply that the linear functional
$$L(f)=\sum_{i=1}^{m} a_i f(i)$$
vanishes on all polynomials of degree at most $n$. The discrete version of the Sturm separation principle shows that a nontrivial functional with this property must have at least $n+1$ sign alternations in its coefficient sequence. The polynomial construction above is preferable because it is elementary and produces the contradiction directly.