# how to prove $\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$ without induction?

$$\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$$

how to prove it without induction?

I tried with several way but I failed

anybody help me ?


\begin{align} \color{#00f}{\large\sum_{k = 0}^{m}{n + k \choose n}}&=\sum_{k = 0}^{m} \int_{\verts{z} = 1}{\pars{1 + z}^{n + k} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} =\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n + 1}} \sum_{k = 0}^{m}\pars{1 + z}^{n + k} \\[3mm]&=\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n + 1}}\, {\pars{1 + z}^{n}\bracks{\pars{1 + z}^{m + 1} - 1} \over \pars{1 + z} - 1} \\[3mm]&=\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\, {\pars{1 + z}^{n + m + 1} \over z^{n + 2}} -\ \overbrace{% \int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{\pars{1 + z}^{n} \over z^{n + 2}}} ^{\ds{=\ 0}} \\[3mm]&= \sum_{k = 0}^{n + m + 1}{n + m + 1 \choose k} \overbrace{\int_{\verts{z} = 1}{z^{k} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}} ^{\ds{\delta_{k,n + 1}}} =\color{#00f}{\large{n + m + 1 \choose n + 1}} \end{align}

• can you solve this question using same method math.stackexchange.com/questions/926978 – user130806 Sep 11 '14 at 17:22
• @user130806 I'll check it later. I don't know yet. Thanks. – Felix Marin Sep 13 '14 at 6:14

There is a combinatorial interpretation of both the expressions

R.H.S. counts the number of ways of picking $n+1$ distinct integer combinations from $S=\{1,2,\ldots,n+m+1\}$

L.H.S. counts the number of picking $n+1$ integers from the set $S$, by first choosing the largest integer $n+k+1$, and then choosing the rest $n$ of them from $\{1,2,\ldots,n+k\}$, for each $k=0,1,2,\ldots,m$.

• Nice interpretation! Perhaps, the largest integer must be "n+k+1"? – Hoda Mar 9 '14 at 1:48
• @Hoda you are right ... thanks for pointing it out :) – r9m Mar 9 '14 at 1:51

Another method:

$$\sum_{k=0}^{m}\binom{n+k}{n}$$

Setting $$n+k \mapsto k$$ and using Hockey-stick identity follows:

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