How to prove that $\sum_{M=k-1}^{2 k-1}\left(q C_{M}^{k-1} q^{k-1} p^{M-(k-1)}+p C_{M}^{k} p^{k} q^{M-k}\right)=1$ where $q+p = 1$ How to prove  $\sum_{M=k-1}^{2 k-1}\left(q C_{M}^{k-1} q^{k-1} p^{M-(k-1)}+p C_{M}^{k} p^{k} q^{M-k}\right)=1$ ,where $q+p = 1$. And here $C_{m}^{n}=\frac{m !}{n !(m-n) !} $ for $m \geq n$, otherwise $0$. I've tried to expand the sum and considered to use the Taylor series in two variables. But I couldn't get the right answer. Am I thinking in a wrong way?
 A: Here we seek to prove that
$$\sum_{M=k-1}^{2k-1} 
\left({M\choose k-1} (1-x)^k x^{M-(k-1)}
+ {M\choose k} x^{k+1} (1-x)^{M-k}\right) = 1.$$
The LHS is
$$\sum_{q=0}^n {q+n-1\choose n-1} (1-x)^n x^q
+ \sum_{q=1}^n {q+n-1\choose n} x^{n+1} (1-x)^{q-1}
\\ = (1-x)^n \sum_{q=0}^n {q+n-1\choose n-1} x^q
+ x^{n+1} \sum_{q=1}^n {q+n-1\choose n} (1-x)^{q-1}.$$
We have for the first sum
$$ [z^n] \frac{1}{1-z} \sum_{q\ge 0} {q+n-1\choose n-1} x^q z^q
= [z^n] \frac{1}{1-z} \frac{1}{(1-xz)^n}
\\ = \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
 \frac{1}{1-z} \frac{1}{(1-xz)^n}.$$
Residues sum to zero and fortunately the residue at infinity is zero
by inspection. Therefore we require the residues at one and at 
$z=1/x.$ We start with
$$(-1)^{n+1} \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
 \frac{1}{z-1} \frac{1}{(xz-1)^n}
\\ =  \frac{(-1)^{n+1}}{x^n} \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\frac{1}{z-1} \frac{1}{(z-1/x)^n}.$$
The residue at one is
$$\frac{(-1)^{n+1}}{x^n} \frac{1}{(1-1/x)^n}
= \frac{(-1)^{n+1}}{(x-1)^n}.$$
Multiply by the factor in front to get a contribution of $-1.$
For the residue at $z=1/x$ we require
$$\frac{1}{(n-1)!} 
\left(\frac{1}{z^{n+1}} \frac{1}{z-1}\right)^{(n-1)}
\\ =  \frac{1}{(n-1)!} 
\sum_{q=0}^{n-1} {n-1\choose q} 
\frac{(-1)^q (n+q)!}{n! z^{n+1+q}}
\frac{(-1)^{n-1-q} (n-1-q)!}{(z-1)^{n-q}}
\\ = (-1)^{n-1} \sum_{q=0}^{n-1} {n+q\choose n} 
\frac{1}{z^{n+1+q} (z-1)^{n-q}}.$$
The residue is (evaluate at $z=1/x$)
$$\frac{(-1)^{n+1}}{x^n} (-1)^{n-1} 
\sum_{q=0}^{n-1} {n+q\choose n} 
x^{n+1+q} \frac{1}{(1/x-1)^{n-q}}
\\ = \sum_{q=0}^{n-1} {n+q\choose n} 
x^{q+1} \frac{x^{n-q}}{(1-x)^{n-q}}
\\ = x^{n+1} \sum_{q=0}^{n-1} {n+q\choose n} 
\frac{(1-x)^q}{(1-x)^{n}}.$$
Multiply by the factor in front and shift the index to get a 
contribution of
$$x^{n+1} \sum_{q=1}^{n} {n+q-1\choose n} (1-x)^{q-1}.$$
Using the fact that residues sum to zero we have shown that
$$(1-x)^n \sum_{q=0}^n {q+n-1\choose n-1} x^q -1 
+ x^{n+1} \sum_{q=1}^n {q+n-1\choose n} (1-x)^{q-1} = 0.$$
which is the claim. 
Remark. This identity turns out to be an identity by Gosper
which was proved at the following MSE 
link. To see this
rewrite as
$$(1-x)^n \sum_{q=0}^n {q+n-1\choose n-1} x^q 
+ x^{n+1} \sum_{q=0}^{n-1} {q+n\choose n} (1-x)^{q} = 1.$$
The original is
$$\sum_{q=0}^{m-1} {n-1+q\choose q} x^n (1-x)^q
+ \sum_{q=0}^{n-1} {m-1+q\choose q} x^q (1-x)^m = 1.$$
Now replace $m$ by $n$ and $n$ by $n+1.$
A: FYI, have a look at the formation:
Consider a game: there are two chessman $A$ and $B$ racing along the axis. $A$ starts at  coordinate $0$ and $B$ starts at coordinate $1$. Every time you pull the trigger, there is possibility $p$ that $A$ moves $1$ step rightwards (while $B$ stays still), otherwise (with possibility $q=1-p$) $B$ moves $1$ step rightwards (while $A$ stays still). Once a chessman reaches coordinate $k+1$, it wins and game's over.
Suppose you pulled the trigger for $M$ times before the final straw. Apparently $M\in [k-1,2k-1]$: $k-1$ for $A=0,B=k$ and $2k-1$ for $A=k,B=k$. Now $\forall M$ there are two cases to terminate the game:


*

*A wins. $i.e.$ $M$ right-steps are assigned $s.t.$ $A=k,B=1+M-k$ and the final step goes to $A$. The probability of this case is $pC_M^kp^kq^{M-k}$.

*B wins. $i.e.$ $M$ right-steps are assigned $s.t.$ $B=k,A=M-(k-1)$ and the final step goes to $B$. The probability of this case is $qC_M^{k-1}q^{k-1}p^{M-k+1}$.
With $M$ traversing among range $[k-1,2k-1]$ and both the two cases, all the possibilities are enumerated completely. Hence LHS$=1$. 
