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

3 Answers 3

8

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,

  • 0
    Well, actually it's the other way: I knew the generating function with respect to $p$ (which is a function of the parameter k)2011-07-15
2

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

1

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]

  • 0
    @Manolito I used the standard Mathematica, version 8.2011-07-14