# Prove that $\sum_{i = n - b}^{a - m} {a - i \choose m}{b + i \choose n} = {a + b + 1 \choose m + n + 1}$

Restrictions on the variables for this identity are as follows: $a \geq m \geq 0$ and $n \geq b \geq 0$.

I have not gotten far with this, but these are my very rudimentary thoughts: We need to define a special element, somehow, and then carve up the $m + n$ remaining elements to be chosen out of the remaining pool of $a + b$ elements by writing $a + b = a - i + b + i$. From the $a - i$ pile, we choose $m$ things. From the $b + i$ pile, we choose $n$ things. My problem is, what is going on with this special element? How is it being defined so as to split things in this precise way?

A hint would be great for the moment.

• facepalm Yeah, there are restrictions. I will edit to update. Might be somewhat important... – BMac Oct 7 '17 at 21:59
• It is, indeed, a typo. I will fix it. – BMac Oct 7 '17 at 22:05
• The typo had me really confused! Anyway, new hint: try drawing $a+b+1$ balls and colouring $m+n+1$ of them black, and then notice where the $m+1$th black ball is and what the indices of the summation are? That should give you the intuition, then for a more formal proof should be quite easy. – mdave16 Oct 7 '17 at 22:07
• So, I lay out my $a + b + 1$ balls in a row, but I can pick the $m + n + 1$ to be colored black from anywhere in that row. So when you say "$m + 1$th black ball," are we counting from left to right? – BMac Oct 7 '17 at 22:13
• I look forward to seeing it and comparing with what I'm working on. I am beginning to see your intuition. I drew an example with bigger numbers and am seeing that the number of summands equals the total number of places where the $m + 1$th ball could show up, counting from the left.Slot $n$ is the last slot where it could appear, otherwise there are not enough left to create our sample of $m + n + 1$. – BMac Oct 7 '17 at 22:33

Combinatorial story

You have been tasked to pick $m+n+1$ books from a bookshelf of $a + b + 1$. You wonder of all the possibilities you could pick. Simple combinatorics tells us the answer is ${a+b+1}\choose{m+n+1}$.

However, you see another solution. You could pick a book in the middle and then take $m$ books of the left of it and $n$ books of the right of it. But you wonder, which books in the middle can you pick?

$$\sum_{\text{middle book place}} [\text{m books on left}]\times[\text{n books on right}]$$

Now, let's fill in this more concretely. Let's say the middle book is in the $j^{\text{th}}$ position. The middle book can essentially be anywhere. Now, the ways you can pick $m$ books on left will be $\text{# books on left} \choose m$. Likewise for $n$ books on right. The books on the left of $j$ will be $j-1$ many, books on the right will be $a+b+1-j$. However, notice that when there are less than $m$ books on the left, there are no ways to pick, so we don't need to count them in the index. Same for $n$ on the right. Now we can change the index. I've taken care of each change with a new line :). The last line is in my opinion the most tricky, but try and denote the shift with $i = -j + a + 1$. I worked out the shift, almost by cheating, since I know what I wanted to mold the answer to be. One could argue there is another final step, noting that addition is commutative and so we can swap the end points of summation.

\begin{align} &\sum_{j = 1}^{a+b+1} {{\text{# books on left} \choose {m}} \cdot {{\text{# books on right} \choose {n}}} }\\ = &\sum_{j = 1}^{a+b+1} {{j-1 \choose {m}} \cdot {{a+b+1-j \choose {n}}} } \\ = &\sum_{j = m+1}^{a+b+1-n} {{j-1 \choose {m}} \cdot {{a+b+1-j \choose {n}}} } \\ = &\sum_{i = a - m}^{n-b} {{a-i \choose {m}} \cdot {{b+i \choose {n}}} } \\ \end{align}

In my opinion, combinatorial story is a very powerful method of understanding combinatorics. Another common technique is to prove it by pure messy unadulterated algebra (not the good kind). I was going to originally prove it with both methods for comparison, but the latter was too messy for me.

You can prove this statement using lattice walks from $(0,0)$ to $(m+n+1, a+b-m-n)$ with $(1,0)$ and $(0,1)$ steps. There are $$\binom{a+b+1}{m+n+1}$$ such walks.

Classify such walks based on the highest $y$-coordinate where they touch the vertical line $x=n$. Counting this way we get the sum $$\binom{n}{n}\binom{a+b-n}{m}+\binom{n+1}{n}\binom{a+b-n-1}{m}+\dotsb+\binom{a+b-m}{n}\binom{m}{m} \tag{1}$$ since we go from the point $(0,0)$ to $(n,k)$ for $0\leq k\leq a+b-m-n$ and then we are forced to go one unit right and then go from $(n+1,k)$ to $(m+n+1, a+b-m-n)$.

But the sum in (1) is exactly $$\sum_{i = n - b}^{a - m} {a - i \choose m}{b + i \choose n}$$ as desired.