2
$\begingroup$

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!

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for answering my question, but now I realize it was poorly worded as the second sum came out of nowhere... $\endgroup$ Commented Jan 30, 2016 at 21:26
  • $\begingroup$ Well, the new sums are easier to compute. $\endgroup$ Commented Jan 31, 2016 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.