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}$

calculuscombinationscombinatoricslimits

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.

Best Answer

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}.$$

Related Question