General strategies for evaluating sums in probabilistic/combinatoric problems: $\sum_n\sum_m {n+m \choose n}p^{n+m}(1-p)^{n+m}$

Question

I have encountered the following summation:

$$p^2\cdot \sum_{n=0}^\infty\sum_{m=0}^\infty {n+m \choose n}p^{n+m}(1-p)^{n+m}$$

This summation arises from naive analysis of this simple probability question:

"Player A plays a match against Player B, and the winner of the match gets a point. Independent matches are repeated until one player is declared the winner by having 2 more points than the other. What is $P(A\text{ wins})$ where $p$ is the likelihood player A wins a match?"

Part of this summation looks very similar to the summation that results from the binomial identity.

---

I missed out on a comprehensive treatment of evaluation of sums and series. I learned a few standard gimmicks like identifying geometric series, Gauss's triangle trick and $\sum_{k=1}^n {n\choose k}=2^n$, but not enough to be completely lost in approaching perturbations of the 'nice' cases like these.

It is somewhat bothering that at this point integrals seem easier to evaluate than summations which are more fundamental and in fact what integration is built off of.

As a general strategy, how does one approach this type of sum?

Answer 1

\begin{equation} \begin{split} \sum_{m \geq 0}\sum_{n \geq 0}\binom{m + n}{n} p^{m + n} (1-p)^{m+n} &\stackrel{(1)}{=} \sum_{m \geq 0}\sum_{n \geq 0}\binom{m}{n} p^m (1-p)^m\\ &\stackrel{(2)}{=} \sum_{m \geq 0}\sum_{n = 0}^m\binom{m}{n} p^m (1-p)^m \\ &\stackrel{(3)}{=} \sum_{m \geq 0} p^m (1-p)^m\sum_{n = 0}^m\binom{m}{n} \\ &= \sum_{m \geq 0} p^m(1-p)^m2^m \\ &= \frac{1}{1 - 2p(1-p)} \\ &= \frac{1}{2p^2 - 2p + 1} \end{split} \end{equation}

Reasons:

$(1)$: Let $q = m + n$, change the index $m$ of the sum to $q$, adjust the sum limits, then rename $q$ as $m$.

$(2)$: $\binom{m}{n} = 0$ if $m, n \in \mathbb{N}_0$ and $n > m$.

$(3)$: Filter out the part that depends on only $n$.

---

I don't know any general method that applies to all sums of this kind. This is very much trial and error. After some time, you get a feel of what should work.

There are of course many techniques, some originating in Combinatorics (eg. formal power series), that handles specific kinds. If you are interested, I can probably point out some resources.

Also, in my opinion, integration is indeed much easier to handle than sums. Granted it is not fundamental, but because of that very reason, there are many more techniques available. In fact, there is an integral test for convergence of infinite series.

Answer 2

Put $q=p(1-p)$ and use the fact that $$\sum_{r=0}^\infty\binom{a+r}a x^r=\frac 1{(1-x)^{a+1}}$$ .

Hence $$\begin{align} p^2\sum_{n=0}^\infty\sum_{m=0}^\infty\binom {n+m}np^{n+m}(1-p)^{n+m} &=p^2\sum_{n=0}^\infty q^n\sum_{m=0}^\infty\binom {n+m}nq^m\\ &=p^2\sum_{n=0}^\infty q^n\cdot \frac 1{(1-q)^{n+1}}\\ &=\frac {p^2}{1-q}\sum_{n=0}^\infty\left(\frac {q}{1-q}\right)^n\\ &=\frac {p^2}{1-q} \cdot\frac 1{1-\frac q{1-q}}\\ &=\frac {p^2}{1-2q}\\ &=\frac {p^2}{2p^2-2p+1}\qquad\blacksquare \end{align}$$