To prove: $\sum_{r=0}^{n}{{(-1)^r}{n\choose r}(n-r)^k}=\begin{cases}0&;& k\lt n\\n!&;& k=n\end{cases}$

Question

To prove: $$\sum_{r=0}^{n}{{(-1)^r}{n\choose r}(n-r)^k}=\begin{cases}0&;& k\lt n\\n!&;& k=n\end{cases}$$

My Attempt:

LHS$={n\choose0}n^k-{n\choose1}(n-1)^k+{n\choose2}(n-2)^k-...+(-1)^{n-1}{n\choose{n-1}}(n-(n-1))^k+(-1)^n{n\choose n}(n-n)^k$

$={n\choose n}n^k-{n\choose{n-1}}(n-1)^k+{n\choose{n-2}}(n-2)^k-...+(-1)^{n-1}{n\choose1}(n-(n-1))^k+(-1)^n{n\choose 0}(n-n)^k$

=$\sum_{r=0}^{n}{{(-1)^{n-r}}{n\choose r}r^k}$

$=(-1)^n\sum_{r=0}^n{(-1)^r{n\choose r}r^k}$

If I add this to the given expression, I get $(-1)^r{n\choose r}$ as common.

Not sure what to do with $(n-r)^k+(-1)^n r^k$

Answer 1

The expression $$\sum_{r = 0}^{n} (-1)^r\binom{n}{r}(n - r)^k$$ counts the number of surjective functions $f: \{1, 2, 3, \ldots, k\} \to \{1, 2, 3, \ldots, n\}$. To see this, observe that there are $n^k$ functions $f: \{1, 2, 3, \ldots, k\} \to \{1, 2, 3, \ldots, n\}$ since there are $n$ possible images in the codomain for each of the $k$ elements in the domain. To ensure that the function is surjective, we must exclude those functions that exclude one or more elements of the codomain from the range. There are $\binom{n}{r}$ ways to exclude $r$ elements of the codomain from the range and $(n - r)^k$ ways to map the $k$ elements of the domain to the remaining $n - r$ elements of the codomain. Applying the Inclusion-Exclusion Principle yields the expression above.

If $k < n$, then at most $k < n$ elements can be in the range, so there are no surjective functions $f: \{1, 2, 3, \ldots, k\} \to \{1, 2, 3, \ldots, n\}$. If $k = n$, then a surjective function $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, n\}$ is a permutation of the set $\{1, 2, 3, \ldots, n\}$, of which there are $n!$. Thus, $$\sum_{r = 0}^{n} (-1)^r\binom{n}{r}(n - r)^k = \begin{cases} 0 & \text{if $k < n$}\\ n! & \text{if $k = n$} \end{cases}$$

Answer 2

Alternative derivation via finite differences.

Consider the discrete derivative operator on $\Bbb R[X]$ defined by \begin{align}\Delta\colon\Bbb R[X]&\longrightarrow\Bbb R[X]\\P(X)&\longmapsto P(X)-P(X-1).\end{align}

• On the one hand, it is easy to see that $\Delta$ lowers the degree. More precisely, if $P=a_kX^k+a_{k-1}X^{k-1}+\cdots+a_0$ with $k\ge1$, then $\Delta P=ka_kX^{k-1}+\cdots$, whereas if $\deg P\le0$, then $\Delta P=0$. By induction, it follows that $\Delta^nP=0$ if $\deg P<n$, and $\Delta^nP=n!a_n$ if $\deg P=n$ and $P=a_nX^n+\cdots$.
• On the other hand, $\Delta$ can be written $\Delta=I-D$ where $I$ is the identity on $\Bbb R[X]$ and $D\colon\Bbb R[X]\to\Bbb R[X]$ maps $P(X)$ to $P(X-1)$, and because $I$ and $D$ commute, the Binomial formula yields $$\Delta^nP=\sum_{r=0}^n\binom nr(-1)^rD^rP=\sum_{r=0}^n(-1)^r\binom nrP(X-r).$$
• As a result, for all $P\in\Bbb R_n[X]$, $$\sum_{r=0}^n(-1)^r\binom nrP(X-r)=\begin{cases}n!a_n,&\text{if $\deg P=n$ and $P=a_nX^n+\cdots$},\\0,&\text{if $\deg P<n$}.\end{cases}$$

---

Now, take $P=X^k$ and evaluate at $X=n$.