Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 7 / b / i / Solution

To obtain the $(k+1)$st head on toss $n+1$, the first $n$ tosses must contain exactly $k$ heads, and the last toss must be a head. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ choices of the first $k$ head positions. By independence, each such arrangement followed by a head has probability $r^k(1-r{)}^{n-k}r$. The arrangements are disjoint, soThis is the negative binomial stopping argument, with $n+1$ counting all tosses up to and including the $(k+1)$st success. It is not merely the probability of $k+1$ heads somewhere among $n+1$ tosses: the last toss is prescribed to be a head.