%pererya.tex:
%%a Plain TeX file by Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
A (Human!) Proof of A Conjectured Triple Sum Identity Made By Juan Sebasti\'an Pereyra 
}
\rm
\bigskip
\centerline{ {\it
Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/} .
March 5, 2013.
Exclusively publised in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger.
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/pj.html} .
Supported in part by the NSF.
}
}

In [P] the following conjecture was made
$$
\sum_{i=1}^n \left [ i^2 \sum_{k=0}^m \left ( {{i-1} \choose {m-k}} {{n-i} \choose {k}} \right )^2 \right ]+
$$
$$
2 \sum_{j=1}^m
\left [ 
\sum_{i=1}^{n-j} i(i+j) \left ( \sum_{k=j}^m
{{i+j-1} \choose {k}} {{n-(i+j)} \choose {m-k}} {{n-i} \choose {m-k+j}} {{i-1} \choose {k-j}}
\right )
\right ]
$$
is equal to
$$
{{n+1} \choose {m}}^2 \left ( \sum_{i=1}^{n-m} i^2 \right ) \quad .
$$

Of course the right side is ${{n+1} \choose {m}}^2 (n-m)(n-m+1)(2n-2m+1)/6$
(using $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$), and the left side can be written more
symmetrically as
$$
\sum_{i,j,k} 
i(i+j) {{i+j-1} \choose {k}} {{n-(i+j)} \choose {m-k}} {{n-i} \choose {m-k+j}} {{i-1} \choose {k-j}} \quad ,
$$
where the summation range is over all triples $(i,j,k)$ for which the binomial coefficients ``make sense''
i.e. whenever you have ${{r} \choose {s}}$ we have $0 \leq s \leq r$).

Writing $a=i+j$, (and leaving $i$ as a discrete variable, but letting $j=a-i$), it is more convenient to evaluate
$$
\sum_{a,k,i} 
ia {{a-1} \choose {k}} {{n-a} \choose {m-k}} {{n-i} \choose {m-k+a-i}} {{i-1} \choose {k-a+i}} \quad .
$$
It is easily seen that this equals the {\it iterated} summation
$$
\sum_{a=1}^n \sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)} \sum_{i=a-k}^{a-k+m}
ia {{a-1} \choose {k}} {{n-a} \choose {m-k}} {{n-i} \choose {m-k+a-i}} {{i-1} \choose {k-a+i}} 
$$
$$
= \, \sum_{a=1}^n 
a \sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)}  {{a-1} \choose {k}} {{n-a} \choose {m-k}}
\sum_{i=a-k}^{a-k+m}
i  {{n-i} \choose {m-k+a-i}} {{i-1} \choose {k-a+i}}  \quad .
$$
Let's do the innermost sum first.
Since $i {{i-1} \choose {k-a+i}}=(a-k) {{i} \choose {a-k}}$
the inner sum is
$$
(a-k) 
\sum_{i=a-k}^{a-k+m} {{n-i} \choose {m-k+a-i}} {{i} \choose {a-k}} =
(a-k) {{n+1} \choose {m}} \quad,
$$
by the celebrated Vandermonde-Chu (alias terminating Gauss's ${}_2F_{1}(1)$ identity).

Now let's do the middle sum
$$
{{n+1} \choose {m}}
\sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)}  (a-k) {{a-1} \choose {k}} {{n-a} \choose {m-k}} \quad .
$$
Now
$$
\sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)}  (a-k) {{a-1} \choose {k}} {{n-a} \choose {m-k}}
$$
$$
=a \sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)}  {{a-1} \choose {k}} {{n-a} \choose {m-k}}
-
 \sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)}  k{{a-1} \choose {k}} {{n-a} \choose {m-k}} \quad .
$$
The first sum is  $a{{n-1} \choose {m}}$, again by Vandermonde, while for the second we replace
$$
k{{a-1} \choose {k}}
$$ 
by  
$$
(a-1){{a-2} \choose {k-1}} \quad 
$$
getting that it equals
$$
(a-1)\sum_{k=\max(0,a-(n-m))}^{\min(a-1,m)}  {{a-2} \choose {k-1}} {{n-a} \choose {m-k}} \quad ,
$$
that again by Vandermonde, equals  $(a-1){{n-2} \choose {m-1}}$.
So the inner and the middle $\sum$'s give the following expression in $m,n,a$:
$$
{{n+1} \choose {m}}
\left (
a {{n-1} \choose {m}} - (a-1) {{n-2} \choose {m-1}} 
\right ) \quad .
$$
Finally to do the outermost sum, w.r.t. to $a$ (don't forget the $a$ in front that we took out since it
didn't depend on $i$ and $k$)
$$
{{n+1} \choose {m}}
\left (
{{n-1} \choose {m}} \left ( \sum_{a=1}^{n} a^2 \right ) 
-
{{n-2} \choose {m-1}} \left ( \sum_{a=1}^{n} a(a-1) \right )
\right )
$$
$$
={{n+1} \choose {m}}
\left (
\frac{(n-1)!}{m!(n-m-1)!} \cdot \frac{n(n+1)(2n+1)}{6}
-
\frac{(n-2)!}{(m-1)!(n-m-1)!} \cdot \frac{(n-1)n(n+1)}{3}
\right )
$$
$$
={{n+1} \choose {m}} \, \cdot \, 
\left (
\frac{(n+1)!}{m!(n-m-1)!} \cdot \frac{(2n+1)}{6}
-
\frac{(n+1)!}{m!(n-m-1)!} \cdot \frac{m}{3}
\right )
$$
$$
={{n+1} \choose {m}} \frac{(n+1)!}{m!(n-m-1)!} \, \cdot \, 
\left ( \frac{2n+1}{6} -\frac{m}{3} \right )
$$
$$
={{n+1} \choose {m}} \frac{(n+1)!}{m!(n-m-1)!}
\, \cdot \, 
\frac{2n-2m+1}{6}
$$
$$
={{n+1} \choose {m}} \, \cdot \,  \frac{(n+1)!}{m!(n-m+1)!} \, \cdot \,  \frac{(n-m)(n-m+1)(2n-2m+1)}{6}
$$
$$
={{n+1} \choose {m}}^2 \, \frac{(n-m)(n-m+1)(2n-2m+1)}{6} \quad \halmos.
$$



{\bf References}

[P] Juan Sebasti\'an Pereyra, {\it private communication}, \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/akherim/pereyraConj.pdf}
\end





