Transformations on $ \sum_{k} {r \choose k}{k \choose n} (-1)^{r-k} = {0 \choose n-r} = \delta_{nr} $ 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.
 A: 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.
A: 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}$
