I need to prove the following equality: $$\sum_{j=k}^{n-m}{j\choose k}{n-j \choose m} = {n+1 \choose k+m+1}$$ That is what I came up with:
Say we have a fence with $n$ sections and $n+1$ posts. We want to color $k+m$ of the sections.
On LHS We choose a fence post between the $k$th and the $(n-m)$th. On its left there are at least $k$ sections, we color $k$ of them. On its right there are at least $m$ sections, we color $m$ of them.
On RHS we choose $k+m+1$ fence posts. For the $k$ posts on the left, we color the the section adjacent to them on the right. The $(k+1)$th post divides the $k$ and the $m$ posts, as we did before. Then we remain with $m$ posts. We will color the sections adjacent to them on the left.
These are two different ways to count the same thing, thus equality. $\square$
Yes, your proof is correct. A slightly simpler way of expressing the same basic idea would be: The right-hand side counts the subsets of $[n+1]$ with $k+m+1$ elements. The left-hand side counts the same thing by enumerating the subsets according to their $(k+1)$-th smallest element $j+1$, which can be anything from $k+1$ to $n-m+1$, with $k$ elements chosen from the $j$ elements below it and $m$ elements chosen from the $n-j$ elements above it.