cómo demostrar $\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$ ¿sin inducción?

Question

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

¿cómo demostrarlo sin inducción?

Lo he intentado de varias maneras pero he fracasado

¿alguien me ayuda?

Answer 1

Existe una interpretación combinatoria de ambas expresiones

R.H.S. cuenta el número de formas de elegir $n+1$ combinaciones enteras distintas de $S=\{1,2,\ldots,n+m+1\}$

L.H.S. cuenta el número de recogidas $n+1$ enteros del conjunto $S$ eligiendo primero el mayor número entero $n+k+1$ y luego elegir el resto $n$ de ellos de $\{1,2,\ldots,n+k\}$ para cada $k=0,1,2,\ldots,m$ .

Answer 2

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

Answer 3

Otro método:

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

Configurar $n+k \mapsto k$ y utilizando Identidad del palo de hockey sigue:

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