3 binomial identities that I could not find a closed form for them

Question

What is the closed form of the following binomial identities:

$$\sum_{k=0}^{m}\binom{n}{k}\binom{r}{k}k\tag{I}$$

I'm not sure if we can find a closed form using Vandermonde's identity.

$$\sum_{k=0}^{n}\binom{m-k-1}{m-n-1}\left(k \right)\tag{II}$$

If I knew a closed form for $\sum_{k=0}^{n}\binom{k}{n}k$ then I would handle that, but unfortunately I don't know.

$$\sum_{k=0}^{n}\binom{n+k}{k}\binom{n}{k}\frac{\left(-1 \right)^k}{k+1}\tag{III}$$

I tried some binomial transformation, but that was not helpful.

---

Source : Concrete mathematics (second edition)

Answer 1

$\text{(I)}$

Defining upper and lower limit for the sum would make it difficult, since we need to consider several conditions , so I prefer not to do that.

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

Or:

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

Hence: $$\bbox[5px,border:2px solid #00A000]{\sum_{k}^{}\binom{n}{k}\binom{r}{k}k=n\binom{n+r-1}{n}=r\binom{n+r-1}{r}}$$

---

$\text{(II)}$

I use the following identity:

$$\sum_{k=n}^{m}\binom{k}{n}k=\sum_{k=0}^{m}\binom{k}{n}k$$$$=\sum_{k=0}^{m}\binom{k-1}{n-1}k+\sum_{k=0}^{m}\binom{k-1}{n}k=n\sum_{\color{red}{k=0}}^{m}\binom{k}{n}+\left(n+1 \right)\sum_{\color{blue}{k=0}}^{m}\binom{k}{n+1}$$$$=n\sum_{\color{red}{k=n}}^{m}\binom{k}{n}+\left(n+1 \right)\sum_{\color{blue}{k=n+1}}^{m}\binom{k}{n+1}$$$$=n\binom{m+1}{n+1}+\left(n+1 \right)\binom{m+1}{n+2}\;\;\;\;\;\;\;\;\;\;\large\color{red}{*}$$

$$\sum_{k=0}^{n}\binom{m-k-1}{m-n-1}\left(k \right)$$

Setting $m-k-1 \mapsto k$ we have:

$$=\sum_{k=m-n-1}^{m-1}\binom{k}{m-n-1}\left(m-1-k \right)=\sum_{k=m-n-1}^{m-1}\binom{k}{m-n-1}\left(m-1-k \right)$$$$=\left(m-1\right)\sum_{k=m-n-1}^{m-1}\binom{k}{m-n-1}-\sum_{k=m-n-1}^{m-1}\binom{k}{m-n-1}k$$$$=\left(m-1\right)\binom{m}{m-n}-\sum_{k=m-n-1}^{m-1}\binom{k}{m-n-1}k$$$$=\left(m-1\right)\binom{m}{n}-\sum_{k=m-n-1}^{m-1}\binom{k}{m-n-1}k$$

Setting $n \mapsto \left(m-n-1\right)$ and $m \mapsto \left(m-1\right)$ in $\large\color{red}{*}$ follows:

$$=\left(m-1\right)\binom{m}{n}-\left(m-n-1\right)\binom{m}{m-n}-\left(m-n \right)\binom{m}{m-n+1}$$$$=n\binom{m+1}{n}-m\binom{m}{n-1}=n\binom{m+1}{n}-m\binom{m}{n-1}$$

Hence:

$$\bbox[5px,border:2px solid #00A000]{\sum_{k=0}^{n}\binom{m-k-1}{m-n-1}\left(k \right)=\binom{m}{n-1}}$$

Which its validity has been checked for $n,m \in \mathbb Z$.

---

$\text{(III)}$

$$\sum_{k=0}^{n}\binom{n+k}{k}\binom{n}{k}\frac{\left(-1 \right)^k}{k+1}=\frac{1}{n+1}\sum_{k=0}^{n}\binom{n+k}{k}\binom{n+1}{k+1}\left(-1 \right)^k$$$$=\frac{1}{n+1}\sum_{k=0}^{n}\binom{-n-1}{k}\binom{n+1}{n-k}=\frac{1}{n+1}\binom{0}{n}= \begin{cases} 1&\, \;\;\;\; n=0\\ \\ 0 &\text{otherwise} \end{cases} $$

Hence:

$$\bbox[5px,border:2px solid #00A000]{\sum_{k=0}^{n}\binom{n+k}{k}\binom{n}{k}\frac{\left(-1 \right)^k}{k+1}=\frac{1}{\left(-n\right)!\left(n+1\right)!}}$$

Answer 2

Let $\Gamma(x)$ denote the Gamma function. (In particular $n!=\Gamma(n+1)$.) Then Mathematica gives the following results by using first Zeilberger's algorithm and then algorithm Hyper (both described in this book):

$$\sum_{k=0}^{m}\binom{n}{k}\binom{r}{k}k=-(m+1) \binom{n}{m+1} \binom{r}{m+1} \, _3F_2(1,m-n+1,m-r+1;m+2,m+2;1)-\binom{n}{m+2} \binom{r}{m+2} \, _3F_2(2,m-n+2,m-r+2;m+3,m+3;1)+\frac{\Gamma (n+r)}{\Gamma (n) \Gamma (r)}$$

(what an evil first sum)

$$\sum_{k=0}^{n}\binom{m-k-1}{m-n-1} k=\frac{\Gamma (m+1)}{\Gamma (n) \Gamma (m-n+2)}$$

and $$\sum_{k=0}^{n}\binom{n+k}{k}\binom{n}{k}\frac{\left(-1 \right)^k}{k+1}=\frac{1}{\Gamma (1-n) \Gamma (n+2)}.$$

Answer 3

Try the techniques in Petkovsek, Wilf, Zeilberger "A = B" (the laborious checking is done in most CAS, e.g. in maxima there is a package for it). It will tell you if it can be summed (and give the sum and an easy proof) or prove it can't be written in closed form.

Answer 4

For the third identity,

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

we have

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

Now the coefficient extractor enforces the range of the sum and we obtain

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