2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

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.