Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Got the solution from Pascal's rule

Solving further is just an iteration.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.