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

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!

• Your two sums don't match. In this on purpose? – Yuval Filmus Jan 30 '16 at 21:08
• Perhaps this is more appropriate for math.se. It seems to have nothing to do with computer science. – Yuval Filmus Jan 30 '16 at 21:08
• The second sum appears when considering $\sum_{N \geq 0} x^N \sum_{i=0}^N \binom{2N-i}{N} 2^i$ This does not seem to be the way to go, as Andrej has shown... – Gobiel Jan 30 '16 at 21:21

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

• Thank you for answering my question, but now I realize it was poorly worded as the second sum came out of nowhere... – Gobiel Jan 30 '16 at 21:26
• Well, the new sums are easier to compute. – Andrej Bauer Jan 31 '16 at 18:23