# On two-term hypergeometric recursions with free lower parameters

J. M. Campbella and Paul Levrieb CONTACT J. M. Campbell. Email:
<EMAIL_ADDRESS>a Department of Mathematics, Toronto Metropolitan
University, 350 Victoria St., Toronto, Ontario, Canada; b Department of
Computer Science, KU Leuven, Celestijnenlaan 200A, 3001 Heverlee (Leuven),
Belgium, and Faculty of Applied Engineering, UAntwerpen, Groenenborgerlaan
171, 2020 Antwerp, Belgium

###### Abstract

Let $F(n,k)$ be a hypergeometric function that may be expressed so that $n$
appears within initial arguments of inverted Pochhammer symbols, as in factors
of the form $\frac{1}{(n)_{k}}$. Only in exceptional cases is $F(n,k)$ such
that Zeilberger’s algorithm produces a two-term recursion for
$\sum_{k=0}^{\infty}F(n,k)$ obtained via the telescoping of the right-hand
side of a difference equation of the form
$p_{1}(n)F(n+r,k)+p_{2}(n)F(n,k)=G(n,k+1)-G(n,k)$ for fixed $r\in\mathbb{N}$
and polynomials $p_{1}$ and $p_{2}$. Building on the work of Wilf, we apply a
series acceleration technique based on two-term hypergeometric recursions
derived via Zeilberger’s algorithm. Fast converging series previously given by
Ramanujan, Guillera, Chu and Zhang, Chu, Lupaş, and Amdeberhan are special
cases of hypergeometric transforms introduced in our article.

###### keywords:

Difference equation; series acceleration; Zeilberger’s algorithm;
hypergeometric series; closed form

††articletype: ARTICLE TEMPLATE

##  1 Introduction

Zeilberger’s algorithm [29, §6] is of great importance in terms of the use of
telescoping in the study of and application of hypergeometric functions.
Recent applications of Zeilberger’s algorithm have concerned computational
problems in the reduction of radicals [14], the study of families of
orthogonal polynomials that generalize the Askey scheme [21], and the covering
of graphs with affine hyperplanes [32]. The importance of Zeilberger’s
algorithm inside and outside of the field of symbolic computation is evidenced
by the influence of Paule and Schorn’s Mathematica implementation of
Zeilberger’s algorithm [28], the influence of Koornwinder’s work concerning
the Maple implementation of Zeilberger’s algorithm and the $q$-analogue of
Zeilberger’s algorithm [20], and the applications of variants and extensions
of Zeilberger’s algorithm, as in with the extended version of Zeilberger’s
algorithm due to Chen, Hou, and Mu [7]. The uses of Zeilberger’s algorithm in
the symbolic computation discipline motivate the development of Zeilberger-
based techniques for determining closed forms that are of interdisciplinary
significance in terms of how such closed forms may be applied within numerical
analysis, and in terms of the evaluation of number-theoretic constants. The
main purpose of this article is to apply a method based on Zeilberger’s
algorithm, building on the work of Wilf [33], Mohammed [27], and Hessami
Pilehrood and Hessami Pilehrood [17], for determining recursions for infinite
families of infinite hypergeometric series that may be applied so as to obtain
accelerated series for universal constants such as $\pi$ and $\frac{1}{\pi}$.

Our recursive approach toward the acceleration of hypergeometric series, as
described in Section 3 below, also builds on the previous work by Chu and
Zhang in [11], Levrie and Nimbran in [23], and Campbell and Levrie in [6, 22],
in which accelerated hypergeometric series were also obtained via
hypergeometric recursions. A main advantage as to how our accelerations build
on past references as in [11, 17, 22, 23, 27, 33] is given by how broadly our
Zeilberger-based technique may be applied to hypergeometric functions
involving multiple free parameters apart from $n$ and $k$, such as

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(n)_{k}^{2}}$ (1)

and

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(n)_{k}(2n)_{k}}$ (2)

and the many variants of (1) and (2) given in Section 4 below; in this regard,
by systematically searching through combinations of rational values for the
entries in the tuple $(a,b,n)$ such that the hypergeometric sum
$\sum_{k=0}^{\infty}F(n,k)$ reduces to a universal constant such as $\pi^{\pm
1}$, this is indicative of an advantage of our using $F$-functions with
multiple free parameters as in (1) and (2), since extending or mimicking the
methods of Wilf in [33] using $F$-functions with multiple free parameters
allows for a greater range of possibilities for closed-form values of
$\sum_{k=0}^{\infty}F(n,k)$, with reference to the constants and convergence
rates shown in Table 1, together with the motivating examples under
consideration in Section 2 below. Our techniques and applications inspired by
Wilf’s acceleration method from [33] have not been considered in past research
influenced by [33], including [2, 9, 11, 19, 24, 26].

$F(n,k)$ | Convergence rate | Constant(s) | Section
---|---|---|---
$\frac{(a)_{k}(b)_{k}}{(n)_{k}^{2}}$ | $\frac{1}{4}$ |  $\frac{1}{\pi}$, $\frac{\sqrt{2}}{\pi}$, $\frac{\sqrt{3}}{\pi}$, $\ln 2$, $G$, $\sqrt{2}$, $\sqrt{3}$, $\pi^{2}$ | 4.1
$\frac{(a)_{k}(b)_{k}}{(n)_{k}(2n)_{k}}$ | $\frac{4}{27}$ |  $\frac{1}{\pi}$, $\frac{\sqrt{2}}{\pi}$, $\frac{\sqrt{3}}{\pi}$, $\sqrt[3]{2}$, $\sqrt{2}$, $\sqrt{3}$, $\frac{\pi}{\sqrt{3}}$ | 4.2
$\frac{(a)_{k}(b)_{k}}{(n)_{k}(3n)_{k}}$ | $\frac{27}{256}$ |  $\frac{1}{\pi}$, $\frac{\sqrt{2}}{\pi}$ | 4.3
$\frac{(a)_{k}(b)_{k}}{(2n)_{k}(3n)_{k}}$ | $\frac{108}{3125}$ |  $\frac{\sqrt{2}}{\pi}$, $\frac{\sqrt{3}}{\pi}$, $\pi$ | 4.4
$\frac{(a)_{k}(b)_{k}}{(n)_{k}(a+n)_{k}}$ | $\frac{1}{4}$ |  $\frac{\pi}{\sqrt{2}}$, $\frac{\pi}{\sqrt{3}}$, $\sqrt[3]{2}$, $\pi$ | 4.5
$\frac{(a)_{k}(b)_{k}}{(n)_{k}(a+2n)_{k}}$ | $\frac{4}{27}$ |  $\frac{\pi}{\sqrt{2}}$, $\frac{\pi}{\sqrt{3}}$, $\pi$ | 4.6
$\frac{(a)_{k}(b)_{k}}{(2n)_{k}(a+n)_{k}}$ | $\frac{4}{27}$ |  $\sqrt[3]{2}$, $\sqrt{2}$, $\frac{\pi}{\sqrt{3}}$ | 4.7
$\frac{(-1)^{k}(a)_{k}(b)_{k}}{(a+n+1)_{k}(b+n+1)_{k}}$ | $-\frac{1}{4}$ |  $G$, $\sqrt[3]{2}$, $\sqrt{2}$, $\sqrt{3}$ | 4.8
$\frac{(a)_{k}^{3}}{(n)_{k}^{3}}$ | $-\frac{1}{27}$ | $\zeta(3)$ | 4.9
Table 1: Organization of Section 4, based on the acceleration method described
in Section 3. We are letting Catalan’s constant be denoted as
$G=1-\frac{1}{3^{2}}+\frac{1}{5^{2}}-\cdots$, and we let Apéry’s constant be
denoted as $\zeta(3)=1+\frac{1}{2^{3}}+\frac{1}{3^{3}}+\cdots$.

##  2 Motivating results and background

Our method is such that fast converging series evaluations given by Ramanujan
[31], Guillera [16], Chu and Zhang [11], Chu [8], Chu [9], Lupaş [24], and
Amdeberhan [1] are special cases of our method. In addition to our new,
recursive proofs of these past results, we highlight a number of our new
results, as below. To begin with, we briefly review some necessary
preliminaries.

For $\Re(x)>0$, the $\Gamma$-function is such that
$\Gamma(x)=\int_{0}^{\infty}u^{x-1}e^{-u}\,du$ [30, §8]. Our applications of
our techniques to obtain the symbolic evaluations in Section 4 often require
the use of the reflection formula

$\Gamma(x)\Gamma(1-x)=\frac{\pi}{\sin(\pi x)}$

and the Gauss multiplication formula

$\Gamma(mx)=(2\pi)^{\frac{1-m}{2}}m^{mx-\frac{1}{2}}\prod_{k=0}^{m-1}\Gamma\left(x+\frac{k}{m}\right).$

The Pochhammer symbol $(x)_{n}$ or rising factorial function is such that
$(x)_{n}=\frac{\Gamma(x+n)}{\Gamma(x)}$, with $(x)_{n}=x(x+1)\cdots(x+n-1)$
for $n\in\mathbb{N}$, and it is not uncommon to write

$\left[\begin{matrix}\alpha,\beta,\ldots,\gamma\vspace{1mm}\\\
A,B,\ldots,C\end{matrix}\right]_{n}=\frac{(\alpha)_{n}(\beta)_{n}\cdots(\gamma)_{n}}{(A)_{n}(B)_{n}\cdots(C)_{n}}.$

As indicated above, our article is devoted to providing and applying new
techniques concerning recursions for hypergeometric series. In this regard, we
recall that generalized hypergeometric series may be defined so that [3]

${}_{p}F_{q}\\!\\!\left[\begin{matrix}a_{1},a_{2},\ldots,a_{p}\vspace{1mm}\\\
b_{1},b_{2},\ldots,b_{q}\end{matrix}\ \Bigg{|}\
x\right]=\sum_{n=0}^{\infty}\left[\begin{matrix}a_{1},a_{2},\ldots,a_{p}\vspace{1mm}\\\
b_{1},b_{2},\ldots,b_{q}\end{matrix}\right]_{n}\frac{x^{n}}{n!},$ (3)

and we let the argument $x$ in (3) be referred to as the rate of convergence
for the series in (3).

We are now in a position to present new formulas introduced in this article as
in the following motivating examples:

(§4.2)
$\displaystyle\frac{768}{\pi}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{1}{2},\frac{3}{4},\frac{3}{4},\frac{5}{4},\frac{5}{4}\vspace{1mm}\\\
1,\frac{4}{3},\frac{5}{3},2,2\end{matrix}\right]_{j}(368j^{3}+952j^{2}+810j+225),$
(4) (§4.8)
$\displaystyle\frac{1215}{7}\sqrt[3]{2}=\sum_{j=0}^{\infty}\left(-\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{2}{3},\frac{11}{12},\frac{17}{12},\frac{13}{6}\vspace{1mm}\\\
1,\frac{3}{2},\frac{7}{4},\frac{9}{4}\end{matrix}\right]_{j}\left(360j^{2}+678j+299\right),$
(5) (§4.5)
$\displaystyle\frac{55\pi}{18}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{5}{6},\frac{5}{6},1\vspace{1mm}\\\
\frac{7}{6},\frac{17}{12},\frac{23}{12}\end{matrix}\right]_{j}(18j^{2}+23j+6),$
(6) (§4.2)
$\displaystyle\frac{2187\sqrt{3}}{4\pi}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{1}{3},\frac{2}{3},\frac{5}{6},\frac{7}{6}\vspace{1mm}\\\
1,\frac{3}{2},2,2\end{matrix}\right]_{j}(621j^{3}+1503j^{2}+1164j+280),$ (7)
(§4.8) $\displaystyle
5\sqrt{3}=\sum_{j=0}^{\infty}\left(-\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{1}{4},\frac{2}{3},\frac{3}{4},\frac{5}{6}\vspace{1mm}\\\
\frac{11}{12},1,\frac{17}{12},\frac{3}{2}\end{matrix}\right]_{j}\left(60j^{2}+51j+10\right),$
(8) (§4.5)
$\displaystyle\frac{4}{3}\sqrt[3]{2}={}_{2}F_{1}\\!\\!\left[\begin{matrix}\frac{1}{2},\frac{2}{3}\vspace{1mm}\\\
\frac{1}{6}\end{matrix}\ \Bigg{|}\ \frac{1}{4}\right],$ (9) (§4.2)
$\displaystyle\frac{480\pi}{7\sqrt{3}}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{2}{3},1,\frac{3}{2},\frac{13}{6}\vspace{1mm}\\\
\frac{4}{3},\frac{11}{6},\frac{7}{3},\frac{7}{3}\end{matrix}\right]_{j}(69j^{3}+247j^{2}+284j+104),$
(10) (§4.3)
$\displaystyle\frac{33554432\sqrt{2}}{105\pi}=\sum_{j=0}^{\infty}\left(\frac{27}{256}\right)^{j}\left[\begin{matrix}\frac{1}{4},\frac{3}{4},\frac{11}{12},\frac{13}{12},\frac{17}{12},\frac{19}{12}\vspace{1mm}\\\
1,\frac{3}{2},\frac{5}{3},2,2,\frac{7}{3}\end{matrix}\right]_{j}\cdot$
$\displaystyle\hskip
36.135pt(175872j^{4}+684544j^{3}+979360j^{2}+609312j+138567),$ (11) (§4.7)
$\displaystyle
45\sqrt{2}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{3}{8},\frac{3}{8},\frac{1}{2},\frac{7}{8},\frac{7}{8}\vspace{1mm}\\\
\frac{3}{4},1,\frac{13}{12},\frac{17}{12},\frac{7}{4}\end{matrix}\right]_{j}(1472j^{3}+1840j^{2}+618j+45),$
(12) (§4.9) $\displaystyle
567\zeta(3)=\sum_{j=0}^{\infty}\left(-\frac{1}{27}\right)^{j}\left[\begin{matrix}\frac{1}{2},\frac{1}{2},\frac{1}{2},1,1,1,1,1\vspace{1mm}\\\
\frac{5}{4},\frac{5}{4},\frac{5}{4},\frac{4}{3},\frac{5}{3},\frac{7}{4},\frac{7}{4},\frac{7}{4}\end{matrix}\right]_{j}\cdot$
$\displaystyle\hskip
36.135pt(7168j^{5}+23168j^{4}+29584j^{3}+18620j^{2}+5761j+698).$ (13)

The above series of convergence rates $\pm\frac{1}{4}$ and $\frac{4}{27}$ have
not previously appeared in relevant literature on accelerated series of such
convergence rates, as in [8, 9, 10, 11]. Many of the above results are heavily
inspired by the accelerated series from references due to Chu et al. as in [8,
9, 10, 11], in which Zeilberger’s algorithm is not involved and WZ theory is
not involved. For example, the motivating example in (4) recalls Example 106
from [11]:

$\frac{32}{\pi}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{1}{2},\frac{1}{4},\frac{1}{4},\frac{3}{4},\frac{3}{4}\vspace{1mm}\\\
1,1,1,\frac{4}{3},\frac{5}{3}\end{matrix}\right]_{j}(368j^{3}+400j^{2}+118j+9),$

but our acceleration method allows us to evaluate series of convergence rates
not involved in references as in [8, 9, 10, 11], and our acceleration method
allows us to determine new proofs of and generalizations of results from
references as in [8, 9, 10, 11]. The 2022 version of the Maple Computer
Algebra System (CAS) cannot evaluate any of the new series given in this
article or the partial sums for such series, as is the case with respect to
the 2022 version of the Mathematica CAS.

In addition to the work of Chu et al. as in [8, 9, 10, 11], our above formulas
for $\frac{1}{\pi}$ and algebraic multiples of $\frac{1}{\pi}$ are directly
inspired by the famous formulas for expressions of such forms due to Ramanujan
[31]. As in each of the articles by Chu et al. among [8, 9, 10, 11], each of
which has heavily motivated our explorations based on new results as in
(4)–(13), we highlight the following formulas due to Ramanujan [31] as being
sources of inspiration underlying our research. Observe that the convergence
rates of $\pm\frac{1}{4}$ in the below formulas due to Ramanujan agree with
(5), (6), (8), and (9):

$\displaystyle\frac{4}{\pi}=\sum_{n=0}^{\infty}\left(\frac{1}{4}\right)^{n}\left[\begin{matrix}\frac{1}{2},\frac{1}{2},\frac{1}{2}\vspace{1mm}\\\
1,1,1\end{matrix}\right]_{n}\left(6n+1\right),$ (14)
$\displaystyle\frac{8}{\pi}=\sum_{n=0}^{\infty}\left(-\frac{1}{4}\right)^{n}\left[\begin{matrix}\frac{1}{4},\frac{1}{2},\frac{3}{4}\vspace{1mm}\\\
1,1,1\end{matrix}\right]_{n}\left(20n+3\right).$

Our acceleration method described in Section 3 and inspired by Wilf’s work in
[33] is such that we may apply this method to formulate a new proof of
Ramanujan’s formula in (14). This recalls Zeilberger’s proof via the WZ
method, as opposed to Zeilberger’s algorithm, for Ramanujan’s
${}_{4}F_{3}(-1)$-series for $\frac{1}{\pi}$ [13], along with Guillera’s WZ
proof of (14) [15].

The ${}_{2}F_{1}\left(\frac{1}{4}\right)$-evaluation shown in (9) is
especially notable, in terms of how it stands out against the neighbouring
formulas among (4)–(8) and (10), since a (nontrivial) polynomial in $n$ is not
involved in the summand of (9). What is even more striking about the formula
for $\sqrt[3]{2}$ in (9) is due to how it relates to the below listed
${}_{2}F_{1}$-formulas from Zucker and Joyce [18, 34] that are highlighted in
the Wolfram MathWorld entry on hypergeometric functions. In this encyclopedia
entry, it is suggested how curious it is how ${}_{2}F_{1}$-functions can
assume integer root values for very specific rational arguments and rational
parameters, as below, again noting the resemblance to our new formula in (9):

$\displaystyle\frac{2}{3}\sqrt{7}={}_{2}F_{1}\\!\\!\left[\begin{matrix}\frac{1}{8},\frac{3}{8}\vspace{1mm}\\\
\frac{1}{2}\end{matrix}\ \Bigg{|}\ \frac{2400}{2401}\right],$
$\displaystyle\frac{3}{4}\sqrt{3}={}_{2}F_{1}\\!\\!\left[\begin{matrix}\frac{1}{6},\frac{1}{3}\vspace{1mm}\\\
\frac{1}{2}\end{matrix}\ \Bigg{|}\ \frac{25}{27}\right],$
$\displaystyle\frac{4}{3}2^{1/6}={}_{2}F_{1}\\!\\!\left[\begin{matrix}\frac{1}{6},\frac{1}{2}\vspace{1mm}\\\
\frac{2}{3}\end{matrix}\ \Bigg{|}\ \frac{125}{128}\right],$
$\displaystyle\frac{3}{4}11^{1/4}={}_{2}F_{1}\\!\\!\left[\begin{matrix}\frac{1}{12},\frac{5}{12}\vspace{1mm}\\\
\frac{1}{2}\end{matrix}\ \Bigg{|}\ \frac{1323}{1331}\right].$

The above series for $\frac{\sqrt{2}}{\pi}$ of convergence rate
$\frac{27}{256}$ shown in (11) is also of especial interest. To the best of
our knowledge, the only series of convergence rate $\frac{27}{256}$ that have
previously appeared are the following series given by Chu [8] via Dougall’s
bilateral ${}_{2}H_{2}$-sum. These past series motivate the new Zeilberger-
based techniques we have introduced for generating and proving evaluations for
series of convergence rate $\frac{27}{256}$:

$\displaystyle\frac{1287\sqrt{3}}{\pi}=\sum_{j=0}^{\infty}\left(\frac{27}{256}\right)^{j}\left[\begin{matrix}\frac{1}{9},\frac{2}{9},\frac{4}{9},\frac{5}{9},\frac{7}{9},\frac{8}{9}\vspace{1mm}\\\
1,1,1,\frac{3}{2},\frac{5}{4},\frac{7}{4}\end{matrix}\right]_{j}\cdot$
$\displaystyle\hskip
108.405pt\text{\footnotesize$(166941j^{4}+260253j^{3}+130464j^{2}+23202j+1120)$},$
$\displaystyle
105\pi=\sum_{j=1}^{\infty}\left(\frac{27}{256}\right)^{j}\left[\begin{matrix}1,\frac{1}{2},\frac{1}{6},\frac{1}{6},\frac{5}{6},\frac{5}{6}\vspace{1mm}\\\
\frac{4}{3},\frac{5}{3},\frac{9}{8},\frac{11}{8},\frac{13}{8},\frac{15}{8}\end{matrix}\right]_{j}\cdot$
$\displaystyle\hskip
108.405pt\text{\footnotesize$(16488j^{5}+42192j^{4}+40606j^{3}+18247j^{2}+3842j+317)/j$},$
$\displaystyle
60\pi-149=\sum_{j=1}^{\infty}\left(\frac{27}{256}\right)^{j}\left[\begin{matrix}1,\frac{1}{2},\frac{1}{6},\frac{1}{6},\frac{5}{6},\frac{5}{6}\vspace{1mm}\\\
\frac{4}{3},\frac{5}{3},\frac{7}{8},\frac{9}{8},\frac{11}{8},\frac{13}{8}\end{matrix}\right]_{j}\cdot$
$\displaystyle\hskip
108.405pt\text{\footnotesize$(32976j^{5}+67896j^{4}+52844j^{3}+19156j^{2}+3167j+180)/j$}.$

We have adopted a “Chu-style” [5] way of denoting hypergeometric series in the
vein of [8, 9, 10, 11], by expressing universal constants in the form

$\sum_{n=0}^{\infty}x^{n}\left[\begin{matrix}\alpha,\beta,\ldots,\gamma\vspace{1mm}\\\
A,B,\ldots,C\end{matrix}\right]_{n}p(n),$ (15)

for a fixed argument $x$ and for a polynomial (or rational function) $p(n)$,
and where for a lower Pochhammer symbol $(\ell)_{n}$ in (15), it is not the
case that there is an upper Pochhammer symbol $(u)_{n}$ in (15) such that
$\ell-u$ is a member of $\mathbb{Z}$.

Our interest in the series for $\frac{\sqrt{2}}{\pi}$ shown in (11) is also
motivated by Ramanujan’s famous series for the same value of
$\frac{\sqrt{2}}{\pi}$, as below [31]:

$\displaystyle\frac{\sqrt{2}}{\pi}=\frac{4}{9}\sum_{n=0}^{\infty}\left(\frac{1}{3}\right)^{4n}\left[\begin{matrix}\frac{1}{2},\frac{1}{4},\frac{3}{4}\vspace{1mm}\\\
1,1,1\end{matrix}\right]_{n}(10n+1),$
$\displaystyle\frac{\sqrt{2}}{\pi}=\frac{4}{9801}\sum_{n=0}^{\infty}\left(\frac{1}{99}\right)^{4n}\left[\begin{matrix}\frac{1}{2},\frac{1}{4},\frac{3}{4}\vspace{1mm}\\\
1,1,1\end{matrix}\right]_{n}(26390n+1103).$

##  3 A Zeilberger-based series acceleration method

For the sake of brevity, we assume some basic familiarity with Zeilberger’s
algorithm [29, §6] and with bivariate hypergeometric functions and the like.
We have systematically performed computational experiments with Maple using
the package given by the input

    with(SumTools[Hypergeometric]):

and with the use of bivariate hypergeometric functions $F(n,k)$ that satisfy
the following:

  1. 1.

The expression $F(n,k)$ satisfies a first-order recurrence according to
Zeilberger’s algorithm, with respect to $n$;

  2. 2.

The expression $F(n,k)$ may be written so as to contain a factor given by the
reciprocal of a Pochhammer symbol involving $n$ as its initial argument;

  3. 3.

Letting the phrase _$n$ -Pochhammer expression_ refer to a Pochhammer symbol
$(\alpha)_{\beta}$ such that $\alpha$ is a rational linear combination of
variables that include $n$ and such that the coefficient of $n$ is nonzero,
the number of lower $n$-Pochhammer expressions in $F(n,k)$ minus the number of
upper $n$-Pochhammer expressions in $F(n,k)$ is at least $2$;

  4. 4.

Letting $G(n,k)$ denote the companion to $F(n,k)$ obtained via Zeilberger’s
algorithm, the limit $\lim_{\ell\to\infty}G(n,\ell)$ vanishes for sufficiently
large $n$; and

  5. 5.

The expression $G(n,0)$ is non-vanishing.

Given a function $F(n,k)$ satisfying the above conditions, we may write

$p_{1}(n)F(n+r,k)+p_{2}(n)F(n,k)=G(n,k+1)-G(n,k)$ (16)

for (nonzero) polynomials $p_{1}$ and $p_{2}$ with integer coefficients and
for fixed $r\in\mathbb{N}$ (typically with $r=1$). Since this construction is
closely related to what is meant by a _Markov–WZ pair_ , it is appropriate to
review the definition of this term given in references such as [17, 27],
recalling that a function that satisfies a linear recurrence with polynomial
coefficients is said to be _P-recursive_.

######  Definition 3.1.

A pair $(F,G)$ of bivariate hypergeometric functions is said to be a
_Markov–WZ_ pair if there is a polynomial $p(n,k)$ of the form

$p(n,k)=a_{0}(n)+a_{1}(n)k+\cdots+a_{\ell}(n)k^{\ell}$

for fixed $\ell\in\mathbb{N}_{0}$ and P-recursive functions $a_{0}(n)$,
$a_{1}(n)$, $\ldots$, $a_{\ell}(n)$ whereby

$p(n+1,k)F(n+1,k)-p(n,k)F(n,k)=G(n,k+1)-G(n,k).$ (17)

So, for the $r=1$ case of (16), a pair $(F,G)$ satisfying (16) is closely
related to what is meant by a Markov–WZ pair, but we do not insist that
$p_{1}(n)=p_{2}(n+1)$, noting the distinction between the difference equation
in (16) and the difference equation in (17).

By writing $f(n)=\sum_{k=0}^{\infty}F(n,k)$, a telescoping phenomenon applied
to (16) gives us that

$p_{1}(n)f(n+r)+p_{2}(n)f(n)=-G(n,0),$ (18)

which we rewrite as

$f(n)=\frac{-G(n,0)}{p_{2}(n)}-\frac{p_{1}(n)}{p_{2}(n)}f(n+r).$ (19)

The repeated application of the $f$-recursion in (19) typically has the effect
of accelerating the convergence of $f$ (cf. [33]), as explored in this
article, again for hypergeometric expressions $F(n,k)$ satisfying the above
listed conditions. Wilf, in [33], introduced the idea of accelerating series
using recursions as in (19) derived via Zeilberger’s algorithm, and Mohammed
[27] explored related accelerated techniques. In this article, we pursue a
full exploration of the acceleration of series using (19) for functions
$F(n,k)$ satisfying the above conditions and with free parameters apart from
$n$ and $k$ involved. This has led us to obtain many new hypergeometric
transforms that are not considered in Wilf’s article [33] or in related work
on Markov–WZ pairs as in [17, 27].

Our experimental use of the Maple CAS has led us to discover how our
acceleration technique may be broadly applied to functions $F(n,k)$ of the
forms indicated as follows:

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(\alpha_{1}+\beta_{1}n)_{k}(\alpha_{2}+\beta_{2}n)_{k}}$
(20)

for free parameters $a$ and $b$ and for fixed parameters $\alpha_{1}$,
$\beta_{1}$, $\alpha_{2}$, and $\beta_{2}$ that we typically set so that
$\beta_{1},\beta_{2}\in\mathbb{N}$. Our application of our Zeilberger-based
acceleration technique using (20) is such that $r=1$ for the recursion
indicated in (19) and for most of the hypergeometric functions $F(n,k)$
considered in this article. In such cases, by rewriting (19) as

$f(n)=g_{1}(n)+g_{2}(n)f(n+1)$ (21)

for rational functions $g_{1}(n)$ and $g_{2}(n)$, the inductive application of
(21) gives us that

$f(n)=\sum_{j=0}^{\infty}\left(\prod_{i=0}^{j-1}g_{2}(n+i)\right)g_{1}(n+j)$
(22)

if

$\lim_{m\to\infty}\prod_{i=0}^{m}g_{2}(n+i)f(n+m+1)$ (23)

vanishes (cf. [33]), in which case the equation in (22) gives us series
accelerations for the hypergeometric functions $F(n,k)$ considered in this
article. It is appropriate to refer to a recursion as in (21) as a two-term
recursion, and this is consistent with combinatorial work on general two-term
recurrences as in [25].

The organization of Section 4 is summarized in Table 1. The organization of
our article, with reference to Table 1 and a similarly organized Table in
[22], is inspired by our past work on hypergeometric recursions and series
accelerations [22], which did not involve Zeilberger’s algorithm, and which
relied on “ad hoc” and experimentally discovered recursions, compared to how
systematically we can apply the method given in our current article.

##  4 Main results

Each of the following subsections is based on a given selection of a
hypergeometric function $F$ satisfying the conditions listed in Section 3.

###  4.1 An acceleration based on $\frac{(a)_{k}(b)_{k}}{(n)_{k}^{2}}$

We begin by setting $F(n,k)$ to be as in (1), and by determining that the
function in (1) satisfies the first out of the conditions listed in Section 3.
In this regard, we may apply the Maple implementation of Zeilberger’s
algorithm to compute the companion function $G(n)=R(n,k)F(n,k)$, where

$R(n,k)=-n^{2}\left(-2n(a+b-k+1)+ab-ak+a-bk+b+3n^{2}\right).$ (24)

This leads us toward the following recursion that we are to apply via
accelerations of series of the form $\sum_{k=0}^{\infty}F(n,k)$.

######  Theorem 4.1.

Letting $f(n)$ denote the hypergeometric series $\sum_{k=0}^{\infty}F(n,k)$,
where $F(n,k)$ is as in (1), the recursion

$f(n)=\frac{a+b+ab-2(1+a+b)n+3n^{2}}{(a+b-2n)(1+a+b-2n)}+\frac{(a-n)^{2}(b-n)^{2}}{(a+b-2n)(1+a+b-2n)n^{2}}f(n+1)$

holds if the above series converge.

###### Proof.

Using Zeilberger’s algorithm, we may determine that

$\displaystyle-(a-n)^{2}(b-n)^{2}F(n+1,k)+n^{2}(-1-a-b+2n)(-a-b+2n)F(n,k)$
$\displaystyle=G(n,k+1)-G(n,k),$

again writing $G(n,k)=F(n,k)R(n,k)$ for the rational function $R(n,k)$
indicated in (24). Applying the partial sum operator $\sum_{k=0}^{m}\cdot$ to
both sides of the above equality, the right-hand side telescopes, so that

$\displaystyle-(a-n)^{2}(b-n)^{2}\sum_{k=0}^{m}F(n+1,k)+n^{2}(-1-a-b+2n)(-a-b+2n)\sum_{k=0}^{m}F(n,k)$
$\displaystyle=G(n,m+1)-G(n,0),$

we let $m\to\infty$, with $\lim_{m\to\infty}G(n,m+1)$ vanishing for $n$ such
that $\sum_{k=0}^{\infty}F(n,k)$ converges. This gives us an equivalent
formulation of the desired result, since it is easily seen that (23) vanishes.
∎

Setting

$g_{1}(n)=\frac{a+b+ab-2(1+a+b)n+3n^{2}}{(a+b-2n)(1+a+b-2n)}$

and

$g_{2}(n)=\frac{(a-n)^{2}(b-n)^{2}}{(a+b-2n)(1+a+b-2n)n^{2}},$

repeated applications of the hypergeometric recursion in Theorem 4.1 give us
that a recursion of the form indicated in (22) holds. This gives us a series
acceleration identity that we are to apply as below.

######  Example 4.2.

Setting $(a,b,n)=\left(\frac{1}{2},\frac{1}{2},2\right)$, we obtain a new,
Zeilberger-based proof of Ramanujan’s formula in (14).

######  Example 4.3.

Setting $(a,b,n)=\left(\frac{1}{2},\frac{1}{2},\frac{3}{2}\right)$, we obtain
Guillera’s formula

$\frac{\pi^{2}}{4}=\sum_{n=0}^{\infty}\left(\frac{1}{4}\right)^{n}\left[\begin{matrix}1,1,1\vspace{1mm}\\\
\frac{3}{2},\frac{3}{2},\frac{3}{2}\end{matrix}\right]_{j}(3n+2),$ (25)

introduced in [16].

######  Example 4.4.

Setting $(a,b,n)=\left(\frac{1}{2},1,\frac{3}{2}\right)$, we obtain a new
proof of Example 84 from Chu and Zhang’s article [11]:

$6G=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{n}\left[\begin{matrix}1,1\vspace{1mm}\\\
\frac{5}{4},\frac{7}{4}\end{matrix}\right]_{j}\frac{6j+5}{2j+1}.$

######  Example 4.5.

Setting $(a,b,n)=\left(\frac{3}{4},\frac{5}{4},2\right)$,

$\frac{2\sqrt{2}}{\pi}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}-\frac{1}{4},-\frac{1}{4},\frac{1}{4},\frac{1}{4}\vspace{1mm}\\\
\frac{1}{2},1,1,1\end{matrix}\right]_{j}(1-48j^{2}).$

######  Example 4.6.

Setting $(a,b,n)=\left(\frac{3}{2},1,2\right)$, we obtain that

$3\ln(2)=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{1}{2},\frac{1}{2}\vspace{1mm}\\\
\frac{5}{4},\frac{7}{4}\end{matrix}\right]_{j}\frac{3j+2}{j+1}.$

######  Example 4.7.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{2}{3},2\right)$, we obtain a new
proof of Example 9 from Chu’s article [8], which is reproduced below:

$\frac{9\sqrt{3}}{2\pi}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{1}{3},\frac{1}{3},\frac{2}{3},\frac{2}{3}\vspace{1mm}\\\
1,1,1,\frac{3}{2}\end{matrix}\right]_{j}(27j^{2}+18j+2).$

######  Example 4.8.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{2}{3},\frac{3}{2}\right)$, we may
obtain that

$\frac{\sqrt{3}}{2}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}-\frac{1}{6},-\frac{1}{6},\frac{1}{6},\frac{1}{6}\vspace{1mm}\\\
\frac{1}{2},\frac{1}{2},\frac{1}{2},1\end{matrix}\right]_{j}(1+36j-108j^{2}).$

######  Example 4.9.

Setting $(a,b,n)=\left(\frac{1}{6},\frac{5}{6},2\right)$, we may obtain a new
proof of Example 15 from Chu’s article [8]:

$\frac{18}{\pi}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{1}{6},\frac{1}{6},\frac{5}{6},\frac{5}{6}\vspace{1mm}\\\
1,1,1,\frac{3}{2}\end{matrix}\right]_{j}(108j^{2}+72j+5).$

######  Example 4.10.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{3}{4},\frac{3}{2}\right)$, we may
obtain that

$\frac{\sqrt{2}}{2}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}-\frac{1}{4},-\frac{1}{4},\frac{1}{4},\frac{1}{4}\vspace{1mm}\\\
\frac{1}{2},\frac{1}{2},\frac{1}{2},1\end{matrix}\right]_{j}(1+16j-48j^{2}).$

By setting

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(k+n)(n)_{k}^{2}},$ (26)

we may obtain many variants of the above series, and many similar
generalizations by generalizing (26).

######  Example 4.11.

Setting $(a,b,n)=\left(-\frac{3}{4},-\frac{1}{4},1\right)$ in the acceleration
derived from (26), we may obtain that

$\frac{16384\sqrt{2}}{105\pi}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{5}{4},\frac{7}{4},\frac{9}{4},\frac{11}{4}\vspace{1mm}\\\
1,2,\frac{5}{2},3\end{matrix}\right]_{j}(16j^{2}+48j+33).$

###  4.2 An acceleration based on $\frac{(a)_{k}(b)_{k}}{(n)_{k}(2n)_{k}}$

We refer to Chu and Zhang’s article [11] on hypergeometric series
accelerations derived via the modified Abel lemma and Dougall’s
${}_{5}F_{4}$-sum, together with references therein, such as the seminal work
by the Chudnovsky brothers [12] and the excellent survey by Baruah et al. on
Ramanujan’s series for $\frac{1}{\pi}$ [4], for background material on the
historical importance of the computational problems concerning the fundamental
constant $\pi$. Since we have applied our acceleration method to obtain a new
proof of Ramanujan’s series for $\frac{1}{\pi}$ in (14), a new proof of
Guillera’s series for $\pi^{2}$ in (25), as well as new proofs of series for
$\frac{1}{\pi}$ and $\frac{\sqrt{3}}{\pi}$ given by Chu and Zhang [11], with
Theorem 4.1 and the corresponding acceleration formula in (22) providing
infinite generalizations for all of these past formulas, this inspires further
applications of the method from Section 3, to obtain faster converging series
relative to Section 4.1. In this regard, by setting $F(n,k)$ to be as in (2),
and by again applying the acceleration technique indicated in Section 3, this
leads us to a hypergeometric transform that may be used to generate series of
convergence rate $\frac{4}{27}\approx 0.148148$.

######  Theorem 4.12.

Letting $f(n)=\sum_{k=0}^{\infty}F(n,k)$ for the hypergeometric function
$F(n,k)$ in (2), the recursion $f(n)=g_{1}(n)+g_{2}(n)f(n+1)$ holds, for

$g_{2}(n)=-\frac{(a-2n-1)(a-2n)(a-n)(b-2n-1)(b-2n)(b-n)}{2n^{2}(2n+1)(a+b-3n-1)(a+b-3n)(a+b-3n+1)}$

and for $g_{1}(n)$ equals to the expression given by the following Mathematica
output.

    Ψ-((a n (2 - b (2 + 5 b) + 6 n + 27 b n - 38 n^2) +
    Ψa^2 (b^2 - 5 b n + 2 n (-1 + 4 n)) +
    Ψ2 n (b + b (3 - 19 n) n + b^2 (-1 + 4 n) +
    Ψn (-3 + n (-2 + 23 n))))/(
    Ψ2 (-1 + a + b - 3 n) (a + b - 3 n) (1 + a + b - 3 n) n))
    Ψ

###### Proof.

We again set $F(n,k)$ to be as indicated in (2). Applying Zeilberger’s
algorithm, we obtain a companion function $G(n,k)=R(n,k)F(n,k)$, for a
rational function $R(n,k)$ given by the following Mathematica output.

    Ψ(1/(k + 2 n))2 n^2 (1 +
    Ψ2 n) ((-1 + b) b (-1 + k) k + (3 (-1 + k) k + b^2 (-2 + 5 k) +
    Ψb (2 + k - 6 k^2)) n + (-6 + 8 b^2 + b (6 - 28 k) +
    Ψk (4 + 9 k)) n^2 + (-4 - 38 b + 39 k) n^3 + 46 n^4 +
    Ψa (-k (-1 + b + b^2 + k - 2 b k) + (2 - b (2 + 5 b) + k + 13 b k -
    Ψ6 k^2) n + (6 + 27 b - 28 k) n^2 - 38 n^3) +
    Ψa^2 (b^2 + (-1 + k) k + (-2 + 5 k) n + 8 n^2 - b (k + 5 n)))
    Ψ

Moreover, Zeilberger’s algorithm gives us that a difference equation of the
form indicated in (16) holds for $r=1$. In this case, the polynomial
$p_{1}(n)$ is given by the following Mathematica output.

    Ψ(a^3*b^3 - 5*a^3*b^2*n + 8*a^3*b*n^2 - 4*a^3*n^3 - 5*a^2*b^3*n +
    Ψ25*a^2*b^2*n^2 - 40*a^2*b*n^3 + 20*a^2*n^4 + 8*a*b^3*n^2 -
    Ψ40*a*b^2*n^3 + 64*a*b*n^4 - 32*a*n^5 - 4*b^3*n^3 + 20*b^2*n^4 -
    Ψ32*b*n^5 + 16*n^6 - a^3*b^2 + 3*a^3*b*n - 2*a^3*n^2 - a^2*b^3 +
    Ψ10*a^2*b^2*n - 23*a^2*b*n^2 + 14*a^2*n^3 + 3*a*b^3*n -
    Ψ23*a*b^2*n^2 + 48*a*b*n^3 - 28*a*n^4 - 2*b^3*n^2 + 14*b^2*n^3 -
    Ψ28*b*n^4 + 16*n^5 + a^2*b^2 - 3*a^2*b*n + 2*a^2*n^2 - 3*a*b^2*n +
    Ψ9*a*b*n^2 - 6*a*n^3 + 2*b^2*n^2 - 6*b*n^3 + 4*n^4)
    Ψ

The corresponding polynomial $p_{2}(n)$ is given by the following Mathematica
output.

    Ψ(-108*n^6 + 4*a^3*n^3 - 36*a^2*n^4 + 108*a*n^5 + 2*a^3*n^2 -
    Ψ18*a^2*n^3 - 54*n^5 + 6*a^2*b*n^2 + 6*a*b^2*n^2 - 36*a*b*n^3 -
    Ψ2*b*n^2 - 4*b*n^3 + 12*a*b^2*n^3 + 12*a^2*b*n^3 - 72*a*b*n^4 -
    Ψ2*a*n^2 + 12*n^4 + 6*n^3 + 4*b^3*n^3 - 36*b^2*n^4 + 108*b*n^5 +
    Ψ2*b^3*n^2 - 18*b^2*n^3 + 54*b*n^4 + 54*a*n^4 - 4*a*n^3)
    Ψ

Manipulating the difference equation in (16) so as to obtain (18) for $r=1$,
the equivalent expression in (19) is equivalent to the desired result, as it
is easily seen that (23) vanishes. ∎

######  Example 4.13.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{3}{4},1\right)$, we may obtain that

$\displaystyle\frac{8192\sqrt{2}}{\pi}=$
$\displaystyle\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{1}{4},\frac{5}{8},\frac{3}{4},\frac{7}{8},\frac{9}{8},\frac{11}{8}\vspace{1mm}\\\
1,\frac{4}{3},\frac{3}{2},\frac{5}{3},2,2\end{matrix}\right]_{j}(11776j^{4}+36352j^{3}+40976j^{2}+19856j+3465).$

######  Example 4.14.

Setting $(a,b,n)=\left(\frac{1}{2},\frac{1}{2},1\right)$, we may obtain the
motivating example highlighted in (4).

######  Example 4.15.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{2}{3},1\right)$, we may obtain the
motivating example highlighted in (7).

######  Example 4.16.

Setting $(a,b,n)=\left(\frac{1}{6},\frac{5}{6},1\right)$, we may obtain that

$\displaystyle\frac{279936}{5\pi}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}$
$\displaystyle\left[\begin{matrix}\frac{1}{6},\frac{7}{12},\frac{5}{6},\frac{11}{12},\frac{13}{12},\frac{17}{12}\vspace{1mm}\\\
1,\frac{4}{3},\frac{3}{2},\frac{5}{3},2,2\end{matrix}\right]_{j}\cdot$
$\displaystyle(59616j^{4}+184032j^{3}+206748j^{2}+99324j+17017).$

######  Example 4.17.

Setting $(a,b,n)=\left(-\frac{3}{4},-\frac{1}{4},\frac{1}{2}\right)$, we may
obtain that

$\displaystyle 3360\sqrt{2}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}$
$\displaystyle\left[\begin{matrix}\frac{5}{8},\frac{3}{4},\frac{7}{8},\frac{9}{8},\frac{5}{4},\frac{11}{8}\vspace{1mm}\\\
\frac{1}{2},1,\frac{3}{2},\frac{3}{2},\frac{11}{6},\frac{13}{6}\end{matrix}\right]_{j}\cdot$
$\displaystyle(11776j^{4}+32256j^{3}+30224j^{2}+11232j+1365).$

######  Example 4.18.

Setting $(a,b,n)=\left(-\frac{2}{3},\frac{2}{3},\frac{4}{3}\right)$, we may
obtain the motivating example highlighted in (10).

######  Example 4.19.

Setting $(a,b,n)=\left(-\frac{5}{6},-\frac{1}{6},\frac{1}{2}\right)$, we may
obtain that

$\displaystyle\frac{25515\sqrt{3}}{8}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}$
$\displaystyle\left[\begin{matrix}\frac{7}{12},\frac{2}{3},\frac{11}{12},\frac{13}{12},\frac{4}{3},\frac{17}{12}\vspace{1mm}\\\
\frac{1}{2},1,\frac{3}{2},\frac{3}{2},\frac{11}{6},\frac{13}{6}\end{matrix}\right]_{j}\cdot$
$\displaystyle(14904j^{4}+40824j^{3}+38079j^{2}+13932j+1624).$

######  Example 4.20.

Setting $(a,b,n)=\left(-\frac{2}{3},-\frac{1}{6},\frac{1}{2}\right)$, we may
obtain that

$\displaystyle
3360\sqrt[3]{2}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}$
$\displaystyle\left[\begin{matrix}\frac{7}{12},\frac{2}{3},\frac{5}{6},\frac{13}{12},\frac{7}{6},\frac{4}{3}\vspace{1mm}\\\
\frac{1}{2},1,\frac{13}{9},\frac{3}{2},\frac{16}{9},\frac{19}{9}\end{matrix}\right]_{j}\cdot$
$\displaystyle(14904j^{4}+38772j^{3}+34434j^{2}+12039j+1330).$

###  4.3 Series of convergence rate $\frac{27}{256}$

We now are to set

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(n)_{k}(3n)_{k}}$ (27)

and to again apply our Zeilberger-based acceleration method. In this case, the
evaluation of the rational certificate corresponding to (27) via Zeilberger’s
algorithm is more unwieldy compared to the $R(n,k)$-expression in Section 4.2,
as is the case with the polynomials $p_{1}(n)$ and $p_{2}(n)$ involved in (16)
for the pair $(F,G)$ corresponding to (27). So, for the sake of brevity, we
leave it to the reader to generate such expressions from (27) using Maple, so
as to verify how we may obtain a recursion of the form displayed in (21).
Accelerating $f(n)$ according to (21), and assigning special values for the
entires in the tuple $(a,b,n)$, we may obtain the following.

######  Example 4.21.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{3}{4},1\right)$, we may obtain that
the motivating example in (11) holds.

######  Example 4.22.

Setting $(a,b,n)=\left(\frac{1}{2},\frac{1}{2},1\right)$, we may obtain that

$\displaystyle\frac{327680}{\pi}=\sum_{j=0}^{\infty}$
$\displaystyle\left(\frac{27}{256}\right)^{j}\left[\begin{matrix}\frac{1}{2},\frac{1}{2},\frac{5}{6},\frac{5}{6},\frac{7}{6},\frac{7}{6},\frac{3}{2}\vspace{1mm}\\\
1,\frac{5}{3},\frac{7}{4},2,2,\frac{9}{4},\frac{7}{3}\end{matrix}\right]_{j}\cdot$
$\displaystyle\text{\footnotesize$(131904j^{6}+777216j^{5}+1886448j^{4}+2413504j^{3}+1716268j^{2}+643120j+99225)$}.$

######  Example 4.23.

Setting $(a,b,n)=\left(\frac{1}{6},\frac{5}{6},1\right)$, we may obtain that

$\displaystyle\frac{17414258688}{77\pi}=\sum_{j=0}^{\infty}$
$\displaystyle\left(\frac{27}{256}\right)^{j}\left[\begin{matrix}\frac{1}{6},\frac{13}{18},\frac{5}{6},\frac{17}{18},\frac{19}{18},\frac{23}{18},\frac{25}{18},\frac{29}{18}\vspace{1mm}\\\
1,\frac{3}{2},\frac{5}{3},\frac{7}{4},2,2,\frac{9}{4},\frac{7}{3}\end{matrix}\right]_{j}$
$(96158016j^{6}+566590464j^{5}+1373338800j^{4}+1751461056j^{3}$
$\displaystyle\text{\footnotesize$+1238515308j^{2}+459977904j+70018325)$}.$

###  4.4 Series of convergence rate $\frac{108}{3125}$

We set

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(2n)_{k}(3n)_{k}}$ (28)

to again obtain a two-term recursion of the form indicated in (21), allowing
us to apply an acceleration of the form indicated in (22). Again, the
$R(n,k)$\- and $p_{1}(n)$\- and $p_{2}(n)$-expressions are unwieldy in this
case, relative to Section 4.2, so we again leave it to the reader to verify
with Maple how these expressions may be computed so as to obtain a
hypergeometric recurrence of the form indicated in (21), for a pair $(F,G)$
corresponding to (28). Specializing values for the entries of the tuple
$(a,b,n)$ yields new results as in the following.

######  Example 4.24.

Setting $(a,b,n)=\left(\frac{1}{2},\frac{1}{2},\frac{1}{2}\right)$, we may
obtain that

$\displaystyle\frac{14175\pi}{8}=\sum_{j=0}^{\infty}$
$\displaystyle\left(\frac{108}{3125}\right)^{j}\left[\begin{matrix}\frac{1}{4},\frac{1}{4},\frac{1}{3},\frac{1}{3},\frac{2}{3},\frac{2}{3},\frac{3}{4},\frac{3}{4},1\vspace{1mm}\\\
\frac{11}{10},\frac{7}{6},\frac{13}{10},\frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{17}{10},\frac{11}{6},\frac{19}{10}\end{matrix}\right]_{j}\cdot$
$(1737792j^{8}+7561536j^{7}+14017560j^{6}+14432512j^{5}+$
$\displaystyle\text{\footnotesize$9006976j^{4}+3479240j^{3}+809366j^{2}+103131j+5472)$}.$

######  Example 4.25.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{2}{3},1\right)$, we may obtain that

$\displaystyle\frac{162\sqrt{3}}{\pi}=\sum_{j=0}^{\infty}$
$\displaystyle\left(\frac{108}{3125}\right)^{j}\left[\begin{matrix}-\frac{2}{9},-\frac{1}{6},-\frac{1}{9},\frac{1}{9},\frac{1}{6},\frac{2}{9},\frac{4}{9},\frac{5}{9}\vspace{1mm}\\\
\frac{1}{2},\frac{3}{5},\frac{4}{5},1,1,1,\frac{6}{5},\frac{7}{5}\end{matrix}\right]_{j}\cdot$
$(-19794537j^{6}-6952473j^{5}+1102491j^{4}+$
$\displaystyle\text{\footnotesize$258147j^{3}-17244j^{2}+396j+80)$}.$

######  Example 4.26.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{3}{4},1\right)$, we may obtain that

$\displaystyle\frac{768\sqrt{2}}{\pi}=\sum_{j=0}^{\infty}$
$\displaystyle\left(\frac{108}{3125}\right)^{j}\left[\begin{matrix}-\frac{3}{8},-\frac{1}{4},-\frac{1}{8},-\frac{1}{12},\frac{1}{12},\frac{1}{8},\frac{1}{4},\frac{3}{8},\frac{5}{12},\frac{7}{12}\vspace{1mm}\\\
\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{4}{5},1,1,1,\frac{6}{5},\frac{4}{3},\frac{7}{5}\end{matrix}\right]_{j}\cdot$
$(1186332672j^{8}+416677888j^{7}-203526144j^{6}-65040384j^{5}+$
$\displaystyle\text{\footnotesize$8069888j^{4}+1789952j^{3}-110576j^{2}+1584j+315)$}.$

###  4.5 An acceleration based on $\frac{(a)_{k}(b)_{k}}{(n)_{k}(a+n)_{k}}$

By setting

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(n)_{k}(a+n)_{k}},$ (29)

we may obtain a new hypergeometric transform that is of a similar character
relative to Theorem 4.1 and that we may apply to prove the motivating examples
given as (6) and (9).

######  Theorem 4.27.

Writing $f(n)=\sum_{k=0}^{\infty}F(n,k)$, with $F(n,k)$ as in (29), the
recursion

$f(n)=\frac{b-2bn+n(-2+a+3n)}{(b-2n)(1+b-2n)}+\frac{(a-n)(b-n)(a-b+n)}{(b-2n)(1+b-2n)(a+n)}f(n+1)$

holds true if the series corresponding to $f(n)$ and $f(n+1)$ converge.

###### Proof.

We again set $F(n,k)$ to be as in (29), and we proceed to apply Zeilberger’s
algorithm. This gives us a companion function $G(n,k)=R(n,k)F(n,k)$, with
$R(n,k)=-((a+n)(n(a+2k+3n-2)-b(k+2n-1)))$. We find that $(F,G)$ satisfies
(16), with $p_{1}(n)=-a^{2}b+a^{2}n+ab^{2}-abn-b^{2}n+2bn^{2}-n^{3}$ and
$p_{2}(n)=ab^{2}-4abn+ab+4an^{2}-2an+b^{2}n-4bn^{2}+bn+4n^{3}-2n^{2}$,
according to the notation in (16) for the $r=1$ case. Again, we may obtain,
from (16), a relation of the form indicated in (18), with the desired result
being equivalent to (19), again for the pair corresponding to (29), since it
is easily seen that the limit shown in (23) vanishes. ∎

######  Example 4.28.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{1}{4},1\right)$, we may obtain the
following formula given as Example 19 in [9]:

$\frac{21\pi}{8\sqrt{2}}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{3}{4},\frac{3}{4},1\vspace{1mm}\\\
\frac{5}{4},\frac{11}{8},\frac{15}{8}\end{matrix}\right]_{j}(12j^{2}+15j+4).$

######  Example 4.29.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{1}{3},1\right)$, we may obtain a new
proof of Example 78 from Chu and Zhang’s article [11]:

$\frac{20\pi}{9\sqrt{3}}=\sum_{j=0}^{\infty}\left(\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{2}{3},\frac{2}{3},1\vspace{1mm}\\\
\frac{4}{3},\frac{4}{3},\frac{11}{6}\end{matrix}\right]_{j}(9j^{2}+11j+3).$

######  Example 4.30.

Setting $(a,b,n)=\left(\frac{1}{6},\frac{1}{6},1\right)$, we may obtain the
motivating example highlighted in (6).

######  Example 4.31.

Setting $(a,b,n)=\left(\frac{1}{6},\frac{1}{3},\frac{5}{6}\right)$, we may
obtain the motivating example in (9).

###  4.6 An acceleration based on $\frac{(a)_{k}(b)_{k}}{(n)_{k}(a+2n)_{k}}$

We set

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(n)_{k}(a+2n)_{k}}$ (30)

and again apply our Zeilberger-based acceleration method.

######  Theorem 4.32.

Letting $f(n)=\sum_{k=0}^{\infty}F(n,k)$, for $F(n,k)$ as in (30), the
recursion $f(n)=g_{1}(n)+g_{2}(n)f(n+1)$ holds true, where

$g_{2}(n)=\frac{2(2n+1)(a-n)(n-b)(a-b+2n)(a-b+2n+1)}{(a+2n)(a+2n+1)(b-3n-1)(b-3n)(b-3n+1)},$

and where $g_{1}(n)$ is given by the following Mathematica output.

    Ψ(a (-1 + b) b - (2 a^2 - 2 (-1 + b) b + a (-3 + b (3 + b))) n -
    Ψ2 (-3 + a + 2 a^2 - 8 a b + b (3 + 4 b)) n^2 + (4 - 31 a +
    Ψ38 b) n^3 -
    Ψ46 n^4)/((-1 + b - 3 n) (b - 3 n) (1 + b - 3 n) (a + 2 n))
    Ψ

###### Proof.

We set $F(n,k)$ as in (30). Using Zeilberger’s algorithm, we obtain the
companion function $G(n,k)=F(n,k)R(n,k)$, for the rational function $R(n,k)$
given by the following Mathematica output.

    Ψ(1/(a + k +
    Ψ2 n))(a + 2 n) (1 + a +
    Ψ2 n) ((-1 + b) b (-1 + k) (a + k) + (2 a^2 + 3 (-1 + k) k +
    Ψb^2 (-2 + 5 k) + a (-3 + b (3 + b - 8 k) + 5 k) +
    Ψb (2 + k - 6 k^2)) n + (-6 + 4 a^2 + 8 b^2 + b (6 - 28 k) +
    Ψk (4 + 9 k) + a (2 - 16 b + 15 k)) n^2 + (-4 + 31 a - 38 b +
    Ψ39 k) n^3 + 46 n^4)
    Ψ

This gives us a difference equation of the form
$p_{1}(n)F(n+1,k)+p_{2}(n)F(n,k)=G(n,k+1)-G(n,k)$. the polynomial $p_{1}(n)$
is given by the following Mathematica output.

    Ψ(4*a^3*b*n - 4*a^3*n^2 - 8*a^2*b^2*n + 20*a^2*b*n^2 - 12*a^2*n^3 +
    Ψ4*a*b^3*n - 12*a*b^2*n^2 + 8*a*b*n^3 - 4*b^3*n^2 + 20*b^2*n^3 -
    Ψ32*b*n^4 + 16*n^5 + 2*a^3*b - 2*a^3*n - 4*a^2*b^2 + 14*a^2*b*n -
    Ψ10*a^2*n^2 + 2*a*b^3 - 10*a*b^2*n + 12*a*b*n^2 - 4*a*n^3 - 2*b^3*n +
    Ψ14*b^2*n^2 - 28*b*n^3 + 16*n^4 + 2*a^2*b - 2*a^2*n - 2*a*b^2 +
    Ψ4*a*b*n - 2*a*n^2 + 2*b^2*n - 6*b*n^2 + 4*n^3)
    Ψ

The polynomial $p_{2}(n)$ is given by the following Mathematica output.

    Ψ-4*a*b*n - a^2*b + -27*a^2*n^3 - 108*n^5 + 27*a^2*b*n^2 -
    Ψ36*a*b^2*n^2 + 108*a*b*n^3 - 4*b*n^2 - 18*b^2*n^2 + 54*b*n^3 - a*b +
    Ψ2*b^3*n + 4*a*b^3*n - 9*a^2*b^2*n + 12*a*n^2 + 3*a*n + a*b^3 -
    Ψ54*n^4 + 12*n^3 + 6*n^2 - 2*n*b + 27*a*b*n^2 - 9*a*b^2*n + 3*a^2*n +
    Ψa^2*b^3 + 4*b^3*n^2 - 36*b^2*n^3 + 108*b*n^4 - 108*a*n^4 - 27*a*n^3
    Ψ

Summing both sides of the given difference equation with respect to $k$, we
may mimic our previous proofs to obtain the desired result, with (23) again
vanishing. ∎

######  Example 4.33.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{1}{4},1\right)$, we may obtain that

$\displaystyle\frac{155925\pi}{128\sqrt{2}}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}$
$\displaystyle\left[\begin{matrix}\frac{3}{4},\frac{3}{4},1,\frac{3}{2},\frac{3}{2}\vspace{1mm}\\\
\frac{19}{12},\frac{13}{8},\frac{23}{12},\frac{17}{8},\frac{9}{4}\end{matrix}\right]_{j}\cdot$
$\displaystyle(2944j^{4}+11408j^{3}+16288j^{2}+10125j+2304).$

######  Example 4.34.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{1}{3},1\right)$, we may obtain that

$\frac{24640\pi}{81\sqrt{3}}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{2}{3},1,\frac{3}{2},\frac{3}{2}\vspace{1mm}\\\
\frac{14}{9},\frac{17}{9},\frac{13}{6},\frac{20}{9}\end{matrix}\right]_{j}(414j^{3}+1323j^{2}+1397j+486).$

######  Example 4.35.

Setting $(a,b,n)=\left(\frac{1}{6},\frac{1}{6},1\right)$, we may obtain that

$\displaystyle\frac{1956955\pi}{648}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}$
$\displaystyle\left[\begin{matrix}\frac{5}{6},\frac{5}{6},1,\frac{3}{2},\frac{3}{2}\vspace{1mm}\\\
\frac{19}{12},\frac{29}{18},\frac{35}{18},\frac{25}{12},\frac{41}{18}\end{matrix}\right]_{j}\cdot$
$\displaystyle(9936j^{4}+38628j^{3}+55236j^{2}+34315j+7776).$

###  4.7 An acceleration based on $\frac{(a)_{k}(b)_{k}}{(2n)_{k}(a+n)_{k}}$

We set

$F(n,k)=\frac{(a)_{k}(b)_{k}}{(2n)_{k}(a+n)_{k}}$ (31)

and again apply our Zeilberger-based acceleration method. This may be used to
obtain a hypergeometric transform much like Theorem 4.32. For the sake of
brevity, we leave it to the reader to fill in the details in regard to our
transform obtained, via Zeilberger’s algorithm, from (31).

######  Example 4.36.

Setting $(a,b,n)=\left(\frac{1}{4},\frac{1}{4},\frac{1}{2}\right)$, we may
obtain the motivating example highlighted in (12).

######  Example 4.37.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{1}{3},\frac{2}{3}\right)$, we may
obtain that

$\frac{320\pi}{9\sqrt{3}}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{1}{2},\frac{1}{2},\frac{2}{3},1\vspace{1mm}\\\
\frac{7}{6},\frac{11}{9},\frac{14}{9},\frac{17}{9}\end{matrix}\right]_{j}(414j^{3}+702j^{2}+359j+54).$

######  Example 4.38.

Setting $(a,b,n)=\left(\frac{1}{3},\frac{1}{6},\frac{1}{2}\right)$, we may
obtain that

$28\sqrt[3]{2}=\sum_{j=0}^{\infty}\left(\frac{4}{27}\right)^{j}\left[\begin{matrix}\frac{1}{3},\frac{5}{12},\frac{2}{3},\frac{11}{12}\vspace{1mm}\\\
1,\frac{10}{9},\frac{13}{9},\frac{16}{9}\end{matrix}\right]_{j}(621j^{3}+828j^{2}+303j+26).$

###  4.8 Series of convergence rate $-\frac{1}{4}$

Setting

$F(n,k)=\frac{(-1)^{k}(a)_{k}(b)_{k}}{(a+n+1)_{k}(b+n+1)_{k}},$ (32)

this leads us, via our acceleration method, to the following hypergeometric
transform that we are to apply to obtain series of convergence rate
$-\frac{1}{4}$.

######  Theorem 4.39.

Writing $f(n)=\sum_{k=0}^{\infty}F(n,k)$ for $F(n,k)$ as in (32), the
recursion

$\displaystyle f(n)=\frac{a(3+2b+3n)+(1+n)(6+3b+5n)}{4(1+a+n)(1+b+n)}+$
$\displaystyle\hskip
38.41139pt\frac{(-2+a-b-n)(1+n)(2+n)(2+a-b+n)}{4(1+a+n)(2+a+n)(1+b+n)(2+b+n)}f(n+2)$

holds true if the series corresponding to the above $f$-expressions converge.

###### Proof.

We again set $F(n,k)$ to be as in (32). Let us write $G(n,k)=F(n,k)R(n,k)$,
where $R(n,k)$ is equal to the following rational function:

$\displaystyle\frac{(a+n+1)(a+n+2)(b+n+1)(b+n+2)}{(a+k+n+1)(b+k+n+1)}\cdot$
$\displaystyle\left(a(2b+2k+3n+3)+b(2k+3n+3)+6kn+2k(k+3)+5n^{2}+11n+6\right).$

In this case, we find that the $r=2$ case of (16) holds, with
$p_{1}(n)=(1+n)(2+n)((a-b)^{2}-(2+n)^{2})$ and
$p_{2}(n)=-4(1+a+n)(2+a+n)(1+b+n)(2+b+n)$. From the difference equation
$p_{1}(n)F(n+2,k)+p_{2}(n)F(n,k)=G(n,k+1)-G(n,k)$, we may obtain an equivalent
formulation of the desired result by summing both sides with respect to $k$
and by making use of a telescoping effect, again with (23) vanishing. ∎

######  Example 4.40.

Setting $a=\frac{1}{2}$ and $b=\frac{1}{2}$ and $n=0$, we obtain Lupaş’ series
evaluation for $G$ [24] given in an equivalent formulation below:

$18G=\sum_{j=0}^{\infty}\left(-\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{1}{2},1,1,1\vspace{1mm}\\\
\frac{5}{4},\frac{5}{4},\frac{7}{4},\frac{7}{4}\end{matrix}\right]_{j}\left(40j^{2}+56j+19\right).$

As indicated in the Wolfram Mathworld entry on Catalan’s constant, the above
formula by Lupaş [24] is used to calculate $G$ in the Wolfram Language. This
motivates our generalization of Lupaş’ formula given by Theorem 4.39, and our
applications of this Theorem, as below.

######  Example 4.41.

Setting $a=-\frac{1}{4}$ and $b=\frac{1}{2}$ and $n=\frac{1}{4}$, we obtain

$21\sqrt{2}=\sum_{j=0}^{\infty}\left(-\frac{1}{4}\right)^{j}\left[\begin{matrix}\frac{5}{8},\frac{3}{4},\frac{9}{8}\vspace{1mm}\\\
1,\frac{11}{8},\frac{15}{8}\end{matrix}\right]_{j}\left(80j^{2}+114j+39\right).$

######  Example 4.42.

Setting $a=\frac{1}{3}$ and $b=\frac{1}{2}$ and $n=-\frac{1}{2}$, we obtain
the motivating example in (8).

######  Example 4.43.

Setting $a=-\frac{5}{6}$ and $b=\frac{2}{3}$ and $n=\frac{5}{6}$, we obtain
the motivating example highlighted in (5).

###  4.9 Series of convergence rate $-\frac{1}{27}$

Setting

$F(n,k)=\frac{(a)_{k}^{3}}{(n)_{k}^{3}}$ (33)

and $f(n)=\sum_{k=0}^{\infty}F(n,k)$, we may apply the procedure indicated in
Section 3 to obtain a recurrence of the form

$f(n)=g_{1}(n)+g_{2}(n)f(n+2),$ (34)

i.e., with $r=2$ according to the notation in (19). This leads us to an
acceleration identity of the form

$f(n)=\sum_{j=0}^{\infty}\left(\prod_{i=0}^{j-1}g_{2}(n+2i)\right)g_{1}(n+2j).$

The $R(n,k)$-certificate obtained from (33) via Zeilberger’s algorithm is more
unwieldy compared to Section 4.8, and similarly for the required polynomial
coefficients, so we leave it to the reader to verify, using Maple, the
acceleration formula in (34).

######  Example 4.44.

Setting $a=1$ and $n=2$, we may obtain an equivalent version of a series
evaluation found by Amdeberhan [1] in 1996:

$24\zeta(3)=\sum_{j=0}^{\infty}\left(-\frac{1}{27}\right)^{j}\left[\begin{matrix}1,1,1\vspace{1mm}\\\
\frac{4}{3},\frac{5}{3},2\end{matrix}\right]_{j}\frac{56j^{2}+80j+29}{(2j+1)^{2}}.$

######  Example 4.45.

Setting $a=\frac{1}{2}$ and $n=\frac{3}{2}$, we may obtain the motivating
example given in (13).

##  5 Conclusion

We conclude by briefly considering some further subjects for exploration.

Although our article is mainly based on the acceleration method described in
Section 3, we have discovered how recurrences as in (34) may be applied in
conjunction with recursions that are not of the form described in Section 3 to
obtain new results and new proofs of past results. For example, the recurrence

$\displaystyle{}_{4}F_{3}\\!\\!\left[\begin{matrix}x,x,x,1\vspace{1mm}\\\
x+y,x+y,x+y\end{matrix}\ \Bigg{|}\
1\right]=\frac{p(x,y)}{3(3y-1)(3y+1)(x+y)^{3}}-$
$\displaystyle\frac{y^{3}(y+1)^{5}}{3(3y-1)(3y+1)(x+y)^{3}(x+y+1)^{3}}\,{}_{4}F_{3}\\!\\!\left[\begin{matrix}x,x,x,1\vspace{1mm}\\\
x+y+2,x+y+2,x+y+2\end{matrix}\ \Bigg{|}\ 1\right]$

for the polynomial
$p(x,y)=28y^{5}+2(39x+1)y^{4}+(87x^{2}-3x-2)y^{3}+9x(5x^{2}-1)y^{2}+3x^{2}(3x^{2}+2x-3)y+3x^{3}(x-1)$
can be shown to be equivalent to (34), and if we apply this recurrence
together with

$\displaystyle{}_{4}F_{3}\\!\\!\left[\begin{matrix}x,x,x,1\vspace{1mm}\\\
x+y,x+y,x+y\end{matrix}\ \Bigg{|}\
1\right]=1+\frac{x^{3}}{(x+y)^{3}}\,{}_{4}F_{3}\\!\\!\left[\begin{matrix}x+1,x+1,x+1,1\vspace{1mm}\\\
x+1+y,x+1+y,x+1+y\end{matrix}\ \Bigg{|}\ 1\right]$

i.e., by applying the above recurrences in a successive fashion, this can be
used to prove that

$\zeta(3)=\frac{1}{16}\sum_{n=1}^{\infty}(-1)^{n-1}\text{\footnotesize$\frac{40885n^{5}-80079n^{4}+61626n^{3}-23366n^{2}+4374n-324}{n^{5}(2n-1)^{3}}$}\frac{1}{\binom{3n}{2n}^{4}\binom{2n}{n}}.$

This series was found in 2005 by Mohammed [27].
Writing $s(x,y)$ in place of the ${}_{4}F_{3}$-expressions on the left-hand
sides of the above recurrences, by writing $s(x,y)$ as a function of
$s(x+2,y+2)$, this leads to the equality of $-8\zeta(3)$ and

$\sum_{n=1}^{\infty}(-1)^{n}\text{\footnotesize$\frac{126392n^{5}-219252n^{4}+144666n^{3}-46039n^{2}+7128n-432}{n^{5}(2n-1)^{3}}$}\frac{1}{\binom{4n}{2n}^{3}\binom{3n}{n}\binom{2n}{n}}.$

This series was used by Sebastian Wedeniwski [27] to calculate Apéry’s
constant with several million correct decimal places. We leave it to a
separate project to fully explore the application of our method in Section 3
in conjunction with recurrences that are not of the form indicated in Section
3.

Our applications of (16) and generalizations of this difference equation lead
us to consider variants of the recurrences we have derived. Is there a way to
use the WZ method to find such non-homogeneous first order linear recurrence
relations? An area of a similar nature to explore has to do with the use of
symmetry in the application of hypergeometric recursions for series
accelerations. For example, we have experimentally discovered that

$\displaystyle{}_{3}F_{2}\\!\\!\left[\begin{matrix}x,y,1\vspace{1mm}\\\
x+y+\frac{1}{2},x+y+\frac{1}{2}\end{matrix}\ \Bigg{|}\
1\right]=\frac{x+2y}{x+y}\ -$
$\displaystyle\frac{y(2y+1)^{2}}{(2x+2y+1)^{2}(x+y)}{}_{3}F_{2}\\!\\!\left[\begin{matrix}x,y+1,1\vspace{1mm}\\\
x+y+\frac{3}{2},x+y+\frac{3}{2}\end{matrix}\ \Bigg{|}\ 1\right],$

and we may obtain similar results via our acceleration method, and we are led
to consider the above recurrence together with the corresponding recurrence
obtained, via symmetry, by permuting $x$ and $y$. Using both recurrences, one
after the other, leads us to new results as in the following:

$\displaystyle\frac{\sqrt{2}}{2}=\sum_{n=0}^{\infty}\frac{3+184n-336n^{2}}{(4n-1)(4n-3)}\frac{\binom{4n}{2n}}{2^{10n}},$
$\displaystyle\frac{\pi^{2}}{2}=\sum_{n=1}^{\infty}\frac{(14n-3)(3n-1)}{n^{3}(2n-1)}\frac{16^{n}}{\binom{4n}{2n}^{2}\binom{2n}{n}}.$

## References

  * [1] T. Amdeberhan, _Faster and faster convergent series for $\zeta(3)$_, Electron. J. Comb. 3:1 (1996), #R13.
  * [2] M. Apagodu and D. Zeilberger, _Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory_ , Adv. Appl. Math. 37:2 (2006), 139–152.
  * [3] W. N. Bailey, _Generalized Hypergeometric Series_ , Cambridge University Press, Cambridge, 1935.
  * [4] N. D. Baruah, B. C. Berndt and H. H. Chan, _Ramanujan’s series for $1/\pi$: a survey_, Amer. Math. Monthly 116:7 (2009), 567–587
  * [5] J. M. Campbell, _Nested radicals obtained via the Wilf–Zeilberger method and related results_ , Maple Trans. 3:3 (2023), Article 16011
  * [6] J. M. Campbell and P. Levrie, _Further WZ-based methods for proving and generalizing Ramanujan’s series_ , J. Difference Equ. Appl. 29:3 (2023), pp. 366–376.
  * [7] W. Y. C. Chen, Q.-H. Hou and Y.-P. Mu, _The extended Zeilberger algorithm with parameters_ , J. Symb. Comput. 47:6 (2012), 643–654.
  * [8] W. Chu, _Dougall’s bilateral ${}_{2}H_{2}$-series and Ramanujan-like $\pi$-formulae_, Math. Comput. 80:276 (2011), 2223–2251.
  * [9] W. Chu, _Infinite series identities derived from the very well-poised $\Omega$-sum_, Ramanujan J. 55:1 (2021), 239–270.
  * [10] W. Chu, _Ramanujan-like formulae for $\pi$ and $1/\pi$ via Gould-Hsu inverse series relations_, Ramanujan J. 56:3 (2021), 1007–1027.
  * [11] W. Chu and W. Zhang, _Accelerating Dougall’s ${}_{5}F_{4}$-sum and infinite series involving $\pi$_, Math. Comput. 83:285 (2014), 475–512.
  * [12] D. V. Chudnovsky and G. V. Chudnovsky, _Approximations and complex multiplication according to Ramanujan_ , in “Ramanujan Revisited”, Proceedings of the Centenary Conference (Urbana–Champaign, 1987), eds. G. E. Andrews, B. C. Berndt, and R. A. Rankin; Academic Press: Boston (1988), 375–472.
  * [13] S. B. Ekhad and D. Zeilberger, _A WZ proof of Ramanujan’s formula for $\pi$_, in “Geometry, analysis and mechanics. Dedicated to Archimedes on his 2281st birthday”, World Scientific: Singapore (1994), 107–108.
  * [14] K. Girstmair, _Reducing radicals in the spirit of Euclid_ , J. Symb. Comput. 104 (2021), 356–365.
  * [15] J. Guillera, _Generators of some Ramanujan formulas_ , Ramanujan J. 11:1 (2006), 41–48.
  * [16] J. Guillera, _Hypergeometric identities for 10 extended Ramanujan-type series_ , Ramanujan J. 15:2 (2008), 219–234.
  * [17] K. Hessami Pilehrood and T. Hessami Pilehrood, _Simultaneous generation for zeta values by the Markov-WZ method_ , Discrete Math. Theor. Comput. Sci. 10:3 (2008), 115–123.
  * [18] G. S. Joyce and I. J. Zucker, Special values of the hypergeometric series. III, Math. Proc. Camb. Philos. Soc. 133:2 (2002), 213–222.
  * [19] M. Kondratieva and S. Sadov, _Markov’s transformation of series and the WZ method_ , Adv. Appl. Math. 34:2 (2005), 393–407.
  * [20] T. H. Koornwinder, _On Zeilberger’s algorithm and its $q$-analogue_, J. Comput. Appl. Math. 48:1-2 (1993), 91–111.
  * [21] I. Lamiri and J. Weslati, _Limit relations involving 2-orthogonal polynomials_ , Integral Transforms Spec. Funct. 32:5-8 (2021), 545–559.
  * [22] P. Levrie and J. Campbell, _Series acceleration formulas obtained from experimentally discovered hypergeometric recursions_ , Discrete Math. Theor. Comput. Sci. 19:1 (2023), dmtcs.9557.
  * [23] P. Levrie and A. S. Nimbran, _From Wallis and Forsyth to Ramanujan_ , Ramanujan J. 47:3 (2018), 533–545.
  * [24] A. Lupaş, _Formulae for some classical constants_ , in “RoGer 2000–Braşov. Proceedings of the 4th Romanian–German seminar on approximation theory and its applications, Braşov, Romania, July 3–5, 2000”, Duisburg: Gerhard-Mercator-Universität Duisburg, Fachbereich Mathematik (2000), 70–76.
  * [25] T. Mansour and M. Shattuck, _A combinatorial approach to a general two-term recurrence_ , Discrete Appl. Math. 161:13-14 (2013), 2084–2094.
  * [26] A. B. Mingarelli, _On a discrete version of a theorem of Clausen and its applications_ , Acta Math. Acad. Paedagog. Nyházi. (N.S.) 29 (2013), 19–42.
  * [27] M. Mohammed, _Infinite families of accelerated series for some classical constants by the Markov-WZ Method_ , Discrete Math. Theor. Comput. Sci. 7:1 (2005), 11–24.
  * [28] P. Paule and M. Schorn, _A_ Mathematica _version of Zeilberger’s algorithm for proving binomial coefficient identities_ , J. Symb. Comput. 20:5-6 (1995), 673–698.
  * [29] M. Petkovšek, H. S. Wilf and D. Zeilberger, $A=B$, A K Peters, Ltd., Wellesley, MA, 1996.
  * [30] E. D. Rainville, _Special Functions_ , The Macmillan Co., Bronx, New York, 1960.
  * [31] S. Ramanujan, _Modular equations and approximations of $\pi$_, Quart. J. Pure Appl. Math. 45 (1914), 350–372.
  * [32] P. Sziklai and Z. Weiner, _Covering all but the low weight vertices of the unit cube_ , J. Comb. Theory, Ser. A 193:6 (2023), Id/No 105671.
  * [33] H. S. Wilf, _Accelerated series for universal constants, by the WZ method_ , Discrete Math. Theor. Comput. Sci. 3:4 (1999), 189–192.
  * [34] I. J. Zucker and G. S. Joyce, _Special values of the hypergeometric series. II_ , Math. Proc. Camb. Philos. Soc. 131:2 (2001), 309–319.


# Beyond the Return: Off-policy Function Estimation under User-specified
Error-measuring Distributions

Audrey Huang
Computer Science
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>&Nan Jiang
Computer Science
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>
###### Abstract

Off-policy evaluation often refers to two related tasks: estimating the
expected return of a policy and estimating its value function (or other
functions of interest, such as density ratios). While recent works on
marginalized importance sampling (MIS) show that the former can enjoy provable
guarantees under realizable function approximation, the latter is only known
to be feasible under much stronger assumptions such as prohibitively
expressive discriminators. In this work, we provide guarantees for off-policy
function estimation under only realizability, by imposing proper
regularization on the MIS objectives. Compared to commonly used regularization
in MIS, our regularizer is much more flexible and can account for an arbitrary
user-specified distribution, under which the learned function will be close to
the groundtruth. We provide exact characterization of the optimal dual
solution that needs to be realized by the discriminator class, which
determines the data-coverage assumption in the case of value-function
learning. As another surprising observation, the regularizer can be altered to
relax the data-coverage requirement, and completely eliminate it in the ideal
case with strong side information.

##  1 Introduction

Off-policy evaluation (OPE) often refers to two related tasks in reinforcement
learning (RL): estimating the expected return of a target policy using a
dataset collected from a different behavior policy, versus estimating the
policy’s value function (or other functions of interest, such as density
ratios). The former is crucial to hyperparameter tuning and verifying the
performance of a policy before real-world deployment in offline RL
[voloshin2019empirical, paine2020hyperparameter, zhang2021towards]. The
latter, on the other hand, plays an important role in (both online and
offline) training, often as the subroutine of actor-critic-style algorithms
[lagoudakis2003least, liu2019off], but is also generally more difficult than
the former: if an accurate value function is available, one could easily
estimate the return by plugging in the initial distribution.

Between the two tasks, the theoretical nature of off-policy return estimation
is relatively well understood, especially in terms of the function-
approximation assumptions needed for sample-complexity guarantees. Among the
available algorithms, importance sampling (IS) and its variants
[precup2000eligibility, thomas2015high, jiang2016doubly] do not require any
function approximation, but incur exponential-in-horizon variance; Fitted-Q
Evaluation [ernst2005tree, le2019batch] can enjoy polynomial sample complexity
under appropriate coverage assumptions, but the guarantee relies on the strong
Bellman-completeness assumption on the function class; marginalized importance
sampling (MIS) methods, which have gained significant attention recently
[liu2018breaking, xie2019towards, uehara2019minimax, nachum2019dualdice], use
two function classes to simultaneously approximate the value and the density-
ratio (or weight) function and optimize minimax objectives. Notably, it is the
only family of methods known to produce accurate return estimates with a
polynomial sample complexity, when the function classes only satisfy the
relatively weak realizability assumptions (i.e., they contain the true value
and weight functions).

In comparison, little is known about off-policy function estimation, and the
guarantees are generally less desirable. Not only do the limitations of IS and
FQE on return estimation carry over to this more challenging task, but MIS
also loses its major advantage over FQE: despite the somewhat misleading
impression left by many prior works, that MIS can handle function estimation
the same way as return estimation,111For example, [liu2019off] assumed a
weight estimation oracle and cited [liu2018breaking] as a possible instance.
MIS for function estimation often requires unrealistic assumptions such as
prohibitively expressive discriminators. For concreteness, a typical guarantee
for function estimation from MIS looks like the following (see e.g., Theorem 4
of [liu2018breaking] and Lemmas 1 and 3 of [uehara2019minimax]):

######  Proposition 1 (Function estimation guarantee for MIS, informal).

Suppose the offline data distribution $d^{D}$ satisfies $d^{D}(s,a)>0,\forall
s,a$. Given value-function class $\mathcal{Q}$ with $q^{\pi}\in\mathcal{Q}$
and weight class $\mathcal{W}=\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$,
$q^{\pi}=\operatorname*{arg\,min}_{q\in\mathcal{Q}}\max_{w\in\mathcal{W}}L(w,q)$
for some appropriate population loss function $L$.222Concretely, one can
choose $L$ as Eq.(4) without the regularization term, which recovers MQL in
[uehara2019minimax].

To enable the identification of the value function $q^{\pi}$, the result
requires the discriminator class $\mathcal{W}$ to be the space of all possible
functions over the state-action space
($\mathcal{W}=\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$). In the finite-
sample regime, using such a class incurs a sample complexity that depends on
the size of the state-action space, which completely defeats the purpose of
function approximation.

In addition, these results only hold asymptotically, where the function of
interest can be exactly identified in a point-wise manner. Such an overly
strong guarantee is unrealistic in the finite-sample regime, where one can
only hope to approximate the function well in an average sense under some
distribution, i.e., finite-sample performance guarantees should ideally bound
$\|\widehat{q}-q^{\pi}\|_{2,\nu}$ for the learned $\widehat{q}$, where
$\|\cdot\|_{2,\nu}$ is $\nu$-weighted 2-norm. Such fine-grained analyses are
non-existent in MIS. Even in the broader literature, such results not only
require Bellman-completeness-type assumptions [uehara2021finite], they also
come with some fixed $\nu$ (which is not necessarily $d^{D}$; see Section 2)
and the user has no freedom in choosing $\nu$. This creates a gap in the
literature, as downstream learning algorithms that use off-policy function
estimation as a subroutine often assume the estimation to be accurate under
specific distributions [kakade2002approximately, abbasi2019politex] (see
details in Appendix LABEL:app:discuss).

To summarize, below are two important open problems on off-policy function
estimation:

  1. 1.

Is it possible to obtain polynomial333By “polynomial”, we mean polynomial in
the horizon, the statistical capacities and the boundedness of the function
classes, and the parameter that measures the degree of data coverage. sample
complexity for off-policy function estimation, using function classes that
only satisfy realizability-type assumptions?

  2. 2.

Can we specify a distribution $\nu$ to the estimation algorithm, such that the
learned function will be close to the groundtruth under $\nu$?

In this work, we answer both open questions in the positive. By imposing
proper regularization on the MIS objectives, we provide off-policy function
estimation guarantees under only realizability assumptions on the function
classes. Compared to commonly used regularization in MIS [nachum2019dualdice,
nachum2020reinforcement, yang2020off], our regularizer is much more flexible
and can account for an arbitrary user-specified distribution $\nu$, under
which the learned function will be close to the groundtruth. We provide exact
characterization of the optimal dual solution that needs to be realized by the
discriminator, which determines the data-coverage assumption in value-function
learning. As another surprising observation, the regularizer can be altered to
relax the data-coverage requirement, and in the ideal case completely
eliminate it when strong side information is available. Proof-of-concept
experiments are also conducted to validate our theoretical predictions.

##  2 Related Works

Regularization in MIS The use of regularization is very common in the MIS
literature, especially in DICE algorithms [nachum2019dualdice,
nachum2019algaedice, yang2020off]. However, most prior works that consider
regularization use tabular derivations and seldom provide finite-sample
function-approximation guarantees on even return estimation, let alone
function estimation. (An exception is the work of [uehara2021finite], who
analyze related estimators under Bellman-completeness-type assumptions; see
the next paragraph.) More importantly, prior works provide very limited
understanding in how choice of regularization affects learning guarantees, and
have considered only naïve forms of regularization (state-action-independent
and typically under $d^{D}$), under which different forms of regularization
are essentially treated equally under a coarse-grained theory [yang2020off].
In contrast, we provide much more fine-grained characterization of the effects
of regularization, which leads to novel insights about how to design better
regularizers, and existing DICE estimators are subsumed as special cases of
our method when we choose very simple regularizers (see Remark
LABEL:rem:dualdice in Section 5).

Fitted-Q Evaluation (FQE) Outside the MIS literature, one can obtain return
and value-function estimation guarantees via FQE [duan2020minimax,
chen2019information, le2019batch, uehara2021finite]. However, it is well
understood that FQE and related approaches require Bellman-completeness-type
assumptions, such as the function class being closed under the Bellman
operator. Even putting aside the difference between completeness vs.
realizability, we allow for a user-specified error-measuring distribution,
which is not available in FQE or any other existing method. The only
distribution these methods are aware of is the data distribution $d^{D}$, and
even so, FQE and variants rarely provide guarantees on
$\|\widehat{q}-q^{\pi}\|_{2,d^{D}}$, but often on the Bellman error (e.g.,
$\|\widehat{q}-\mathcal{T}^{\pi}\widehat{q}\|_{2,d^{D}}$) instead
[uehara2021finite], and obtaining guarantees on a distribution of interest
often requires multiple indirect translations and loose relaxations.

LSTDQ Our analyses focus on general function approximation. When restricted to
linear classes, function estimation guarantees for $q^{\pi}$ under $d^{D}$ can
be obtained by LSTDQ methods [lagoudakis2003least, bertsekas2009projected,
dann2014policy] when the function class only satisfies realizability of
$q^{\pi}$ [perdomo2022sharp]. However, this requires an additional matrix
invertibility condition (see Assumption 3 of [perdomo2022sharp]), and it is
still unclear what this condition corresponds to in general function
approximation.444It is hinted by [uehara2019minimax] that the invertibility is
related to a loss minimization condition in MIS, but the connection only holds
for return estimation. Moreover, many general methods—including MIS
[uehara2019minimax] and other minimax methods [antos2008learning,
xie2021bellman]—coincide with LSTDQ in the linear case, so the aforementioned
results can be viewed as a specialized analysis leveraging the properties of
linear classes.

PRO-RL [zhan2022offline] Our key proof techniques are adapted from
[zhan2022offline], whose goal is offline policy learning. They learn the
importance weight function $w^{\pi}$ for a near-optimal $\pi$, and provide
$\|\widehat{w}-w^{\pi}\|_{2,d^{D}}$ guarantees as an intermediate result.
Despite using similar technical tools, our most interesting and surprising
results are in the value-function estimation setting, which is not considered
by [zhan2022offline]. Our novel algorithmic insights, such as incorporating
error-measuring distributions and approximate models in the regularizers, are
also potentially useful in [zhan2022offline]’s policy learning setting. Our
analyses also reveal a number of important differences between OPE and offline
policy learning, which will be discussed in Appendix LABEL:app:discuss.

##  3 Preliminaries

We consider off-policy evaluation (OPE) in Markov Decision Processes (MDPs).
An MDP is specified by its state space $\mathcal{S}$, action space
$\mathcal{A}$, transition dynamics
$P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ ($\Delta(\cdot)$ is the
probability simplex), reward function
$R:\mathcal{S}\times\mathcal{A}\to\Delta([0,1])$, discount factor
$\gamma\in[0,1)$, and an initial state distribution
$\mu_{0}\in\Delta(\mathcal{S})$. We assume $\mathcal{S}$ and $\mathcal{A}$ are
finite and discrete, but their cardinalities can be arbitrarily large. Given a
target policy $\pi:\mathcal{S}\to\Delta(\mathcal{A})$, a random trajectory
$s_{0},a_{0},r_{0},s_{1},a_{1},r_{1},\ldots$ can be generated as
$s_{0}\sim\mu_{0},a_{t}\sim\pi(\cdot|s_{t}),r_{t}\sim
R(\cdot|s_{t},a_{t}),s_{t+1}\sim P(\cdot|s_{t},a_{t})$, $\forall t\geq 0$; we
use $\mathbb{E}_{\pi}$ and $\mathbb{P}_{\pi}$ to refer to expectation and
probability under such a distribution. The expected discounted return (or
simply return) of $\pi$ is
$J(\pi):=\mathbb{E}_{\pi}[\sum_{t}\gamma^{t}r_{t}]$. The Q-value function of
$\pi$ is the unique solution of the Bellman equations
$q^{\pi}=\mathcal{T}^{\pi}q^{\pi}$, with the Bellman operator
$\mathcal{T}^{\pi}:\mathbb{R}^{\mathcal{S}\times\mathcal{A}}\to\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$
defined as $\forall
q\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}},(\mathcal{T}^{\pi}q)(s,a):=\mathbb{E}_{r\sim
R(\cdot|s,a)}[r]+\gamma(P^{\pi}q)(s,a)$. Here
$P^{\pi}\in\mathbb{R}^{|\mathcal{S}\times\mathcal{A}|\times|\mathcal{S}\times\mathcal{A}|}$
is the state-action transition operator of $\pi$, defined as
$(P^{\pi}q)(s,a):=\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a),a^{\prime}\sim\pi(\cdot|s^{\prime})}[q(s^{\prime},a^{\prime})]$.
Functions over $\mathcal{S}\times\mathcal{A}$ (such as $q$) are also treated
as $|\mathcal{S}\times\mathcal{A}|$-dimensional vectors interchangeably.

In OPE, we want to estimate $q^{\pi}$ and other functions of interest based on
a historical dataset collected by a possibly different policy. As a standard
simplification, we assume that the offline dataset consisting of $n$ i.i.d.
tuples $\\{(s_{i},a_{i},r_{i},s_{i}^{\prime})\\}_{i=1}^{n}$ sampled as
$(s_{i},a_{i})\sim d^{D}$, $r\sim R(\cdot|s_{i},a_{i})$, and
$s_{i}^{\prime}\sim P(\cdot|s_{i},a_{i})$. We call $d^{D}$ the (offline) data
distribution. As another function of interest, the (marginalized importance)
weight function $w^{\pi}$ is defined as
$w^{\pi}(s,a):=d^{\pi}(s,a)/d^{D}(s,a)$, where
$d^{\pi}(s,a)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}_{\pi}[s_{t}=s,a_{t}=a]$
is the discounted state-action occupancy of $\pi$. For technical convenience
we assume $d^{D}(s,a)>0~{}\forall s,a$, so that quantities like $w^{\pi}$ are
always well defined and finite.555It will be trivial to remove this assumption
at the cost of cumbersome derivations. Also, these density ratios can still
take prohibitively large values even if they are finite, and we will need to
make additional boundedness assumptions to enable finite-sample guarantees
anyway, so their finiteness does not trivialize the analyses. Similarly to
$q^{\pi}$, $w^{\pi}$ also satisfies a recursive equation, inherited from the
Bellman flow equation for $d^{\pi}$:
$d^{\pi}=(1-\gamma)\mu_{0}^{\pi}+\gamma\widetilde{P}^{\pi}d^{\pi}$, where
$(s,a)\sim\mu_{0}^{\pi}\Leftrightarrow s\sim\mu_{0},a\sim\pi(\cdot|s)$ is the
initial state-action distribution, and $\widetilde{P}^{\pi}:=(P^{\pi})^{\top}$
is the transpose of the transition matrix.

Function Approximation We will use function classes $\mathcal{Q}$ and
$\mathcal{W}$ to approximate $q^{\pi}$ and $w^{\pi}$, respectively. We assume
finite $\mathcal{Q}$ and $\mathcal{W}$, and extension to infinite classes
under appropriate complexity measures (e.g., covering number) is provided in
Appendix LABEL:appendix:infinite.

Additional Notation $\|\cdot\|_{2,\nu}:=\sqrt{\mathbb{E}_{\nu}[(\cdot)^{2}]}$
is the weighted 2-norm of a function under distribution $\nu$. We also use a
standard shorthand $f(s,\pi):=\mathbb{E}_{a\sim\pi(\cdot|s)}[q(s,a)]$.
Elementwise multiplication between two vectors $u$ and $v$ of the same
dimension is $u\circ v$, and elementwise division is $u/v$.

##  4 Value-function Estimation

In this section we show how to estimate $\widehat{q}\approx q^{\pi}$ with
guarantees on $\|\widehat{q}-q^{\pi}\|_{2,\nu}$ for a user-specified $\nu$,
and identify the assumptions under which provable sample-complexity guarantees
can be obtained. We begin with the familiar Bellman equations, that $q^{\pi}$
is the unique solution to:

$\displaystyle\mathbb{E}_{r\sim
R(\cdot|s,a)}[r]+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}[q(s^{\prime},\pi)]-q(s,a)=0,~{}\forall
s,a\in\mathcal{S}\times\mathcal{A}.$ (1)

While the above set of equations uniquely determines $q=q^{\pi}$, this is only
true if we can enforce all the $|\mathcal{S}\times\mathcal{A}|$ constraints,
which is intractable in large state-space problems. In fact, even estimating
(a candidate $q$’s violation of) a single constraint is infeasible as that
requires sampling from the same state multiple times, which is related to the
infamous double-sampling problem [baird1995residual].

To overcome this challenge, prior MIS works often relax Eq.(1) by taking a
weighted combination of these equations, e.g.,

$\displaystyle\mathbb{E}_{d^{D}}\left[w(s,a)\left(r(s,a)+\gamma
q(s^{\prime},\pi)-q(s,a)\right)\right]=0,~{}\forall w\in\mathcal{W}.$ (2)

Instead of enforcing $|\mathcal{S}\times\mathcal{A}|$ equations, we only
enforce their linear combinations; the linear coefficients are
$d^{D}(s,a)\cdot w(s,a)$, and $w$ belongs to a class $\mathcal{W}$ with
limited statistical capacity to enable sample-efficient estimation. While each
constraint in Eq.(2) can now be efficiently checked on data, this comes with a
big cost that a solution to Eq.(2) is not necessarily $q^{\pi}$. Prior works
handle this dilemma by aiming lower: instead of learning $\widehat{q}\approx
q^{\pi}$, they only learn $\widehat{q}$ that can approximate the policy’s
return, i.e. $\mathbb{E}_{s\sim\mu_{0}}[\widehat{q}(s,\pi)]\approx
J(\pi)=\mathbb{E}_{s\sim\mu_{0}}[q^{\pi}(s,\pi)]$. While [uehara2019minimax]
show that the latter is possible when $w^{\pi}\in\mathcal{W}$, they also show
explicit counterexamples where $\widehat{q}\neq q^{\pi}$ even with infinite
data. As a result, how to estimate $\widehat{q}\approx q^{\pi}$ under
comparable realizability assumptions (instead of the prohibitive
$\mathcal{W}=\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ as in Proposition 1)
is still an open problem.

###  4.1 Estimator

We now describe our approach to solving this problem. Recall that the goal is
to obtain error bounds for $\|\widehat{q}-q^{\pi}\|_{2,\nu}$ for some
distribution $\nu\in\Delta(\mathcal{S}\times\mathcal{A})$ specified by the
user. Note that we do not require information about $r$ and $s^{\prime}$ that
are generated after $(s,a)\sim\nu$ and only care about the $(s,a)$ marginal
itself, so the user can pick $\nu$ in an arbitrary manner without knowing the
transition and the reward functions of the MDP. We assume that $\nu$ is given
in a way that we can take its expectation
$\mathbb{E}_{(s,a)\sim\nu}[(\cdot)]$, and extension to the case where $\nu$ is
given via samples is straightforward.

To achieve this goal, we first turn Eq.(1) into an equivalent constrained
convex program: given a collection of strongly convex and differentiable
functions $\\{f_{s,a}:\mathbb{R}\to\mathbb{R}\\}_{s,a}$—we will refer to the
collection as $f$ and discuss its choice later—consider

$\displaystyle\min_{q}\;$
$\displaystyle\mathbb{E}_{(s,a)\sim\nu}[f_{s,a}(q(s,a))]$ (3) s.t.
$\displaystyle\mathbb{E}_{r\sim
R(\cdot|s,a)}[r]+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}[q(s^{\prime},\pi)]-q(s,a)=0,~{}\forall
s,a\in\mathcal{S}\times\mathcal{A}.$

The constraints here are the same as Eq.(1). Since Eq.(1) uniquely determines
$q=q^{\pi}$, the feasible space of Eq.(3) is a singleton, so we can impose any
objective function on top of these constraints (here we use
$\mathbb{E}_{(s,a)\sim\nu}[f_{s,a}(q(s,a))]$) and it will not change the
optimal solution (which is always $q^{\pi}$, the only feasible point). As we
will see, however, $f=\\{f_{s,a}:\mathbb{R}\to\mathbb{R}\\}_{s,a}$ will serve
as an important regularizer in the function-approximation setting and is
crucial to our estimation guarantees.

######  Remark 1 ($(s,a)$-dependence of $f$).

Regularizers in prior works are $(s,a)$-independent [nachum2019dualdice,
yang2020off, zhan2022offline]. As we will see in Section 4.3, allowing for
$(s,a)$-dependence is very important for designing regularizers with improved
guarantees and performances.

We now rewrite (3) in its Lagrangian form, with $d^{D}\circ w$ serving the
role of dual variables:

$\min_{q}\max_{w}L_{f}^{q}(q,w):=\mathbb{E}_{\nu}[f_{s,a}(q(s,a))]+\mathbb{E}_{d^{D}}\left[w(s,a)\left(r(s,a)+\gamma
q(s^{\prime},\pi)-q(s,a)\right)\right].$ (4)

Finally, our actual estimator approximates Eq.(4) via finite-sample
approximation of the population loss $L_{f}^{q}$, and searches over restricted
function classes $\mathcal{Q}$ and $\mathcal{W}$ for $q$ and $w$,
respectively:

$\widehat{q}=\operatorname*{arg\,min}_{q\in\mathcal{Q}}\max_{w\in\mathcal{W}}\widehat{L}_{f}^{q}(q,w),$
(5)

where
$\widehat{L}_{f}^{q}(q,w)=\mathbb{E}_{\nu}[f_{s,a}(q(s,a))]+\frac{1}{n}\sum_{i=1}^{n}w(s_{i},a_{i})\left(r_{i}+\gamma
q(s_{i}^{\prime},\pi)-q(s_{i},a_{i})\right).$

#### Intuition for identification

Before giving the detailed finite-sample analysis, we provide some high-level
intuitions for why we can obtain the desired guarantee on
$\|\widehat{q}-q^{\pi}\|_{2,\nu}$. Note that Eq.(4) is structurally similar to
Eq.(2), and we still cannot verify the Bellman equation for $q^{\pi}$ in a
per-state-action manner, so the caveat of Eq.(2) seems to remain; why can we
identify $q^{\pi}$ under $\nu$?

The key here is to show that it suffices to check the loss function
$L_{f}^{q}$ only under a special choice of $w$ (as opposed to all of
$\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$). Importantly, this special $w$ is
not $w=w^{\pi}$;666In fact, $w^{\pi}$ should not appear in our analysis at
all: $w^{\pi}$ is defined w.r.t. the initial distribution of the MDP,
$\mu_{0}$, which has nothing to do with our goal of bounding
$\|\widehat{q}-q^{\pi}\|_{2,\nu}$. rather, it is the saddle point of our
regularized objective $L_{f}^{q}$: let $(q^{\pi},w_{f}^{*})$ be a saddle point
of $L_{f}^{q}$ (we will give the closed form of $w_{f}^{*}$ later). As long as
$w_{f}^{*}\in\mathcal{W}$—even if $\mathcal{W}$ is extremely “simple” and
contains nothing but $w_{f}^{*}$—we can identify $q^{\pi}$.

To see that, it is instructive to consider the special case of
$\mathcal{W}=\\{w_{f}^{*}\\}$ and the limit of infinite data. In this case,
our estimator becomes
$\operatorname*{arg\,min}_{q\in\mathcal{Q}}L_{f}^{q}(q,w_{f}^{*})$. By the
definition of saddle point:

$L_{f}^{q}(q^{\pi},w_{f}^{*})\leq L_{f}^{q}(q,w_{f}^{*}),~{}\forall q.$

While this shows that $q^{\pi}$ is a minimizer of the loss, it does not imply
that it is a unique minimizer. However, identification immediately follows
from the convexity brought by regularization: since
$f:\mathbb{R}\to\mathbb{R}$ is strongly convex,
$q\to\mathbb{E}_{\nu}[f_{s,a}(q(s,a))]$ as a mapping from
$\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ to $\mathbb{R}$ is strongly convex
under $\|\cdot\|_{2,\nu}$ (see Lemma LABEL:lem:strongly_convex in Appendix
LABEL:app:proof_value for a formal statement and proof), and
$L_{f}^{q}(q,w_{f}^{*})$ inherits such convexity since the other terms are
affine in $q$. It is then obvious that $q^{\pi}$ is the unique minimizer of
$L_{f}^{q}(q^{\pi},w_{f}^{*})$ up to $\|\cdot\|_{2,\nu}$, that is, any
minimizer of $L_{f}^{q}$ must agree with $q^{\pi}$ on $(s,a)$ pairs supported
on $\nu$. Our finite-sample analysis below shows that the above reasoning is
robust to finite-sample errors and the inclusion of functions other than
$w_{f}^{*}$ in $\mathcal{W}$.

###  4.2 Finite-sample Guarantees

In this subsection we state the formal guarantee of our estimator for
$q^{\pi}$ and the assumptions under which the guarantee holds. We start with
the condition on the regularization function $f$:

######  Assumption 1 (Strong convexity of $f$).

Assume $f_{s,a}:\mathbb{R}\to\mathbb{R}$ is nonnegative, differentiable, and
$M^{q}$-strongly convex for each $s\in\mathcal{S},a\in\mathcal{A}$. In
addition, assume both $f_{s,a}$ and its derivative $f_{s,a}^{\prime}$ take
finite values for any finite input.

This assumption can be concretely satisfied by a simple choice of
$f_{s,a}(x)=\frac{1}{2}x^{2}$, which is independent of $(s,a)$ and yields
$M^{q}=1$. Alternative choices of $f$ will be discussed in Section 4.3. Next
are the realizability and boundedness of $\mathcal{W}$ and $\mathcal{Q}$:

######  Assumption 2 (Realizability).

Suppose $w^{*}_{f}\in\mathcal{W}$, $q^{\pi}\in\mathcal{Q}$.

######  Assumption 3 (Boundedness of $\mathcal{W}$ and $\mathcal{Q}$).

Suppose $\mathcal{W}$ and $\mathcal{Q}$ are bounded, that is,
$C_{\mathcal{Q}}^{q}:=\max_{q\in\mathcal{Q}}\|q\|_{\infty}<\infty$,
$C_{\mathcal{W}}^{q}:=\max_{w\in\mathcal{W}}\|w\|_{\infty}<\infty$.

As a remark, Assumption 2 implicitly assumes the existence of $w_{f}^{*}$. As
we will see in Section 4.3, the existence and finiteness of $w_{f}^{*}$ is
automatically guaranteed given the finiteness of $f_{s,a}^{\prime}$
(Assumption 1) and $d^{D}(s,a)>0~{}\forall s,a$. More importantly, Assumptions
2 and 3 together imply that $\|q^{\pi}\|_{\infty}\leq C_{\mathcal{Q}}^{q}$ and
$\|w_{f}^{*}\|_{\infty}\leq C_{\mathcal{W}}^{q}$, which puts constraints on
how small $C_{\mathcal{Q}}^{q}$ and $C_{\mathcal{W}}^{q}$ can be. For example,
it is common to assume that $C_{\mathcal{Q}}^{q}=\tfrac{1}{1-\gamma}$, i.e.,
the maximum possible return when rewards are bounded in $[0,1]$, and this way
$\|q^{\pi}\|_{\infty}\leq C_{\mathcal{Q}}^{q}$ will hold automatically. The
magnitude of $\|w_{f}^{*}\|_{\infty}$ and $C_{\mathcal{W}}^{q}$, however, is
more nuanced and interesting, and we defer the discussion to Section 4.3.

Now we are ready to state the main guarantee for identifying $q^{\pi}$. All
proofs of this section can be found in Appendix LABEL:app:proof_value.

######  Theorem 2.

Suppose Assumptions 1, 2, 3 hold. Then, with probability at least $1-\delta$,

$\displaystyle||\widehat{q}-q^{\pi}||_{2,\nu}\leq
2\sqrt{\frac{\epsilon_{stat}^{q}}{M^{q}}},$

where
$\epsilon_{stat}^{q}=\left(C_{\mathcal{W}}^{q}+(1+\gamma)C_{\mathcal{W}}^{q}C_{\mathcal{Q}}^{q}\right)\sqrt{\frac{2\log\frac{2|\mathcal{W}||\mathcal{Q}|}{\delta}}{n}}$.

Theorem 2 shows the desired bound on $\|\widehat{q}-q^{\pi}\|_{2,\nu}$, which
depends on the magnitude of functions in $\mathcal{W}$ and $\mathcal{Q}$ as
well as their logarithmic cardinalities, which are standard measures of
statistical complexity for finite classes. One notable weakness is the
$O(n^{-\nicefrac{{1}}{{4}}})$ slow rate; this is due to translating the
$\epsilon_{stat}^{q}=O(n^{-\nicefrac{{1}}{{2}}})$ deviation between $L$ and
$\widehat{L}$ into $\|\widehat{q}-q^{\pi}\|_{2,\nu}$ via a convexity argument,
which takes square root of the error. The possibility of and obstacles to
obtaining an $O(n^{-\nicefrac{{1}}{{2}}})$ rate will be discussed in Section
LABEL:sec:conclusion.

###  4.3 On the Closed Form of $w_{f}^{*}$ and the Data Coverage Assumptions

One unusual aspect of our guarantees in Section 4.2 is that we do not make any
explicit data coverage assumptions, yet such assumptions are known to be
necessary even for return estimation (typically the boundedness of
$w^{\pi}=d^{\pi}/d^{D}$). Indeed, our data-coverage assumption is implicit in
Assumptions 2 and 3, which require $\|w_{f}^{*}\|_{\infty}\leq
C_{\mathcal{W}}^{q}<\infty$. If data fails to provide sufficient coverage,
$\|w_{f}^{*}\|_{\infty}$ will be large and our bound in Theorem 2 will suffer
due to a large value of $C_{\mathcal{W}}^{q}$.

To make the data coverage assumption explicit, we provide the closed-form
expression of $w_{f}^{*}$:

######  Lemma 3.

The saddle point of (4) is
$(q^{\pi},w_{f}^{*})=\operatorname*{arg\,min}_{q}\operatorname*{arg\,max}_{w}L_{f}^{q}(q,w)$,
where

$w_{f}^{*}=(I-\gamma\widetilde{P}^{\pi})^{-1}\left(\nu\circ
f^{\prime}(q^{\pi})\right)/d^{D}.$ (6)

Here $f^{\prime}(q^{\pi})$ is the shorthand for
$[f^{\prime}_{s,a}(q^{\pi}(s,a))]_{s,a}\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$.

The closed-form expression in Eq.(6) looks very much like a density ratio: if
we replace $\nu\circ f^{\prime}(q^{\pi})$ with $\mu_{0}^{\pi}$, we have
$(I-\gamma\widetilde{P}^{\pi})^{-1}\mu_{0}^{\pi}=d^{\pi}/(1-\gamma)$, and the
expression would be the ratio between $d^{\pi}$ and $d^{D}$ (up to a horizon
factor). Therefore, $w_{f}^{*}$ can be viewed as the density ratio of $\pi$
against $d^{D}$ when $\pi$ starts from the “fake” initial distribution
$\nu\circ f^{\prime}(q^{\pi})$. However, $\nu\circ f^{\prime}(q^{\pi})$ is in
general not a valid distribution, as it is not necessarily normalized or even
non-negative, making $\|w_{f}^{*}\|_{\infty}$ difficult to intuit. Below we
give relaxations of $\|w_{f}^{*}\|_{\infty}$, which are more interpretable and
give novel insights into how to relax the data-coverage assumption via
tweaking $f$.

######  Proposition 4.

$\|w_{f}^{*}\|_{\infty}\leq\tfrac{1}{1-\gamma}\cdot\|d_{\nu}^{\pi}/d^{D}\|_{\infty}\cdot\|f^{\prime}(q^{\pi})\|_{\infty}$,
where $d_{\nu}^{\pi}$ is the discounted state-action occupancy of $\pi$ under
$\nu$ as the initial state-action distribution.

The proposition states that $\|w_{f}^{*}\|_{\infty}$ can be bounded if data
provides sufficient coverage over $d_{\nu}^{\pi}$, and if
$f^{\prime}(q^{\pi})$ is bounded. The former shows that $d^{D}$ needs to cover
not only $\nu$, but also state-action pairs reachable by $\pi$ starting from
$\nu$. The latter is easily satisfied, and can be bounded again for concrete
choices of $f$, e.g.
$\|f^{\prime}(q^{\pi})\|_{\infty}\leq\|q^{\pi}\|_{\infty}\leq\frac{1}{1-\gamma}$
for $f_{s,a}(x)=\tfrac{1}{2}x^{2}$.

#### Designing $f$ to relax the coverage assumption

Lemma 3 shows that the coverage assumption (bounded $\|w_{f}^{*}\|_{\infty}$)
depends on $f$ (or rather its derivative $f^{\prime}$), which opens up the
possibility of properly designing $f$ to relax it. In fact, we could
completely eliminate the coverage assumption if we could set
$f^{\prime}(q^{\pi})=\mathbf{0}$, but that would require unrealistically
strong side information.

As a concrete example, consider $f_{s,a}(x)=\tfrac{1}{2}(x-q^{\pi}(s,a))^{2}$,
and it is easy to verify that
$f^{\prime}_{s,a}(q^{\pi}(s,a))=x-q^{\pi}(s,a)|_{x=q^{\pi}(s,a)}=0$. Compared
to $f_{s,a}(x)=\tfrac{1}{2}x^{2}$, the new $f$ essentially adds a 1st-order
term $q^{\pi}(s,a)\cdot x$ to change $w_{f}^{*}$, while leaving the convexity
required by Assumption 1 intact, which only depends on the 2nd-order term
$\tfrac{1}{2}x^{2}$. Of course, this is not a viable choice of $f$ in practice
as it requires knowledge of $q^{\pi}$, which is precisely our learning target.

While the reason $f_{s,a}(x)=\tfrac{1}{2}(x-q^{\pi}(s,a))^{2}$ can eliminate
the coverage requirement is obvious retrospectively ($q^{\pi}$ already
minimizes $\mathbb{E}_{\nu}[f(q)]$ even without any data), our analyses apply
much more generally and characterize the effects of arbitrary $f$ on the
coverage assumption. Inspired by this example, we can consider practically
feasible choices such as $f_{s,a}(x)=\tfrac{1}{2}(x-\widetilde{q}(s,a))^{2}$,
where $\widetilde{q}$ is an approximation of $q^{\pi}$ obtained by other
means, e.g. a guess based on domain knowledge. If $\widetilde{q}\approx
q^{\pi}$, our estimator enjoys significantly relaxed coverage requirements.
But even if $\widetilde{q}$ is a poor approximation of $q^{\pi}$, it does not
affect our estimation guarantees as long as the condition implied by
Proposition 4 is satisfied. (In fact, $f_{s,a}(x)=\tfrac{1}{2}x^{2}$ is a
special case of $\widetilde{q}\equiv 0$.) Such a use of approximate models is
similar to how doubly robust estimators [dudik2011doubly, jiang2016doubly,
thomas2016data] enjoy reduced variance given an accurate model, and remain
unbiased even if the approximate model is arbitrarily poor. We will show in
Section LABEL:sec:experiments that this idea is empirically effective.

##  5 Weight-function Estimation

Similar to value-function estimation, our methodology can also be applied to
estimate the weight function $w^{\pi}$. Due to the similarity with Section 4
in the high-level spirit, we will be concise in this section and only explain
in detail when there is a conceptual difference from Section 4. Some notations
(such as the function classes $\mathcal{W}$ and $\mathcal{Q}$) will be abused,
but we emphasize that this section considers a different learning task than
Section 4, so they should be viewed as different objects (e.g., the
realizability assumptions for $\mathcal{W}$ and $\mathcal{Q}$ below will be
different from those in Section 4).

As before, we assume that the user provides a distribution777Recall we assume
$d^{D}(s,a)>0~{}\forall s,a$ for technical convenience. When this is not the
case, $\eta$ should be supported on $d^{D}$, as the target function $w^{\pi}$
is only defined on the support of $d^{D}$.
$\eta\in\Delta(\mathcal{S}\times\mathcal{A})$ and our goal is to develop an
estimator with guarantees on $\|\widehat{w}-w^{\pi}\|_{2,\eta}$. Analogous to
Section 4, consider

$\displaystyle\min_{w}\;$
$\displaystyle\mathbb{E}_{(s,a)\sim\eta}[f_{s,a}(w(s,a))]$ (7) s.t.
$\displaystyle\textstyle
d^{D}(s,a)w(s,a)=(1-\gamma)\mu_{0}^{\pi}(s,a)+\gamma\sum_{s^{\prime},a^{\prime}}P^{\pi}(s,a|s^{\prime},a^{\prime})d^{D}(s^{\prime},a^{\prime})w(s,a),~{}\forall
s,a.$

Here $f=\\{f_{s,a}\\}_{s,a}$ will need to satisfy similar assumptions as in
Section 4. The constraints are the Bellman flow equations with a change of
variable $d(s,a)=d^{D}(s,a)\cdot w(s,a)$. Their unique solution is
$d(s,a)=d^{\pi}(s,a)$ (and hence $w(s,a)=d^{\pi}(s,a)/d^{D}(s,a)$), thus the
feasible space is again a singleton, and the objective does not alter the
optimal solution. We then use dual variables $q$ to rewrite (7) in its
Lagrangian form: $\min_{w}\max_{q}L_{f}^{w}(q,w):=$

$\mathbb{E}_{\eta}\left[f_{s,a}(w(s,a))\right]+(1-\gamma)\mathbb{E}_{\mu_{0}}\left[q(s,\pi)\right]+\mathbb{E}_{d^{D}}\left[w(s,a)(\gamma
q(s^{\prime},\pi)-q(s,a))\right]$ (8)

We approximate the saddle-point solutions by optimizing the empirical loss
$\widehat{L}_{f}^{w}$ over restricted function classes
$\mathcal{W},\mathcal{Q}$:
$\widehat{w}=\operatorname*{arg\,min}_{w\in\mathcal{W}}\max_{q\in\mathcal{Q}}\widehat{L}_{f}^{w}(q,w)$,
where
$\widehat{L}_{f}^{w}(q,w):=\mathbb{E}_{\eta}\left[f_{s,a}(w(s,a))\right]+(1-\gamma)\frac{1-\gamma}{n_{0}}\sum_{j=1}^{n_{0}}q(s_{j},\pi)+\frac{1}{n}\sum_{i=1}^{n}w(s_{i},a_{i})\left(\gamma
q(s_{i}^{\prime},\pi)-q(s_{i},a_{i})\right)$, and $\\{s_{j}\\}_{j=1}^{n_{0}}$
is a separate dataset sampled i.i.d. from $\mu_{0}$ to provide information
about the initial distribution.

We provide the closed-form expression for the saddle point of $L_{f}^{w}$
below, which resembles the Q-function for a proxy reward function
$f^{\prime}(w^{\pi})\circ\eta/d^{D}$.

######  Lemma 5.

The closed form solutions of (8) are
$(w^{\pi},q_{f}^{*})=\operatorname*{arg\,min}_{w}\operatorname*{arg\,max}_{q}L_{f}^{w}(q,w)$,
where

$q_{f}^{*}=(I-\gamma P^{\pi})^{-1}(f^{\prime}(w^{\pi})\circ\eta/d^{D}).$ (9)