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.


1 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.


Your Answer

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

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