Combinatorial proof of $\sum_{k=n}^{q-m} \binom{k}{n} \binom{q-k}{m} = \binom{q+1}{m+n+1}$ [duplicate]

Question

I have been trying to see how to combinatorially prove equation (6.97) from this document, which states that

$$\sum_{k=n}^{q-m} \binom{k}{n} \binom{q-k}{m} = \binom{q+1}{m+n+1}$$

My first thought was to take some set $S = \lbrace 1, 2, \cdots, q+1\rbrace$ and first just count the number of $(m+n+1)$-sets that can arise from it, giving the right-hand side. For the left-hand side, that would imply we need to partition $S$ in a manner that could produce the desired sum, but when I try this out for values $q = 3$, $m = n = 1$, there does not seem to be any valuable pattern going this route that I can see.

Does anyone have some hint about what combinatorial object I could use to count two ways and prove this?

Answer 1

For the LHS, first choose the $(n+1)$-th element from $n+1,\ldots,q+1-m$ (the right limit is $q+1-m$ so as to leave at least $m$ elements). Let this be $k+1$. Now you have to choose $n$ elements from $1,2,\ldots,k$ and the remaining $m$ from the remaining $q-k$ elements.