Sums of binomial coefficients in which lower index remains fixed

Question

How can I prove that $ \sum_{k=1}^{m} {{k+n} \choose {n+1}} = {{ m + n + 1 } \choose {n+2}} $?

I have managed to prove that $ \sum_{k=0}^{m} {{k+n} \choose {n}} = {{ m + n + 1 } \choose {n+1}} $

Although it seams intuitive that the second implies the first, I haven't been able to deal with the extra +1.

Thanks in advance

Answer 1

Note that $$\sum_{k=1}^{m} {{k+n} \choose {n+1}}=\sum_{k=1}^{m} {{k-1+n+1} \choose {n+1}}=\sum_{j=0}^{m-1} {{j+n+1} \choose {n+1}}={{ (m-1) + (n+1) + 1 } \choose {(n+1)+1}}$$ where at the last step we use the identity you have already proved.

Answer 2

The given sum $$S=\sum_{k=1}^{n} {k+n \choose n+1}$$ is nothing but coefficient of $x^{n+1}$ in $$(1+x)^{n+1}+(1+x)^{n+2}+(1+x)^{n+3}+....+(1+x)^{n+m}$$ $$=(1+x)^{n+1} [1+(1+x)^1+(1+x)^2+(1+x)^3+...+(1+x)^{m-1}]$$ $$=(1+x)^{n+1}\left(\frac{(1+x)^{m}-1}{1+x-1}\right).$$ So S= coefficient of $x^{n+2}$ in $$ [(1+x)^{n+m+1}- (1+x)^{n+1}] ={n+m+1 \choose n+2}. $$

Answer 3

Here is a nice combinatorial approach:

Suppose we have to choose $(n+2)$ boys out of $(m+n+1)$ boys which obviously can be done in ${m+n+1} \choose {n+2}$ ways. Suppose all these boys are of different ages. Also note that each of these groups has a unique youngest memeber.

Now , we are gonna do the same selection but in a different way. We first arrange the $(m+n+1)$ boys in ascending order of their ages. Then

• we count the no of groups of boys which contain the youngest member, which can be done in ${m+n} \choose {n+1}$ ways(because the youngest boy has already been choosen and we have to choose $(n+1)$ more).

• next, we count the no of groups of boys which contain the second-most youngest member, which can be done in ${m+n-1} \choose {n+1}$ ways( note that these groups can not contain the youngest member)

• ...

• ...

• lastly we count the no of groups of boys which contain the $m$-th youngest memeber, which can be done in ${n+1} \choose {n+1}$ ways (note that we always have to choose atleast one member whose age is less than or equal to the $m$-th youngest member).

  Now we sum up all the number of groups to get the final result. Thus we have proved-

  $$ \sum_{k=1}^{m} {{k+n} \choose {n+1}} = {{ m + n + 1 } \choose {n+2}} $$