\documentclass[12pt,reqno]{amsart}


\textwidth15.6cm
\textheight22.8cm
\hoffset-1truecm
\voffset-.5truecm

\newtheorem{Theorem}{Theorem}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Lemma}[Theorem]{Lemma} 
\newtheorem{Proposition}[Theorem]{Proposition} 

\theoremstyle{remark}

\newtheorem*{Remark}{Remark}

%\numberwithin{equation}{section}

%\input sekr

\def\ep{\varepsilon}
\def\po#1#2{(#1)_#2}
\def\fl#1{\left\lfloor#1\right\rfloor}


\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc C.~Krattenthaler}
\vskip18pt
\centerline{Institut Girard Desargues,
Universit\'e Claude Bernard Lyon-I}
\centerline{21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France}
\centerline{E-mail: \tt kratt@euler.univ-lyon1.fr}
\centerline{WWW: \footnotesize\tt http://igd.univ-lyon1.fr/\~{}kratt}
}


\title{Hypergeometric proof of a curious identity of
Lyons, Paule and Riese}
\author[C. Krattenthaler]{\box\Adr}
\address{Institut Girard Desargues,
Universit\'e Claude Bernard Lyon-I,
21, avenue Claude Bernard,
F-69622 Villeurbanne Cedex, France}

\dedicatory{Dedicated to Ratan Prakash Agarwal}

\thanks{$^\dagger$ Research partially supported by 
EC's IHRP Programme, grant HPRN-CT-2001-00272, 
``Algebraic Combinatorics in Europe"}

\subjclass[2000]{Primary 33C20;
 Secondary 05A19}

\keywords{double sum, hypergeometric series, hypergeometric
summations, hypergeometric transformations}

\begin{abstract}
We give a classical hypergeometric proof of an identity of Lyons, Paule and
Riese, which arose in work of Lyons and Steif on determinantal processes, and
which was originally proved by the former authors by the use of computer
algorithms.
\end{abstract}
\maketitle

\section{Introduction} \label{sec:1}

In recent work of Lyons and Steif \cite{LyStAA} on determinantal
processes, in order to do 
the estimation of the entropy of a certain process, it
turned out to be necessary to prove the following identity between a
double sum and a linear combination of two harmonic numbers:
\begin{align} \notag
\sum _{n=1} ^{\infty}
\sum _{k=0} ^{2n-1}\binom {2n-1}k\frac {1}
{2^{2n-1}\,(2n-1)\,(k-j-n+1/2)}&=
-\frac {2} {j}\sum _{k=1} ^{j}\frac {1} {2k-1}\\
 \label{eq:1} 
&=-\frac {2} {j}\left(H_{2j}-\tfrac {1} {2}H_j\right),
\end{align}
where $H_m$ denotes the $m$-th harmonic number $
\sum _{i=1} ^{m}\frac {1} {i}$.
This identity was proved by Lyons, Paule and Riese
in \cite{LyPRAA} by the use of computer
algorithms for the summation of binomial and hypergeometric series. More
precisely, it is the {\sl Mathematica} implementations for
the Gosper--Zeilberger algorithm \cite{PeWZAA,ZeilAM,ZeilAV}
developed by Paule and Schorn \cite{PaScAA}, and the {\sl
Mathematica} implementation of (a significantly enhanced version of)
Sister Celine's algorithm (see \cite{PeWZAA}) developed by Riese,
Wegschaider and Zimmermann \cite{WegsAA,RiZiAA} which was used
there for the proof of \eqref{eq:1}.

On the other hand, if one is interested to ``go to the roots" of an
identity, then one is (usually) obliged to look for a ``classical" proof,
based on summation and transformation formulas for hypergeometric
series. This is what we do in this note. As a result, we present a
proof of identity \eqref{eq:1} 
which makes use of Kummer's $_2F_1$-summation formula
(see \eqref{eq:3} below), of
Gau\ss' (first) $_2F_1$-summation formula (see \eqref{eq:4} below), 
and, as an unexpected ingredient, of a limiting case of the
non-terminating extension of Whipple's transformation due to Bailey
(see \eqref{eq:6} below).

\section{Proof of the identity}
Using the standard hypergeometric notation
$${}_p F_q\!\left[\begin{matrix} a_1,\dots,a_p\\ b_1,\dots,b_q\end{matrix}; 
z\right]=\sum _{m=0} ^{\infty}\frac {\po{a_1}{m}\cdots\po{a_p}{m}}
{m!\,\po{b_1}{m}\cdots\po{b_q}{m}} z^m\ ,$$
where the Pochhammer symbol 
$(\alpha)_m$ is defined by $(\alpha)_m:=\alpha(\alpha+1)\cdots(\alpha+m-1)$,
$m\ge1$, $(\alpha)_0:=1$, 
we may rewrite the sum over $k$ on the left-hand side of \eqref{eq:1} 
in the form
\begin{equation} \label{eq:2} 
-\sum _{n\ge1} ^{}
 \frac{1}{2^{2 n-2}\,\left(  2 n -1\right) \,
       \left(  2 n+ 2 j  -1 \right) } 
 {} _{2} F _{1} \!\left [ \begin{matrix} { \frac{1}{2}
        - j - n, 1 - 2 n}\\ { \frac{3}{2} - j - n}\end{matrix} ; {\displaystyle
        -1}\right ]. 
\end{equation}
Next we apply the contiguous relation
$$
{} _2 F _1 \!\left [ \begin{matrix} { a, b}\\ { c}\end{matrix} ;
   {\displaystyle z}\right ] =
  {} _2 F _1 \!\left [ \begin{matrix} { a + 1, b}\\ { c + 1}\end{matrix} ;
    {\displaystyle z}\right ]  - 
   {\frac {b\left( c - a \right)  z 
        }
     {c \left(  c+1 \right)  }}
  {} _2 F _1 \!\left [ \begin{matrix} { a + 1, b+1}\\ { c + 2
        }\end{matrix} ; {\displaystyle z}\right ]
$$
in its iterated form
$$ {} _{2} F _{1} \!\left [ \begin{matrix} { a, b}\\ { c}\end{matrix} ; {\displaystyle
   z}\right ]= \sum _{r=0} ^ {m}{\left( -1 \right) }^ r{\binom m r}
 \frac{\,z^
   r\,({ \textstyle b}) _{r}
   \,({ \textstyle  c-a}) _{r} }{({ \textstyle c}) _{r} \,({ \textstyle
   c + m}) _{r} }
{} _{2} F _{1} \!\left [ \begin{matrix} { a + m, b + r}\\ { c
   + m + r}\end{matrix} ; {\displaystyle z}\right ].$$
With $m=j$ this yields 
$$
-\sum _{n\ge1} ^{}
\sum _{r=0} ^{j} {\binom j r}
\frac{r! \,
       ({ \textstyle 1 - 2 n}) _{r} }{2^{2 n}\,
       ({ \textstyle \frac{1}{2} - n}) _{ r+1} \,
       ({ \textstyle \frac{1}{2} - j - n}) _{ r+1} } 
{} _{2} F _{1} \!\left [ \begin{matrix} { 1 - 2 n + r, \frac{1}{2}
        - n}\\ { \frac{3}{2} - n + r}\end{matrix} ; {\displaystyle
        -1}\right ]
$$
for the expression \eqref{eq:2}. The $_2F_1$-series can be summed by means
of Kummer's summation (cf.\ \cite[(1.7.1.6), corrected,
(2.3.2.9); Appendix (III.5)]{SlatAC})
\begin{equation} \label{eq:3} 
{} _{2} F _{1} \!\left [ \begin{matrix} { a, b}\\ { 1 + a - b}\end{matrix} ;
   {\displaystyle -1}\right ] =
 \frac {\Gamma( 1 + {\frac a 2})\,\Gamma( 1 + a - b)} 
{ \Gamma(1 + a)\, \Gamma(1 + {\frac a 2} -
   b)}.
\end{equation}
In fact, since we can restrict $r$ to $r\le 2n-1$ because of the term
$(1-2n)_r$ in the numerator of the summand, 
the $_2F_1$-series is a terminating series, in which case
actually a limit case of Kummer's summation must be considered. It
turns out that the $_2F_1$-series is 0 for even $r$. The result of the
summation for odd $r$, $r=2s-1$, yields the expression
$$ -
\sum _{n\ge1} ^{}
\sum _{s=1} ^{\fl{(j+1)/2}}{\binom j {2 s-1}}
 \frac{  
       (2 s-1)! \,
       ({ \textstyle 1 - 2 n}) _{2 s-1} \,
       ({ \textstyle n - s}) _{n - s} }{2^{2 n-1}\,
({ \textstyle \frac{1}{2} - n})
        _{2 s} \,({ \textstyle \frac{1}{2} - j - n}) _{2 s} \,
       ({ \textstyle \frac{1}{2} - s}) _{n - s} } .$$
Now we interchange the summations over $n$ and $s$,
and we write the (now inner) sum over $n$ in hypergeometric
notation. It should be noted that the term $(1-2n)_{2s-1}$ implies that the sum
over $n$ may be started at $s$ (instead of at 1). The result is 
$$
\sum _{s=1} ^{\fl{(j+1)/2}} {\left( -1 \right) }^s
\frac{2^{ 2 s-2}   
     {\left( s -1\right) !}^2\,({ \textstyle 2 + j - 2 s}) _{ 2 s-1} }
     {\left(2 s-1 \right) !\,
     ({ \textstyle \frac{1}{2} - j - s}) _{2 s} }
{} _{2} F _{1} \!\left [ \begin{matrix} { \frac{1}{2} + j -
      s, s}\\ { \frac{1}{2} + j + s}\end{matrix} ; {\displaystyle 1}\right ].$$
The $_2F_1$-series can be evaluated by means of 
Gau\ss' $_2F_1$-summation formula (cf.\ \cite[(1.7.6); 
Appendix (III.3)]{SlatAC})
\begin{equation} \label{eq:4} 
{} _{2} F _{1} \!\left [ \begin{matrix} { a, b}\\ { c}\end{matrix} ; {\displaystyle
   1}\right ] =\frac {\Gamma( c)\,\Gamma( c-a-b)} {\Gamma(
c-a)\,\Gamma( c -b)} .
\end{equation}
If we subsequently write the remaining sum over $s$ in hypergeometric
notation, then we arrive at
\begin{equation} \label{eq:5} 
 \frac{j }{\frac{1}{2} - j}
{} _{4} F _{3} \!\left [ \begin{matrix} {  1,
      1, \frac{1}{2} - \frac{j}{2},
1 - \frac{j}{2}}\\ { \frac{3}{2},  \frac{3}{2} -
      j,\frac{3}{2}}\end{matrix} ; {\displaystyle 1}\right ].
\end{equation}
This is not exactly the final result. We now appeal to one of the
bigger identities of hypergeometric theory, the non-terminating Whipple
transformation due to Bailey (cf.\ \cite[(2.4.4.3), reversed]{SlatAC}),
\begin{multline} \label{eq:6}
{} _{4} F _{3} \!\left [ \begin{matrix} { a, b, c, d}\\ { e, f, 1 + a + b + c + d
    - e - f}\end{matrix} ; {\displaystyle 1}\right ] \\
 =
   \frac{
       \Gamma({ \textstyle  e + f-a }) \,
       \Gamma({ \textstyle   e + f-a - b - c}) \,
       \Gamma({ \textstyle  e + f -a - b - d}) \,
       \Gamma({ \textstyle  e + f -a - c - d}) }{\Gamma({ \textstyle 
        e + f-a - b}) \,\Gamma({ \textstyle   e + f-a - c}) \,
       \Gamma({ \textstyle   e + f-a - d}) \,
       \Gamma({ \textstyle   e + f-a - b - c - d}) }\\
\times
{} _{7} F _{6} \!\left [ \begin{matrix} { -1 - a + e + f, \frac{1}{2} -
        \frac{a}{2} + \frac{e}{2} + \frac{f}{2},  f-a,  e-a, b, c, d}\\ {
        - \frac{1}{2}  - \frac{a}{2} + \frac{e}{2} +
        \frac{f}{2}, e, f,  e + f-a - b,  e + f-a - c,  e +
        f-a - d}\end{matrix} ; {\displaystyle 1}\right ] \\
 -
    \frac{\Gamma({ \textstyle e}) \,
      \Gamma({ \textstyle f}) \,
  \Gamma({ \textstyle a + b + c + d - e - f}) \,
      \Gamma({ \textstyle  e + f-a - b - c}) \,
       \Gamma({ \textstyle  e + f-a - b - d })  }
{   \Gamma({ \textstyle   e + f-a - b - c - d}) \,
       \Gamma({ \textstyle  2e + f-a - b - c - d }) \,
       \Gamma({ \textstyle  e + 2f-a - b - c - d }) }\\
\times
\frac {      \Gamma({ \textstyle  e + f-a - c - d }) \,
       \Gamma({ \textstyle   e + f-b - c - d})} 
 { \Gamma({ \textstyle a}) \,
       \Gamma({ \textstyle b}) \,\Gamma({ \textstyle c}) \,
       \Gamma({ \textstyle d})   }
{} _{4} F _{3} \!\left [ \begin{matrix} {  e + f-a - b - c, }\\ { 
        2 e + f-a - b - c - d, }\end{matrix} \right .\\
\left.\begin{matrix}  
         e + f-a - b - d,  e + f-a - c - d,  e + f-b - c - d\\
 e + 2 f-a - b - c - d, 1 - a - b - c - d + e +
        f\end{matrix} ; {\displaystyle 1}\right ].
\end{multline}
In this identity we substitute $a=b=1$, $c=\frac {1} {2}-\frac {j}
{2}$, $d=1-\frac {j} {2}$, $e=\frac {3} {2}+\ep$, and $f=\frac {3}
{2}+\ep-j$. With this choice, the second summand on the right-hand
side vanishes, and the result is
\begin{multline*}  
{} _{4} F _{3} \!\left [ \begin{matrix} { 1, 1, \frac{1}{2} - \frac{j}{2}, 1 -
    \frac{j}{2}}\\ { \frac{3}{2} + \ep, \frac{3}{2} +
    \ep - j, \frac{3}{2} - 2 \ep}\end{matrix} ;
    {\displaystyle 1}\right ] \\
 =
   \frac{ 
      \Gamma({ \textstyle \frac{1}{2} + 2 \ep}) \,
      \Gamma({ \textstyle 2 + 2 \ep - j}) \,
      \Gamma({ \textstyle 2 \ep - \frac{j}{2}}) \,
      \Gamma({ \textstyle \frac{1}{2} + 2 \ep - \frac{j}{2}}) }
      {\Gamma({ \textstyle - \frac{1}{2}  + 2 \ep})
       \,\Gamma({ \textstyle 1 + 2 \ep - j}) \,
      \Gamma({ \textstyle 1 + 2 \ep - \frac{j}{2}}) \,
      \Gamma({ \textstyle \frac{3}{2} + 2 \ep - \frac{j}{2}}) }\\
\times
{} _{6} F _{5} \!\left [ \begin{matrix} { \frac{3}{2} + \ep -
       \frac{j}{2}, \frac{1}{2} + \ep - j, \frac{1}{2} +
       \ep, \frac{1}{2} - \frac{j}{2}, 1 - \frac{j}{2}, 1}\\ {
       \frac{1}{2} + \ep - \frac{j}{2}, \frac{3}{2} +
       \ep, \frac{3}{2} + \ep - j, \frac{3}{2} +
       2 \ep - \frac{j}{2}, 1 + 2 \ep -
       \frac{j}{2}}\end{matrix} ; {\displaystyle 1}\right ] .
\end{multline*}
Now we let $\ep\to0$. As a result we obtain that the expression
\eqref{eq:5} is equal to
$$ \frac{2}{\frac {1} {2}-j}\,
{} _{3} F _{2} \!\left [ \begin{matrix} { \frac{1}{2} - j, \frac{1}{2},
      1}\\ { \frac{3}{2}, \frac{3}{2} - j}\end{matrix} ; {\displaystyle 1}\right
      ] .$$
By the definition of the hypergeometric series, this is
$$
\sum _{k=0} ^{\infty} \frac{1}{\left( \frac{1}{2} + k \right) \,
     \left( \frac{1}{2} - j + k \right) }.$$
Upon partial fraction expansion this becomes
\begin{align*}
-\lim_{M\to\infty}\frac {2} {j}\sum _{k=0} ^{M} 
&\left( \frac{1}{ 2 k +1 } +
   \frac{1}{   2 j - 2 k -1 }\right)=
-\frac {2} {j}\sum _{k=0} ^{j-1} 
\left( \frac{1}{ 2 k +1 } +
   \frac{1}{   2 j - 2 k -1 }\right)\\
&\kern4cm
-\lim_{M\to\infty}\frac {2} {j}\sum _{k=j} ^{M} 
\left( \frac{1}{ 2 k +1 } +
   \frac{1}{   2 j - 2 k -1 }\right)\\
&\kern3cm
=-\frac {2} {j}\sum _{k=1} ^{j}\frac {1} {2k-1}-\frac {2} {j}
\lim_{M\to\infty}
\sum _{k=M-j+1} ^{M}\frac {1} {2k+1}.
\end{align*}
Clearly, this expression is equal to the desired result
$$-\frac {2} {j}\sum _{k=1} ^{j}\frac {1} {2k-1}.$$





\begin{thebibliography}{1}


\bibitem{LyStAA} R.    Lyons and J. Steif, {\em Stationary determinantal processes:
phase multiplicity, Bernoullicity, entropy, and domination}, Duke Math.\ J.
{\bf 120} (2003), 515--575.

\bibitem{LyPRAA} R.    Lyons, P. Paule and A. Riese, {\em A
computer proof of a series
evaluation in terms of harmonic numbers}, Appl.\ Algebra
Engrg.\ Comm.\ Comput.\ {\bf 13} (2002), 327-333.

\bibitem{PaScAA} P.    Paule and M. Schorn,
{\em A Mathematica version of Zeilberger's algorithm 
for proving binomial coefficient identities},
J. Symbol\. Comp\. {\bf 20} (1995), 673--698.

\bibitem{PeWZAA} M.    Petkov\v sek, H. Wilf and D. Zeilberger,
{\em A=B}, A.K. Peters, Wellesley, 1996.

\bibitem{RiZiAA} A. Riese and B. Zimmermann,
{\em Randomization speeds up hypergeometric 
summation}, in preparation.

\bibitem{SlatAC} L. J. Slater,
{\em Generalized hypergeometric functions},
Cambridge University Press, Cambridge, 1966.

\bibitem{WegsAA} K.    Wegschaider, {\em Computer generated
proofs of binomial multi-sum identities}, diploma thesis,
Johannes Kepler University, Linz, Austria, 1997.

\bibitem{ZeilAM} D.    Zeilberger,
{\em A fast algorithm for proving terminating 
hypergeometric identities}, Discrete Math.\ {\bf 80} (1990),
207--211.

\bibitem{ZeilAV} D.    Zeilberger,
{\em The method of creative telescoping},
J. Symbolic Comput.\ {\bf 11} (1991), 195--204.

\end{thebibliography}







\end{document}
