# Finding the sum $\sum_{j=k}^n (-1)^{j+k}\binom{n}{j}\binom{j}{k}$

I am prepping for my mid semester exam, and came across with the following question:

Find the closed form for the sum $\sum_{j=k}^n (-1)^{j+k}\binom{n}{j}\binom{j}{k}$, using the assumption that $k = 0, 1,...n$ and $n$ can be any natural number.

So what I have done is to note the fact that $$\binom{n}{j}\binom{j}{k}= \frac{n!}{j!(n-j)!}\frac{j!}{k!(j-k)!}=\frac{n!}{(n-j)!\ k!\ (j-k)!}$$

Then we can write the summation as $$\sum_{j=k}^n {(-1)^{j+k}\binom{n}{j}\binom{j}{k}}= \sum_{j=k}^n (-1)^{j+k} \frac{n!}{(n-j)!\ k!\ (j-k)!} = \frac{n!}{k!} \sum_{j=k}^n (-1)^{j+k} \frac{1}{(n-j)!\ (j-k)!}$$

I tried to let $m=j-k$: $$\frac{n!}{k!} \sum_{m=0}^{n-k} (-1)^{m+2k} \frac{1}{(n-m-k)!\ m!}=\frac{n!}{k!} \sum_{m=0}^{n-k} (-1)^{m} \frac{1}{(n-m-k)!\ m!}$$

But I am not sure what to proceed next. Any help would be highly appreciated!

• The generating function proof that this sum is $1$ when $k=n$ and $0$ otherwise is really nice; the sum is the coefficient of $x^k$ in the double binomial expansion of $((x+1)-1)^n$! May 21, 2016 at 22:21

Note that

$$\frac{1}{(n-m-k)!\ m!}=\frac{1}{(n-k)!}\cdot \frac{(n-k)!}{(n-m-k)!\ m!}=\frac{1}{(n-k)!}\binom{n-k}{m}$$ Then, you'll have $$\frac{n!}{k!\ (n-k)!}\sum_{m=0}^{n-k}(-1)^m\cdot 1^{n-k-m}\cdot\binom{n-k}{m}$$

• Oh right! So that's essentially 0 by the binomial theorem? Mar 12, 2016 at 12:27
• @Joshua: It is $0$ when $k\not=n$. It is $1$ when $k=n$. Mar 12, 2016 at 12:40

Here is a cleaner way to solve it, without mucking around with factorials.

It's useful to know the "trinomial revision" identity, $$\binom{x}{n}\binom{n}{m} = \binom{x}{m}\binom{x-m}{n-m},$$ which holds for all reals $x$ and integers $m,n$. The combinatorial interpretation (under a condition that certain values be nonnegative integers) is that these are two different expressions for the number of ways to distribute $x$ items among three boxes of sizes $m,\; n-m,$ and $x-n$. This can be called the trinomial coefficient $$\binom{a+b+c}{a,\;b,\;c}= \frac{(a+b+c)!}{a!b!c!}.$$

Now we can begin. We assume $k$ and $n$ are nonnegative integers with $k \leqslant n$. Notice that after trinomial revision, the index variable $j$ appears in only one of the binomial coefficients.

\begin{align*} \sum_{j=k}^n (-1)^{j+k}\binom{n}{j}\binom{j}{k} &= \binom{n}{k} \sum_{k \leqslant j \leqslant n} (-1)^{j+k}\binom{n-k}{j-k} \\ &= \binom{n}{k}\sum_{k-k \leqslant j-k\leqslant n-k}(-1)^{j-k}(-1)^{2k}\binom{n-k}{j-k} \\ &= \binom{n}{k} \sum_{0 \leqslant \ell \leqslant n-k} (-1)^\ell \binom{n-k}{\ell} \\ &= \binom{n}{k} (1+ (-1))^{n-k} \\ &= \delta_{nk}. \end{align*}

The second to last line is an application of the binomial theorem. Note that $0^0 = 1$ by convention.

The computational argument is easier and quicker, but for the record there is also a combinatorial argument.

As usual let $[n]=\{1,\ldots,n\}$; we’ll count the $k$-element subsets of $[n]$ that contain every element of $[n]$ in two ways.

First, it’s clear that there is such a set if and only if $k=n$, and in that case there is exactly one, $[n]$ itself.

On the other hand, for each $i\in[n]$ let $\mathscr{A}_i$ be the family of $k$-element subsets of $[n]$ that do not contain $i$. If $I$ is any non-empty subset of $[n]$, there are clearly $\binom{n-|I|}k$ $k$-element subsets of $[n]\setminus I$, i.e.,

$$\left|\bigcap_{i\in I}\mathscr{A}_i\right|=\binom{n-|I|}k\;.$$

It follows from the inclusion-exclusion principle that

\begin{align*} \left|\bigcup_{i\in[n]}\mathscr{A}_i\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{i\in I}\mathscr{A}_i\right|\\ &=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\binom{n-|I|}k\\ &=\sum_{j=1}^n(-1)^{j+1}\binom{n}j\binom{n-j}k\;, \end{align*}

since $[n]$ has $\binom{n}j$ subsets $I$ of cardinality $j$. Now $\bigcup_{i\in[n]}\mathscr{A}_i$ is the collection of $k$-element subsets of $[n]$ that do not contain every element of $[n]$, so $[n]$ has

\begin{align*} \binom{n}k-\left|\bigcup_{i\in[n]}\mathscr{A}_i\right|&=\binom{n}k-\sum_{j=1}^n(-1)^{j+1}\binom{n}j\binom{n-j}k\\ &=\binom{n}k+\sum_{j=1}^n(-1)^j\binom{n}j\binom{n-j}k\\ &=\sum_{j=0}^n(-1)^j\binom{n}j\binom{n-j}k\\ &=\sum_{j=0}^n(-1)^j\binom{n}{n-j}\binom{n-j}k\\ &\overset{(1)}=\sum_{j=0}^n(-1)^{n-j}\binom{n}j\binom{j}k\\ &\overset{(2)}=(-1)^{n+k}\sum_{j=0}^n(-1)^{j+k}\binom{n}j\binom{j}k\\ &=(-1)^{n+k}\sum_{j=k}^n(-1)^{j+k}\binom{n}j\binom{j}k\;. \end{align*}

$k$-element subsets that do contain every element of $[n]$. (In step $(1)$ I replaced $n-j$ with $j$ everywhere, in step $(2)$ I used the fact that $(-1)^{-r}=(-1)^r$ for any integer $r$, and the $k$ terms that I threw away in the last step were all $0$ anyway.) Thus,

$$(-1)^{n+k}\sum_{j=k}^n(-1)^{j+k}\binom{n}j\binom{j}k=\begin{cases} 1,&\text{if }k=n\\ 0,&\text{otherwise}\;, \end{cases}$$

and since $(-1)^{n+k}=1$ when $k=n$, we have

$$\sum_{j=k}^n(-1)^{j+k}\binom{n}j\binom{j}k=\begin{cases} 1,&\text{if }k=n\\ 0,&\text{otherwise}\;. \end{cases}$$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\, #2 \,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ When $\ds{k > 0}$, $\ds{{j \choose k} = 0}$ when $0 \leq j < k$ and the sum over $\ds{j}$ can be extended to $\ds{j = 0,1,2,\ldots,n}$. When $\ds{k = 0}$, the whole sum already 'start' at $\ds{j = 0}$. Then,

\begin{align} \color{#f00}{\sum_{j = k}^{n}\pars{-1}^{\,j + k}{n \choose j}{j \choose k}} & = \pars{-1}^{\,k}\sum_{j = 0}^{n}\pars{-1}^{\,j}{n \choose j}\ \overbrace{% \oint_{\verts{z} = 1}{\pars{1 + z}^{j} \over z^{k + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ {j \choose k}}} \\[3mm] & = \pars{-1}^{\,k}\oint_{\verts{z} = 1}{1 \over z^{k + 1}} \sum_{j = 0}^{n}{n \choose j}\pars{-1 - z}^{\,j}\,{\dd z \over 2\pi\ic} \\[3mm] & = \pars{-1}^{k}\oint_{\verts{z} = 1}{1 \over z^{k + 1}} \bracks{1 + \pars{-1 - z}}^{\,n}\,{\dd z \over 2\pi\ic} = \pars{-1}^{k + n}\ \overbrace{\oint_{\verts{z} = 1}{1 \over z^{k + 1 - n}} \,{\dd z \over 2\pi\ic}}^{\ds{\delta_{kn}}} \\[3mm] & = \color{#f00}{% \delta_{kn} = \left\lbrace\begin{array}{lcrcl} 0 & \mbox{if} & k & \not= & n \\ 1 & \mbox{if} & k & = & n \end{array}\right.} \end{align}

Let the integer $k$ be fixed and let $\mathcal C_k$ denote the linear operator acting upon polynomials in $x$ that returns the value of the coefficient of $x^k$. Then evidently, \begin{align} \sum_{j=k}^n {(-1)^{j+k}\binom{n}{j}\binom{j}{k}} &= \sum_{j=k}^n {(-1)^{j}\binom{n}{j}\cdot \mathcal C_k \cdot (1-x)^j} \\ &= \mathcal C_k\cdot\sum_{j=0}^n {(-1)^{j}\cdot (1-x)^j\binom{n}{j}}\\ &= \mathcal C_k\cdot(1-(1-x))^n \\ &= \mathcal C_k\cdot x^n \\ &= \delta_{kn} \end{align}where $\delta_{kn}$ is the Kronecker delta.

Q.E.D.