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

Question

Using the Central Limit Theorem , Evaluate $$\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$$

My solution: Let $\{X_n\}$ be a sequence of iid R.V's each having $Geo(\frac{1}{2})$

Then $E(X_n)=1$ and $Var(X_n)=2 < \infty,n\in N$

Also $S_n=\sum_{k=1}^nX_k\sim NB(n,\frac{1}{2})$

By Lindeberg-Levy CLT, $$\begin{align} \lim_{n \to \infty}P[\frac{S_n-E(S_n)}{\sqrt{V(S_n)}}\leq x] &= \Phi(x), \forall x \in R\\ \implies \lim_{n \to \infty}P[\frac{S_n-n}{\sqrt{2n)}}\leq x] &= \Phi(x), \forall x \in R\end{align}$$ Now put $x=0$ $$\begin{align} \lim_{n \to \infty}P[S_n \leq n]&= \Phi(0) \\ \implies \lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}} &=\frac{1}{2}\end{align}$$ Am I right? Is there any other way to solve the limit? So that I can check the limit(Though it is completely unnecessary for the given question). Please help. Thank in advance.

Answer 1

Another way is to use the combinatorial identity $\displaystyle \sum_{j=0}^m \binom{m+j}{j} 2^{m-j}= 4^m$. (See end of post for a proof.)

Dividing by $4^m$, setting $m = n-1$, and extracting the last term, the OP's sum becomes $$ \binom{2n-1}{n} \frac{1}{4^n} + \frac{1}{2} \sum_{j=0}^{n-1}{{j+n-1} \choose j}\frac{1}{2^{j+n-1}} = \binom{2n}{n} \frac{1}{2 \cdot 4^n} + \frac{1}{2}.$$

Since the central binomial coefficient has asymptotic $\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}$, the last expression approaches $\frac{1}{2}$ as $n \to \infty$.

---

Combinatorial proof that $\displaystyle \sum_{j=0}^m \binom{m+j}{j} 2^{m-j}= 4^m$ (borrowed from an answer of mine on math.SE):

Suppose you flip coins until you obtain either $m+1$ heads or $m+1$ tails. After either heads or tails "wins" you keep flipping until you have a total of $2m+1$ coin flips. The two sides count the number of ways for heads to win.

For the left side: Condition on the number of tails $j$ obtained before head $m+1$. There are $\binom{m+j}{j}$ ways to choose the positions at which these $j$ tails occurred from the $m+j$ total options, and then $2^{m-j}$ possibilities for the remaining flips after head $m+1$. Summing up yields the left side.

For the right side: Heads wins on half of the total number of sequences; i.e., $\frac{1}{2}(2^{2m+1}) = 4^m$.

---

Added: Byron Schmuland has recently answered this question on math.SE as well. My answer is similar to his.