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!
Finding a closed form for a discrete sum using generating functions
combinatorics;discrete mathematics
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}.$$