Orthogonality for Binomial Coefficients Could somebody explain to me where these two formulas come from as applications of the binomial theorem?
 $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$
for non-negative integers $r\lt n$. And
$$\sum_{k=0}^n {n \choose k}(-1)^kk^n=(-1)^nn!$$
 A: They don’t come from the binomial theorem: they come from the inclusion-exclusion principle. This is easier to see if you multiply them by $(-1)^n$ to get
$$\sum_{k=0}^n\binom{n}k(-1)^{n-k}k^r=\begin{cases}
0,&\text{if }r<n\\
n!,&\text{if }r=n\;.
\end{cases}$$
The left-hand side counts surjections from $[r]=\{1,\ldots,r\}$ to $[n]=\{1,\ldots,n\}$. Of course this is $0$ when $r<n$ and $n!$ when $r=n$.
The left-hand side can be rewritten as follows:
$$\begin{align*}
\sum_{k=0}^n\binom{n}k(-1)^{n-k}k^r&=\sum_{k=0}^n\binom{n}{n-k}(-1)^{n-k}k^r\\
&=\sum_{k=0}^n\binom{n}k(-1)^k(n-k)^r\\
&=n^r-\binom{n}1(n-1)^r+\binom{n}2(n-2)^r-+\ldots\;.
\end{align*}$$
The first term, $n^r$, is the number of functions from $[r]$ to $[n]$. For each $k\in[n]$ there are $(n-1)^r$ functions from $[r]$ to $[n]\setminus\{k\}$, and there are $n$ possible choices for $k$; subtracting $\binom{n}1(n-1)^r$ throws out these non-surjective functions from $[r]$ to $[n]$. However, functions whose ranges miss (at least) two elements of $[n]$ get thrown out (at least) twice and have to be added back in, giving
$$n^r-\binom{n}1(n-1)^r+\binom{n}2(n-2)^r\;.$$
This is now an overcount, since functions whose ranges miss (at least) three elements of $[n]$ have now been counted once, removed three times, and recounted three times: on net they’ve been counted once and need to be thrown away again.
The inclusion-exclusion principle ensures that the full summation correctly accounts for everything and therefore really does give the number of surjections from $[r]$ to $[n]$.
A: A Proof Using Binomial Theorem:
We prove by induction.
The binomial theorem says $$(x-1)^n = \sum_{k}{n\choose k}(-1)^{n-k} x^k.$$ Setting $x=1$ gives a proof for $r=0$. Suppose the statement is true for $<r$.
Suppose $r\leq n$. Take $r$th derivative of the formula above, we get $$\begin{eqnarray}n(n-1)\ldots (n-r+1)(x-1)^{n-r} &=& \sum_{k}{n\choose k}(-1)^{n-k}k(k-1)\ldots (k-r+1)x^{k-r}\\ &=& \sum_{k}{n\choose k}(-1)^{n-k}P(k)x^{k-r},\end{eqnarray}$$ where $P(k)=k^r+$ lower terms. Set $x=1$. By the induction hypothesis, the terms evaluated by the lower terms sum to $0$, and so RHS $=\sum_k{n\choose k}(-1)^{n-k}k^r$. If $r < n$, then LHS $=0$. If $r=n$, then LHS $=n!$. This completes the proof.
Remark: A slick way to prove it is to count the number of surjections from $[r]$ to $[n]$. By the inclusion-exclusion principle, we get the number of surjections equal to $$\sum_k {n\choose k}(-1)^{n-k}k^r.$$ However, when $r<n$, there are no surjections, whereas, when $r=n$, there are $n!$ many.
A: Consider $\binom{k}{j}$ as a degree $k$ polynomial (combinatorial polynomial) in $k$:
$$
\binom{k}{j}=\frac{k(k-1)(k-2)\cdots(k-j+1)}{j!}\tag{1}
$$
It is not to difficult to see that we can write any polynomial of degree $m$ as sum of combinatorial polynomials of degree $m$ or less. In particular, we have
$$
\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}
k^m=\sum_{j=0}^mj!\stirtwo{m}{j}\binom{k}{j}\tag{2}
$$
where $\stirtwo{m}{j}$ is a Stirling Number of the Second Kind.
Since $k^m$ can be written as a sum of combinatorial polynomials of degree $m$ or less,
$$
n\gt m\implies\stirtwo{m}{n}=0\tag{3}
$$
Furthermore, since the coefficient of $k^m$ in $m!\binom{k}{m}$ is $1$,
$$
\stirtwo{m}{m}=1\tag{4}
$$
Using $(2)$ in your sum yields
$$
\begin{align}
\sum_{k=0}^n\binom{n}{k}(-1)^kk^m
&=\sum_{k=0}^n\binom{n}{k}(-1)^k\sum_{j=0}^mj!\stirtwo{m}{j}\binom{k}{j}\\
&=\sum_{j=0}^mj!\stirtwo{m}{j}\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{k}{j}\\
&=\sum_{j=0}^mj!\stirtwo{m}{j}\sum_{k=0}^n(-1)^k\binom{n}{j}\binom{n-j}{k-j}\\
&=\sum_{j=0}^mj!\stirtwo{m}{j}\binom{n}{j}(-1)^j(1-1)^{n-j}\\
&=(-1)^nn!\stirtwo{m}{n}\tag{5}
\end{align}
$$
Equtions $(3)$, $(4)$, and $(5)$ give the results sought.
A: Rather than try to interpret this as a direct application of the binomial formula, I think it is better to recognise summations of the form $\sum_k(-1)^k\binom nkf(x+k)$ or $\sum_k(-1)^k\binom nkf(x-k)$ as coming from repeated finite differences of $f$. In your example it is $f(x)=x^r$ for fixed $0\leq r\leq n$, taken eventually at $x=0$. However this also occurs in different guises in this question and another and one similar to this one (and maybe in others I failed to find).
On the space of functions defined at integer (or non-negative integer) arguments, define the forward difference operator $\Delta$ by
$$
  \Delta(f)=\bigl(x\mapsto f(x+1)-f(x)\bigr) \qquad \text{for any $f:\Bbb Z\to\Bbb R$}
$$
Then one since has $\Delta=S-I$ where $S$ is the shift operator $f\mapsto\bigl(x\mapsto f(x+1)\bigr)$ and $I$ is the identity $f\mapsto \bigl(x\mapsto f(x)\bigr)=f$; since these operators commute one can apply the binomial formula to get
$$
   \Delta^n(f) = \sum_{k=0}^n\binom nk(-I)^{n-k}S^k(f)
 = \left(x\mapsto \sum_{k=0}^n(-1)^{n-k}\binom nkf(x+k) \right) .
$$
For the purpose of recognition it is useful to have a variant where the exponent of $-1$ matches the lower index in the binomial coefficient:
$$
  \sum_{k=0}^n(-1)^k\binom nkf(x+k) = (-1)^n\Delta^n(f)(x)
$$
Now the point that makes this easy to compute in certain situations, like that of the question, is that $\Delta$ lowers the degree of polynomial functions, killing constant ones, and multiplies the leading coefficient by the degree just like differentiation does. This means that with $f:x\mapsto x^r$ and $0\leq r\leq n$ one has $\Delta^n(f)=(x\mapsto 0)$ when $r<n$, while $\Delta^n(f)=(x\mapsto n!)$ when $r=n$. This gives your two equations.
