# Combinatorics - binary - very interesting question

I tried to solve this problem without any success. I really hope that you will know the answer.
$f(n,m)$ presents the number of binary strings (empty string included) that include at most n times '1', and at most m times '0'.

Prove:
$$f(n,m) = \binom{n+m+2}{n+1}-1$$

-
We have $f(1,0) = 1$, but your formula gives $2$. Are you sure it's right? Edit: This was in answer to the original version of the question, before it was edited. – user155747 Jun 7 '14 at 8:52
Shouldn't it have have something to do with powers of two? – tpb261 Jun 7 '14 at 8:53

Here's the answer. Consider the number $g(n,k)$ of binary strings with exactly $k$ zeros (and at most $n$ ones). These strings can have $0,1,\ldots,n$ ones, i.e., they may look as follows

$$\underbrace{0\cdots 0}_{k \text{ times}},\qquad \underbrace{0\cdots 0}_{k \text{ times}}1,\qquad \underbrace{0\cdots 0}_{k \text{ times}}11,\:\ldots,\:\underbrace{0\cdots 0}_{k \text{ times}}\underbrace{11\ldots 1}_{n \text{ times}}$$

Of course, each time, we may distribute the $k$ zeros among a total of $k+j$ digits, for $j=0,\ldots,n$. Thus, this number is given as

$$g(n,k)=\sum_{j=0}^n\binom{k+j}{k}$$

It is well-known that (**)

$$\binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{k+n}{k}=\binom{k+n+1}{k+1},$$

and thus,

$$g(n,k)=\sum_{j=0}^n\binom{k+j}{k}=\binom{k+n+1}{k+1}=\binom{k+n+1}{n}.$$

Now, your strings may have between $0$ and $m$ zeros. Thus, the solution to your problem is

$$f(n,m)=\sum_{k=0}^m g(n,k)=\sum_{k=0}^m\binom{k+n+1}{n}=\binom{n+1}{n}+\cdots+\binom{n+m+1}{n}$$

and applying (**) again yields

$$f(n,m)=\binom{n+m+2}{n+1}-\binom{n}{n}=\binom{n+m+2}{n+1}-1.$$

EDIT To prove (**), you can telescope. Note that $\binom{k+j}{k}=\binom{k+j+1}{k+1}-\binom{k+j}{k+1}$, so

$$\sum_{j=0}^n\binom{k+j}{k}=\sum_{j=0}^n(\binom{k+j+1}{k+1}-\binom{k+j}{k+1})=\binom{k+n+1}{k+1}-\binom{k}{k+1}=\binom{k+n+1}{k+1}.$$

-