Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Evaluate $$\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$$

I don't understand where to start. Please help.

share|cite|improve this question
I think the limit will be $\frac{1}{2}$. See… – A.D Jan 26 '13 at 18:38
Seems related to the negative binomial distribution. – guy Jan 26 '13 at 23:13
up vote 4 down vote accepted

As guy notes, the sum has a probabilistic interpretation. Suppose that you toss a fair coin until you have either $n$ heads or $n$ tails. The probability that you need $j+n$ tosses in total is $2{j+n-1\choose j}(1/2)^{j+n}$ for $0\leq j\leq n-1$. The factor of $2$ in the front comes from the two cases, whether the series ends with a head or a tail.

Since the probabilities add up to one, we have
$$2\sum_{j=0}^{n-1} {j+n-1\choose j}\left({1\over2}\right)^{j+n}=1,$$ and so $$\sum_{j=0}^{n-1} {j+n-1\choose j}\left({1\over2}\right)^{j+n}={1\over2}.$$

The sum considered by the OP has one additional term that goes to zero. So as $n\to\infty$, $$\sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}={1\over2}+{2n-1\choose n-1}{1\over 2^{2n}}\to{1\over2}.$$

Added: The additional term has the product representation $${2n-1\choose n-1}{1\over 2^{2n}}={1\over2}\prod_{j=1}^n \left(1-{1\over 2j}\right).$$ Using the elementary arguments from my answer here we get the upper bound $${2n-1\choose n-1}{1\over 2^{2n}}\leq{3\over 8\sqrt{n+1}},$$ which shows that the extra term goes to zero. Of course, there are other ways to do this.

See this question as well.

share|cite|improve this answer
+1. Maybe an explanation of why the additional term goes to zero, too? – Mike Spivey Jan 27 '13 at 0:10
Added reference: See equation (5.20) in Concrete Mathematics by Graham, Knuth, and Patashnik. – Byron Schmuland Jan 27 '13 at 1:22
@ByronSchmuland +1, There is a sign typo though: $$ \sum_{j=0}^n \binom{n+j-1}{j} \frac{1}{2^{n+j}} = \frac{1}{2} +\frac{1}{2^{2n}} \binom{2n-1}{n-1} $$ – Sasha Jan 27 '13 at 2:51
@Sasha Thanks for that. – Byron Schmuland Jan 27 '13 at 3:12
Thanks for your answer. – Argha Jan 27 '13 at 6:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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