0
$\begingroup$

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?

  • 0
    Are you perhaps talking about the sum of the terms on the left?2012-11-12
  • 0
    It will be much easier to read if you use TeX formula.2012-11-12
  • 0
    yes Robert I am taking about the sum on L.H.S.2012-11-12
  • 0
    I have changed the index of the summation to $k$. Please make sure this is the expression you intended.2012-11-12

3 Answers 3

0

Got the solution from Pascal's rule

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

Solving further is just an iteration.

4

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

2

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.