Transformations on $ \sum_{k} {r \choose k}{k \choose n} (-1)^{r-k} = {0 \choose n-r} = \delta_{nr} $

Question

This equality holds

$$ \sum_{k} {r \choose k}{k \choose n} (-1)^{r-k} = {0 \choose n-r} = \delta_{nr} , $$ integer n, integer r $\geq$ 0, and $\delta$ is the Kronecker delta.

However, I'm confused how did Knuth change it into the following:

When r and m are nonnegative intergers we have: $$ \sum_{k} {r \choose k} (-1)^{r-k} (c_{0} {k \choose 0} + c_{1} {k \choose 1} + c_{2} {k \choose 2} + ... + c_{m} {k \choose m} ) = c_{r}, $$

since the other terms vanish after summation.

I'm also confused how did he derive the next statement:

$$ \sum_{k} {r \choose k} (-1)^{r-k} (b_{0} + b_{1}k + ... + b_{r}k^{r} ) = r! b_{r}, $$

interger $\geq$ 0, where $b_{0} + ... + b_{r}k^{r}$ represents any polynomial whatever of degree r or less.

-----End Question----

Citation: 'TAOCP 3rd Ed Vol.1' page 64

My research identifies the following 3 formulas, but I can't see a direct application of them to the above. $$ \sum_{k=0}^{n}{r+k \choose k} = {r \choose 0} + {r+1 \choose 1} + ... + {r+n \choose n} = {r+n+1 \choose n}, $$ integer n $\geq$ 0.

$$ \sum_{k=0}^{n}{k \choose m} = {0 \choose m} + {1 \choose m} + ... + {n \choose m} = {n+1 \choose m+1}, $$ integer m$\geq$0, integer n$\geq$0.

$$ \sum_{k\leq n}{r \choose k}(-1)^{k} = {r \choose 0} - {r \choose 1} + ... + (-1)^{n}{r \choose n} = (-1)^{n}{r-1 \choose n}, $$ integer n.

Answer 1

We already know for non-negative integers $r,n$ the validity of \begin{align*} \sum_{k=0}^r\binom{r}{k}\binom{k}{n}(-1)^{r-k}=\delta_{nr}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^r}&\color{blue}{\binom{r}{k}(-1)^{r-k}\left(c_0\binom{k}{0}+c_1\binom{k}{1}+\cdots+c_m\binom{k}{m}\right)}\\ &=\sum_{k=0}^r\binom{r}{k}(-1)^{r-k}\sum_{q=0}^mc_q\binom{k}{q}\tag{2}\\ &=\sum_{q=0}^mc_q\sum_{k=0}^r\binom{r}{k}\binom{k}{q}(-1)^{r-k}\tag{3}\\ &=\sum_{q=0}^mc_q\delta_{qr}\tag{4}\\ &\,\,\color{blue}{=c_r}\tag{5} \end{align*} and the claim follows.

Comment:

• In (2) we use the sigma-notation to write the expression somewhat more compactly.

• In (3) we reorder to sum and prepare this way the application of (1)

• In (4) we apply (1)

• In (5) we note that $c_r$ only might give a non-zero contribution.

In order to answer the second question we recall that $\binom{k}{q}=\frac{k(k-1)\cdots(k-q+1)}{q!}$ can be seen as polynomial in $k$ of degree $q$ and \begin{align*} \left\{1,k,\ldots,k^r\right\}\qquad\text{and}\qquad \left\{\binom{k}{0},\binom{k}{1},\ldots,\binom{k}{r}\right\}\tag{6} \end{align*} are bases of an $r$-dimensional vector spcace of polynomials in $k$ of degree $\leq r$ together with addition and scalar multiplication.

We obtain \begin{align*} &\sum_{k=0}^r\binom{r}{k}(-1)^{r-k}\left(b_0+b_1k+\cdots b_rk^r\right)\tag{7}\\ &\quad=\sum_{k=0}^r\binom{r}{k}(-1)^{r-k}\left(c_0\binom{k}{0}+c_1\binom{k}{2}+\cdots+c_r\binom{k}{r}\right)\tag{8}\\ &\quad=c_r\tag{9} \end{align*}

Comment:

• In (8) we represent the polynomial using binomial coefficients according to (7).

• In (9) we apply the binomial identity (5).

Conclusion: We consider in (7) the expression $b_0+b_1k+\cdots b_rk^r$ as polynomial in $k$ of degree $r$ with $b_r$ the coefficient of $k^r$. From (8) we obtain since $$c_r\binom{k}{r}=\frac{c_r}{r!}k(k-1)\cdots(k-r+1)$$ is a polynomial in $k$ of degree $r$ and all other binomial coefficients have degree less than $r$ the relation \begin{align*} \color{blue}{c_r=r!b_r} \end{align*} and the claim follows.

Answer 2

Note the Identity that $${r \choose k}{k \choose n}= {r \choose n} {r-n \choose r-k}$$ Then $$S= \sum_{k=n}^{r} (-1)^{r-k}{r \choose k}{k \choose n} ={r \choose n} \sum_{k=n}^{r} (-1)^{r-k}{r-n \choose r-k}$$ Let $r-k=p$, then $$S={r \choose n}\sum_{p=0}^{n-r} (-1)^{p} {r-n \choose p}= {r \choose n}(1-1)^{r-n}=0 ~if~ r\ne n; 1 ~if~r=n.$$ So Eventually $S=\delta_{rn}$