# Algebraic proof for the following identity

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.

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

$$\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?

• I was just about to give that. +1 – robjohn Apr 2 '14 at 20:19
• 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! – User38 Apr 2 '14 at 20:30
• I guess I was mistakenly given the acceptance. Tag, you're it! – robjohn Apr 3 '14 at 0:31

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}

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