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