Number of binary strings with $n$ ones and $m$ zeros $f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros.
Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$
I got to the point that:
$$\sum_{a=0}^n \sum_{b=0}^m {a+b \choose a}$$
And I also understand that there are $(n+1)$ options for the amount of ones and $(m+1)$ options for the amount of zeros.
 A: Let $S$ be the set of binary strings of length $n+m+2$ with $n+1$ ones and $m+1$ zeroes.  By definition, $$|S|=\binom{n+m+2}{n+1}.$$
Let $L \in S$.  Let $\beta$ be the bit in the last place of $L$ and $\overline{\beta}$ be the complement of $\beta$.
Since $n \geq 0$ and $m \geq 0$, we know $L$ has the form $$L=(\text{substring } X,\overbrace{\overline{\beta},\overline{\beta},\ldots,\overline{\beta}}^i,\overbrace{\beta,\beta,\ldots,\beta}^j)$$ where $i \geq 1$ (and $i$ is the maximum such positive integer possible) and $j \geq 1$.  We observe:


*

*The substring $X$ obtained is a binary string with at most $n$ ones and at most $m$ zeroes.

*Every non-empty binary string $X$ with at most $n$ ones and at most $m$ zeroes can be obtained uniquely in this way (by appending ones and zeroes to it in the appropriate way).

*The empty binary string $X$ can be obtained in exactly two ways.
Hence there are $|S|-1$ binary strings with at most $n$ ones and at most $m$ zeroes.
A: As remarked by Daniel Fischer above, you can apply the "hockey stick" identities to find your sum; these are the sums going down the diagonals of Pascal's triangle:
For the inner sum, use
$\binom{a}{a}+\binom{a+1}{a}+\binom{a+2}{a}+\cdots+\binom{a+m}{a}=\binom{a+m+1}{a+1}$; 
and for the outer sum, use
$\binom{m+1}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\cdots+\binom{m+n+1}{n+1}=\binom{m+n+2}{n+1}$.
(The first sum goes down a right-to-left diagonal, and
the second sum goes down a left-to-right diagonal.)
A: We can find the sum by generating functions
\begin{align*}
  \sum_{b=0}^{m} \binom{a+b}{b} &= [x^m] \frac{1}{(1-x)}\frac{1}{(1-x)^{a+1}} \\
  \implies \sum_{a=0}^{n} \sum_{b=0}^{m} \binom{a+b}{b} &= [x^m]\sum_{a=0}^{n}\frac{1}{(1-x)^{a+2}} \\
  &= [x^m]\left(\frac{1}{x\left(1-x\right)^{n+2}}-\frac{1}{x\left(1-x\right)}\right) \\
    &= \binom{m+n+2}{m+1}-1
\end{align*}
