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

Question

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 ?

Answer 1

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.

Answer 2

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