Telescoping method, summation formulas, and inversion pairs

1.   Introduction

The telescoping method aims to solve the following problem: For a sequence $f(k)$ in some class ${\mathcal S}$, decide whether there exists $g(k)\in {\mathcal S}$ such that

The sequence $g(k)$ is called the anti-difference of $f(k)$. Clearly, once we obtain $g(k)$, we will derive the indefinite summation formula

Gosper [7] solved the telescoping problem for hypergeometric terms by giving the so-called Gosper's algorithm. As mentioned in the book of Petkovše et al. [12], Gosper's algorithm is one of the landmarks in the history of symbolic summation. It not only fully solves the telescoping problem of hypergeometric terms, but also plays an important role in the creative telescoping algorithm developed by Wilf and Zeilberger [15].

Since the appearance of Gosper's algorithm and Zeilberger's algorithm, the telescoping method for more general sequences has been extensively studied. Chyzak [4] extended Zeilberger's algorithm to holonomic sequences. Inspired by Karr's summation algorithm [8], Schneider [13] presented an approach to summation in difference rings. Recently, Paule and Schneider [11] gave a symbolic summation theory for unspecified sequences.

This paper is motivated by considering the inversion formulas of basic and elliptic hypergeometric series. We find that the idea of Gosper's algorithm is an efficient mechanism for this purpose.

Let us recall the main steps of Gosper's algorithm. Suppose $t_k$ is a hypergeometric term, i.e., the ratio $t_{k+1}/t_k$ is a rational function of $k$. We first write the ratio $t_{k+1}/t_k$ in the form

where $a(k), b(k), c(k)$ are polynomials in $k$ such that $\gcd (a(k),b(k+h)) = 1$ for all nonnegative integers $h$. Then a hypergeometric telescoping $z_k$ of $t_k$ exists if and only if there is a polynomial solution $x(k)$ to the linear difference equation

If $x(k)$ exists, the telescoping of $t_k$ is

To deal with sequences which are not hypergeometric, we release the restriction that $t_{k+1}/t_k$ is a rational function of $k$ so that the $a(k),b(k),c(k)$ in (2) are arbitrary functions of $k$. It is straightforward to check that if $x(k)$ is a function satisfying (3), then the function $z_k$ given by (4) is still a telescoping of $t_k$.

This observation motivates a new approach to the definite summation of sequences beyond the hypergeometric ones. Given a sequence $t_k$, we get (2) by spreading out the common factors of the numerator and the denominator of the ratio $t_{k+1}/t_k$ up to a shift. Then we try to find a function $x(k)$ satisfying (3). Once we have (2) and (3), we will obtain the telescoping $z_k$ and thus derive the summation formula (1).

Recall that two upper triangle matrices $(f_{n,k})_{n,k \ge 0}, (g_{n,k})_{n,k \ge 0}$ are called an inversion pair if

If $(f,g)$ is an inversion pair, we have

There are many interesting applications of the inversion pairs. For example, Warnaar [14] established some new identities on multibasic theta hypergeometric series by elliptic analogue of the inverse relations. Ma gave an extension of Warnaar's matrix inversion and obtained a series of classical identities in [10].

Ma [10] showed that the inversion relations (5) can be derived by summation formulas of form (1). This enables us to study inversion pairs by solving the telescoping problem. We will see that the trivial case of $x(k) = 1$ leads to the key summation formula (Theorem 4) in [10]. Note that the assumption on $f,g$ in Ma's formula (Equaiton (6) below) is nothing but the Gosper equation (3).

Along this approach, we construct a new summation formula which extends Ma's result. Based on it and the related inversion pairs, we are able to derive several basic hypergeometric identities and elliptic hypergeometric identities.

The paper is organized as follows. In Section 2, we give a simple proof of Ma's summation formula based on the telescoping method. Then in Section 3, we propose a bibasic extension of Ma's summation formula along the telescoping approach and give some applications. Then in Section 4, we present a summation formula corresponding to the non trivial case where $x(k) \not = 1$. Section 5 provides the inversion formulas related to the summation formulas.

Notation. Throughout this paper, we will employ the following standard notations for the theory of $q$-series and elliptic functions [6]. Assume $|q|<1$, we define the $q$-shifted factorials by

Write

an basic hypergeometric series $_{r}\phi_s$ is defined by

and the balanced basic hypergeometric series $_{r+1}\phi_r$ is defined by $z = q$ and the parameters satisfy $b_1b_2\cdots b_r = qa_1a_2\cdots a_{r+1}$.

Assume further that $|p|<1$. The elliptic function is defined by

The elliptic analogues of the $q$-shifed factorials are given by

Also, we write

Note that $\theta(x;0) = 1-x$ and hence $(a;q,0)_n = (a;q)_n$.

The balanced, very-well-poised, elliptic (or modular) hypergeometric series is defined by

where the parameters satisfy $(a_4\cdots a_{r+1})^2 = a_1^{r-3}q^{r-5}$.

We follow the usual convention in defining produces as

2.   A simple proof of Ma's formula

Ma used the following summation formula to prove the inversion formulas. We will give a simple proof by the idea of Gosper's algorithm.

Theorem 2.1. ([10,Theorem 4]). Let $f(a,b)$ and $g(a,b)$ be two arbitrary nonzero functions over $\mathbb{C}$ in variables $a,b$ such that

and ${a_i},{b_i},{c_i},{d_i}$ be arbitrary sequences such that none of the denominators in (7) vanishes. Then for any nonnegative integers $m,n$,

Proof. Let

We have

Set

Then by the assumption (6), we have

Therefore, the telescoping of $t_k$ is

we get the formula (7) by summing $k$ from $-n$ to $m$.

3.   A bibasic extension of Ma's formula

Motivated by Ma's summation formula, we consider another special kind of $f(a,b)$ and derive a new summation formula.

Theorem 3.1. Let $f(a,b)$ be an arbitrary nonzero functions over $\mathbb{C}$ in variables $a,b$ such that

and ${a_i},{b_i},{c_i},{d_i},{e_i}$ be arbitrary sequences such that none of the denominators in (9) vanishes. Then for any nonnegative integers $m,n$, we have

Proof. Let

Then,

Set

We see that (2) holds. By the assumption (8), we have

Hence by the Gosper's algorithm, we obtain the telescoping of $t_k$:

we get the formula (9) by summing $k$ from $-n$ to $m$, .

Now we give some applications of Theorem 3.1. The first one is a summation formula for finite series.

Corollary 3.1. Let ${a_i},{b_i},{c_i},{d_i},{e_i}$ be arbitrary sequences with $a_i^2 = b_ic_id_ie_i$ such that none of the denominators in (10) vanishes. Then for any nonnegative integer $m$, we have

Proof. Let $f(a,b) = 1-a/b$. It is straightfoward to check that (8) holds by the assumption $a_i^2 = b_ic_id_ie_i$. Hence by Theorem 3.1, we derive (10).

Corollary 3.1 is equivalent to a result of Ian G. Macdonald, first published by Bhatnagar and Milne [2,Eq.(2.30)]. From this formula, we can derive several summation identities. Here are two examples.

Example 3.1. In Corollary 3.1, set

where $a = b c d$. We derive that

Let $m\rightarrow\infty$, we obtain a balanced $_6\phi_5$ series [6,Page 356,Eq. (Ⅱ.20)]

Example 3.2. Setting

in Corollary 3.1, we derive an indefinite bibasic summation formula [6,Eq. (Ⅱ.36)]:

Gasper and Rahman used this identity to set up a series of quadratic and cubic summation and transformation formulas of basic hypergeometric series.

The second one is an elliptic hypergeometric identity.

Corollary 3.2. Let ${a_i},{b_i},{c_i},{d_i},{e_i}$ be arbitrary sequences with $a_i^2 = b_ic_id_ie_i$ such that none of the denominators in (11) vanishes. Then for any nonnegative integer $m,n$, we have

Proof. Let $f(a,b) = \theta(a/b;p)$. Noting that $a^2 = bcde$, we have Weierstrass' identity

which means that $f(a,b)$ satisfies (8). Hence by Theorem 3.1, we derive (11).

This formula has been stated in an equivalent form by Warnaar [14,Eq.(3.2)]. We list some applications of Corollary 3.2 on elliptic hypergeometric series.

Example 3.3. Setting

and $n = 0$ in Corollary 3.2 where $a = bcd$, and making some simplifications, we deduce that a special case of [6,Page 321,Eq.(11.4.4)] where $a = bcd$

Example 3.4. Setting

and $n = 0$ in Corollary 3.2, we get

It is an indefinite elliptic hypergeometric series of Warnaar [14]. Moreover, Warnaar used the specialization of this identity to set up a pair of inverse matrices.

Example 3.5. Setting

in Corollary 3.2, and making some simplifications, we deduce that [6,Page 326,Eq.(11.6.6)]

4.   A general summation formula

In this section, we consider the case of nontrivial $x(k)$, i.e., $x(k) \not = 1$. For an arbitrary function $g(a,b)$, we will find a function $x(k)$ satisfying (3) and derive a general summation formula.

Theorem 4.1. Let $g(a,b)$ be an arbitrary function over the complex field $\mathbb{C}$ in variables $a,b$, and ${a_i},{b_i},{c_i},{p_i},{q_i},{r_i}$ be arbitrary sequences such that none of the denominators in (13) vanishes. Suppose $x(k)$ is a function over the complex field $\mathbb{C}$ which satisfies

Then for any nonnegative integers $m,n$,

Proof. Let

Then,

Set

We see that (2) holds. By the assumption (12), we have

Hence the telescoping of $t_k$ is given by

We get the formula (13) by summing $k$ from $-n$ to $m$ and making some simplifications.

Actually, given an arbitrarily function $g(a,b)$, we can derive an explicit formula for the function $x(k)$ by taking a nonzero initial value $x(0)$. This allows us to construct some new summation identities. In the following part of this section, we will give some applications of Theorem 4.1. We only consider the simple case $x(0) = 1$.

To derive hypergeometric identities, we take $g(a,b) = a-b$ and obtain

Corollary 4.1. Let ${a_i}, b_i, c_i, {p_i},{q_i},{r_i}$ be arbitrary sequences such that none of the denominators in (14) vanishes. Then for any nonnegative integer $m,n$, we have

Proof. Let $g(a,b) = a-b$. Then by (12) we derive that

Considering the initial value, we have

Hence by Theorem 4.1 we obtain (14).

As examples, we derive the following hypergeometric and basic hypergeometric identities.

Example 4.1. Setting $n = 0$ and

in (14) where $0\leq i\leq m$, we see that

After some simplifications, we derive that

Example 4.2. Setting $n = 0$ and

in (14), we see that

After some simplifications, we derive that

Example 4.3. Let

Setting $n = 0$ and

in (14), we see that

After some simplifications, we derive that [1,Exapmle 6.2]

where

Now we consider another choice of the function $g(a,b)$.

Corollary 4.2. Let ${a_i},{b_i},{c_i},{p_i},{q_i},{r_i}$ be arbitrary sequences such that none of the denominators in (15) vanishes. Then for any nonnegative integers $m,n$, we have

Proof. Let $g(a,b) = 1-ab$. Then by (12) we have

Considering the initial value, we derive that

Hence by Theorem 4.1 we obtain (15).

Example 4.4. Set $n = 0$ and

in (15), we see that

After some simplifications, we derive

We remark that this formula is a result of Gosper, first published by Bauer and Petkovšek [1,Eq.(6.39)].

5.   Inversion pairs

In this section, we will derive an inversion pair via the summation formula (9) and present some applications.

To construct the inversion pair, we first take $n = 0$ and $m = n$ in (9) and multiply both sides by the common denominator. We thus have

Lemma 5.1. Let $f(a,b)$ be an arbitrary function over the complex field $\mathbb{C}$ in variables $a,b$ which satisfies (8), and ${a_i},{b_i},{c_i},{d_i},{e_i}$ be arbitrary sequences. Then for any nonnegative integers $n$,

Now we are ready to give the inversion pair.

Theorem 5.1. Let $z$ and $x_i, y_i$ $(i\in\mathbb{Z})$ be indeterminate such that none of the denominators in (18) and (19) vanishes. Suppose $f(x,y)$ is a bivariate function over the complex field $\mathbb{C}$ in variables $x,y$ which satisfies (8) and

for any variable $t$. Set

and

Then $F = (f_{n,k})_{n,k\in \mathbb{Z}}$ and $G = (g_{n,k})_{n,k\in \mathbb{Z}}$ form an inversion pair.

Proof. Since $f(tx,ty) = f(x,y)$, we have

Therefore it holds for $l = n$.

Now assume $n\geq l+1$. Take $n\rightarrow n-l$ and

in (16). The first product of the right hand side of (16) contains the term

and the second product of the right hand side of (16) contains the term

Noting that $f(x,y) = -(x/y)f(y,x)$ implies that $f(x,x) = 0$, we thus derive that the right hand side of (16) is zero.

By the relation (17), the left hand side becomes

Dividing the factor

we could get it.

It is straightforward to check that $f(x,y) = 1-x/y$ satisfies (8) and (17). We thus obtain

Corollary 5.1. Let

and

Then $(f_{n,k})$ and $(g_{n,k})$ form an inversion pair.

We remark that this inversion pair was first given by Krattenthaler [9,Eq.(1.5)]. From this inversion pair, we can derive several classical inversion pairs.

Example 5.1. Set $z = a$, $x_j = bq^j$ and $y_j = q^j$ in Corollary 5.1. After some simplifications, we derive the inversion pair

and

This pair is due to Bressoud [3], which was used to study the finite forms of Rogers-Ramanujan identities.

Example 5.2. Set $z = a$, $x_j = bp^j$ and $y_j = q^j$ in Corollary 5.1. After some simplifications, we derive the following inversion pair

and

Notice that it is an inversion pair that involves rising $q$-factorials with two different bases, mentioned by Gasper [5]. They used this matrix inverse to derive numerous bibasic, cubic, and quartic summation formulas for basic hypergeometric series.

By the definition of theta functions, we see that $f(x,y) = \theta(x/y;p)$ also satisfies (8) and (17). Therefore,

Corollary 5.2. Let

and

Then $(f_{n,k})$ and $(g_{n,k})$ form an inversion pair.

This is a pair of inverse matrices due to Warnaar [14] and the elliptic analogue of inverse matrices of Krattenthaler [9,Eq.(1.5)]. Moreover, we can derive the classical pairs of inverse matrices.

Example 5.3. Set $z = ab$, $x_j = aq^j$ and $y_j = r^j$ in Corollary 5.2, making some simplifications, we can derive a pair of inverse matrices

then

We note that the case of $p = 0$ corresponds to [5,Eqs. (3.2) and (3.3)] and [9,Eq. (4.3)].

Example 5.4. Set $z = ab$, $x_j = aq^j$ and $y_j = q^{rj}$ in Corollary 5.2. After some simplifications, we derive the following inversion pair

and

It is due to Warnaar [14,Eq.(3.5)], who used it to set up a series of summation and transformation formulas for terminating, balanced, very-well poised, elliptic hypergeometric series.

Acknowledgments

The work was supported by the National Natural Science Foundation of China (grant 11771330). The authors would like to thank the referees for their careful reading of the manuscript and for their constructive suggestions provided in the reports.