Show $\sum_{k=0}^{n} \binom{n}{k} \binom{r+k}{n} =\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} \binom{r+k}{k} 2^k$?

Question

Title is not long enough, this has 2 parts of equality. Show $$\sum_{k=0}^{n} \binom{n}{k} \binom{r+k}{n} = \sum_{k=0}^{n} \binom{n}{k} \binom{r}{k} 2^k = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} \binom{r+k}{k} 2^k$$

So, using

$$ \binom{r+k}{n}=\sum_{l=0}^{n}\binom{r}{l}\binom{k}{n-l} $$

Then

$$ \sum_{k=0}^{n} \binom{n}{k} \binom{r+k}{n}=\sum_{k=0}^{n}\binom{n}{k} \sum_{l=0}^{n}\binom{r}{l}\binom{k}{n-l} $$

It looks like using $$ \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r} $$

more or less solves the 1st equality, by using $u=n-k$

$$ \binom{n}{k}\binom{r}{l}\binom{k}{n-l}=\binom{n}{u}\binom{r}{u}\binom{n-u}{l-u} $$

then (for $s=l-u$)

$$ \sum_{u=0}^{n}\binom{n}{u}\binom{r}{u}\sum_{l=0}^{n}\binom{n-u}{l-u}=\sum_{u=0}^{n}\binom{n}{u}\binom{r}{u}\sum_{s=0}^{n-u}\binom{n-u}{s}=\sum_{u=0}^{n}\binom{n}{u}\binom{r}{u}2^{n-u} $$

which by $\binom{n}{k}=\binom{n}{n-k}$ and $n-u=k$ equals

$$ \sum_{k=0}^{n}\binom{n}{k}\binom{r}{n-k}2^{k} $$

Not sure what property turns $\binom{r}{n-k}$ into $\binom{r}{k}$ here?

2nd equality maybe uses

$$ \sum_{s=k}^{n}(-1)^{s-k}\binom{s}{k}\binom{n}{s}=\delta_{k,n} $$

and i'm not sure how to get that one?

Answer 1

Hint: For the first one: You are right, just use it.

$$\sum _{k=0}^n\binom{n}{k}\binom{r+k}{n}=\sum _{k=0}^n\binom{n}{k}\sum _{l=0}^n\binom{r}{l}\binom{k}{n-l}=\sum _{k=0}^n\sum _{l=0}^n\binom{r}{l}\left (\binom{n}{k}\binom{k}{n-l}\right )$$ $$=\sum _{k=0}^n\sum _{l=0}^n\binom{r}{l}\left (\binom{n}{n-l}\binom{l}{k-n+l}\right )=\sum _{l=0}^n\binom{r}{l}\binom{n}{n-l}\sum _{k=0}^n\binom{l}{k-n+l}$$ using $\binom{l}{k-n+l}=\binom{l}{n-k}$ and $k'=n-k,$ we get $$\sum _{l=0}^n\binom{r}{l}\binom{n}{n-l}\sum _{k=0}^n\binom{l}{k-n+l}=\sum _{l=0}^n\binom{r}{l}\binom{n}{l}\sum _{k=0}^n\binom{l}{n-k}=\sum _{l=0}^n\binom{r}{l}\binom{n}{l}\sum _{k'=0}^n\binom{l}{k'}=\sum _{l=0}^n\binom{r}{l}\binom{n}{l}2^l$$

For the second one:

Start on the right hand side and do exactly as in the first one with $\binom{r+k}{r}.$ You will get something like:
$$\sum _{k=0}^n\sum _{l=0}^r\binom{n}{k}\binom{r}{l}\binom{k}{r-l}(-1)^{n-k}2^k$$ Exchange the orther of summation, use again the property of $\binom{a}{b}\binom{b}{c}.$ Use the binomial theorem using the $2$ and the $-1$. Let me know if you need more explanation.

Answer 2

For this kind of problems, one usually tries generating functions.

Generating function for the left hand side: \begin{eqnarray} \sum_{n \geq 0}\left(\sum_{0\leq k\leq n} \binom n k \binom{r+k}n\right) T^n &=& \sum_{k \geq 0}\sum_{n \geq k} \binom{r + k}k\binom r{n - k} T^n\\ &=& \sum_{k\geq 0}\binom{r + k}k T^k\sum_{n \geq 0}\binom r n T^n\\ &=& \frac{(1+T)^r}{(1-T)^{r+1}}, \end{eqnarray} where in the first line we used the identity $\binom n k \binom {r + k} n = \binom {r + k} k \binom r {n - k}$.

Generating function for the right hand side: \begin{eqnarray} \sum_{n \geq 0}\left(\sum_{0\leq k\leq n}(-1)^{n - k}\binom n k \binom {r+k} k 2^k\right)T^n &=& \sum_{k \geq 0}\binom{r + k}k2^k\sum_{n \geq k}(-1)^{n - k}\binom n k T^n\\ &=& \sum_{k \geq 0}\binom{r + k}k2^kT^k\sum_{n \geq 0}\binom {n+k} k (-T)^n\\ &=& \sum_{k \geq 0}\binom{r + k}k(2T)^k\frac1{(1+T)^{k + 1}}\\ &=& \frac1{1 + T}\sum_{k \geq 0}\binom{r + k}k\left(\frac{2T}{1+T}\right)^k\\ &=&\frac1{1+T}\cdot\frac1{\left(1 - \frac{2T}{1+T}\right)^{r + 1}}\\ &=& \frac{ (1+T)^r}{(1-T)^{r + 1}}. \end{eqnarray}

Answer 3

We seek to verify that

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

We get for the first sum

$$[z^n] (1+z)^r \sum_{k=0}^n {n\choose k} (1+z)^k = [z^n] (1+z)^r (2+z)^n.$$

The second sum is

$$\sum_{k=0}^n {n\choose k} {r\choose n-k} 2^{n-k} = 2^n [z^n] (1+z)^r \sum_{k=0}^n {n\choose k} z^k 2^{-k} \\ = 2^n [z^n] (1+z)^r (1+z/2)^n = [z^n] (1+z)^r (2+z)^n.$$

We see that the second is the same as the first. The third one gives

$$\sum_{k=0}^n (-1)^{n-k} {n\choose k} {r+k\choose r} 2^k \\ = [z^r] (1+z)^r \sum_{k=0}^n (-1)^{n-k} {n\choose k} 2^k (1+z)^k \\ = [z^r] (1+z)^r (2(1+z)-1)^n = [z^r] (1+z)^r (2z+1)^n \\ = \sum_{k=0}^r {r\choose r-k} {n\choose k} 2^k = \sum_{k=0}^r {r\choose k} {n\choose k} 2^k.$$

Now if $r\lt n$ we may extend the upper range to $n$ because the first binomial coefficient is zero in the added range. If $r\gt n$ we may lower to $n$ as the second binomial coefficient is zero on the removed values. We find

$$\sum_{k=0}^n {r\choose k} {n\choose k} 2^k$$

which shows the second sum is equal to the third and we may conclude.

Answer 4

Here we extend this answer.

---

$$ \begin{align} \sum_{k=0}^n(-1)^{n-k}2^k\binom{n}{k}\binom{r+k}{k} &=\sum_{k=0}^n\sum_{j=0}^n(-1)^n\binom{k}{j}\binom{n}{k}\binom{-r-1}{k}\tag{1a}\\ &=\sum_{j=0}^n\sum_{k=0}^n(-1)^n\binom{n}{j}\binom{n-j}{n-k}\binom{-r-1}{k}\tag{1b}\\ &=\sum_{j=0}^n(-1)^n\binom{n}{j}\binom{n-r-j-1}{n}\tag{1c}\\ &=\sum_{j=0}^n\binom{n}{j}\binom{r+j}{n}\tag{1d} \end{align} $$ Explanation:
$\text{(1a):}$ $(-1)^k\binom{r+k}{k}=\binom{-r-1}{k}\quad$ (negative binomial coefficient)
$\phantom{\text{(1a):}}$ $2^k=\sum\limits_{j=0}^k\binom{k}{j}=\sum\limits_{j=0}^n\binom{k}{j}$ since $\binom{k}{j}=0$ for $j\gt k$
$\text{(1b):}$ $\binom{k}{j}\binom{n}{k}=\binom{n}{j}\binom{n-j}{n-k}\quad$ (expand into ratios of factorials)
$\text{(1c):}$ sum in $k\qquad\qquad\quad$ Vandermonde's Identity
$\text{(1d):}$ $(-1)^n\binom{n-r-j-1}{n}=\binom{r+j}{n}\quad$ (negative binomial coefficient)

---

$$ \begin{align} \sum_{k=0}^n\binom{n}{k}\binom{r+k}{n} &=\sum_{k=0}^n\sum_{j=0}^n\binom{n}{k}\binom{k}{j}\binom{r}{n-j}\tag{2a}\\ &=\sum_{j=0}^n\sum_{k=0}^n\binom{n}{n-j}\binom{n-j}{k-j}\binom{r}{n-j}\tag{2b}\\ &=\sum_{j=0}^n2^{n-j}\binom{n}{n-j}\binom{r}{n-j}\tag{2c}\\ &=\sum_{j=0}^n2^j\binom{n}{j}\binom{r}{j}\tag{2d} \end{align} $$ Explanation:
$\text{(2a):}$ $\binom{r+k}{n}=\sum\limits_{j=0}^n\binom{k}{j}\binom{r}{n-j}\quad$ (Vandermonde's Identity)
$\text{(2b):}$ $\binom{n}{k}\binom{k}{j}=\binom{n}{n-j}\binom{n-j}{k-j}\quad$ (expand into ratios of factorials)
$\text{(2c):}$ $2^{n-j}=\sum\limits_{k=j}^n\binom{n-j}{k-j}=\sum\limits_{k=0}^n\binom{n-j}{k-j}$ since $\binom{n-j}{k-j}=0$ for $k\lt j$
$\text{(2d):}$ substitute $j\mapsto n-j$