The Extended Zeilberger’s Algorithm with Parameters

William Y.C. Chen^{1}, Qing-Hu Hou^{2} and Yan-Ping Mu^{3}

1,2Center for Combinatorics, LPMC-TJKLC Nankai University Tianjin 300071, P. R. China

3College of Science Tianjin University of Technology Tianjin 300384, P.R. China

1chen@nankai.edu.cn, ^{2}hou@nankai.edu.cn, ^{3}yanping.mu@gmail.com

Dedicated to Professor Wen-Tsun Wu on the occasion of his ninetieth birthday

Abstract

For a hypergeometric series ∑_{k} f(k, a, b, …, c) with parameters a, b, …, c, Paule has found a variation of Zeilberger’s algorithm to establish recurrence relations involving shifts on the parameters. We consider a more general problem concerning several similar hypergeometric terms f_{1}(k, a, b, …, c), f_{2}(k, a, b, …, c), …, f_{m}(k, a, b, …, c). We present an algorithm to derive a linear relation among the sums ∑_{k} f_{i}(k, a, b, …, c) (1 ≤ i ≤ m). Furthermore, when the summand f_{i} contains the parameter x, we can require that the coefficients be x-free. Such relations with x-free coefficients can be used to determine whether a polynomial sequence satisfies the three term recurrence and structure relations for orthogonal polynomials. The q-analogue of this approach is called the extended q-Zeilberger’s algorithm, which can be employed to derive recurrence relations on the Askey-Wilson polynomials and the q-Racah polynomials.

Keywords: Zeilberger’s algorithm, the Gosper algorithm, hypergeometric series, orthogonal polynomials

AMS Subject Classification: 33F10, 33C45, 33D45

1. Introduction

Based on Gosper’s algorithm, Zeilberger [14, 16] has developed a powerful theory for proving identities on hypergeometric series and basic hypergeometric series. Let F (n, k) be a double hypergeometric term, namely, F (n + 1, k)/F (n, k) and F (n, k + 1)/F (n, k) are both rational functions of n and k. Zeilberger’s algorithm is devised to find a double hypergeometric term G(n, k) and polynomials a_{0}(n), a_{1}(n), …, a_{m}(n) which are independent of k such that

a_{0}(n)F (n, k)+a_{1}(n)F (n+1, k)+⋯+a_{m}(n)F (n+m, k) = G(n, k+1)−G(n, k).

(1.1)

Writing

S(n) = ∑_{k=0}^{∞} F (n, k).

Summing (1.1) over k, we deduce that

a_{0}(n)S(n)+a_{1}(n)S(n+1)+⋯+a_{m}(n)S(n+m) = G(n, ∞)−G(n, 0). (1.2)

Thus the identity

∑_{k=0}^{∞} F (n, k) = f(n)  (1.3)

can be justified by verifying that f(n) also satisfies (1.2) and both sides of (1.3) share the same initial values.

Paule [12] extended Zeilberger’s algorithm to the multi-variable case and found many applications. Let n denote the vector of variables (n_{1}, …, n_{r}) and F (n, k) be a multi-variable hypergeometric term, that is,

\frac{F (n_{1} + 1, n_{2}, …, n_{r}, k)}{F (n_{1}, n_{2}, …, n_{r}, k)}, …, \frac{F (n_{1}, n_{2}, …, n_{r} + 1, k)}{F (n_{1}, n_{2}, …, n_{r}, k)}, \frac{F (n_{1}, n_{2}, …, n_{r}, k + 1)}{F (n_{1}, n_{2}, …, n_{r}, k)}

are all rational functions of n and k. Given m shifts γ_{1}, …, γ_{m} ∈ ℤ^{r} of the variables n, he found that one can use a similar procedure to Zeilberger’s algorithm to find a multi-variable hypergeometric term G(n, k) and coefficients α_{1}(n), …, α_{m}(n) which are independent of k such that

∑_{i=1}^{m} α_{i}(n)F (n + γ_{i}, k) = G(n, k + 1) − G(n, k).  (1.4)

The main idea of this paper is the observation that Paule’s approach can be further extended to a more general telescoping problem. Let f_{1}(k, a, b, …, c), …, f_{m}(k, a, b, …, c) be m similar hypergeometric terms of k with parameters a, b, …, c, namely, the ratios

\frac{f_{i}(k, a, b, …, c)}{f_{j}(k, a, b, …, c)} and \frac{f_{i}(k + 1, a, b, …, c)}{f_{i}(k, a, b, …, c)}

are all rational functions of k and a, b, …, c. Find a hypergeometric term g(k, a, b, …, c), that is, the ratio g(k + 1, a, b, …, c)/g(k, a, b, …, c) is a rational function of k and a, b, …, c, and polynomial coefficients a_{1}(a, b, …, c), a_{2}(a, b, …, c), …, a_{m}(a, b, …, c) which are independent of k such that

a_{1}f_{1}(k) + a_{2}f_{2}(k) + ⋯ + a_{m}f_{m}(k) = g(k + 1) − g(k).  (1.5)

For brevity, from now on we may omit the parameters a, b, …, c and write f_{i}(k) for f_{i}(k, a, b, …, c), a_{i} for a_{i}(a, b, …, c), and g(k) for g(k, a, b, …, c). Once the telescoping relation (1.5) is established, summing over k often leads to a homogenous relation among the sums ∑_{k} f_{1}(k), …, ∑_{k} f_{m}(k):

a_{1} ∑_{k} f_{1}(k) + a_{2} ∑_{k} f_{2}(k) + ⋯ + a_{m} ∑_{k} f_{m}(k) = 0.

Let F (n, k) be a multi-variable hypergeometric term and γ_{i} ∈ ℤ^{r}. Then f_{i}(k, n) = F (n + γ_{i}, k) are similar hypergeometric terms of k with parameters n_{1}, …, n_{r}. Therefore, Paule’s equation (1.4) is a special case of (1.5). However, we should note that the extended Zeilberger’s algorithm is very much in the spirit of the original algorithm of Zeilberger, and it should be regarded as a variation as well because the implementation of the extended algorithm is essentially the same as the original algorithm.

As an application of our algorithm, one can determine whether a given hypergeometric series satisfies the recurrence relation and the structure relations for orthogonal polynomials. Meanwhile, we obtain the coefficients in these relations. For instance, let P_{n}(x) = ∑_{k} P_{n,k}(x) be the hypergeometric representation of the Jacobi polynomials as given in (3.3). Set

f_{1}(k) = P_{n,k}(x), f_{2}(k) = P′_{n+1,k}(x), f_{3}(k) = P′_{n,k}(x), f_{4}(k) = P′_{n−1,k}(x),

where P′_{n,k}(x) denotes the derivative of P_{n,k}(x) with respect to x. The extended Zeilberger’s algorithm enables us to find the structure relation for P_{n}(x)

P_{n}(x) = ã_{n}P′_{n+1}(x) + b̃_{n}P′_{n}(x) + c̃_{n}P′_{n−1}(x).  (1.6)

It is worth mentioning that neither the original Zeilberger’s algorithm nor the variation of Paule is directly applicable to the above relation (1.6) involving derivatives.

Furthermore, it is important to impose an additional requirement that the coefficients a_{1}, …, a_{m} in (1.5) are not only independent of k but also independent of some other parameters such as the variable x occurring as the variable of orthogonal polynomials. For example, ã_{n}, b̃_{n} and c̃_{n} in (1.6) are required to be independent of the variable x. Based on this parameterfree property of the coefficients, Chen and Sun [6] have developed a computer algebra approach to proving identities on Bernoulli polynomials and Euler polynomials.

We should notice that Koepf and Schmersau [10] have shown that one can derive the recurrence relation and structure relations for orthogonal polynomials by variations of Zeilberger’s algorithm. For each of the three kinds of relations, they have provided an algorithm. The extended Zeilberger’s algorithm serves as a unification of their algorithms and applies to more general cases. For instance, our algorithm can also be used to derive recurrence relations for the connection coefficients between two classes of Meixner polynomials with different parameters.

In another direction, the extended Zeilberger’s algorithm can be adapted to deal with basic hypergeometric terms. Using the q-analogue of this algorithm, we can recover the three term recurrence relations for the Askey-Wilson polynomials and the q-Racah polynomials.

Let us recall some terminology and notation. A function t(k) is called a hypergeometric term if t(k + 1)/t(k) is a rational function of k. A hypergeometric series is defined by

rF_{s} ( \begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix} | z) = ∑_{k=0}^{∞} \frac{(a_{1})_{k} ⋯ (a_{r})_{k}}{(b_{1})_{k} ⋯ (b_{s})_{k}} \frac{z^{k}}{k!} ,

where (a)_{k} = a(a + 1) ⋯ (a + k − 1) is the raising factorial. The q-shifted factorial is given by (a; q)_{k} = (1 − a)(1 − aq) ⋯ (1 − aq^{k−1}) and we write

(a_{1}, …, a_{m}; q)_{k} = (a_{1}; q)_{k} ⋯ (a_{m}; q)_{k}.

Then a basic hypergeometric series is defined by

rϕ_{s} [ \begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix} | q; z] = ∑_{k=0}^{∞} \frac{(a_{1}, ⋯, a_{r}; q)_{k}}{(b_{1}, ⋯ b_{s}; q)_{k}} \frac{z^{k}}{(q; q)_{k}} ((−1)^{k}q^{\binom{k}{2}})^{s−r+1} .

2. The Extended Zeilberger’s Algorithm

Let f_{1}(k), f_{2}(k), …, f_{m}(k) be similar hypergeometric terms with parameters a, b, …, c. Recall that two hypergeometric terms f(k) and g(k) are said to be similar if their ratio is a rational function of k and the parameters. We assume that

\frac{f_{1}(k + 1)}{f_{1}(k)} = \frac{u(k)}{v(k)} and \frac{f_{i}(k)}{f_{1}(k)} = \frac{p_{i}(k)}{Q(k)}, i = 1, 2, …, m,  (2.1)

where u(k), v(k), p_{i}(k), Q(k) are polynomials in k and the parameters a, b, …, c. Suppose that f_{i}(k) satisfy (2.1). Then

\frac{f_{i}(k + 1)}{f_{i}(k)} = \frac{f_{i}(k + 1)/f_{1}(k + 1)}{f_{i}(k)/f_{1}(k)} \frac{f_{1}(k + 1)}{f_{1}(k)} = \frac{p_{i}(k + 1)Q(k)u(k)}{p_{i}(k)Q(k + 1)v(k)}

and

\frac{f_{i}(k)}{f_{j}(k)} = \frac{f_{i}(k)/f_{1}(k)}{f_{j}(k)/f_{1}(k)} = \frac{p_{i}(k)}{p_{j}(k)}

are rational functions of k and a, b, …, c. Thus (2.1) is equivalent to the statement that f_{1}(k), f_{2}(k), …, f_{m}(k) are similar hypergeometric terms.

Our aim is to find coefficients a_{1}, …, a_{m} as rational functions in the parameters a, b, …, c but independent of k (called k-free coefficients) such that

a_{1}f_{1}(k) + a_{2}f_{2}(k) + ⋯ + a_{m}f_{m}(k) = g(k + 1) − g(k)  (2.2)

for some hypergeometric term g(k) with parameters a, b, …, c. By the similarity of f_{1}(k), …, f_{m}(k),

t_{k} = a_{1}f_{1}(k) + a_{2}f_{2}(k) + ⋯ + a_{m}f_{m}(k)  (2.3)

is a hypergeometric term of k with parameters a, b, …, c. So we can apply Gosper’s algorithm [8] to find g(k) such that t_{k} = g(k + 1) − g(k). Notice that we always have a trivial solution a_{1} = a_{2} = ⋯ = a_{m} = 0 and g(k) = 0.

Notice that by multiplying the common denominator, the coefficients a_{1}, …, a_{m} in (2.2) become polynomials in the parameters a, b, …, c. If no confusion arises, we may not mention the parameters a, b, …, c. In the usual case n is the parameter for identities on finite sums.

It follows from (2.3) that

\frac{t_{k+1}}{t_{k}} = \frac{f_{1}(k + 1)}{f_{1}(k)} \frac{∑_{i=1}^{m} a_{i}f_{i}(k + 1)/f_{1}(k + 1)}{∑_{i=1}^{m} a_{i}f_{i}(k)/f_{1}(k)}
= \frac{u(k)Q(k)}{v(k)Q(k + 1)} \frac{∑_{i=1}^{m} a_{i}p_{i}(k + 1)}{∑_{i=1}^{m} a_{i}p_{i}(k)}.

Suppose that

\frac{u(k)Q(k)}{v(k)Q(k + 1)} = \frac{a(k)}{b(k)} \frac{c(k + 1)}{c(k)}

is a Gosper representation, i.e., a(k), b(k), c(k) are polynomials such that gcd(a(k), b(k + h)) = 1 for all non-negative integers h. Then a Gosper representation of t_{k+1}/t_{k} is given by

\frac{t_{k+1}}{t_{k}} = \frac{a(k)}{b(k)} \frac{c(k + 1)P (k + 1)}{c(k)P (k)},

where

P (k) = ∑_{i=1}^{m} a_{i}p_{i}(k).  (2.4)

Gosper’s algorithm states that g(k) exists if and only if there exists a polynomial x(k) such that

a(k)x(k + 1) − b(k − 1)x(k) = c(k)P (k).  (2.5)

Moreover, the degree bound d for x(k) can be estimated by a(k) and b(k). Suppose

x(k) = ∑_{i=0}^{d} c_{i}k^{i}.

By comparing the coefficients of each power of k on both sides, we obtain a system of linear equations on a_{1}, …, a_{m} and c_{0}, c_{1}, …, c_{d}. Solving the system of linear equations, we find coefficients a_{1}, …, a_{m} and

g(k) = \frac{b(k − 1)x(k)}{c(k)Q(k)}f_{1}(k).

The extended Zeilberger’s algorithm can be described in terms of the following steps.

Input: m similar hypergeometric terms f_{1}(k), …, f_{m}(k). Output: k-free coefficients a_{1}, a_{2}, …, a_{m} and a hypergeometric term g(k) satisfying (2.2).

1. Compute the rational functions

r_{i}(k) = \frac{f_{i}(k)}{f_{1}(k)} and r(k) = \frac{f_{1}(k + 1)}{f_{1}(k)}.

Set Q(k) to be the common denominator of r_{1}(k), …, r_{m}(k),

p_{i}(k) = r_{i}(k)Q(k),

and let P (k) be given by (2.4).

2. Compute a Gosper representation of

r(k)\frac{Q(k)}{Q(k + 1)} = \frac{a(k)}{b(k)} \frac{c(k + 1)}{c(k)}.

3. Compute the degree bound d for x(k) and solve the equation (2.5) by the method of undetermined coefficients to obtain the k-free coefficients a_{1}, …, a_{m} and the polynomial x(k).

4. The hypergeometric term g(k) is then given by

g(k) = \frac{b(k − 1)x(k)}{c(k)Q(k)}f_{1}(k).

Suppose that F (n, k) is a double hypergeometric term. Let f_{i}(k) = F (n+i−1, k). Then the extended Zeilberger’s algorithm reduces to the original Zeilberger’s algorithm. More generally, suppose that n = (n_{1}, …, n_{r}), F (n, k) is a multi-variable hypergeometric term and γ_{i} ∈ ℤ^{r}. The specialization f_{i}(k) = F (n + γ_{i}, k) reduces to Paule’s variation.

As will be seen, in some applications it is necessary to require that the coefficients a_{1}, …, a_{m} be independent of some parameters, say, the parameter a. More precisely, let f_{1}(k, a, b, …, c), …, f_{m}(k, a, b, …, c) be m similar multi-variable hypergeometric terms, that is,

\frac{f_{i}(k + 1, a, b, …, c)}{f_{i}(k, a, b, …, c)} and \frac{f_{i}(k, a, b, …, c)}{f_{1}(k, a, b, …, c)}  (2.6)

are rational functions of k, a, b, …, c. We aim to find a_{1}, a_{2}, …, a_{m} not only independent of k but also independent of the parameter a such that (2.2) holds.

Since the solutions (a_{1}, …, a_{m}, g(k)) of (2.2) form a linear vector space, we may use the following form as the output

a_{1} = v_{1}, …, a_{r} = v_{r},
a_{r+1} = h_{r+1}(v_{1}, …, v_{r}), …, a_{m} = h_{m}(v_{1}, …, v_{r}),  (2.7)
g(k) = h(v_{1}, …, v_{r})f_{1}(k),

where v_{1}, …, v_{r} are free variables and h_{r+1}, …, h_{m}, h are linear combinations of v_{1}, …, v_{r}. For this purpose, we should first ignore the independence of a and apply the extended Zeilberger’s algorithm to find the solution (2.7). By (2.6), the functions h_{r+1}, …, h_{m} are rational functions of the parameters a, b, …, c and thus can be written as

h_{i} = p_{i}(a, b, …, v_{1}, …, v_{r})/q_{i}(a, b, …, c),

where p_{i}, q_{i} are relatively prime polynomials. Now consider the additional requirement that a_{1}, a_{2}, …, a_{m} are independent of the parameters a. Therefore, all the coefficients of

p_{i}(a, b, …, c, v_{1}, …, v_{r}) − a_{i}q_{i}(a, b, …, c)

in variable a must be zero. This gives a system of linear equations on a_{1}, …, a_{m} and v_{1}, …, v_{r}. Upon solving these equations, we eventually find a_{1}, a_{2}, …, a_{m} which are independent of k and the parameter a. The above version of the extended Zeilberger’s algorithm will still be called the extended Zeilberger’s algorithm.

Let us take the Hermite polynomials as the first example to show how to use the above algorithm to derive linear relations on sums of similar hypergeometric terms with parameters.

Example 2.1 The Hermite polynomials H_{n}(x) are given by

H_{n}(x) = (2x)^{n} _{2}F_{0} ( −\frac{n}{2}, −\frac{n−1}{2} | − \frac{1}{x^{2}} ) ,  (2.8)

see [2, Section 6.1]. We aim to find a three term recurrence

xH_{n}(x) = α_{n}H_{n+1}(x) + β_{n}H_{n}(x) + γ_{n}H_{n−1}(x)

with coefficients α_{n}, β_{n}, γ_{n} being independent of x. Let

H_{n,k}(x) = (2x)^{n} \frac{( − \frac{n}{2})_{k}(\frac{−n+1}{2})_{k}}{k!} (−\frac{1}{x^{2}} )^{k}

be the summand in (2.8). We first ignore the x-freeness requirement and apply the extended Zeilberger’s algorithm to the four similar hypergeometric terms with parameters n and x

f_{1}(k) = xH_{n,k}(x), f_{2}(k) = H_{n+1,k}(x), f_{3}(k) = H_{n,k}(x), f_{4}(k) = H_{n−1,k}(x).

We find that

a_{1} = v_{1}, a_{2} = v_{2}, a_{3} = −x(v_{1} + 2v_{2}), a_{4} = 2nv_{2},  (2.9)

and

g(k) = \frac{−4kv_{2}}{n + 1 − 2k} xH_{n,k}(x).  (2.10)

Now it is time to impose the x-freeness condition to give an additional equation

v_{1} + 2v_{2} = 0.

Hence we obtain

a_{1} = v_{1}, a_{2} = −\frac{v_{1}}{2} , a_{3} = 0, a_{4} = −nv_{1}, g(k) = \frac{2kv_{1}}{n + 1 − 2k} xH_{n,k}(x).

It follows that

v_{1}xH_{n,k}(x) − \frac{v_{1}}{2} H_{n+1,k}(x) − nv_{1}H_{n−1,k}(x) = g(k + 1) − g(k).

Summing over k, we deduce that

xH_{n}(x) = \frac{1}{2}H_{n+1}(x) + nH_{n−1}(x).

3. Orthogonal Polynomials

Using the extended Zeilberger’s algorithm, we can determine whether a hypergeometric series satisfies a three term relation and the structure relations for a sequence of orthogonal polynomials. In other words, one can verify the orthogonality of a terminating hypergeometric series by using the extended Zeilberger’s algorithm.

The method to derive the relation in Example 2.1 is in fact valid in the general case. Given a hypergeometric series P_{n}(x), we can compute the coefficients for the following recurrence relation

xP_{n}(x) = α_{n}P_{n+1}(x) + β_{n}P_{n}(x) + γ_{n}P_{n−1}(x).

Let P_{n}(x) = ∑_{k} P_{n,k}(x), where P_{n,k}(x) is a hypergeometric term of k with parameters n and x. Set

f_{1}(k) = xP_{n,k}(x), f_{2}(k) = P_{n+1,k}(x), f_{3}(k) = P_{n,k}(x), f_{4}(k) = P_{n−1,k}(x).

Clearly, f_{1}, f_{2}, f_{3} and f_{4} are similar hypergeometric terms. So we can use the extended Zeilberger’s algorithm to find a_{1}, a_{2}, a_{3}, a_{4} which are independent of k and x such that

a_{1}xP_{n,k}(x) + a_{2}P_{n+1,k}(x) + a_{3}P_{n,k}(x) + a_{4}P_{n−1,k}(x) = g(k + 1) − g(k).

Then summing over k leads to

α_{n} = −a_{2}/a_{1}, β_{n} = −a_{3}/a_{1}, γ_{n} = −a_{4}/a_{1}.

By this method, we can recover the three term recurrences for the Laguerre polynomials, the Jacobi polynomials, the Charlier polynomials, the Meixner polynomials, the Kravchuk polynomials and the Hahn polynomials, as listed in the following table. Notice that we have adopted the notation in [9].

monic OPs  coefficients (α_{n} = 1)

Laguerre ; L_{n}^{(a)}(x) β_{n} = a + 2n + 1, γ_{n} = n(a + n)

\begin{matrix}Jacobi \\ P_{n}^{(a, b)}(x) \end{matrix}  \begin{cases}β_{n} = \frac{−(a−b)(a+b)}{(2n+2+a+b)(2n+a+b)} \\ γ_{n} = \frac{4(n+b)(a+n)(n+a+b)n}{(2n+a+b+1)(2n+a+b−1)(2n+a+b)^{2}} \end{cases}

Charlier ; C_{n}(x; a) β_{n} = a + n, γ_{n} = an

\begin{matrix}Meixner \\ M_{n}(x; b, c) \end{matrix}  β_{n} = \frac{cb + nc + n}{1 − c}, γ_{n} = \frac{nc(b + n − 1)}{(c − 1)^{2}}

Krawtchouk ; K_{n}(x; p, N) \begin{cases}β_{n} = Np − 2np + n, \\ γ_{n} = pn(1 − p)(N − n + 1) \end{cases}

\begin{matrix}Hahn \\ Q_{n}(x; a, b, N) \end{matrix} \begin{cases}β_{n} = \frac{(b+a+2n^{2}+2n+2nb+2na+a^{2}+ab)N−n(a−b)(n+a+b+1)}{(2n+a+b)(2n+2+a+b)} \\ γ_{n} = \frac{n(N−n+1)(n+b)(a+n)(n+a+b)(a+b+N+1+n)}{(2n+a+b+1)(2n+a+b−1)(2n+a+b)^{2}} \end{cases}

Example 3.1 The Wilson polynomials W_{n}(x) are given by

\frac{W_{n}(x^{2})}{(a + b)_{n}(a + c)_{n}(a + d)_{n}} = _{4}F_{3}( \begin{matrix}−n, n + a + b + c + d − 1, a + xi, a − xi \\ a + b, a + c, a + d \end{matrix} | 1),

where i = \sqrt{−1}, see [15]. Let W_{n,k}(x^{2}) be the summand of the right hand side multiplied by the factor (a + b)_{n}(a + c)_{n}(a + d)_{n}. Applying the the extended Zeilberger’s algorithm to the similar terms

f_{1}(k) = x^{2}W_{n,k}(x^{2}), f_{2}(k) = W_{n+1,k}(x^{2}), f_{3}(k) = W_{n,k}(x^{2}), f_{4}(k) = W_{n−1,k}(x^{2}),

we obtain the following relation, see also [9, p. 24]

xW_{n}(x) = α_{n}W_{n+1}(x) + β_{n}W_{n}(x) + γ_{n}W_{n−1}(x),

where

α_{n} = −\frac{a + b + c + d + n − 1}{(a + b + c + d + 2n)(a + b + c + d + 2n − 1)},

β_{n} = \frac{4n^{2} − 4(1 − a − b − c − d)n + (a + b + c + d)^{2} − 2(a^{2} + b^{2} + c^{2} + d^{2})}{8}

+ \frac{(a + b + c + d − 2)(a + b − c − d)(a + c − b − d)(a + d − b − c)}{8(a + b + c + d + 2n)(a + b + c + d + 2n − 2)},

and

γ_{n} = −(a + b + n − 1)(a + c + n − 1)(a + d + n − 1)

× \frac{(b + c + n − 1)(b + d + n − 1)(c + d + n − 1)n}{(a + b + c + d + 2n − 1)(a + b + c + d + 2n − 2)}.

Example 3.2 The Racah polynomials R_{n}(x) are given by

R_{n}(x(x + c + d + 1)) = _{4}F_{3}( \begin{matrix}−n, n + a + b + 1, −x, x + c + d + 1 \\ a + 1, b + d + 1, c + 1 \end{matrix} | 1),

see [4]. The extended Zeilberger’s algorithm gives the recurrence relation of the Racah polynomials [9, p. 27]

xR_{n}(x) = α_{n}R_{n+1}(x) + β_{n}R_{n}(x) + γ_{n}R_{n−1}(x),

where

α_{n} = \frac{(a + n + 1)(c + n + 1)(a + b + n + 1)(d + b + n + 1)}{(a + b + 2n + 1)(a + b + 2n + 2)},

β_{n} = \frac{−4n^{2} − 4(a + b + 1)n + (a − 2d − b − 2 − 2c)(a − b)}{8}

− \frac{(c + 1)(b + d + 1)}{2} − \frac{(a − b)(a + b)(a − 2d − b)(a − 2c + b)}{8(a + b + 2n)(a + b + 2n + 2)},

and

γ_{n} = \frac{(b + n)(a − d + n)(a + b − c + n)n}{(a + b + 2n)(a + b + 2n + 1)}.

Example 3.3 Askey and Ismail [3] provided two hypergeometric representations for the Pollaczek polynomials:

P_{n}(x) = η^{n} _{2}F_{1} ( \begin{matrix}−n, b(x − η)/ξ, \\ b/a \end{matrix} | − \frac{ξ}{aη} )

= ζ^{n} _{2}F_{1} ( \begin{matrix}−n, b(ζ − x)/ξ, \\ b/a \end{matrix} | \frac{ξ}{aζ} ) ,

where

ξ = \sqrt{(1 + a)^{2}x^{2} − 4a}, η = ((1 + a)x − ξ)/2a, ζ = ((1 + a)x + ξ)/2a.

Using the extended Zeilberger’s algorithm, we derive the following three term recurrence from either representation [3]:

xP_{n}(x) = \frac{an + b}{(1 + a)n + b}P_{n+1}(x) + \frac{n}{(1 + a)n + b}P_{n−1}(x).

We continue to show that the extended Zeilberger’s algorithm can be employed to express the derivatives of orthogonal polynomials in terms the original polynomials, and vice versa. Let P_{n,k}(x) be the summand of the hypergeometric representation of P_{n}(x) and P′_{n,k}(x) be the derivative of P_{n,k}(x). It is easily seen that P′_{n,k}(x) is similar to P_{n,k}(x). This enables us to derive the three term recurrence for P′_{n}(x) and the structure relations for P_{n}(x) as given below

σ(x)P′_{n}(x) = a_{n}P_{n+1}(x) + b_{n}P_{n}(x) + c_{n}P_{n−1}(x),  (3.1)

and

P_{n}(x) = ā_{n}P′_{n+1}(x) + b̄_{n}P′_{n}(x) + c̄_{n}P′_{n−1}(x),  (3.2)

where σ(x) is a polynomials in x of degree less than or equal to 2 and a_{n}, b_{n}, c_{n}, ā_{n}, b̄_{n}, c̄_{n} are constants not depending on x. To derive (3.1), we set

f_{1}(k) = σ(x)P′_{n,k}(x), f_{2}(k) = P_{n+1,k}(x), f_{3}(k) = P_{n,k}(x), f_{4}(k) = P_{n−1,k}(x).

To establish (3.2), we set

f_{1}(k) = P_{n,k}(x), f_{2}(k) = P′_{n+1,k}(x), f_{3}(k) = P′_{n,k}(x), f_{4}(k) = P′_{n−1,k}(x).

Example 3.4 The monic Jacobi polynomials are given by

P_{n}(x) = \frac{(a + 1)_{n}2^{n}}{(n + a + b + 1)_{n}} _{2}F_{1} ( \begin{matrix}−n, n + a + b + 1 \\ a + 1 \end{matrix} | \frac{1 − x}{2}) .  (3.3)

Let P_{n,k}(x) denote the summand. Its derivative with respect to x equals

P′_{n,k}(x) = −\frac{(a + 1)_{n}2^{n}}{(n + a + b + 1)_{n}} \frac{(−n)_{k}(n + a + b + 1)_{k}}{2(a + 1)_{k}(k − 1)!} (\frac{1 − x}{2})^{k−1} .

Consider the four similar terms

f_{1}(k) = xP′_{n,k}(x), f_{2}(k) = P′_{n+1,k}(x), f_{3}(k) = P′_{n,k}(x), f_{4}(k) = P′_{n−1,k}(x).

By the extended Zeilberger’s algorithm with parameters n and x, we find that

xP′_{n}(x) = \frac{n}{n + 1}P′_{n+1}(x) − \frac{(a + 2 + b)(a − b)}{(2n + 2 + a + b)(2n + a + b)}P′_{n}(x)

+ \frac{4n(b + n)(a + n)(n + a + b + 1)}{(2n + a + b + 1)(2n + a + b − 1)(2n + a + b)^{2}} P′_{n−1}(x),

(1 − x^{2})P′_{n}(x) = −nP_{n+1}(x) + \frac{2n(a − b)(n + a + b + 1)}{(2n + 2 + a + b)(2n + a + b)}P_{n}(x)

+ \frac{4(n + b)(a + n)(n + a + b + 1)(n + a + b)n}{(2n + a + b + 1)(2n + a + b − 1)(2n + a + b)^{2}} P_{n−1}(x).

and

P_{n}(x) = \frac{1}{n + 1}P′_{n+1}(x) + \frac{2(a − b)}{(2n + 2 + a + b)(2n + a + b)}P′_{n}(x)

− \frac{4(n + b)(a + n)n}{(2n + a + b + 1)(2n + a + b − 1)(2n + a + b)^{2}} P′_{n−1}(x).

The following example is concerned with expressing the shifts of orthogonal polynomials with parameters in terms of the original polynomials and their derivatives.

Example 3.5 Let

P_{n}^{(a, b)}(x) = \frac{(a + 1)_{n}2^{n}}{(n + a + b + 1)_{n}} _{2}F_{1} ( \begin{matrix}−n, n + a + b + 1 \\ a + 1 \end{matrix} | \frac{1 − x}{2})

be the Jacobi polynomials, see [2, 9]. By applying the extended Zeilberger’s algorithm to f_{1}(k) = P_{n,k}^{(a+1, b)}(x) (f_{1}(k) = P_{n,k}^{(a, b+1)}(x), respectively) and

f_{2}(k) = P_{n+1,k}^{(a, b)} ′(x), f_{3}(k) = P_{n,k}^{(a, b)} ′(x), f_{4}(k) = P_{n−1,k}^{(a, b)} ′(x),

we are led to the known relations due to Koepf and Schmersau [10]

P_{n}^{(a+1, b)}(x) = \frac{1}{n + 1}P_{n+1}^{(a, b)} ′(x) + \frac{2(a + 1 + n)}{(2n + 2 + a + b)(2n + a + b + 1)}P_{n}^{(a, b)} ′(x)

and

P_{n}^{(a, b+1)}(x) = \frac{1}{n + 1}P_{n+1}^{(a, b)} ′(x) − \frac{2(b + 1 + n)}{(2n + 2 + a + b)(2n + a + b + 1)}P_{n}^{(a, b)} ′(x).

Moreover, we can deduce the following relations which seem to be new:

P_{n}^{(a+1, b−1)}(x) = \frac{1}{n + 1}P_{n+1}^{(a, b)} ′(x) + \frac{4(a + 1 + n)}{(2n + 2 + a + b)(2n + a + b)}P_{n}^{(a, b)} ′(x)

+ \frac{4(a + 1 + n)(a + n)n}{(2n + a + b − 1)(2n + a + b + 1)(2n + a + b)^{2}} P_{n−1}^{(a, b)} ′(x),

and

P_{n}^{(a−1, b+1)}(x) = \frac{1}{n + 1}P_{n+1}^{(a, b)} ′(x) − \frac{4(b + 1 + n)}{(2n + 2 + a + b)(2n + a + b)}P_{n}^{(a, b)} ′(x)

+ \frac{4(b + 1 + n)(b + n)n}{(2n + a + b − 1)(2n + a + b + 1)(2n + a + b)^{2}} P_{n−1}^{(a, b)} ′(x).

The extended Zeilberger’s algorithm can also be employed to compute the connection coefficients of two sequences of orthogonal polynomials. Ronveaux [13] developed an approach to computing recurrence relations for the connection coefficients. The extended Zeilberger’s algorithm serves this purpose without resorting to the properties of the orthogonal polynomials. As an example, let us consider the connection coefficients of two classes of Meixner polynomials with different parameters.

Example 3.6 Let M_{n}^{(γ, μ)}(x) be the monic Meixner polynomials defined by

M_{n}^{(γ, μ)}(x) = (γ)_{n} (\frac{μ}{μ − 1})^{n} _{2}F_{1} ( \begin{matrix}−n, −x \\ γ \end{matrix} | 1 − \frac{1}{μ}) ,

see [9, p. 45]. We wish to find a recurrence relation for the connection coefficients C_{m}(n) defined by

M_{n}^{(γ, μ)}(x) = ∑_{m=0}^{n} C_{m}(n)M_{m}^{(δ, ν)}(x).  (3.4)

To this end, we first find a difference operator which eliminates M_{n}^{(γ, μ)}(x). This goal can be achieved by applying the extended Zeilberger’s algorithm to the similar terms

f_{1}(k) = M_{n,k}^{(γ, μ)}(x), f_{2}(k) = M_{n,k}^{(γ, μ)}(x + 1), and f_{3}(k) = M_{n,k}^{(γ, μ)}(x − 1),

where

M_{n,k}^{(γ, μ)}(x) = (γ)_{n} (\frac{μ}{μ − 1})^{n} \frac{(−n)_{k}(−x)_{k}}{(γ)_{k}k!} (1 − \frac{1}{μ})^{k} .

From the telescoping relation generated by the extended Zeilberger’s algorithm, we deduce that

(xμ+μγ +x−n+nμ)M_{n}^{(γ, μ)}(x)−μ(γ +x)M_{n}^{(γ, μ)}(x+1)−xM_{n}^{(γ, μ)}(x−1) = 0.

Let

S_{m}(x) = (xμ+μγ+x−n+nμ)M_{m}^{(δ, ν)}(x)−μ(γ+x)M_{m}^{(δ, ν)}(x+1)−xM_{m}^{(δ, ν)}(x−1),

which can be used to establish a linear relation on the connection coefficients C_{m}(n). Indeed, it follows from (3.4) that

∑_{m=0}^{n} C_{m}(n)S_{m}(x) = 0.  (3.5)

Suppose that we can express S_{m}(x) in terms of a suitable basis {P_{m}(x)}:

S_{m}(x) = a_{m}P_{m+1}(x) + b_{m}P_{m}(x) + c_{m}P_{m−1}(x),  (3.6)

where a_{m}, b_{m} and c_{m} are independent of x. Substituting (3.6) into (3.5), by the linear independence of P_{m}(x) for m = 0, 1, 2, …, that is, the coefficients of P_{i}(x) are all zeros, we find

a_{m−1}C_{m−1}(n) + b_{m}C_{m}(n) + c_{m+1}C_{m+1}(n) = 0.  (3.7)

Thus the question has become how to find the polynomials P_{m}(x) in order to determine the coefficients a_{m}, b_{m} and c_{m}. In view of the relation (3.6), we consider a hypergeometric term P_{m}(x) that is similar to S_{m}(x) so that we can solve the equation

S_{m}(x) − a_{m}P_{m+1}(x) − b_{m}P_{m}(x) − c_{m}P_{m−1}(x) = 0

by using the extended Zeilberger’s algorithm. In fact, we may choose

P_{m}(x) = Δ(M_{m}^{(δ, ν)}(x)) = M_{m}^{(δ, ν)}(x + 1) − M_{m}^{(δ, ν)}(x).

It is easily checked that P_{m}(x) satisfies (3.6) and the corresponding coefficients are given by

a_{m} = \frac{(μ − 1)(n − m)}{m + 1}, c_{m} = \frac{(ν − μ)(δ + m − 1)mν}{(1 − ν)^{2}} ,

b_{m} = \frac{−νμm − mμ + 2mν + νμγ − νn + νδ − ν + μ − νμδ − μγ + νnμ}{1 − ν}.

Hence we have derived a recurrence relation (3.7) for the connection coefficients C_{m}(n).

4. q-Orthogonal Polynomials

The extended Zeilberger’s algorithm can be readily adapted to basic hypergeometric terms t_{k} with parameters a, b, …, c, that is, the ratio of two consecutive terms is a rational function of q^{k} and the parameters. The q-analogue of the extended Zeilberger’s algorithm will be called the extended q-Zeilberger’s algorithm. Let f_{1}(k), f_{2}(k), …, f_{m}(k) be similar q-hypergeometric terms, namely,

f_{i}(k)/f_{j}(k) and f_{i}(k + 1)/f_{i}(k) (1 ≤ i, j ≤ m)

are rational functions of q^{k} and the parameters. The objective of the extended q-Zeilberger’s algorithm is to find a q-hypergeometric term g(k) and coefficients a_{1}, a_{2}, …, a_{m} which are independent of k such that

a_{1}f_{1}(k) + a_{2}f_{2}(k) + ⋯ + a_{m}f_{m}(k) = g(k + 1) − g(k).  (4.1)

The detailed description of the extended q-Zeilberger’s algorithm is similar to that of the ordinary case, hence is omitted. We will only give examples to demonstrate how to use this method to compute the three term recurrences and structure relations for q-orthogonal polynomials.

Example 5.1 The discrete q-Hermite I polynomials are given by [1]

H_{n}(x) = q^{\binom{n}{2}} _{2}ϕ_{1} [ \begin{matrix}q^{−n}, x^{−1} \\ 0 \end{matrix} | q; −qx] .

Let dH_{n}(x) = \frac{H(xq)−H(x)}{(q−1)x} be the q-difference of H_{n}(x). We derive that

xdH_{n}(x) = \frac{1 − q^{n}}{1 − q^{n+1}} dH_{n+1}(x) + q^{n−2}(1 − q^{n})dH_{n−1}(x)

and

dH_{n}(x) = \frac{1 − q^{n}}{1 − q} H_{n−1}(x).

Example 5.2 The Askey-Wilson polynomials p_{n}(x; a, b, c, d|q) are defined by

\frac{a^{n}p_{n}(x; a, b, c, d|q)}{(ab, ac, ad; q)_{n}} = _{4}ϕ_{3} [ \begin{matrix}q^{−n}, abcdq^{n−1}, ae^{iθ}, ae^{−iθ} \\ ab, ac, ad \end{matrix} | q; q] , x = cos θ,

see [7, (7.5.2)]. Let t_{n,k}(x) be the summand of the right hand side multiplied by (ab, ac, ad; q)_{n}/a^{n}. Applying the extended q-Zeilberger’s algorithm to

f_{1}(k) = xt_{n,k}(x), f_{2}(k) = t_{n+1,k}(x), f_{3}(k) = t_{n,k}(x), f_{4}(k) = t_{n−1,k}(x),

we find that

xp_{n}(x) = α_{n}p_{n+1}(x) + β_{n}p_{n}(x) + γ_{n}p_{n−1}(x),

where

α_{n} = \frac{1 − abcdq^{n−1}}{2(1 − abcdq^{2n})(1 − abcdq^{2n−1})},

β_{n} = \frac{q^{n−1}(abcdq^{2n−1} + 1)((a + b + c + d)q + bcd + acd + abd + abc)}{2(1 − abcdq^{2n})(1 − abcdq^{2n−2})}

− \frac{q^{2n−2}(1 + q)((bcd + acd + abd + abc)q + abcd(a + b + c + d))}{2(1 − abcdq^{2n})(1 − abcdq^{2n−2})},

and

γ_{n} = (1 − q^{n})(1 − abq^{n−1})(1 − acq^{n−1})(1 − adq^{n−1})

× \frac{(1 − bcq^{n−1})(1 − bdq^{n−1})(1 − cdq^{n−1})}{2(1 − abcdq^{2n−1})(1 − abcdq^{2n−2})}.

Example 5.3 The q-Racah polynomials R_{n}(x; a, b, c, d|q) are given by

R_{n}(q^{−x} + cdq^{x+1}; a, b, c, d|q) = _{4}ϕ_{3} [ \begin{matrix}q^{−n}, abq^{n+1}, q^{−x}, cdq^{x+1} \\ aq, bdq, cq \end{matrix} | q; q] ,

see [9, p. 122]. The extended q-Zeilberger’s algorithm gives the following recurrence relation first derived by Askey and Wilson [4] using a transformation formula on a _{8}ϕ_{7} series:

xR_{n}(x) = α_{n}R_{n+1}(x) + β_{n}R_{n}(x) + γ_{n}R_{n−1}(x),

where

α_{n} = \frac{(1 − aq^{n+1})(1 − abq^{n+1})(1 − bdq^{n+1})(1 − cq^{n+1})}{(1 − abq^{2n+1})(1 − abq^{2n+2})},

β_{n} = \frac{q^{n+1}(abq^{2n+1} + 1)(c + bcd + dc + a + bd + ab + ca + abd)}{(1 − abq^{2n})(1 − abq^{2n+2})}

− \frac{q^{2n+1}(1 + q)(ab^{2}d + abcd + ca + bcd + abd + ab + abc + a^{2}b)}{(1 − abq^{2n})(1 − abq^{2n+2})},

and

γ_{n} = \frac{(1 − q^{n})(1 − bq^{n})(c − abq^{n})(d − aq^{n})q}{(1 − abq^{2n})(1 − abq^{2n+1})} .

10826038.

Acknowledgments. This work was supported by the 973 Project on Mathematical Mechanization, the National Natural Science Foundation, the PCSIRT project of the Ministry of Education, and the Ministry of Science and Technology of China.

Y.-P. Mu was supported by National Natural Science Foundation of China, Project

References

[1] W.A. Al-Salam and L. Carlitz, Some orthogonal q-polynomials, Math. Nachr. 30 (1965) 47–61.

[2] G.E. Andrews, R. Askey, and R. Roy, Special Functions, Cambridge University Press, Cambridge, 1999.

[3] R. Askey and M. Ismail, Recurrence Relations, Continued Fractions and Orthogonal Polynomials, Amer. Math. Society 49, 1984.

[4] R. Askey and J. Wilson, A set of orthogonal polynomials that generalize the Racah coefficients or 6-j symbols, SIAM J. Math. Analysis 10 (1979) 1008–1016.

[5] R. Askey and J. Wilson, Some basic hypergeometric orthogonal polynomials that generalize Jacobi polynomials, Memoirs of the AMS 319, Providence, Rhode Island, 1985.

[6] W.Y.C. Chen and L.H. Sun, Extended Zeilberger’s algorithm for identities on Bernoulli and Euler polynomials, J. Number Theory 129 (2009) 2111–2132.

[7] G. Gasper and M. Rahman, Basic Hypergeometric Series, 2nd Ed., Cambridge University Press, Cambridge, MA, 2004.

[8] R.W. Gosper, Jr., Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75(1) (1978) 40–42.

[9] R. Koekoek and R.F. Swarttouwu, The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue, preprint, 1998.

[10] W. Koepf and D. Schmersau, Representations of orthogonal polynomials, J. Comput. Appl. Math. 90 (1998) 57–94.

[11] A.F. Nikiforov, S.K. Suslov, and V.B. Uvarov, Classical Orthogonal Polynomials of a Discrete Variable, Springer-Verlag, New York, 1991.

[12] P. Paule, Contiguous relations and creative telescoping, preprint, 2005.

[13] A. Ronveaux, Orthogonal polynomials: connection and linearization coefficients, In: Proceedings of the International Workshop on Orthogonal Polynomials in Mathematical Physics, M. Alfaro et al. Eds., 1996, pp. 131–142.

[14] H.S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math. 108 (1992) 575–633.

[15] J.A. Wilson, Some hypergeometric orthogonal polynomials, SIAM J. Math. Anal. 11 (1980) 690–701.

[16] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991) 195–204.