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

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?

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.