Suppose we're playing the following dart game:
The player can play up to $T$ rounds. In each round of the game, the player first throw a black dart, and then a white dart. Each dart independently hit the bullseye with probability $p$. Game continues until $K$ darts have hit the bullseye. He/she "wins" if none of the darts that hit the bullseye are white. What's the winning probability?
Here is my solution:
Suppose the player wins at $n$ th round, i.e he/she has thrown $n$ black darts and $n$ white darts. In order for the player to win at this time, all the white darts must not hit the bullseye, and the $n$ th black dart must hit the bullseye, and there must be other $(k-1)$ out of the first $(n-1)$ black darts hit the bullseye. Put it together, we have
$$Pr[Win] = \sum_{n=k}^T (1-p)^n \cdot p \cdot {n-1 \choose k-1} p^{k-1} (1-p)^{n-k} $$
i.e.
$$Pr[Win] = p^k \sum_{n=k}^T {n-1 \choose k-1} (1-p)^{2n-k} $$
But I don't a good idea to simplify this further, or upper bound it. Can anyone help? Thanks!
It's probably an extended hint rather than the full answer.
The last expression after a bit of algebra can be rewritten as $$ S_1 = \sum_{j=0}^{r} \binom{m+j}{m} x^j $$ The binomial coefficient $\binom{m+j}{m} = \binom{-m+1}{j}$, so the sum is $$ S_2 = \sum_{j=0}^{\infty} \binom{-m+1}{j} (-x)^j = \frac{1}{(1+x)^{m-1}} $$
You need to do more algebra carefully, because the last expression is for the infinite sum.