Find my mistake: Prove $\sum_{i=0}^{r} \sum_{j=0}^{c} \binom{i+j}{j}=\binom{r+c+2}{c+1}-1$

Question

I want to prove $\sum_{i=0}^{r} \sum_{j=0}^{c} \binom{i+j}{j}=\binom{r+c+2}{c+1}-1$, but the result is different. What is wrong?

$$\begin{align} &\sum_{i=0}^{r} \sum_{j=0}^{c} \binom{i+j}{j}\\ =&\sum_{i=0}^{r} \sum_{j=0}^{c} [x^j]\frac{1}{(1-x)^{i-1}} \\ =&\sum_{j=0}^{c} [x^{j}] \frac{1-\frac{1}{(1-x)^{r}}}{x} \\ =&[x^{c}] \frac{\frac{1}{1-x}-\frac{1}{(1-x)^{r+1}}}{x} \\ =&\binom{r+c+2}{c+1}\\ \end{align}$$

Answer 1

If a proof using coefficient extractors is desired we may proceed as follows:

$$\sum_{p=0}^n \sum_{q=0}^m {p+q\choose q} = \sum_{p=0}^n \sum_{q\ge 0} {p+q\choose q} [[0\le q\le m]] \\ = \sum_{p=0}^n \sum_{q\ge 0} {p+q\choose q} [z^m] \frac{z^q}{1-z} = [z^m] \frac{1}{1-z} \sum_{p=0}^n \sum_{q\ge 0} {p+q\choose q} z^q \\ = [z^m] \frac{1}{1-z} \sum_{p=0}^n \frac{1}{(1-z)^{p+1}} = [z^m] \frac{1}{(1-z)^2} \sum_{p=0}^n \frac{1}{(1-z)^{p}} \\ = [z^m] \frac{1}{(1-z)^2} \frac{1/(1-z)^{n+1}-1}{1/(1-z)-1} = [z^m] \frac{1}{1-z} \frac{1/(1-z)^{n+1}-1}{z} \\ = [z^{m+1}] \frac{1}{1-z} (1/(1-z)^{n+1}-1) = -1 + [z^{m+1}] \frac{1}{(1-z)^{n+2}} \\ = -1 + {m+1+n+1\choose n+1}.$$

This is

$$\bbox[5px,border:2px solid #00A000]{ -1 + {m+n+2\choose n+1}}$$

as claimed.

Answer 2

In this sort of calculation, it’s usually a good idea to look for the simplest example and check each step using it. In the present case, the simplest example is $r=c=0$. Going through the steps in the displayed equations, you can see that the value is $1$ in the first line, still $1$ in the second line, but then $0$ in the third line. So there must actually be two mistakes, since in the last line the value is $2$.

I'm not sure how you arrived at the third line; I get

\begin{eqnarray} \sum_{i=0}^r\frac1{(1-x)^{i-1}} &=& (1-x)\sum_{i=0}^r\frac1{(1-x)^i} \\ &=& (1-x)\frac{1-\frac1{(1-x)^{r+1}}}{1-\frac1{1-x}} \\ &=& -(1-x)^2\frac{1-\frac1{(1-x)^{r+1}}}x\;. \end{eqnarray}

Answer 3

Here's a direct proof: \begin{align} \sum_{i=0}^{r} \sum_{j=0}^{c} \binom{i+j}{j} &=\sum_{i=0}^{r} \sum_{j=0}^{c} \binom{i+j}{i}\\ &=\sum_{i=0}^{r} \binom{i+c+1}{i+1}\\ &=\sum_{i=0}^{r} \binom{i+c+1}{c}\\ &=\sum_{i=1}^{r+1} \binom{i+c}{c}\\ &=\sum_{i=0}^{r+1} \binom{i+c}{c}-\binom{0+c}{c}\\ &=\binom{r+c+2}{c+1}-1 \end{align}