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

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}$$

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}$$