Question in basic probability-coin tossing Came across the following question:

Given a coin with probability $0< p< 1$ to fall on "head". Tossing it independently. Given $n,m\in\mathbb{N}$ what is the probability to get $n$ "head"s before $m$ "tail"s?

My approach was: the n heads need to occur in the $(n+m-1)$ first tosses. 
There're $n+m-1\choose n$ ways to pick $n$ elements from this group.   In each pick, we need to have $n$ heads meaning the probability is $p^n$. 
Summing all up I get ${n+m-1\choose n}\cdot p^n$.
The result in the book is: $\sum_{k=n}^{m+n-1}{n+m-1\choose k}\cdot p^{k}\cdot (1-p)^{n+m-1-k}$ which I don't understand why.
 A: You were on the right track, but not quite there.   You were trying to caluclate the probability for obtaining exactly $n$ heads before the $m$~th tail.   That is the probability for obtaining $n$ heads and $m-1$ tails among $n+m-1$ tosses, and then a tail on the next toss.$$\dbinom{n+m-1}{n}\cdot p^n\cdot (1-p)^{m}$$
However you were ashed for the probability for obtailing at least $n$ heads before $m$ tails.  That is the probability for obtailing $n$ or more tails among the first $n+m-1$ tosses, and then whatever on the tosses after that.
$$\sum_{k=n}^{n+m-1}\dbinom{n+m-1}{k}\cdot p^k\cdot (1-p)^{n+m-1-k}$$
A: The problem with your approach is that you might have more than $n$ heads in the first $n+m-1$ tosses. You have counted the probability that tosses $1,...,n$ are all heads and you've counted the probability that tosses $2,...,n+1$ are all heads separately, but by doing this you're counting the times that all of $1,...,n+1$ are heads twice (well, actually $n+1$ times because of other combinations that I didn't mention). So your method overestimates the probability you want.
The probability of exactly $n$ heads would be $\binom{n+m-1}{n}p^n(1-p)^{m-1}$ (the value you had times the probability that the other coins are all tails). But what you want is the probability of at least $n$ heads, i.e. $\sum_{k=n}^{n+m-1}P(k\text{ heads})$, which is what the formula in the book counts.
