$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.
Best Answer
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.