Show that $\sum_{r=0}^{n}\binom{n}{r}\binom{m+r}{n}= \sum_{r=0}^{n}\binom{n}{r}\binom{m}{r}2^r$

Question

Here $\binom{a}{b}$ is the number of ways in which $b$ objects can be chosen from a collection of $a$ distinct objects.

Show that: $$\binom{n}{0}\binom{m}{n}+\binom{n}{1}\binom{m+1}{n}+\binom{n}{2}\binom{m+2}{n}+ ...+\binom{n}{n}\binom{m+n}{n}$$

is equal to the series $$\binom{n}{0}\binom{m}{0}+\binom{n}{1}\binom{m}{1}2+\binom{n}{2}\binom{m}{2}2^2+...+\binom{n}{n}\binom{m}{n}2^n$$

I tried to find a combinatorical proof, but cannot find a suitable bijection

Answer 1

Maybe this counts as a (analytic) combinatorial proof: $$ \begin{eqnarray*}S(m,n)=\sum_{r=0}^{n}\binom{n}{r}2^r \binom{m}{m-r} &=& [x^m]\left[\left(\sum_{r\geq 0}\binom{n}{r}2^r x^r\right)\cdot\left(\sum_{r\geq 0}\binom{m}{r}x^r\right)\right]\\&=&[x^m]\left[(2x+1)^n (x+1)^m\right]\\&=&[x^m]\left[(x+(x+1))^n (x+1)^m\right]\\&=&[x^m]\sum_{r=0}^{n}\binom{n}{r}(x+1)^{r+m} x^{n-r}\\&=&\sum_{r=0}^{n}\binom{n}{r}[x^{m+r-n}](x+1)^{r+m}\\&=&\sum_{r=0}^{n}\binom{n}{r}\binom{m+r}{n}.\end{eqnarray*}$$

Answer 2

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\, #2 \,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$

\begin{align} \color{#f00}{\sum_{r = 0}^{n}{n \choose r}{m + r \choose n}} & = \sum_{r = 0}^{n}{n \choose r} \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{m + r} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{m} \over z^{n + 1}} \sum_{r = 0}^{n}{n \choose r}\pars{1 + z}^{r}\,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{m}\pars{2 + z}^{n} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} \\[3mm] & = 2^{n}\sum_{r = 0}^{m}{m \choose r} \sum_{r' = 0}^{n}{n \choose r'}{1 \over 2^{r'}} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n - r - r' + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] & = 2^{n}\sum_{r = 0}^{m}{m \choose r} \sum_{r' = 0}^{n}{n \choose r'}{\delta_{r',n - r} \over 2^{r'}} \\[3mm] & = 2^{n}\sum_{r = 0}^{m}{m \choose r}{n \choose n - r}{1 \over 2^{n - r}} \sum_{r' = 0}^{n}\delta_{r',n - r}\tag{1} \end{align}

However, $$ \sum_{r' = 0}^{n}\delta_{r',n - r} = \left\lbrace\begin{array}{l} \ds{1\quad\mbox{if}\quad 0\ \leq\ n - r\ \leq\ n} \\[1mm] \ds{0}\quad\mbox{otherwise} \end{array}\right. $$

such that $\pars{1}$ becomes $$ \color{#f00}{\sum_{r = 0}^{n}{n \choose r}{m + r \choose n}} = \color{#f00}{\sum_{r = 0}^{\min\braces{m,n}}{m \choose r}{n \choose r}2^{r}} $$