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

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

-
I think the limit will be $\frac{1}{2}$. See stats.stackexchange.com/questions/48411/… – A.D Jan 26 '13 at 18:38
Seems related to the negative binomial distribution. – guy Jan 26 '13 at 23:13

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.

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