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}$ 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.
 A: 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} 
$$
A: 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.$
A: 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:
           □
           □
         □ □
         □
   □ □ ■ □
 □ □
       ⇓
             □
             □
           □ □
           □
       ■ ■ □
   □ □ ■ ■
 □ □

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