8
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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,

$\endgroup$
3
  • $\begingroup$ @Aryabhata: It certainly did! Thanks. $\endgroup$ Jul 13 '11 at 18:41
  • $\begingroup$ 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$. $\endgroup$ Jul 14 '11 at 14:35
  • $\begingroup$ Well, actually it's the other way: I knew the generating function with respect to $p$ (which is a function of the parameter $k$) $\endgroup$ Jul 15 '11 at 10:59
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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]

$\endgroup$
4
  • $\begingroup$ I think that will do; thanks a lot. Did you use standard Mathematica? or did you use some special package? $\endgroup$ Jul 14 '11 at 14:37
  • $\begingroup$ 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? $\endgroup$ Jul 14 '11 at 14:44
  • $\begingroup$ 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? $\endgroup$ Jul 14 '11 at 15:03
  • $\begingroup$ @Manolito I used the standard Mathematica, version 8. $\endgroup$
    – Sasha
    Jul 14 '11 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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