# Find the limit $\lim\limits_{n \to +\infty}\sum\limits_{k=n}^{3n} \binom{k-1}{n-1} \left(\frac{1}{3}\right)^n \left(\frac{2}{3}\right)^{k-n}$

The problem is to find the following limit:

$$\lim_{n \to +\infty}\sum\limits_{k=n}^{3n} \binom{k-1}{n-1} \left(\dfrac{1}{3}\right)^n \left(\dfrac{2}{3}\right)^{k-n}$$

I see that it looks similarly to the formula from the binomial theorem, but don't get how we can make use of it.

Any ideas would be greatly appreciated.

• AFAIK, there is no standard way to use the $C_i^j$ symbol. By $C_{k-1}^{n-1}$, do you mean the number of ways to choose $k-1$ things from $n-1$ things? If so, note that all terms other than the first one in the sum are zero. If you mean the reverse, note that each term in the sum is non-negative, so the sum itself is at least $\binom{3n-1}{n-1} 2^{2n}/3^n$ (which is the very last term), which goes to infinity with $n$. – stochasticboy321 Apr 10 '17 at 3:35
• @stochasticboy321 I meant the latter one (edited the question accordingly). But the upper bound you provided is not correct - in denominator there should be $3^{3n}$. – Ramil Apr 10 '17 at 3:59
• I would suggest trying to find a combinatorial interpretation for the sum - an individual term is, for instance, $\frac nk$ times the probability of rolling exactly $n$ 1s in $k$ rolls of a 3-sided die. – Steven Stadnicki Apr 10 '17 at 6:14

The sum over all integers is \begin{align} \sum_{k=n}^\infty\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n} &=\left(\frac13\right)^n\sum_{k=n}^\infty(-1)^{k-n}\binom{-n}{k-n}\left(\frac23\right)^{k-n}\\ &=\left(\frac13\right)^n\sum_{k=0}^\infty\binom{-n}{k}\left(-\frac23\right)^k\\ &=\left(\frac13\right)^n\left(\frac13\right)^{-n}\\[9pt] &=1\tag{1} \end{align} Furthermore, $$\frac{\binom{k}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n+1}}{\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}}=\frac23\frac{k}{k-n+1}\tag{2}$$ which is $1$ when $k\approx3n$. That is, the summand is at its maximum near $k\approx3n$. By the method of Laplace, the sum to the maximum tends to one half the total sum, so we get that $$\bbox[5px,border:2px solid #C0A000]{\lim_{n\to\infty}\sum_{k=n}^{3n}\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}=\frac12}\tag{3}$$

Application of Laplace's Method

Let $$f_n(k)=\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}\tag{4}$$ From $(3)$, we can derive that for $k-3n=O\!\left(\sqrt{n}\right)$, \begin{align} \log(f_n(k+1))-\log(f_n(k)) &=\log\left(\frac23\frac{k}{k-n+1}\right)\\ &=\log\left(\frac{1+\frac{k-3n}{3n}}{1+\frac1{6n}+\frac{k-3n}{2n}}\right)\\ &=\log\left(1-\frac{k-3n}{6n}\right)+O\!\left(\frac1n\right)\\ &=-\frac{k-3n}{6n}+O\!\left(\frac1n\right)\tag{5} \end{align} From $(5)$, we get that $$f_n(k)=c\,e^{-\frac{(k-3n)^2}{12n}+O\left(\frac1{\sqrt{n}}\right)}\tag{6}$$ Since the sum for all $k$ of $f_n(k)$ is $1$, we get $$f_n(k)=\frac1{\sqrt{12\pi n}}\,e^{-\frac{(k-3n)^2}{12n}}+O\!\left(\frac1n\right)\tag{7}$$ Since $(7)$ is symmetric about $k=3n$, the sum for $k\lt3n$ will be approximately the same as the sum for $k\gt3n$. Thus, the sum for $k\lt3n$ will be approximately $\frac12$.

• Very nice! (+1) Could you provide a reference regarding the methods of stationary phase? – Markus Scheuer Apr 10 '17 at 15:51
• @MarkusScheuer: actually, since the exponent is real, it should be Laplace's Method. That is, since $\frac23\frac{k}{k-n+1}=\frac{2(k-3n)+6n}{3(k-3n)+6n+1}\approx1-\frac{k-3n}{6n}$, we have $\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}\approx\frac1{\sqrt{12\pi n}}e^{-\frac{(k-3n)^2}{12n}}$ when $k\approx3n$. – robjohn Apr 10 '17 at 17:38
• I see. Thanks a lot for the info. Best regards, – Markus Scheuer Apr 10 '17 at 18:38
• Stationary Phase and Laplace's Method are related by a rotation in the complex plane. I sometimes cite one instead of the other. Note that I did add a link to my answer. – robjohn Apr 10 '17 at 23:47
• Great, instructive elaboration! Many thanks! :-) – Markus Scheuer Apr 11 '17 at 5:34

Consider $\{\xi_i, i \in \mathbb{N}\}$ -- iid $\mathrm{Geom}\left(\frac13\right)$ variables ($\xi_i \geq 1$).

$$\Pr\left(\sum\limits_{i = 1}^n \xi_i \leq 3n \right) = \sum\limits_{k = n}^{3n}\Pr\left(\sum\limits_{i = 1}^n \xi_i = k \right) = \sum\limits_{k = n}^{3n} \binom{k - 1}{n - 1}\left(\frac13\right)^n \left(\frac23\right)^{k - n}$$ It is so because we iterate from $n$ to $3n$ (these are the all possible variants for the sum of $n$ geometric variables). Then there are $\binom{k - 1}{n - 1}$ variants to have the needed sum (stars and bars method) and the probability of each variant is really obvious because all of the variables have $1/3$ in pmf and other sum in exponent is overall $k - n$.

So, our answer is (remember that $\mathsf{E}\xi_i = 3$)

$$\lim\limits_{n \to +\infty} \Pr\left(\sum\limits_{i = 1}^n \xi_i \leq 3n \right) = \lim\limits_{n \to +\infty} \Pr\left(\sum\limits_{i = 1}^n (\xi_i - \mathsf{E}\xi_i) \leq 0 \right) = \lim\limits_{n \to +\infty}\Pr\left(\frac{\sum\limits_{i = 1}^n(\xi_i - \mathsf{E}\xi_i)}{\sqrt{n\mathsf{D}\xi_1}} \leq 0 \right)$$

The equation under the probability converges in distribution (due to central limit theorem) to $X \sim \mathcal{N}(0, 1)$ and obviously the limit is $1/2$ because $\Pr(X \leq 0) = \frac12$.