# 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!$$

• Sorry, I was just confused by $0^0$. – Math.StackExchange Mar 23 '15 at 22:46
• Is the index of $k$ meant to start from $0$ or $1$ - the $k=0$ term is always zero? – MCT Mar 23 '15 at 22:47
• @Soke: At $0$: it matters when $n=1$ and $r=0$. – Brian M. Scott Mar 23 '15 at 22:49
• @BrianM.Scott Oh, didn't consider that $r$ could be zero. Got it – MCT Mar 23 '15 at 22:50
• Hint: observe that the LHS is just $(xD)^r(1-x)^n|_{x=1}$, so this is $0$ for non-negative integers r<n. So, it suffices to show $(xD)^n(1-x)^n|_{x=1}=(-1)^nn!$ – Math.StackExchange Mar 23 '15 at 22:54

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]$.

• nice answer. good one. – GA316 Mar 24 '15 at 0:14
• This problem shows up quite frequently here, for example at this MSE link. – Marko Riedel Mar 24 '15 at 0:31
• @Marko: Thanks. I thought that it was familiar, but I couldn’t quickly find an earlier example. – Brian M. Scott Mar 24 '15 at 0:35

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.

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.

• (+1) You don’t even need the combinatorial polynomials: $(2)$ has a fairly easy combinatorial proof if ${m\brace j}$ is simply defined to be the number of partitions of $[m]$ into $j$ parts, and this makes the last step (of evaluating ${m\brace n}$) even easier. – Brian M. Scott Mar 24 '15 at 0:42
• @BrianM.Scott: This is where our views of what is derived and what is defined differ. I consider $(2)$ as the definition of the Stirling Numbers of the Second Kind, and therefore, it needs no proof. Using the combinatorial definition of the Stirling Numbers, you are correct. Thanks for mentioning the alternate perspective. – robjohn Mar 24 '15 at 0:48

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.