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

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)

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

• @ Maximilian Janisch, Thanks, but are you sure that there does not exist any other way? Using hypergeometric functions is like writing the identities just in another form (not indeed a closed form) – user715522 Mar 7 '20 at 15:32
• @user715522 I would be surprised if there was a simpler form of writing the first sum since Mathematica has an extensive list of more than 300'000 hypergeometric function identities that it can use for simplification. (It is still possible that a simpler form exists though) – Maximilian Janisch Mar 7 '20 at 15:40
• @ Maximilian Janisch , I found the second one and it coincides with your answer, thanks – user715522 Mar 7 '20 at 17:33

$$\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)!}}$$

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.

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