Kvant Math Problem 138
For $m=1$ and $n=2$,
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m21s
Source on kvant.digital
Problem
Prove that if $m$ and $n$ are integers and $1 \le m \lt n$, then $$\sum_{k=1}^n (-1)^k k^m C_n^k=0,$$ where $C_n^k$ are the binomial coefficients, that is, the coefficients of the polynomial $$(1+x)^m=\sum_{k=0}^n C_n^k x^k.$$
For example, if $n=4$, then $C_4^0=1$, $C_4^1=4$, $C_4^2=6$, $C_4^3=4$, $C_4^4=1$, and the equalities $$\begin{gather*} 1 \cdot 4+2 \cdot 6-3 \cdot 4+4 \cdot 1=0,\ -1^2 \cdot 4+2^2 \cdot 6-3^2 \cdot 4+4^2 \cdot 1=0,\ -1^3 \cdot 4+2^3 \cdot 6-3^3 \cdot 4+4^3 \cdot 1=0. \end{gather*}$$ hold.
M. I. Sidorov
Exploration
For $m=1$ and $n=2$,
$$(-1)^1\cdot 1\cdot \binom21+(-1)^2\cdot 2\cdot \binom22=-2+2=0.$$
For $m=2$ and $n=3$,
$$-1^2\binom31+2^2\binom32-3^2\binom33=-3+12-9=0.$$
For $m=2$ and $n=4$,
$$-1^2\binom41+2^2\binom42-3^2\binom43+4^2\binom44 =-4+24-36+16=0.$$
The expression resembles the derivatives of $(1-x)^n$. Indeed,
$$(1-x)^n=\sum_{k=0}^n(-1)^k\binom nk x^k.$$
Differentiating once gives
$$-n(1-x)^{n-1}=\sum_{k=1}^n(-1)^k k\binom nk x^{k-1}.$$
Substituting $x=1$ yields
$$\sum_{k=1}^n(-1)^k k\binom nk =0$$
whenever $n\ge2$.
For higher powers $k^m$, repeated differentiation may work. After $m$ differentiations,
$$\sum_{k=m}^n(-1)^k k(k-1)\cdots(k-m+1)\binom nk x^{k-m}$$
appears. Evaluating at $x=1$ gives $0$ because $(1-x)^n$ has a zero of order $n$ at $x=1$, and $m<n$.
The remaining difficulty is that the differentiated expression contains falling factorials
$$k(k-1)\cdots(k-m+1),$$
not powers $k^m$.
The crucial point is to express $k^m$ as a linear combination of falling factorials
$$k(k-1)\cdots(k-j+1), \qquad 0\le j\le m.$$
This must be proved carefully. A polynomial argument should suffice: these falling factorials form a basis of the vector space of polynomials of degree at most $m$.
Another possibility is to use the operator
$$x\frac d{dx}.$$
Applying it to $x^k$ produces
$$x\frac d{dx}(x^k)=kx^k.$$
Repeated application gives
$$\left(x\frac d{dx}\right)^m x^k=k^m x^k.$$
Applying this operator to $(1-x)^n$ and then setting $x=1$ may immediately produce the desired identity, because every derivative up to order $m$ of $(1-x)^n$ vanishes at $x=1$ when $m<n$.
This second approach is shorter and avoids the basis argument. The only delicate point is proving that
$$\left(x\frac d{dx}\right)^m (1-x)^n$$
still vanishes at $x=1$. Since every application of $x\frac d{dx}$ is a linear combination of derivatives up to order $m$, and each derivative of order less than $n$ vanishes at $x=1$, the argument should work.
Problem Understanding
We must prove that for integers $m,n$ satisfying $1\le m<n$,
$$\sum_{k=1}^n(-1)^k k^m\binom nk=0.$$
This is a Type B problem, a pure proof problem.
The core difficulty is that powers $k^m$ do not arise directly from the binomial expansion of $(1-x)^n$. The correct mechanism is the differential operator
$$x\frac d{dx},$$
whose repeated application multiplies the monomial $x^k$ by $k^m$.
The essential idea is to apply this operator to the identity
$$(1-x)^n=\sum_{k=0}^n(-1)^k\binom nk x^k$$
and then substitute $x=1$. Since $(1-x)^n$ has a zero of order $n$ at $x=1$, every derivative of order less than $n$ vanishes there.
Proof Architecture
First, prove that for every integer $r\ge0$,
$$\left(x\frac d{dx}\right)^r x^k=k^r x^k.$$
This follows by induction on $r$.
Next, apply the operator $\left(x\frac d{dx}\right)^m$ termwise to
$$(1-x)^n=\sum_{k=0}^n(-1)^k\binom nk x^k.$$
The previous lemma transforms the right-hand side into
$$\sum_{k=0}^n(-1)^k k^m\binom nk x^k.$$
Then prove that $\left(x\frac d{dx}\right)^m(1-x)^n$ is a linear combination of derivatives
$$(1-x)^n,\frac d{dx}(1-x)^n,\dots,\frac{d^m}{dx^m}(1-x)^n.$$
Each derivative of order at most $m<n$ vanishes at $x=1$, because $(1-x)^n$ has a zero of multiplicity $n$ there.
Substituting $x=1$ then yields the desired identity.
The most delicate point is justifying rigorously that every derivative of order less than $n$ of $(1-x)^n$ vanishes at $x=1$, and that repeated application of $x\frac d{dx}$ cannot produce derivatives of order exceeding $m$.
Solution
Consider the differential operator
$$D=x\frac d{dx}.$$
We first prove that for every integer $r\ge0$,
$$D^r(x^k)=k^r x^k.$$
For $r=0$,
$$D^0(x^k)=x^k=k^0x^k.$$
Assume
$$D^r(x^k)=k^r x^k$$
for some $r\ge0$. Then
$$D^{r+1}(x^k) =D\bigl(k^r x^k\bigr) =k^r D(x^k).$$
Since
$$D(x^k)=x\frac d{dx}(x^k)=x(kx^{k-1})=kx^k,$$
we obtain
$$D^{r+1}(x^k)=k^r\cdot kx^k=k^{r+1}x^k.$$
The induction is complete.
Now write the binomial identity
$$(1-x)^n=\sum_{k=0}^n(-1)^k\binom nk x^k.$$
Apply the operator $D^m$ termwise:
$$D^m(1-x)^n =\sum_{k=0}^n(-1)^k\binom nk D^m(x^k).$$
Using the lemma,
$$D^m(1-x)^n =\sum_{k=0}^n(-1)^k k^m\binom nk x^k.$$
Since $m\ge1$, the term with $k=0$ equals $0$, so
$$D^m(1-x)^n =\sum_{k=1}^n(-1)^k k^m\binom nk x^k.$$
We now evaluate at $x=1$.
The polynomial $(1-x)^n$ has a zero of multiplicity $n$ at $x=1$. Hence for every integer $j$ satisfying $0\le j<n$,
$$\frac{d^j}{dx^j}(1-x)^n\Big|_{x=1}=0.$$
It remains to show that $D^m(1-x)^n$ is a linear combination of derivatives of orders at most $m$.
For $m=1$,
$$D=x\frac d{dx},$$
so the statement holds.
Assume that for some $m\ge1$,
$$D^m=\sum_{j=0}^m p_j(x)\frac{d^j}{dx^j},$$
where the $p_j(x)$ are polynomials. Then
$$D^{m+1} =x\frac d{dx}\left(\sum_{j=0}^m p_j(x)\frac{d^j}{dx^j}\right).$$
Applying the product rule,
$$D^{m+1} =\sum_{j=0}^m xp_j'(x)\frac{d^j}{dx^j} +\sum_{j=0}^m xp_j(x)\frac{d^{j+1}}{dx^{j+1}}.$$
Thus $D^{m+1}$ is a linear combination of derivatives of orders at most $m+1$.
By induction, $D^m$ is a linear combination of derivatives of orders at most $m$.
Since $m<n$, every derivative of $(1-x)^n$ appearing in $D^m(1-x)^n$ vanishes at $x=1$. Therefore
$$D^m(1-x)^n\Big|_{x=1}=0.$$
Evaluating the earlier identity at $x=1$ gives
$$0 =\sum_{k=1}^n(-1)^k k^m\binom nk.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the identity
$$D^m(x^k)=k^m x^k.$$
A careless argument might confuse $D^m$ with ordinary differentiation. For example,
$$\frac{d^2}{dx^2}(x^k)=k(k-1)x^{k-2},$$
which is not $k^2x^k$. The operator $D=x\frac d{dx}$ behaves differently:
$$D(x^k)=kx^k,$$
and applying $D$ again gives
$$D^2(x^k)=D(kx^k)=kD(x^k)=k^2x^k.$$
The eigenfunction property of monomials is the exact mechanism producing powers $k^m$.
The second delicate step is the vanishing at $x=1$. One must verify that no derivative of order $\ge n$ appears inside $D^m$. The inductive description of $D^m$ as a combination of derivatives up to order $m$ guarantees this. Since $m<n$, every derivative involved annihilates $(1-x)^n$ at $x=1$.
To confirm this explicitly, take
$$\frac{d^j}{dx^j}(1-x)^n =(-1)^j\frac{n!}{(n-j)!}(1-x)^{n-j}.$$
If $j<n$, then $n-j>0$, so substituting $x=1$ gives $0$.
The third delicate point is the omission of the $k=0$ term. When $m\ge1$,
$$0^m=0,$$
so the term
$$(-1)^0 0^m \binom n0$$
vanishes. If $m=0$, the identity would become
$$\sum_{k=0}^n(-1)^k\binom nk=(1-1)^n=0,$$
which is also true, but the problem assumes $m\ge1$.
Alternative Approaches
Another proof uses falling factorials. Define
$$(k)_j=k(k-1)\cdots(k-j+1).$$
Differentiating
$$(1-x)^n=\sum_{k=0}^n(-1)^k\binom nk x^k$$
exactly $j$ times gives
$$\frac{d^j}{dx^j}(1-x)^n =\sum_{k=j}^n(-1)^k (k)_j\binom nk x^{k-j}.$$
Substituting $x=1$ yields
$$\sum_{k=0}^n(-1)^k (k)_j\binom nk=0$$
for every $j<n$.
The polynomial $k^m$ can be expressed uniquely as a linear combination of
$$1,(k)_1,(k)_2,\dots,(k)_m.$$
Replacing $k^m$ by this combination reduces the desired identity to the already proved identities for falling factorials.
The operator method is preferable because it produces $k^m$ directly and avoids introducing a second polynomial basis.