# Yet another sum involving binomial coefficients

Let $k,p$ be positive integers. Is there a closed form for the sums

$$\sum_{i=0}^{p} \binom{k}{i} \binom{k+p-i}{p-i}\text{, or}$$

$$\sum_{i=0}^{p} \binom{k-1}{i} \binom{k+p-i}{p-i}\text{?}$$

(where 'closed form' should be interpreted as a representation which is free of sums, binomial coefficients, or any other hypergeometric functions).

-

Lets examine the first sum. I can't seem to find a closed form, but there is something very nice with the generating series. They are simple, and symmetrical with respect to the variables $p$ and $k$.

Result: Your sum is the $k^{th}$ coefficient of $\frac{(1+x)^{p}}{\left(1-x\right)^{p+1}},$ and also the $p^{th}$ coefficient of $\frac{(1+x)^{k}}{\left(1-x\right)^{k+1}}.$

The Generating Series for the variable $p$

Consider

$$F(x)=\sum_{p=0}^{\infty}\sum_{i=0}^{p}\binom{k}{i}\binom{k+p-i}{p-i}x^{p}.$$

Changing the order of summation, this becomes

$$F(x)=\sum_{i=0}^{\infty}\binom{k}{i}\sum_{p=i}^{\infty}\binom{k+p-i}{p-i}x^{p},$$

and then shifting the second sum we have

$$F(x)=\sum_{i=0}^{\infty}\binom{k}{i}x^{i}\sum_{p=0}^{\infty}\binom{k+p}{p}x^{p}.$$ Since the rightmost sum is $\frac{1}{(1-x)^{k+1}}$ we see that the generating series is $$F(x)=\frac{1}{(1-x)^{k+1}}\sum_{i=0}^{\infty}\binom{k}{i}x^{i}=\frac{\left(1+x\right)^{k}}{(1-x)^{k+1}}$$

by the binomial theorem.

The Generating Series for the variable $k$:

Lets consider the other generating series with respect to the variable $k$. Let

$$G(x)=\sum_{k=0}^{\infty}\sum_{i=0}^{p}\binom{k}{i}\binom{k+p-i}{p-i}x^{k}.$$

Then

$$G(x)=\sum_{i=0}^{p}\sum_{k=i}^{\infty}\binom{k}{i}\binom{k+p-i}{p-i}x^{k}=\sum_{i=0}^{p}x^{i}\sum_{k=0}^{\infty}\binom{k+i}{i}\binom{k+p}{p-i}x^{k}.$$

Splitting up the binomial coefficients into factorials, this is

$$=\sum_{i=0}^{p}x^{i}\sum_{k=0}^{\infty}\frac{(k+i)!}{k!i!}\frac{(k+p)!}{(k+i)!(p-i)!}x^{k}=\sum_{i=0}^{p}\frac{x^{i}p!}{i!\left(p-i\right)!}\sum_{k=0}^{\infty}\frac{\left(k+p\right)!}{k!p!}x^{k}.$$

Consequently,

$$G(x)=\frac{(1+x)^{p}}{\left(1-x\right)^{p+1}}.$$

Comments: I am not sure why the generating series has this symmetry. Perhaps you can use this property to tell you more about the sum/generating series.

Hope that helps,

-
@Aryabhata: It certainly did! Thanks. – Eric Naslund Jul 13 '11 at 18:41
Thank you Eric; it's beautiful. I did know the generating function with respect to $k$, but I had not realized that it was the same with respect to $p$. – Manolito Pérez Jul 14 '11 at 14:35
Well, actually it's the other way: I knew the generating function with respect to $p$ (which is a function of the parameter $k$) – Manolito Pérez Jul 15 '11 at 10:59

I derived the following simple inequality (confirmed numerically): for any $0 < s < 1/2$, $$\sum\limits_{i = 0}^p {{k \choose i}{k + p - i \choose p - i}} \le \frac{1}{{(1 - 2s)^k }}\bigg(\frac{{1 - s}}{s}\bigg)^p.$$ Given $0 < s < 1/2$, let $X$ be a binomial$(k,s)$ random variable, and $Y$ a binomial$(k+p-X,t)$ random variable, where $t=s/(1-s) \, (\in (0,1))$. Then, by the law of total probability, $${\rm P}(X + Y = p) = \sum\limits_{i = 0}^p {{\rm P}(X + Y = p|X = i){\rm P}(X = i)} = \sum\limits_{i = 0}^p {{\rm P}(Y = p - i|X = i){\rm P}(X = i)}.$$ Noting that $${\rm P}(X = i) = {k \choose i}s^i (1-s)^{k-i}$$ and $${\rm P}(Y = p - i|X = i) = {k + p - i \choose p - i}t^{p - i} (1 - t)^k ,$$ and using $$\frac{s}{{(1 - s)t}} = 1,$$ we get $${\rm P}(X + Y = p) = (1 - s)^k (1 - t)^k t^p \sum\limits_{i = 0}^p {{k \choose i}{k + p - i \choose p - i}} .$$ Finally, from ${\rm P}(X + Y = p) \leq 1$ and $$(1 - s)^k (1 - t)^k t^p = (1 - 2s)^{k} \bigg(\frac{s}{{1 - s}}\bigg)^p ,$$ it follows that $$\sum\limits_{i = 0}^p {{k \choose i}{k + p - i \choose p - i}} \le \frac{1}{{(1 - 2s)^k }}\bigg(\frac{{1 - s}}{s}\bigg)^p.$$

-
Very nice ! Thanks. – Manolito Pérez Jul 14 '11 at 14:36
Thank you too... – Shai Covo Jul 14 '11 at 15:25

Using a computer algebra system I get

In[114]:= Sum[ Binomial[k, i] Binomial[k+p-i,p-i],{i,0,p}]

Out[114]= Binomial[k + p, p] Hypergeometric2F1[-k, -p, -k - p, -1]

and

In[115]:= Sum[Binomial[k - 1, i] Binomial[k + p - i, p - i], {i, 0, p}]

Out[115]= Binomial[k + p, p] Hypergeometric2F1[1 - k, -p, -k - p, -1]

-
I think that will do; thanks a lot. Did you use standard Mathematica? or did you use some special package? – Manolito Pérez Jul 14 '11 at 14:37
I know there is a Mathematica package and a Maple package accompanying the book "A=B", by Wilf, Zeilberger and Petkovsek, and which can solve this kind of problems, but I still don't know how to use them. Does anybody know? – Manolito Pérez Jul 14 '11 at 14:44
I will leave the question open to see if anybody can find another formula. By the way, I know there is a Mathematica package and a Maple package accompanying the book "A=B", which can solve this kind of problems, but I still don't know how to use them. Does anybody know? – Manolito Pérez Jul 14 '11 at 15:03
@Manolito I used the standard Mathematica, version 8. – Sasha Jul 14 '11 at 16:35