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


  • 2
    $\begingroup$ Your two sums don't match. In this on purpose? $\endgroup$ – Yuval Filmus Jan 30 '16 at 21:08
  • 3
    $\begingroup$ Perhaps this is more appropriate for math.se. It seems to have nothing to do with computer science. $\endgroup$ – Yuval Filmus Jan 30 '16 at 21:08
  • $\begingroup$ 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... $\endgroup$ – 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.


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.