How do I prove this identity
$$\sum_{k=0}^{n}{\binom{m+k-1}{k}}=\binom{m+n}{n}$$
Can anybody also shed some light on intuition (may be a double counting proof) about how right hand side of the identity turns out to be the total number of multichoose possible over n items.
Consider the set $[m+n]=\{1,2\cdots m+n\}$. If you take a size $n$ subset $S$ from this $[m+n]$, it will contain the first $n-k$ integers for some $k$ where $0\leq k\leq n$, but not the $n-k+1$th element.
If I know that a size $n$ subset contains the first $n-k$ elements, then I can only choose the last $k$ elements. Furthermore, I have to choose from $m+n-(n-k)=m+k$ elements, since the first $n-k$ have already been included. This is slightly off from what's on the left hand side. This is why I also required that the subset have the first $n-k$ elements, but not the $n-k+1$th, as I also have to exclude that element from my choices when I fill in the rest of the set. This means I can fill in the rest of the set ${m+k-1\choose k}$ ways.
This added condition is important, since it negates double counting- I look for the largest $n-k$ such that my set contains those elements, so there's only one such $k$ for each set. The left side of that identity counts those subsets for all possible $k$, which gives our identity.