
% ----------------------------------------------------------------
% AMS-LaTeX Paper ************************************************
% **** -----------------------------------------------------------
\documentclass{amsart}
\usepackage{graphicx}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\numberwithin{equation}{section}
% MATH -----------------------------------------------------------
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\newcommand{\A}{\mathcal{A}}
\def\qbinom#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}}

% ----------------------------------------------------------------
\begin{document}

\title{Some Nice Sums are Almost as Nice if you turn them Upside Down}
\maketitle

\vskip 10pt

\begin{center}
{\bf Moa Apagodu}\\
{Department of Mathematics, Virginia Commonwealth University,\\ Richmond, VA 08854, USA}

\vskip 10pt

{\bf Doron Zeilberger} \\
Department of Mathematics, Rutgers University,
Hill Center-Busch Campus, \\110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
\end{center}

\begin{abstract}

  {We represent the sums $\sum_{k=0}^{n-1}{n \choose k}^{-2}\,\,,\sum_{k=0}^{m}{m\choose k}^{-1}{a\choose n-k}^{-1},$  $\sum_{k=0}^{n-1}\frac{q^{-k(k-1)}}{{\genfrac{[}{]}{0pt}{}{n}{k}}_q }$, 
and the sum of the reciprocal of the summand in Dixon's identity, each as a product of an {\it indefinite hypergeometric sum}
times a (closed form) {\it hypergeometric sequence}} .

\end{abstract}

\vskip 10pt

\noindent In [3], Rocket proved the formula
$$
\sum_{k=0}^{n}{n \choose k}^{-1}  = \frac {n+1}{2^n}\sum_{j=0}^{n}\frac{2^j}{j+1}\,\,, \eqno(Rockett)
$$

\noindent for all nonnegative integers $n$. Since then,
several authors (e.g. [1][4][5]) used different techniques to re-derive (\emph{Rockett}) and considered 
analogous, more complicated, sums.\\

As we all know, 
$$
\sum_{k=0}^{n}{n \choose k}  = 2^n \,\,, \eqno(Binomial)
$$
is the {\it simplest} example of a {\bf definite} binomial coefficient sum that evaluates in {\it closed-form}.
Such sums have the form
$$
\sum_{k=0}^{n} F(n,k)  = A(n) \,\, ,
$$
where $A(n)$ is {\it hypergeometric} (i.e. $A(n+1)/A(n)$ equals $P(n)/Q(n)$ for some polynomials $P(n),Q(n)$ of $n$,
in other words, is a {\it rational function} of $n$),
and $F(n,k)$ is {\it bi-hypergeometric} (i.e $F(n+1,k)/F(n,k)$  and $F(n,k+1)/F(n,k)$ are both rational functions of $R(n,k)$).
Other famous examples, are 
$$
\sum_{k=0}^{n} {n \choose k}{a \choose k}  = {n+a \choose a} \,\, ,
\eqno(Chu-Vandermonde)
$$
and
$$
\sum_{k=-n}^{n} (-1)^k {a+n \choose n+k}  {b+n \choose b+k}  {a+b \choose a+k}  
= 
\frac{(a+b+n)!}{a!b!n!}
 \,\, ,
\eqno(Dixon)
$$
The {\it best} thing that can happen to a binomial coefficients sum is to he evaluable in {\it closed form},
i.e. as a hypergeometric sequence. The {\it next best} thing is to be ``almost closed-form'', i.e. of the form
$$
ClosedForm (n) \cdot \left ( \sum_{j=1}^{n} h(j) \right ) \quad ,
$$
where $h(j)$ is hypergeometric in the {\it single} variable $j$.

Inspired by $(Rocket)$, that has this ``almost perfect'' form, and that came out from considering
the sum of the reciprocal of the {\it simplest} binomial coefficient sum known,
we searched for other cases where one starts from a well-known binomial coefficients sum that
evaluates in closed form, and looks at what happens if one considers the sum of the reciprocal
of the summand. To our great surprise and delight, it worked for the Chu-Vandermonde summand and
for the Dixon summand (see below). To our disappointment, it didn't work for the so-called
Pfaff-Saalschutz identity (see, e.g. [2]).

\noindent  We use the WZ method([2]), and the reader is assumed to be familiar with it. 
In particular we used Zeilberger's Maple package {\tt EKHAD} (procedure zeillim) accompanying
[2]. {\tt EKHAD} is available from

{\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/EKHAD} .

In most applications, the summation limits are {\it natural},
i.e. the summand is well-defined vanishes at $k=-1$ and $k=n+1$ (or in the case of $(Dixon)$,
at $k=-n-1$ and $k=n+1$)
so one can get a {\it homogeneous} first-order linear recurrence for the definite sum,
that leads to a closed-form solution. In the present cases,
this is no longer the case, and we only get
{\it inhomogeneous} first-order linear recurrences, that leads to the ``almost-perfect'' kind of solutions.


\noindent Consider the sum 
$$
f(n):=\sum_{k=\alpha}^{n-\beta}F(n,k)\,\,,
$$

\noindent where $\alpha$ and $\beta$ are constants and $[\alpha,n-\beta]$ is properly contained in $[0,n]$, the support of $F(n,k)$. 
Assume also that there exists a function $G(n,k)$, (the so-called certificate) such that
$$
a(n)F(n+1,k)+b(n)F(n,k)=G(n,k+1)-G(n,k)\,\,. \eqno(WZeqn)
$$

\noindent Take $\alpha=0$ and $\beta=1$. Then, if we add both sides of (\emph{WZeqn}) from $k=0$ to $k=n$ and rewrite the result we get a nonhomogeneous recurrence relation satisfied by $f(n)$:

$$
a(n)f(n+1)+b(n)f(n)= G(n,n)-G(n,0)+a(n)F(n+1,n)\eqno{(nonhomorec)}
$$

\noindent Finally, we solve (\emph{nonhomorec}) and get the following representation of $f(n)$ as an indefinite sum:
$$
f(n)=g(n)\sum_{i=0}^{n-1}\frac{C(i)}{g(i)a(i)}\,\,,
$$

\noindent where $C(i)$ is the right-hand side of ($\emph{nonhomorec}$) and $g(n)$ is the solution to the associated homogeneous equation $a(n)f(n+1)+b(n)f(n)=0$. \\

\noindent We note that in cases where $\alpha \neq 0$ and $\beta\neq 1$, the left-hand side of (\emph{nonhomrec}) remains the same. The only change is on the right-hand side. \\

\noindent \textbf{Theorem 1}:

$$
\sum_{k=0}^{n-1}{n \choose k}^{-2}=\frac{(n+1)!(n+1)^2}{(n+\frac{3}{2})!4^n}\sum_{j=0}^{n-1}\frac{(3j^3+12j^2+18j+10)4^j(j+3/2)!}
{(j+1)^2(j+1)!(j+2)^3} \,\,.
$$

\noindent \textbf{Proof}: We construct the function

$$
G(n,k)=\frac{(2k-3n-6)(k-n-1)^2}{{n \choose k}^{2}}
$$

\noindent such that $(4n+10)(n+1)^2F(n+1,k)-(n+2)^2F(n,k)=G(n,k+1)-G(n,k)$, where $F(n,k)$ is the summand on the left-hand side sum.\\

\noindent Next add both sides from $k=0$ to $k=n$ and rearrange to get the nonhomogeneous recurrence relation satisfied by the sum on the left-hand side, $S_n$ :

$$
(4n+10)(n+1)^2S_{n+1}-(n+2)^2S_n=3n^3+12n^2+18n+10\,\,\,.
$$

\noindent Finally the theorem follows by solving this recurrence with the initial condition $S_1=1$.\\


\noindent Next we give q-analog of (\emph{Rokett}). Let $(a,q,n)= (1-aq)(1-aq^2)\ldots(1-aq^{n-1})$. \\

\vskip .2in

\noindent \textbf{Theorem  2} [q-binomial]:

$$
\sum_{k=0}^{n-1} \frac{q^{-k(k-1)/2}}{{\genfrac{[}{]}{0pt}{}{n}{k}}_q  } = \frac{(q^2,q,n)}{(q^2,q^2,n)}\sum_{i=0}^{n-1}
\frac{C(i)(q^2,q^2,i)}{(q^2,q,i)(q^{i+1}-1)(q^{i+2}-1)}\,\,,
$$

\noindent where
$$C(i)=(q^{3(i+2-i^2)/2}+2q^{2i+2}-q^{-(i+1)(i-2)/2}-q^{-(i+1)(i-4)}-q^{i+1}-q^{3i+3}-q^{-i(i-1)/2})\,\,.$$

\noindent \textbf{Proof}: We construct the function

$$
G(n,k)=\frac{q^{n+1}(q^{n-k+1}-1)q^{-k(k-1)/2}}{ {\genfrac{[}{]}{0pt}{}{n}{k}}_q }
$$

\noindent such that $(q^{n+2}-1)F(n,k)-(q^{n+}-1)(q^{n+1}+1)F(n+1,k)=G(n,k+1)-G(n,k)$, where $F(n,k)$ is the summand on the left-hand side.\\

\noindent Add both sides from $k=0$ to $k=n$ and rearrange to get the nonhomogeneous recurrence relation satisfied by the sum on the left-hand side, $S_n$ :\\

$$
(q^{n+2}-1)S_n-(q^{n+}-1)(q^{n+1}+1)S_{n+1} = \frac{C(n)}{q^{n+1}-1}\,\,\,.
$$

\noindent Finally the theorem follows by solving this recurrence with the initial condition $S_1=1$. \\

$$
\sum_{k=0}^{n} \frac{q^{-k(k-1)/2}}{{\genfrac{[}{]}{0pt}{}{n}{k}}_q  }=q^{-n(n-1)/2}+\frac{(q^2,q,n)}{(q^2,q^2,n)}\sum_{i=0}^{n-1}
\frac{C(i)(q^2,q^2,i)}{(q^2,q,i)(q^{i+1}-1)(q^{i+2}-1)}\,\,.
$$

\vskip .2in

\noindent Next we consider the reciprocal of the summand in Chu-Vandermonde and Dixon's classical identities. \\

\vskip .2in

\noindent \textbf{Theorem 3} [Chu-Vandermonde] \\

$$
\sum_{k=0}^{m-1}{m\choose k}^{-1}{a\choose n-k}^{-1}=g(m)\sum_{i=0}^{m-1}\frac{C(i)}{g(i)(i+2)(a+i-n+2)}
$$

\noindent where

$$
g(m)= \frac{(a+m-n+1)!(a+4)!(m+1)}{2(a+m+3)!(a-n+2)!}
$$

and\\

$$
C(m)=(n+m+mn+1){a\choose n}^{-1} + (2m+a-n+3){a\choose n-m}^{-1}\,\,.
$$

\noindent \textbf{Proof}: The proof follows similarly from the recurrence relation

$$
(m+2)(a+m-n+2)S_m-(a+m+4)(m+1)S_{m+1}=C(m)\,\,.
$$

\noindent where $S_m$ is the sum on left-hand side.

\vskip .2in

\noindent \textbf{Theorem 4} [Dixon] \\

$$
\sum_{k=0}^{n-1}(-1)^k{n+b\choose n+k}^{-1}{n+c\choose c+k}^{-1}{b+c\choose b+k}^{-1} =g(n)\sum_{i=0}^{m-1}\frac{-C(i)}{g(i)(2i+2)(c+i+2)(b+i+2)}
$$

\noindent where\\

$$
g(n)= \frac{(c+n+1)(b+n+1)}{(c+1)(b+1)}\frac{(c+b+2)!n!}{(b+c+n+2)!}
$$

\noindent and\\

$
C(n)=(-1)^n(bc+3bn+3b+3nc+5n^2+2n+3c+7){n+b\choose 2n}^{-1}{b+c\choose b+n}^{-1} - (n+bn+nc+bc+b+c+1)
{n+b\choose n}^{-1}{n+c\choose c}^{-1}{b+c\choose b}^{-1}\,\,.
$\\

\vskip .2in


\noindent \textbf{Proof}: The proof follows similarly from the recurrence relation

$$
2(n+1)(c+n+2)(b+n+2)S_n-2(c+n+1)(b+n+1)(b+c+n+3)S_{n+1}=C(n)\,\,.
$$

\noindent where $S_n$ is the sum on left-hand side.

\vskip .2in

\noindent \textbf{Remarks} a) From the recurrence in the proof of theorem 1,

$$
2S_n=\frac{(n+1)^3}{2n^3+3n^2}S_{n-1}+\frac{3n^3+3n^2+3n+1}{2n^3+3n^2}
$$

\noindent that implies

$$
\lim_{n\rightarrow \infty} \sum_{k=0}^{n}{n \choose k}^{-2}=2\,\,.
$$


\noindent b) Identity (\emph{Rockett}) is a special case of the following identity with $x=y=1$ in

$$
\sum_{k=0}^{n}{n \choose k}^{-1}x^ky^{n-k}=x^n+\left(\frac{xy}{x+y}\right)^n(n+1)\sum_{j=0}^{n-1}\frac{((j+1)y^{j+2}+yx^{j+1})(x+y)^j}
{(xy)^{j+1}(j+1)(j+2)}
$$

\noindent which follows from the recurrence [$S_n$ the left-hand side sum]:\\

$$
(x+y)(n+1)S_{n+1}-(n+2)xyS_n = (n+1)y^{n+2}+yx^{n+1}\,\,.
$$

\vskip .2in

\noindent c) T. Mansour [1] derived the following representation for the reciprocals of binomial coefficients to any power m as:

$$
\sum_{k=0}^{n-1}{n \choose k}^{-m}=(n+1)^m\sum_{k=0}^{n}\left[\sum_{j=0}^{k}\frac{(-1)^j}{{n-k+1+j}} {k \choose j}\right]^m\,\,.
$$


\noindent {\bf References}\\

\bibliographystyle{amsplain}

\noindent [1]  T. Mansour,"Combinatorial Identities and Inverse Binomial Coefficients", Advances in Applied Mathematics, \textbf{28}, 196-202(2002).\\

\noindent [2]  M. Petkovsek, H.S. Wilf, D. Zeilberger, "A=B", A.K. Peters Ltd., 1996.\\

\noindent [3] A.M. Rokett, "Sum of the inverse of binomial coefficients", Fibonacci Quart., 19, 433-437(1981).\\

\noindent [4] R. Sprugnoli, "Sums of Reciprocals of the Central Binomial Coefficients", E. J. of Combinatorial Number Theory \textbf{6}, \#A27(2006).\\

\noindent [5] B. Sury, " Sum of the Reciprocals of the Binomial Coefficients", Europ. J. Combinatorics, 14, 351-353 (1993).

\end{document}


