# simple binomial theorem proof

I am trying to prove this binomial statement:

For $a \in \mathbb{C}$ and $k \in \mathbb{N_0}$, $\sum_{j=0}^{k} {a+j \choose j} = {a+k+1 \choose k}.$

I am stuck where and how to start. My steps are these:

${a+j \choose j} = \frac{(a+j)!}{j!(a+j-j)!} = \frac{(a+j)!}{j!a!}$ but now I dont know how to go further to show the equality.

Or I said: $\sum_{j=0}^{k} {a+j \choose j} = {a+k \choose k} +\sum_{j=0}^{k-1} {a+j \choose j} = [help!] = {a+k+1 \choose k}$

Thanks for help!

-

One way to prove that

$$\sum_{j=0}^k\binom{a+j}j=\binom{a+k+1}k\tag{1}$$

is by induction on $k$. You can easily check the $k=0$ case. Now assume $(1)$, and try to show that

$$\sum_{j=0}^{k+1}\binom{a+j}j=\binom{a+(k+1)+1}{k+1}=\binom{a+k+2}{k+1}\;.$$

To get you started, clearly

\begin{align*} \sum_{j=0}^{k+1}\binom{a+j}j&=\binom{a+k+1}{k+1}+\sum_{j=0}^k\binom{a+j}j\\ &=\binom{a+k+1}{k+1}+\binom{a+k+1}k \end{align*}

by the induction hypothesis, so all that remains is to show that

$$\binom{a+k+1}{k+1}+\binom{a+k+1}k=\binom{a+k+2}{k+1}\;,$$

which should be very easy.

It’s also possible to give a combinatorial proof. Note that $\binom{a+j}j=\binom{a+j}a$ and $\binom{a+k+1}k=\binom{a+k+1}{a+1}$. Thus, the righthand side of $(1)$ is the number of ways to choose $a+1$ numbers from the set $\{1,\dots,a+k+1\}$. We can divide these choices into $k+1$ categories according to the largest number chosen. Suppose that the largest number chosen is $\ell$; then the remaining $a$ numbers must be chosen from $\{1,\dots,\ell-1\}$, something that can be done in $\binom{\ell-1}a$ ways. The largest of the $a+1$ numbers can be any of the numbers $a+1,\dots,a+k+1$, so $\ell-1$ ranges from $a$ through $a+k$. Letting $j=\ell-1$, we see that the number of ways to choose the $a+1$ numbers is given by the lefthand side of $(1)$: the term $\binom{a+j}j=\binom{a+j}a$ is the number of ways to make the choice if $a+j+1$ is the largest of the $a+1$ numbers.

-
okay. Thanks Brian!. i wil try now. :) – doniyor Dec 9 '12 at 21:13
@doniyor: You’re welcome! (And I’ve added the combinatorial proof; you’ll probably be asked at some point to come up with a combinatorial argument or two, and the more of them you see, the easier it will be.) – Brian M. Scott Dec 9 '12 at 21:18
great, many thanks Brian. wonderful explanation! – doniyor Dec 9 '12 at 21:23

Look for Pascal's rule "http://en.wikipedia.org/wiki/Pascal's_rule". After this it is easy.

-
many thanks. :) – doniyor Dec 9 '12 at 21:09