1
$\begingroup$

Give an algebraic proof that $\binom{n+1}{m+1} = \sum_{k=m}^{n} \binom{k}{m}$.

I've tried using Pascal's rule and looking for a telescopic sum, but I can't find one.

Any help is appreciated.

$\endgroup$
3
$\begingroup$

I've tried using Pascal's rule and looking for a telescopic sum,

How about

$$\binom{k}{m} + \binom{k}{m+1} = \binom{k+1}{m+1},$$

which transforms to

$$\binom{k}{m} = \binom{k+1}{m+1} - \binom{k}{m+1}$$

to nicely telescope?

$\endgroup$
  • $\begingroup$ I was just about to give that. +1 $\endgroup$ – robjohn Apr 2 '14 at 20:19
  • $\begingroup$ Ahh of course! I get it that it is equal to (n+1 choose m+1) -(m choose m+1) which is zero. Hence it is equal to (n+1 choose m+1). Thanks! $\endgroup$ – User38 Apr 2 '14 at 20:30
  • 1
    $\begingroup$ I guess I was mistakenly given the acceptance. Tag, you're it! $\endgroup$ – robjohn Apr 3 '14 at 0:31
3
$\begingroup$

By the Binomial Theorem, we have $$ \begin{align} \color{#C00000}{\sum_{k=0}^n(1+x)^k} &=\sum_{k=0}^n\sum_{j=0}^k\binom{k}{j}x^j\\ &=\sum_{j=0}^n\color{#00A000}{\sum_{k=j}^n\binom{k}{j}}x^j \end{align} $$ By the formula for the sum of a geometric series, we also have $$ \begin{align} \color{#C00000}{\frac{(1+x)^{n+1}-1}{x}} &=\sum_{j=0}^n\color{#00A000}{\binom{n+1}{j+1}}x^j \end{align} $$

$\endgroup$
  • $\begingroup$ You found an excellent replacement for the telescoping sum. $\endgroup$ – Daniel Fischer Apr 2 '14 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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