Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

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,

share|improve this answer
    
@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. $$

share|improve this answer
    
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]

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.