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 ?
 A: 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$.
A: $\newcommand{\+}{^{\dagger}}
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\down}{\downarrow}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\isdiv}{\,\left.\right\vert\,}
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left( #1 \right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}
 \newcommand{\wt}[1]{\widetilde{#1}}$
$\ds{\sum_{k = 0}^{m}{n + k \choose n} = {n + m + 1 \choose n + 1}:\ {\large ?}}$

\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}

A: 
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}$$
