# How to perform the summation/addition of binomial coefficients?

From my textbook:

\begin{align} \sum_{k=0}^n \binom {m+k}m &= \binom {m+n}m + \sum_{k=0}^{n-1} \binom {m+k}m\\\\\\ &= \binom {m+n}m + \binom {m+n}{m+1}\\\\\\ &= \binom {m+1+n}{m+1} \end{align}

I can't understand (1) how the summation works for binomial (the second one, where the ending index is $n-1$) and (2) how the addition works.

Regarding the addition, should I always write down the expression and do calculations, or there is a simple formula (maybe the Pascal's rule)?

\begin{align} \binom {m+n}m + \binom {m+n}{m+1} &= \frac {(m+n)!}{m!(m+n-m)!} + \frac {(m+n)!}{(m+1)!(m+n-m-1)!}\\\\\\ &= \frac {(m+n)!}{m!n!} + \frac {(m+n)!}{(m+1)!(m+n-1)!}\\\\\\ &= \dots \end{align}

Let’s take a look:

\begin{align} \sum_{k=0}^n \binom {m+k}m &= \binom {m+n}m + \sum_{k=0}^{n-1} \binom {m+k}m\\\\\\ &= \binom {m+n}m + \binom {m+n}{m+1}\\\\\\ &= \binom {m+1+n}{m+1} \end{align}

This is part of a proof by induction that

$$\sum_{k=0}^n\binom{m+k}m=\binom{m+1+n}{m+1}\tag{1}$$

for all $n\in\Bbb N$. Let $P(n)$ be the specific assertion in $(1)$, that the identity is true for the particular value $n$. Then the calculation above is the induction step: the induction hypothesis is that $P(n-1)$ is true, and we’re showing that this implies that $P(n)$ is true. $P(n-1)$, written out in full, is that

$$\sum_{k=0}^{n-1}\binom{m+k}m=\binom{m+1+(n-1)}{m+1}=\binom{m+n}{m+1}\;;\tag{2}$$

we’ll use this in a moment.

The first equality in the calculation is simply splitting the $k=n$ term off from the rest of the summation. The second step uses $(2)$, the induction hypothesis, to replace $\sum_{k=0}^{n-1}\binom{m+k}m$ by its value $\binom{m+n}{m+1}$. And the third and last equality is just Pascal’s identity, which in its general form states that

$$\binom{n+1}k=\binom{n}k+\binom{n}{k-1}\;.\tag{3}$$

This can be proved either combinatorially or algebraically, as you set out to do with the special case needed for the calculation here. If you’re going to prove it algebraically, though, it’s easier to prove the general form $(3)$ and then substitute into it to get the special case that you need.

• Thanks. But I still can't understand why $\sum_{k=0}^{n-1} \binom {m+k}m = \binom {m+n}{m+1}$. – user34295 Apr 4 '13 at 11:00