# Sum of combinations

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?

-
Are you perhaps talking about the sum of the terms on the left? –  Robert Israel Nov 12 '12 at 19:45
It will be much easier to read if you use TeX formula. –  Patrick Li Nov 12 '12 at 19:49
yes Robert I am taking about the sum on L.H.S. –  user669083 Nov 12 '12 at 19:51
I have changed the index of the summation to $k$. Please make sure this is the expression you intended. –  Austin Mohr Nov 12 '12 at 20:19

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.

-

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$.

-

Got the solution from Pascal's rule

http://en.wikipedia.org/wiki/Pascal%27s_rule

Solving further is just an iteration.

-