Show that $\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i (n-i)^k=0$ for $0\leq k<n$

Question

I am trying to prove that $\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i (n-i)^k=0$ for $0\leq k<n$.

This is clear from a combinatorics perspective (since this sum computes the number of surjective functions from a set $A$ of cardinality $k$ to a set $B$ of cardinality $n$ and if $k<n$ clearly there will be an element of $B$ which is not in $f(A)$ so there cannot be a surjective function from $A$ to $B$) but I would like to prove it algebraically.

I have tried by induction on $n$.

If $n=0$ the claim is vacuously true (since there is no $k\in\mathbb{N}$ such that $0\leq k $ and $k<0$). Suppose now the equality is true for some $n\in\mathbb{N}$ i.e. $\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i (n-i)^k=0$ for $0\leq k<n$; we have to prove it for $n+1$ i.e. we have to show that $\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i (n-i)^k=0$ for $0\leq k<n+1$ or, equivalently, for $0\leq k\leq n$. Since by inductive hypothesis we already know that equality holds for $0\leq k\leq n-1$ it remains to prove it only for $k=n$ and in this case we have \begin{align*} \sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i(n-i)^k&=\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i(n-i)^n=\sum\limits_{i=0}^{n}n\frac{(n-1)!}{i!(n-i)(n-i-1)!}(-1)^i(n-i)^n\\ &=n\sum\limits_{i=0}^{n}\binom{n-1}{i}(-1)^i(n-i)^{n-1}. \end{align*} Now, I haven't been able to prove that this last sum is $0$ so I would be grateful if someone would give me an hint about how to prove this (or, equivalently, would point out if there exists some other and perhaps more straightforward way to prove this result). Thanks.

Answer 1

This formula can be seen, via inclusion-exclusion, as the number of onto functions from $X=\{1,\dots,k\}\to Y=\{1,\dots,n\}.$

Let $A$ be all functions $X\to Y.$ Let $A_i$ be the set of functions whose range does not include $i.$ Then, given $I\subseteq Y,$ we have:

$$\left|\bigcap_{i\in I}A_i\right|=(n-|I|)^k,$$ and thus the number of onto functions $X\to Y$ is, by inclusion-exclusion:

$$|A\setminus(A_1\cup \cdots\cup A_n)|=\sum_{i=0}^n(-1)^i\binom ni(n-i)^k$$

But since $k<n,$ there are no such functions.

We also get, when $k=n$ that the sum is $n!$

---

Alternatively, we can talk about the operator $\Delta$ acting on functions of the natural numbers:

$$(\Delta f)(m)=f(m+1)-f(m).$$

This can be written as $\Delta=S-I,$ where $(Sf)(m)=f(m+1)$ and $I$ is the identity operator.

Then we show that if $f$ is a polynomial of degree $d$ then $\Delta f$ is a polynomial of degree $d-1.$ So if $f$ is a polynomial of degree $k,$ then $\Delta^nf$ is the zero polynomial for $n>k.$

But $\Delta^n =\sum_{i=0}^n(-1)^i\binom ni S^{n-i},$ so:

$$(\Delta^n f)(m)=\sum_{i=0}^n(-1)^i\binom ni f(m+n-i)$$

So we actually get a stronger result:

$$\sum_{i=0}^{n}(-1)^i\binom ni (m+n-i)^k=0\tag1$$

For any natural numbers $m,n,k$ with $k<n.$ Your formula is just the case when $m=0.$

This approach shows why induction is hard. If $f(m)=m^k,$ then $(\Delta f)(m)$ is not some $\alpha m^{k-1},$ but a complicated mix of monomials. Stating the result about polynomials of degree $<n$ makes the induction easier.

---

$(1)$ can still be seen as an inclusion-exclusion count - it counts the function $[k]\to[n+m]$ whose range includes $\{1,2,\dots,n\}.$

But $(1)$ is true for any $m,$ including real and complex $m.$ Indeed, for $m$ in any unital ring.

Indeed, the equality can be written as an equality in $\mathbb Z[x],$ the ring of polynomials in $x.$ Then, for $k<n:$

$$\sum_{i=0}^n (-1)^i\binom ni (x+n-i)^k=0$$

Given any unital ring $R$ and $m\in R,$ there is a homomorphism $\mathbb Z[x]\to R$ sending $p(x)\mapsto p(m).$

---

So, finally, an induction proof. We will prove that if $f(x)$ is a polynomial with $\deg f<n,$ then:

$$\sum_{i=0}^n (-1)^i\binom ni f(x+n-i)=0$$

We will assume you can prove the case $n=1.$

We will assume true for $n.$

Let $f(x)$ be a polynomial of degree less than $n+1.$

Then let $g(x)=f(x+1)-f(x).$ Show $\deg g(x)<n.$

Then, by the induction hypothesis:

$$\begin{align}0&=\sum_{i=0}^{n} (-1)^i\binom ni g(x+n-i)\\&=\sum_{i=0}^n (-1)^i(f(x+n+1-i)-f(x+n-i))\\&=\sum_{i=0}^n(-1)^i\binom ni f(x+n+1-i)+\sum_{j=1}^{n+1}(-1)^j\binom n{j-1} f(x+n+1-j)\\ &=\sum_{i=0}^{n+1}(-1)^i\binom{n+1}i f(x+n+1-i) \end{align} $$

Where $j=i+1,$ and we can expand the two sums to $i=n+1$ and $j=0$ since $\binom nk=0$ when $k=-1,n+1.$

This proof is, essentially, doing the same as the $\Delta$ proof, just hiding the idea of linear operators. At heart, we are just proving the binomial expansion of $(S-I)^n.$

Answer 2

Since $a_k:=\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^i (n-i)^k=(-1)^n\sum\limits_{j=0}^{n}\binom{n}{j}(-1)^j j^k$, I will consider the latter sum instead.

Define $f(x)=(-1)^n\sum_{j=0}^n\binom{n}{j}(-1)^je^{jx}$. Then $a_k=f^{(k)}(0)$. However, by the binomial theorem, $f(x)=(-1)^n(1-e^x)^n$. Therefore, for $k=0,1,\ldots,n$, we have $f^{(k)}(x)=(1-e^x)^{n-k}p_k(e^x)$ for some polynomial $p_k$. It follows that $a_k=f^{(k)}(0)=0$ when $k<n$.

Edit. In hindsight, this does not really answer the OP’s question, as the OP asks for an algebraic proof. I guess one needs some umbral calculus here, but I am not familiar with those stuffs.