The probability of obtaining a head when flipping a coin is $p$. The coin is flipped until $n$ heads occur in a row. What the expected number of flips required for this to happen?
My solution. Let $X$ be the random variable representing the number of flips required. We need at least $n$ flips. So I have
$$P(X = k) = p^{n}(1-p)^{k-n}, \quad k =n, n+1, n+2,... ,\infty$$
So,
$$E(X) = \sum _{k = n}^{\infty} k p^{n}(1-p)^{k-n}$$
Summing the above series, I obtain $E(X) = \frac{p^{n}(n+1) + p^{n}}{(1-p)^{2}}$. But this solution is obviously wrong, since the required answer should be $\frac{1-p^{n}}{p^{n}(1-p)}$.
So where is the error in my reasoning?
Well, $p^n (1-p)^{k-n}$ is the probability of $k-n$ tails followed by $n$ heads, which is only one way to get $n$ heads in a row for the first time. Let $\mu_n$ denote the desired mean so $\mu_1=\frac{1}{p}$ (note this agrees with the correct answer), and $\mu_{n+1}$ is the mean number of flips needed if we first get $n$ heads in a row in $\mu_n$ flips on average, followed by another head with probability $p$ or us starting all over again with probability $1-p$. Your challenge is to prove this implies $\mu_{n+1}=p^{-1}(\mu_n+1)$, which implies by induction the desired $\mu_n=\frac{p^{-n}-1}{1-p}$.