Proof of a combination identity: $\sum\limits_{i=0}^m\sum\limits_{j=0}^m\binom{i+j}{i}\binom{2m-i-j}{m-i}=\frac {m+1}2\binom{2m+2}{m+1}$

Question

I'm studying the special case of question Finding expected area enclosed by the loop when $m=n$ and $A=2n$. I found $f_{n,n}(2n)=S(n-2)$, where $S$ is defined as

$$S(m)=\sum_{i=0}^m\sum_{j=0}^m\binom{i+j}{i}\binom{2m-i-j}{m-i}.$$

Wolframalpha gives $S(m)=\displaystyle\frac {m+1}2\binom{2m+2}{m+1}$. How to prove it?

Some thoughts so far:

I found that $f_{n,n}(2n)=\displaystyle\frac {n-1}2\binom{2n-2}{n-1}=\frac {n-1}2f_{n,n}(2n-1)$, so there might have a combinatorial proof for the summation.

Answer 1

Here is a combinatorial proof that $$ f_{n,n}(2n)=(2n-3)f_{n-1,n-1}(2n-3)\tag{1} $$ Note that $(1)$ is equivalent to $f_{n,n}(2n)=\frac{n-1}2\binom{2n-2}{n-1}$, after some algebraic manipulations and using the formula $f_{n-1,n-1}(2n-3)=\binom{2n-4}{n-2}.$

Every pair of nonintersecting paths from $(0,0)$ to $(n,n)$ with area $2n$ can be uniquely chosen by the following process:

• Choose a pair of paths from $(0,0)$ to $(n-1,n-1)$ with area $2n-3$.
• Select one of the $2n-3$ interior squares, and perform the "expansion" illustrated below.

The shaded box represents the selected square:

           □
           □
         □ □
         □
   □ □ ■ □
 □ □
       ⇓
             □
             □
           □ □
           □
       ■ ■ □
   □ □ ■ ■
 □ □

Answer 2

Starting from

$$\sum_{p=0}^m \sum_{q=0}^m {p+q\choose p} {2m-p-q\choose m-p} = \frac{1}{2} (m+1) {2m+2\choose m+1}$$

we obtain

$$\sum_{p=0}^m \sum_{q=0}^m {p+q\choose p} {2m-p-q\choose m-q} \\ = \sum_{p=0}^m \sum_{q=0}^m {p+q\choose p} [z^{m-q}] (1+z)^{2m-p-q} \\ = \sum_{p=0}^m [z^m] \sum_{q=0}^m {p+q\choose p} z^q (1+z)^{2m-p-q}.$$

Now when $q\gt m$ we have no contribution to the coefficient extractor and we may continue with

$$\sum_{p=0}^m [z^{m}] (1+z)^{2m-p} \sum_{q\ge 0} {p+q\choose p} z^q (1+z)^{-q} \\ = \sum_{p=0}^m [z^{m}] (1+z)^{2m-p} \frac{1}{(1-z/(1+z))^{p+1}} \\ = \sum_{p=0}^m [z^{m}] (1+z)^{2m+1} = [z^{m}] (1+z)^{2m+1} \sum_{p=0}^m 1 \\ = (m+1) {2m+1\choose m} = (m+1) \frac{m+1}{2m+2} {2m+2\choose m+1} \\ = \frac{1}{2} (m+1) {2m+2\choose m+1}.$$

This is the claim.

Here we have used the fact that when $q\le 2m-p$ we have $z^q \times (1+z)^{2m-p-q} = z^q + \cdots$ and when $q \gt 2m-p$ we again find $z^q \times 1/(1+z)^{q-(2m-p)} = z^q + \cdots,$ i.e. no pole at zero of $(1+z)^{2m-p-q}$ for all values of $q.$

Answer 3

Another possible approach is as follows.

Starting from the "Double Convolution" identity $$ \eqalign{ & \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} { \left( \matrix{ r + k \cr k \cr} \right) \left( \matrix{ s - k \cr m - k \cr} \right) } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} { \left( { - 1} \right)^{\,k} \left( \matrix{ - r - 1 \cr k \cr} \right) \left( { - 1} \right)^{\,m - k} \left( \matrix{m - s - 1 \cr m - k \cr} \right) } = \cr & = \left( { - 1} \right)^{\,m} \left( \matrix{ m - s - r - 2 \cr m \cr} \right) = \cr & = \left( \matrix{ s + r + 1 \cr m \cr} \right) \quad \left| \matrix{ \;r,s \in C \hfill \cr \;m \in Z \hfill \cr} \right. \cr } $$ where the steps are : "upper negation" $\to$ "convolution" $\to$ "upper negation".

Then $$ \eqalign{ & \sum\limits_{0\, \le \,i\, \le \,m} {\sum\limits_{0\, \le \,j\, \le \,m} {\left( \matrix{ i + j \cr i \cr} \right)\left( \matrix{ 2m - i - j \cr m - i \cr} \right)} } = \cr & = \sum\limits_{0\, \le \,j\, \le \,m} {\left( \matrix{ 2m + 1 \cr m \cr} \right)} = \left( {m + 1} \right)\left( \matrix{ 2m + 1 \cr m \cr} \right) = \cr & = \left( {m + 1} \right){{\left( {2m + 1} \right)!} \over {m!\left( {m + 1} \right)!}} = {{\left( {2m + 1} \right)!} \over {m!m!}} \cr} $$ and $$ \eqalign{ & {{m + 1} \over 2}\left( \matrix{ 2m + 2 \cr m + 1 \cr} \right) = {{\left( {m + 1} \right)} \over 2}{{\left( {2m + 2} \right)!} \over {\left( {m + 1} \right)!\left( {m + 1} \right)!}} = \cr & = {1 \over 2}{{\left( {2m + 2} \right)!} \over {\left( {m + 1} \right)!m!}} = {1 \over 2}{{\left( {2m + 2} \right)\left( {2m + 1} \right)!} \over {\left( {m + 1} \right)!m!}} = {{\left( {2m + 1} \right)!} \over {m!m!}} \cr} $$

Answer 4

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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}$

$\ds{\sum_{i = 0}^{m}\sum_{j = 0}^{m}{i + j \choose i} {2m - i - j \choose m - i} = {m + 1 \over 2}{2m + 2 \choose m + 1}:\ {\LARGE ?}}$

Note that $\ds{{2m - i - j \choose m - i} = 0}$ whenever $\ds{j > m}$. Then, \begin{align} &\bbox[10px,#ffd]{\sum_{i = 0}^{m}\sum_{j = 0}^{m}{i + j \choose i} {2m - i - j \choose m - i}} = \sum_{i = 0}^{m}\sum_{j = 0}^{\infty}{i + j \choose j} {2m - i - j \choose m - j} \\[5mm] = &\ \sum_{i = 0}^{m}\sum_{j = 0}^{\infty} \bracks{{-i - 1 \choose j}\pars{-1}^{\, j}} \bracks{{i - m - 1 \choose m - j}\pars{-1}^{m - j}} \\[5mm] = &\ \pars{-1}^{m}\sum_{i = 0}^{m}\sum_{j = 0}^{\infty} {-i - 1 \choose j}\bracks{z^{m - j}}\pars{1 + z}^{i - m - 1} \\[5mm] = &\ \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{-m - 1} \sum_{i = 0}^{m}\pars{1 + z}^{i}\sum_{j = 0}^{\infty} {-i - 1 \choose j}z^{\,j} \\[5mm] = &\ \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{-m - 1} \sum_{i = 0}^{m}\pars{1 + z}^{i}\pars{1 + z}^{-i - 1} \\[5mm] = &\ \pars{-1}^{m}\pars{m + 1}\bracks{z^{m}}\pars{1 + z}^{-m - 2} = \pars{-1}^{m}\pars{m + 1}{-m - 2 \choose m} \\[5mm] = &\ \pars{-1}^{m}\pars{m + 1}\bracks{{2m + 1 \choose m}\pars{-1}^{m}} = \pars{m + 1}{2m + 1 \choose m + 1} \\[5mm] = &\ \pars{m + 1}{\pars{2m + 1}! \over \pars{m + 1}!\, m!} = \pars{m + 1}{\pars{2m + 2}! \over \pars{m + 1}!\, \pars{m + 1}!}\, {m +1 \over 2m + 2} \\[5mm] = &\ \bbx{{m + 1 \over 2}{2m + 2 \choose m + 1}} \end{align}