**Problem Detail:**

Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N cigarettes in the Banach cigarette problem ; so there is a combinatorial explanation which I do not consider here.

$$ \sum_{i=0}^{N} \binom{2N-i}{N} 2^i = 2^{2N} $$

I wish to know how one would go about finding this closed form using generating functions. More precisely, how would you evaluate

$$ \sum_{N \geq i} \binom{2N-i}{N} x^N $$

Thanks!

###### Asked By : Gobiel

###### Answered By : Andrej Bauer

The term $t_N = {2 N - i \choose N} x^N$ of the sum is *hypergoemtric* ($t_{N+1}/t_N$ is a rational function of $N$) which means that the closed form of the sum can be found using Gosper's algorithm, if it exists and is hypergeometric.

When I run the algorithm with Mathematica it says $$x^i \cdot {}_2F_1(\frac{i+1}{2}, \frac{i+2}{2}; i+1; 4 x)$$ where ${}_2F_1$ is the hypergeometric function. This means that a closed form of the kind you are expecting does not exist.

**Supplemental:**

Gosper's algorithm computes $$\sum _{i=0}^n \binom{2 n-i}{n} 2^i = 4^n$$ and then $$\sum _{n=0}^{\infty } x^n \sum _{i=0}^n \binom{2 n-i}{n} 2^i = \frac{1}{1 - 4 x}.$$

Question Source : http://cs.stackexchange.com/questions/52491

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback