# Find limit $\lim_{n\to\infty}\sum_{k=n}^{5n}{k-1\choose n-1}\left(\frac{1}{5}\right)^{n}\left(\frac{4}{5}\right)^{k-n}$

The question is pretty straightforward.

Find $$\lim_{n\to\infty}\sum_{k=n}^{5n}{k-1\choose n-1}\left(\frac{1}{5}\right)^{n}\left(\frac{4}{5}\right)^{k-n}$$

Attempt

1. Let's denote $$F$$ as \begin{align*} & \lim_{n\to\infty}\sum_{k=n}^{5n}{k-1 \choose n-1}\left(\frac{1}{5}\right)^{n}\left(\frac{4}{5}\right)^{k-n} = \\ &= \lim_{n\to\infty}\left(\frac{1}{5}\right)^{n}\frac{1}{(n-1)!}\sum_{k=n}^{5n}\left(\frac{4}{5}\right)^{k-n}\frac{(k-1)!}{(k-n)!} = \\ &= \lim_{n\to\infty}\left(\frac{1}{5}\right)^{n}\frac{1}{(n-1)!}\sum_{k=0}^{4n}\left(\frac{4}{5}\right)^{k}\frac{(k+n-1)!}{k!} = F \end{align*}
2. Try to establish a lower and upper bounds of denoted function $$F$$, lower bound set to 0, and upper bound to $$\lim_{n\to\infty}\left(\frac{1}{5}\right)^{n}\frac{1}{(n-1)!}\sum_{k=0}^{\infty}\left(\frac{4}{5}\right)^{k}\frac{(k+n-1)!}{k!}$$ The sum inside of a limit equals to $$(1 + \frac{4}{5})^{n}$$ (by using Taylor series). By substituting this into the obtained upper bound, we're getting $$0$$ as an answer.
• @Qurultay I don't think it can be solved by usual calculus' techniques. Here it's clearly a binomial distribution being expressed, so it may involve some properties of statistics. Also answer of $0$ might be wrong (as these calculations are somewhat cumbersome). – Inter Veridium Feb 22 at 10:48

A probabilistic interpretation:

Let $$X_1, \dots, X_{5n}$$ be independent Bernoulli variables each with mean $$p = 1/5$$. Note that when the sum $$X := \sum X_i$$ is at least $$n$$, we can define the index $$T$$ of the $$n$$-th variable with $$X_i = 1$$ (i.e. we let $$T$$ be the $$n$$-th smallest element of the set $$\{i : X_i = 1\}$$). When $$X < n$$, we can set $$T = \bot$$ to indicate that $$T$$ is undefined.

Now note that for $$n \leq k \leq 5n$$, we have $$T = k$$ if and only if $$X_k = 1$$ and exactly $$n-1$$ of the $$k-1$$ variables $$X_1, \dots, X_{k-1}$$ have $$X_i = 1$$. This means $$\mathbb{P}[T = k] = \binom{k-1}{n-1} \left(\frac{1}{5}\right)^n \left(\frac{4}{5}\right)^{k-n}$$ hence $$\mathbb{P}[X \geq n] = \mathbb{P}[T \neq \bot] = \sum_{k=n}^{5n} \mathbb{P}[T = k] = \sum_{k=n}^{5n} \binom{k-1}{n-1} \left(\frac{1}{5}\right)^n \left(\frac{4}{5}\right)^{k-n}.$$

But by the central limit theorem, we have $$\lim_{n \to \infty} \mathbb{P}[X \geq n] = \lim_{n \to \infty} \mathbb{P} \left[ \frac{X - n}{\sqrt{5n \mathrm{Var}[X_1]}} \geq 0 \right] = \mathbb{P}[Y \geq 0]$$ for $$Y$$ a standard normal variable (i.e. $$Y \sim N(0, 1)$$). This probability is just $$1/2$$ (the standard normal distribution is symmetric), hence $$\lim_{n \to \infty} \sum_{k=n}^{5n} \binom{k-1}{n-1} \left(\frac{1}{5}\right)^n \left(\frac{4}{5}\right)^{k-n} = \frac{1}{2}.$$

• This's a nice answer, thank you. I'll set a bounty for it if nothing else comes up (I also wonder if it can be solved by manipulating factorials, series, etc) – Inter Veridium Feb 24 at 0:00

We can rewrite the sum as \eqalign{ & S(n) = \sum\limits_{k = n}^{5n} {\left( \matrix{ k - 1 \cr n - 1 \cr} \right)p^{\,n} q^{\,k - n} } \quad \left| {\,1 \le n} \right.\quad = \cr & = p^{\,n} \sum\limits_{k = n}^{5n} {\left( \matrix{ k - 1 \cr k - n \cr} \right)q^{\,k - n} } = \sum\limits_{k = 0}^{4n} {\left( \matrix{ k + n - 1 \cr k \cr} \right)\left( {1 - q} \right)^{\,n} q^{\,k} } \cr} where as usual we put $$q=1-p$$.

The summand is $${\left( \matrix{ k + n - 1 \cr k \cr} \right)\left( {1 - q} \right)^{\,n} q^{\,k} }$$ which is the pmf of the Negative Binomial distribution $$NB(k;\,n,q)$$.

Thus our sum is the CDF of the above distribution computed at $$4n$$, which is \eqalign{ & S(n) = \sum\limits_{k = 0}^{4n} {\left( \matrix{ k + n - 1 \cr k \cr} \right)\left( {1 - q} \right)^{\,n} q^{\,k} } = 1 - I_{\,q} (4n + 1,n) = \cr & = I_{\,p} (n,4n + 1) = {{{\rm B}\left( {p;\;n,4n + 1} \right)} \over {{\rm B}\left( {n,4n + 1} \right)}} \cr} where $$I_x$$ is the Regularized Incomplete Beta function.

The mean and variance of the NB distribution are $$\mu = {{qn} \over {1 - q}}\quad \sigma ^{\,2} = {{qn} \over {\left( {1 - q} \right)^{\,2} }}$$ and for large $$n$$ it will converge to the Normal distribution with standard variable $${{x - \mu } \over {\sigma \sqrt 2 }} = {{\left( {1 - q} \right)} \over {\sqrt {2qn} }}\left( {x - {{qn} \over {1 - q}}} \right)$$

Concerning the asymptotics for $$n \to \infty$$, the NB will converge to the Normal distribution and therefore $$S(n)$$ will converge to the CDF of the Normal distribution for $$x=4n$$ \eqalign{ & S(n) = \sum\limits_{k = 0}^{4n} {\left( \matrix{ k + n - 1 \cr k \cr} \right)\left( {1 - q} \right)^{\,n} q^{\,k} } \approx \cr & \approx \Phi \left( {{{\left( {1 - q} \right)} \over {\sqrt {2qn} }}\left( {4n - {{qn} \over {1 - q}}} \right)} \right) = \cr & = \Phi \left( {{{\left( {1 - q} \right)\sqrt n } \over {\sqrt {2q} }}\left( {4 - {q \over {1 - q}}} \right)} \right) \approx \cr & \approx H\left( {4 - {q \over {1 - q}}} \right) \cr} where $$H$$ is the Heaviside step function , with $$H(0)=1/2$$, which is the case in your question.

• For $n \rightarrow \infty$ the skewness of the beta distribution with parameters $n$, $4n+1$ tends to zero and it's asymptotic expected value is $\frac{1}{5}$. It follows that the distribution is asymptotically symmetric and for $p=\frac{1}{5}$ we get the answer $\frac{1}{2}$ by symmetry and $0$/$1$ for $p$ less/greater than that. – Bartek Feb 25 at 2:39
• @Bartek: very good, thanks indeed for the help : that explains in fact the behaviour at varying $p$ that comes from computation! I am not so expert with the Beta, can you please substantiate your comment into an answer that would complete mine ? or feel free to add to the above. – G Cab Feb 25 at 10:19
• @GCab Impressive, I guess I'll have to pick up a lot of material to understand it. :) – Inter Veridium Feb 26 at 16:07
• @InterVeridium: thanks for the bounty :). Actually , the step through the NB distribution makes quite simpler to individuate the asymptotic behaviour of the truncated sum. Instead, using the alternative through the Hypergeometric function revealed not to be so tractable. – G Cab Feb 26 at 16:51

Imagine an infinite sequence of independent trials with probability $$1/5$$ if success on each trial.

On average, then it takes $$5$$ trials to get one success.

Let $$X$$ be the number of trials needed to get $$n$$ successes.

Then the expected value of $$X$$ is $$5n.$$

The variance of $$X$$ is $$20n.$$

That last is somewhat more work to prove, but it is $$n$$ times the variance of the number of trials needed to get one success, since $$X$$ is the sum of $$n$$ independent copies of that random variable.

Thus the random variable $$\dfrac{X-5n}{\sqrt{20n}}$$ has expected value $$0$$ and standard deviation $$1.$$ And as $$n\to\infty,$$ the distribution of this random variable approaches that of the standard normal random variable $$Z.$$

$$\frac{n-5n}{\sqrt{20n}} \le \frac{X-5n}{\sqrt{20n}} \le \frac{5n-5n}{\sqrt{20n}} = 0.$$ So the limit is $$\Pr(Z\le 0) = \dfrac 1 2.$$