Simple binomial theorem proof: $\sum_{j=0}^{k} \binom{a+j}j = \binom{a+k+1}k$

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.

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