<s>[INST] Prove equality involving binomial coefficients I was solving a probability problem and I got a different answer than the one given in the book. Seems the authors were using a different way of counting/arguing.
For the two answers to be equal, the following equality should hold true. 
$$\sum_{k=0}^{b-1} \binom{a+k-1}{a-1} p^a (1-p)^k = \sum_{k=a}^{a+b-1} \binom {a+b-1}{k} p^{k} (1-p)^{a+b-k-1}$$
How can this be proved? 
And the problem itself was: in a series of Bernoulli trials with probability for success in a single trial equal to $p$, what is the probability to get $a$ successes before getting $b$ failures?
I think you guys will reverse engineer how I counted and how the authors counted. 
 [/INST] Starting from
$$\sum_{k=0}^{b-1} {a+k-1\choose a-1} p^a (1-p)^k
= \sum_{k=a}^{a+b-1} {a+b-1\choose k} p^k (1-p)^{a+b-k-1}$$
we simplify to
$$\sum_{k=0}^{b-1} {a+k-1\choose a-1} p^a (1-p)^k
= \sum_{k=0}^{b-1} {a+b-1\choose a+k} p^{a+k} (1-p)^{b-k-1}$$
or
$$\sum_{k=0}^{b-1} {a+k-1\choose a-1} (1-p)^k
= \sum_{k=0}^{b-1} {a+b-1\choose a+k} p^k (1-p)^{b-k-1}.$$
We get for the LHS
$$\sum_{k\ge 0} {a+k-1\choose a-1} (1-p)^k
[[0\le k\le b-1]]
\\ = \sum_{k\ge 0} {a+k-1\choose a-1} (1-p)^k
[z^{b-1}] \frac{z^k}{1-z}
\\ = [z^{b-1}] \frac{1}{1-z}
\sum_{k\ge 0} {a+k-1\choose a-1} (1-p)^k z^k
\\ = [z^{b-1}] \frac{1}{1-z} \frac{1}{(1-(1-p)z)^a}.$$
The RHS is
$$\sum_{k=0}^{b-1} p^k (1-p)^{b-k-1}
[z^{b-1-k}] \frac{1}{(1-z)^{a+k+1}}
\\ = [z^{b-1}] \frac{1}{(1-z)^{a+1}}
\sum_{k=0}^{b-1} p^k (1-p)^{b-k-1}
\frac{z^k}{(1-z)^{k}}.$$
There is  no contribution to  the coefficient extractor in  front when
$k\gt b-1$ and we may extend $k$ to infinity, getting
$$(1-p)^{b-1} [z^{b-1}] \frac{1}{(1-z)^{a+1}}
\sum_{k\ge 0} p^k (1-p)^{-k}
\frac{z^k}{(1-z)^{k}}
\\ = (1-p)^{b-1} [z^{b-1}] \frac{1}{(1-z)^{a+1}}
\frac{1}{1-pz/(1-p)/(1-z)}
\\ = (1-p)^{b-1} [z^{b-1}] \frac{1}{(1-z)^a}
\frac{1}{1-z-pz/(1-p)}
\\ =  [z^{b-1}] \frac{1}{(1-(1-p)z)^a}
\frac{1}{1-(1-p)z-pz}
\\ = [z^{b-1}] \frac{1}{1-z} \frac{1}{(1-(1-p)z)^a}.$$
The LHS and the RHS are seen to be the same and we may conclude.
 Remark.  The  first  one  is the  easy  one  and  follows  by
inspection. The Iverson bracket may be  of interest here as an example
of the method.
</s>