Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
okay. Thanks Brian!. i wil try now. :) –  doniyor Dec 9 '12 at 21:13
1  
@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
add comment

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

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

Your Answer

 
discard

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.