World's most popular travel blog for travel bloggers.

# Finding a closed form for a discrete sum using generating functions

, ,
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!

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

Best Answer from StackOverflow

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

3200 people like this

#### Post a Comment

Let us know your responses and feedback