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!
 A: 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}$$
A: 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.
A: 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}$$
A: $\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}
A: 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.
