Trying to prove, for all $k$ and $n$, $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}.$
I have tried solving it through induction, but is there a cleaner non-induction based solution to this?
Trying to prove, for all $k$ and $n$, $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}.$
I have tried solving it through induction, but is there a cleaner non-induction based solution to this?
Got the solution from Pascal's rule
http://en.wikipedia.org/wiki/Pascal%27s_rule
Solving further is just an iteration.
In choosing a set of $m+1$ items from $1,2,\ldots,n+1$, the largest could be $k+1$ where $k$ is anywhere from $m$ to $n$; then you can choose any $m$ items from $1$ to $k$.
Let $C(n,m)=n!/(m!(n-m)!)$. Use the identity: $C(k,m)=C(k+1,m+1)-C(k,m+1)$, then use the method of differences to find your sum.