Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 7 down vote accepted

One way to prove that


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


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


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.

share|cite|improve this answer
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 "'s_rule". After this it is easy.

share|cite|improve this answer
many thanks. :) – doniyor Dec 9 '12 at 21:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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