For $1\leq j\leq i\leq n$, does $\sum_{k=j}^i (-1)^{i-k} \binom{n-k}{i-k} \binom{n-j}{k-j}$ equal $\delta_{i,j}$? For $1\leq j\leq i\leq n$, does $\sum_{k=j}^i (-1)^{i-k} \binom{n-k}{i-k} \binom{n-j}{k-j}$ equal $\delta_{i,j}$ ?
If so, how best to prove it ?
 A: 
We obtain
  \begin{align*}
\sum_{k=j}^i&(-1)^{i-k}\binom{n-k}{i-k}\binom{n-j}{k-j}\\
&=\sum_{k=j}^i(-1)^{i-k}\frac{(n-k)!}{(i-k)!(n-i)!}
\cdot\frac{(n-j)!}{(k-j)!(n-k)!}\tag{1}\\
&=\sum_{k=j}^i(-1)^{i-k}\frac{(i-j)!}{(i-k)!(k-j)!}
\cdot\frac{(n-j)!}{(n-i)!(i-j)!}\tag{2}\\
&=\binom{n-j}{n-i}\sum_{k=j}^i(-1)^{i-k}\binom{i-j}{k-j}\tag{3}\\
&=\binom{n-j}{n-i}\sum_{k=0}^{i-j}(-1)^{i-j+k}\binom{i-j}{k}\tag{4}\\
&=\binom{n-j}{n-i}(-1)^{i-j}(1-1)^{i-j}\tag{5}\\
&=\delta_{i,j}
\end{align*}

Comment:


*

*In (1) we use $\binom{p}{q}=\frac{p!}{q!(p-q)!}$.

*In (2) we cancel $(n-k)!$ expand with $(i-j)!$ and do some rearrangements.

*In (3) we can factor out $\binom{n-j}{n-i}$ which is independent from the index variable $k$.

*In (4) we shift the index $k$ to start the series from $k=0$.

*In (5) we use the binomial theorem with $(1-1)^{i-j}$.

Here is a different technique based upon generating functions. It is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$.
This way we can write e.g. 
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}
We obtain
  \begin{align*}
\sum_{k=j}^i&(-1)^{i-k}\binom{n-k}{i-k}\binom{n-j}{k-j}\\
&=\sum_{k= j}^\infty(-1)^{i-k}[z^{i-k}](1+z)^{n-k}[u^{k-j}](1+u)^{n-j}\tag{6}\\
&=(-1)^i[z^i](1+z)^n\sum_{k= j}^\infty\left(-\frac{z}{1+z}\right)^k
[u^k]u^j(1+u)^{n-j}\tag{7}\\
&=(-1)^i[z^i](1+z)^n\sum_{k= 0}^\infty\left(-\frac{z}{1+z}\right)^{k+j}
[u^k](1+u)^{n-j}\tag{8}\\
&=(-1)^i[z^{i}](1+z)^n\left(-\frac{z}{1+z}\right)^{j}\left(1-\frac{z}{1+z}\right)^{n-j}\tag{9}\\
&=(-1)^{i-j}[z^{i-j}]1\tag{10}\\
&=\delta_{i,j}
\end{align*}

Comment:


*

*In (6) we apply the coefficient of operator twice and we set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

*In (7) we use the linearity of the coefficient of operator, do some rearrangements and apply the rule $$[z^{i-k}]A(z)=[z^i]z^kA(z)$$

*In (8) we shift the index $j$ to start the series from $j=0$.

*In (9) we factor out $\left(-\frac{z}{1+z}\right)^j$ and apply the substitution rule of the coefficient of operator with $u:=-\frac{z}{1+z}$
\begin{align*}
A(z)=\sum_{k=0}^\infty a_kz^k=\sum_{k=0}^\infty z^k[u^k]A(u)
\end{align*}

*In (10) we can make essential simplifications.
A: A combinatorial proof isn’t too hard. Let $r=n-j$ and $s=i-j$. Then
$$\begin{align*}
\sum_{k=j}^i(-1)^{i-k}\binom{n-k}{i-k}\binom{n-j}{k-j}&=\sum_{k=0}^{i-j}(-1)^{i-j-k}\binom{n-j-k}{i-j-k}\binom{n-j}k\\
&=(-1)^s\sum_{k=0}^s(-1)^k\binom{r-k}{s-k}\binom{r}k\;.
\end{align*}$$
Suppose that we want to count the $s$-element subsets of $[r]$ that are empty; clearly this is $1$ if $s=0$ and $0$ otherwise. On the other hand, we can use an inclusion-exclusion argument. For $k\in[r]$ let $A_k$ be the family of $s$-element subsets of $[r]$ that contain $k$. If $\varnothing\ne I\subseteq[r]$, then
$$\left|\,\bigcap_{k\in I}A_k\,\right|=\binom{r-|I|}{s-|I|}\;,$$
so
$$\left|\,\bigcup_{k=1}^rA_k\,\right|=\sum_{\varnothing\ne I\subseteq[r]}(-1)^{|I|-1}\left|\,\bigcap_{k\in I}A_k\,\right|=\sum_{k=1}^r(-1)^{k-1}\binom{r}k\binom{r-k}{s-k}\;.$$
This is the number of $s$-element subsets of $[r]$ that contain at least one member of $[r]$, i.e., the number of non-empty $s$-element subsets of $[r]$, so the number of empty $s$-element subsets of $[r]$ is
$$\begin{align*}
\binom{r}s-\sum_{k=1}^r(-1)^{k-1}\binom{r}k\binom{r-k}{s-k}&=\binom{r}s+\sum_{k=1}^r(-1)^k\binom{r}k\binom{r-k}{s-k}\\
&=\sum_{k=0}^r(-1)^k\binom{r}k\binom{r-k}{s-k}\;.
\end{align*}$$
Thus,
$$\sum_{k=0}^r(-1)^k\binom{r}k\binom{r-k}{s-k}=\begin{cases}
1,&\text{if }s=0\\
0,&\text{otherwise}\;,
\end{cases}$$
and multiplying this by $(-1)^s$ doesn’t change anything, since $(-1)^0=1$.
