Prove that $\sum_{k=n}^{5n} C_{k-1}^{n-1} (4/5)^{k-n}$ is equal to 1

Question

I want to evaluate this limit:

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

and I try to show, that sums

$$ \displaystyle \sum_{n=k}^{5n} C_{k-1}^{n-1} \left(\frac{1}{5} \right)^{n} \left(\frac{4}{5}\right)^{k-n} $$ is equal to $5^{-n}$.

So if I write sum such $$ \left(\frac{1}{5} \right)^{n} \sum_{n=k}^{5n} C_{k-1}^{n-1} \left(\frac{4}{5}\right)^{k-n} $$ I should exlpain, that sums above is equal to $1$. And my troubleshooting: how to prove this?

Wolfram provided solution: this limit euqal $0$.

Answer 1

The following slightly different limit is probably what is intended: $$\lim_{n \to \infty} \sum_{k=n}^{5n} \binom {k-1}{n-1} \left(\frac15\right)^n \left(\frac45\right)^{k-n}.$$ It is equal to $\frac12$.

To see this, interpret the sum as a probability. Take a biased coin that lands heads with probability $\frac15$, and flip it until it lands heads $n$ times. The summand $\binom {k-1}{n-1} \left(\frac15\right)^n \left(\frac45\right)^{k-n}$ is the probability that it will take exactly $k$ coinflips for the coin to land heads $n$ times: for this to happen, the last of $k$ coinflips must be heads, so we choose which $n-1$ of the first $k-1$ coinflips were heads, multiply by the probability of $n$ heads, and multiply by the probability of $n-k$ tails. Therefore the overall sum is the probability that it will take at most $5n$ coinflips for the coin to land heads $n$ times.

The number of coinflips this takes can be written as $X_1 + X_2 + \dots + X_n$ where $X_i \sim \text{Geometric}(\frac15)$ is the number of coinflips it takes to go from $i-1$ to $i$ heads. Each $X_i$ has expected value $5$ and variance $20$, so the sum has expected value $5n$ and variance $20n$.

By the central limit theorem, the quantity $$ Z_n := \frac{(X_1 + X_2 + \dots + X_n) - 5n}{\sqrt{20n}} $$ converges in distribution to a standard normal random variable. In particular, $\lim_{n \to \infty} \Pr[Z_n \le 0] = \frac12$, since a standard normal random variable is equally likely to be positive or negative.

But the event that $Z_n \le 0$ is exactly the event that $X_1 + X_2 + \dots + X_n \le 5n$, which is the event whose probability is given by the sum we started with, so the original limit is also $\frac12$.

Answer 2

First, let's note the full sum $$ \begin{align} \sum_{k=n}^\infty\binom{k-1}{n-1}\left(\frac15\right)^n\left(\frac45\right)^{k-n} &=\sum_{k=0}^\infty\binom{k+n-1}{n-1}\left(\frac15\right)^n\left(\frac45\right)^k\tag{1a}\\ &=\sum_{k=0}^\infty(-1)^{k}\binom{-n}{k}\left(\frac15\right)^n\left(\frac45\right)^k\tag{1b}\\ &=\left(\frac15\right)^n\sum_{k=0}^\infty\binom{-n}{k}\left(-\frac45\right)^k\tag{1c}\\ &=\left(\frac15\right)^n\left(1-\frac45\right)^{-n}\tag{1d}\\[9pt] &=1\tag{1e} \end{align} $$ Explanation:
$\text{(1a):}$ substitute $k\mapsto k+n$
$\text{(1b):}$ negative binomial coefficients
$\text{(1c):}$ simplify
$\text{(1d):}$ Binomial Theorem
$\text{(1d):}$ simplify

Next, let's estimate the partial sum $$ \sum_{k=n}^{5n}\binom{k-1}{n-1}\left(\frac15\right)^n\left(\frac45\right)^{k-n} =\sum_{k=0}^{4n}\binom{k+n-1}{n-1}\left(\frac15\right)^n\left(\frac45\right)^k\tag2\\ $$ Note that the ratio of two terms is $$ \begin{align} \frac{\binom{k+n}{n-1}\left(\frac45\right)^{k+1}}{\binom{k+n-1}{n-1}\left(\frac45\right)^k} &=\frac45\frac{k+n}{k+1}\tag{3a}\\ &=e^{\log\left(\frac45\right)+\log\left(1+\frac{n-1}{k+1}\right)}\tag{3b} \end{align} $$ Thus, the difference of the logarithms is $$ \log\left(\frac45\right)+\log\left(1+\frac{n-1}{k+1}\right)\tag4 $$ which vanishes when $k=4n-5$. The derivative of $(4)$ is $$ -\frac{k+1}{n+k}\frac{n-1}{(k+1)^2}=-\frac{n-1}{(k+1)(n+k)}\tag5 $$ When $(4)$ vanishes, $(5)$ is $$ -\frac1{20(n-1)}\tag6 $$ Using $(6)$ as the second derivative of the logarithm, Laplace's Method says that this binomial sum is approximately $$ \frac1{\sqrt{40\pi(n-1)}}\int_{-\infty}^{k-4n}e^{-\frac{x^2}{40(n-1)}}\,\mathrm{d}x\tag7 $$ which for $k=4n$ gives $$ \lim_{n\to\infty}\sum_{k=0}^{4n}\binom{k+n-1}{n-1}\left(\frac15\right)^n\left(\frac45\right)^k=\frac12\tag8 $$