q-Hypergeometric Solutions of q-Difference Equations

Sergei A. Abramov^{∗}

Computer Center of the Russian Academy of Science, Vavilova 40, Moscow 117967, Russia.

            abramov@ccas.ru

Peter Paule^{†}

Institut für Mathematik, RISC, Johannes Kepler University, A–4040 Linz, Austria.

                                        peter.paule@risc.uni-linz.ac.at

Marko Petkovšek^{‡}

Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia.

                       marko.petkovsek@mat.uni-lj.si

Abstract

We present algorithm qHyper for finding all solutions y(x) of a linear homogeneous q-difference equation such that y(qx) = r(x)y(x) where r(x) is a rational function of x. Applications include construction of basic hypergeometric series solutions, and definite qhypergeometric summation in closed form.

1 Introduction

As a motivating example, consider the following second-order q-difference equation

y_{n+2} − (1 + q) x y_{n+1} + x^{2}y_{n} = 0  (1)

where x = q^{n}. This is a homogeneous linear equation with coefficients which are polynomials in x. It is easy to check that y_{n}^{(1)} = q^{\binom{n}{2}} and y_{n}^{(2)} = q^{\binom{n}{2}−n} both solve (1). Note that their consecutive-term ratios, y_{n+1}^{(1)}/y_{n}^{(1)} = q^{n} = x and y_{n+1}^{(2)}/y_{n}^{(2)} = q^{n−1} = x/q, are rational functions of x. We call such solutions q-hypergeometric. This paper describes an algorithm for finding all q-hypergeometric solutions of linear q-difference equations with polynomial coefficients, and presents some of its applications.

∗The research described in this publication was made possible in part by Grant J12100 from the International Science Foundation and Russian Government.

†Supported in part by grant P7720 of the Austrian FWF.

‡Supported in part by grant J2-6193-0101-94 of the Slovenian Ministry of Science and Technology.

The algebraic framework that we use is the following. Let IF be a computable field of characteristic zero, q ∈ IF a nonzero element which is not a root of unity, and x transcendental over IF. Denote by ε the unique automorphism of IF(x) which fixes IF and satisfies εx = qx. Then IF(x) together with the q-shift operator ε is a difference field [7].

Let ρ be a nonnegative integer and p_{i} ∈ IF(x), for i = 0, 1, …, ρ, rational functions such that p_{ρ}, p_{0} ≠ 0. Then

L = ∑_{i=0}^{ρ} p_{i}ε^{i}  (2)

is a linear q-difference operator of order ρ with rational coefficients. Two such operators may be multiplied by using the commutation relation

ε x = q x ε

and extending it by distributivity. Division of operators can be performed using the rule

f(x) ε^{k} = (\frac{f(x)}{g(q^{k−m}x)} ε^{k−m}) g(x) ε^{m}

for right-dividing a monomial f(x) ε^{k} by another monomial g(x) ε^{m} (m ≤ k). As with ordinary polynomials, for any two operators L_{1}, L_{2} where L_{2} ≠ 0, there are operators Q and R such that L_{1} = QL_{2} + R and ord R < ord L_{2}. Thus one can compute greatest common right divisors (and also least common left multiples, see [6]) of q-difference operators by the right-Euclidean algorithm.

We are interested in nonzero solutions y of the homogeneous equation

Ly = 0  (3)

where L is as in (2). Note that by clearing denominators in (3) we can restrict attention to operators L with polynomial coefficients p_{i} ∈ IF[x]. In general solutions of (3) cannot be found within the coefficient field IF(x). Rather, we look for them in some difference extension ring M of IF(x). Thus the problem of finding q-hypergeometric solutions of a q-difference equation contains two “parameters”: the ground field IF, and the difference extension ring M.

We call an element a ∈ M polynomial^{1} if a ∈ IF[x], rational^{1} if a ∈ IF(x), and a qhypergeometric term^{1} if a ≠ 0 and ε a = r a for some r ∈ IF(x). Note that q-hypergeometric terms form a multiplicative group.

Let y ∈ M be q-hypergeometric with ε y = r y. Then it is easy to see that y is a solution of (3) if and only if L_{1} = ε − rI (where I is the identity operator) is a right divisor of L. This splits the search for q-hypergeometric solutions of (3) into two steps: 1. find first-order right divisors L_{1} of L (the nontrivial part), 2. solve the corresponding first-order equations L_{1}y = 0 in M. Note that step 1 does not depend on the choice of M.

1All these concepts are relative to the field IF.

The overview of the paper is as follows. An algorithm for finding first-order right divisors of linear q-difference operators with rational coefficients (called qHyper) is presented in Section 4. It is a q-analogue of algorithm Hyper for finding hypergeometric solutions of difference equations described in [13]. In preparation, we show how to find polynomial solutions of (3) in Section 2, and give a suitable normal form for rational functions in Section 3. In Section 5, we discuss solutions of the first-order equation ε y = r y in two specific instances of the extension ring M: the ring of germs of sequences over IF, and the ring of formal power series over IF. In Section 6 we show how to solve nonhomogeneous equations Ly = f with q-hypergeometric right-hand side f. In Section 7, we describe applications of qHyper to the problem of closed-form evaluation of definite q-hypergeometric sums.

In our examples, we use the following q-calculus notation. Let (z; q)_{n} = (1 − z)(1 − zq) ⋯ (1 − zq^{n−1}) for n ≥ 1 and (z; q)_{0} = 1 be the q-shifted factorials, and (z; q)_{∞} = ∏_{k=0}^{∞}(1 − zq^{k}) the corresponding infinite product. For integer m let [m] = (1 − q^{m})/(1 − q). Note that −q^{m}[−m] = [m] = 1 + q + … + q^{m−1} for m ≥ 1. Thus [m] turns into m as q → 1. The same applies to [m]_{d} defined as [m] with q replaced by q^{d}, d a positive integer. Let [m]! = [1][2] · . . . · [m] for m ≥ 1 and [0]! = 1. For integer n and nonnegative integer k, the Gaussian polynomial or the q-binomial coefficient is defined as \left[{n \atop k}\right] = [n][n − 1] · . . . · [n − k + 1]/[k]!. These definitions are introduced to make the analogy with the case q → 1 more transparent. For instance, when q → 1 the q-factorial [m]! turns into the ordinary factorial m!, and the q-binomial coefficient \left[{n \atop k}\right] turns into the ordinary binomial coefficient \binom{n}{k}. Again [m]_{d}! and

\left[{n \atop k}\right]_{d} denote the corresponding versions with q replaced by q^{d}. The q-shifted factorials relate to the Gaussian polynomials via

(z; q)_{n} = ∑_{k=0}^{n}(−1)^{k}\left[{n \atop k}\right]q^{\binom{k}{2}}z^{k},  (4)

a q-analogue of the binomial theorem.

We use IN to denote the set of nonnegative integers.

Sometimes we need to find the largest n ∈ IN (if any) such that q^{n} is a root of a given polynomial with coefficients in IF. Therefore we assume that IF is a q-suitable field, meaning that there exists an algorithm which given p ∈ IF[x] finds all n ∈ IN such that p(q^{n}) = 0. Since by assumption q is neither a root of unity nor zero, the set of all such n is finite.

Example 1 Let IK be any computable field. Then IF = IK(q) where q is transcendental over IK is q-suitable, as shown by the following algorithm: Let p(x) = ∑_{i=0}^{d} c_{i}x^{i} where c_{i} = ∑_{j=0}^{d_{i}} a_{i,j}q^{j} ∈ IK[q]. Compute s = min{i; c_{i} ≠ 0} and t = min{j; a_{s,j} ≠ 0}. Then p(q^{n}) = 0 only if n ≤ t, and the set of all such n can be found by consecutively testing the values n = t, t − 1, …, 0. □

It is easy to see that if IF is a q-suitable field and α is either transcendental or algebraic over IF, then the extension IF(α) is also q-suitable.

2 Polynomial solutions

First we show how to find solutions y ∈ IF[x] of Ly = 0 where L is as in (2) but with p_{i} ∈ IF[x]. Let p_{i} = ∑_{k=0}^{d} c_{ik}x^{k} where not all c_{id} are zero. Assume that y = ∑_{j=0}^{n} a_{j}x^{j} where a_{n} ≠ 0. Substituting these expressions into Ly = 0 and replacing k by l = j + k yields

∑_{i,l,j} c_{i,l−j}a_{j}q^{ij}x^{l} = 0

which implies that

∑_{j=max{l−d,0}}^{min{l,n}} ∑_{i=0}^{ρ} c_{i,l−j}a_{j}q^{ij} = 0, for 0 ≤ l ≤ n + d.  (5)

In particular, for l = n + d,

∑_{i=0}^{ρ} c_{id}q^{in} = 0,  (6)

and for l = 0,

a_{0} ∑_{i=0}^{ρ} c_{i0} = 0.  (7)

From (6) it follows that q^{n} is a root of the polynomial p(x) = ∑_{i=0}^{ρ} c_{id}x^{i}. Let n_{0} be the largest n ∈ IN such that p(q^{n}) = 0. Since IF is q-suitable there is an algorithm to compute n_{0}. All polynomial solutions y of Ly = 0 can now be found by the method of undetermined coefficients. Ultimately, the problem is reduced to a system of linear algebraic equations over IF with n_{0} + 1 unknowns. – A more efficient method leading to a system with at most ρ unknowns is described in [2].

3 A normal form for rational functions

Theorem 1 Let r ∈ IF(x) \ {0}. Then there are z ∈ IF and monic polynomials a, b, c ∈ IF[x] such that

r(x) = z \frac{a(x)}{b(x)} \frac{c(qx)}{c(x)},  (8)
gcd(a(x), b(q^{n}x)) = 1 for all n ∈ IN,  (9)
gcd(a(x), c(x)) = 1,  (10)
gcd(b(x), c(qx)) = 1,  (11)
c(0) ≠ 0.  (12)

Proof: Write r(x) = \frac{f(x)}{g(x)} where f, g are relatively prime polynomials. We start by finding the set S of all n ∈ IN such that f(x) and g(q^{n}x) have a nonconstant common factor. To this end consider the polynomial R(w) = Resultant_{x}(f(x), g(wx)). By the well-known properties of polynomial resultants, S = {n ∈ IN; R(q^{n}) = 0}.

Assume that S = {n_{1}, n_{2}, …, n_{t}} where t ≥ 0 and n_{1} < n_{2} < ⋯ < n_{t}. In addition, let n_{t+1} = +∞. Define polynomials f_{i} and g_{i} inductively by setting

f_{0}(x) = f(x), g_{0}(x) = g(x),

and for i = 1, 2, …, t,

s_{i}(x) = gcd(f_{i−1}(x), g_{i−1}(q^{n_{i}}x)),
f_{i}(x) = f_{i−1}(x)/s_{i}(x),
g_{i}(x) = g_{i−1}(x)/s_{i}(q^{−n_{i}}x).

Now take

z = α/β,
a(x) = f_{t}(x)/α,
b(x) = g_{t}(x)/β,
c(x) = ∏_{i=1}^{t} ∏_{j=1}^{n_{i}} s_{i}(q^{−j}x),

where α and β denote the leading coefficients of f_{t}(x) and g_{t}(x), respectively. Before proving (8) – (12) we state a lemma.

Lemma 1 Let n ∈ IN. If 0 ≤ l ≤ i, j ≤ t and n < n_{l+1}, then gcd(f_{i}(x), g_{j}(q^{n}x)) = 1.

Proof: Assume first that n ∉ S. Then R(q^{n}) ≠ 0, hence gcd(f(x), g(q^{n}x)) = 1. Since f_{i}(x) | f(x) and g_{j}(x) | g(x) it follows that gcd(f_{i}(x), g_{j}(q^{n}x)) = 1, too.

To prove the lemma for n ∈ S we use induction on l.

l = 0: In this case there is nothing to prove since there is no n ∈ S such that n < n_{1}. l > 0: Assume that the lemma holds for all n < n_{l}. It remains to show that it also

holds for n = n_{l}. Since f_{i}(x) | f_{l}(x) and g_{j}(x) | g_{l}(x), it follows that gcd(f_{i}(x), g_{j}(q^{n_{l}}x)) divides gcd(f_{l}(x), g_{l}(q^{n_{l}}x)) = gcd(f_{l−1}(x)/s_{l}(x), g_{l−1}(q^{n_{l}}x)/s_{l}(x)). By the definition of s_{l}(x) the latter gcd is 1, completing the proof. □

Now we proceed to verify properties (8) – (12).

(8):

z \frac{a(x)}{b(x)} \frac{c(qx)}{c(x)} = \frac{f_{t}(x)}{g_{t}(x)} ∏_{i=1}^{t} ∏_{j=1}^{n_{i}} \frac{s_{i}(q^{1−j}x)}{s_{i}(q^{−j}x)}

= \frac{f_{0}(x)}{∏_{i=1}^{t} s_{i}(x)} \frac{∏_{i=1}^{t} s_{i}(q^{−n_{i}}x)}{g_{0}(x)} ∏_{i=1}^{t} \frac{s_{i}(x)}{s_{i}(q^{−n_{i}}x)} = \frac{f(x)}{g(x)} = r(x).

(9): Let i = j = l = t in Lemma 1. Then gcd(f_{t}(x), g_{t}(q^{n}x)) = 1 for all n < n_{t+1} = +∞. In other words, gcd(a(x), b(q^{n}x)) = 1 for all n ∈ IN.

(10): If a(x) and c(x) have a non-constant common factor then so do f_{t}(x) and s_{i}(q^{−j}x), for some i and j such that 1 ≤ i ≤ t and 1 ≤ j ≤ n_{i}. Since g_{i−1}(q^{n_{i}−j}x) = g_{i}(q^{n_{i}−j}x)s_{i}(q^{−j}x), it follows that g_{i−1}(q^{n_{i}−j}x) contains this factor as well. As n_{i} − j < n_{i}, this contradicts Lemma 1. Hence a(x) and c(x) are relatively prime.

(11): If b(x) and c(qx) have a non-constant common factor then so do g_{t}(x) and s_{i}(q^{−j}x), for some i and j such that 1 ≤ i ≤ t and 1 ≤ j +1 ≤ n_{i}. Since f_{i−1}(q^{−j}x) = f_{i}(q^{−j}x)s_{i}(q^{−j}x), it follows that f_{i−1}(x) and g_{t}(q^{j}x) contain this factor as well. As j < n_{i}, this contradicts Lemma 1. Hence b(x) and c(qx) are relatively prime.

(12): It is easy to see that s_{i}(x) divides both f(x) and g(q^{n_{i}}x). Hence s_{i}(0) = 0 would imply that f(0) = g(0) = 0, contrary to the assumption that f and g are relatively prime. It follows that s_{i}(0) ≠ 0 for all i, and consequently c(0) ≠ 0. □

Example 2 Let

r(x) = \frac{(x − 1)(q^{3}x − 1)}{(qx − 1)(q^{4}x − 1)}.

Rewriting this as

r(x) = \frac{1}{q^{4}} \frac{x − 1}{x − q^{−4}} \frac{(qx − q^{−2})(qx − q^{−1})}{(x − q^{−2})(x − q^{−1})}

we can read off

z = q^{−4},
a(x) = x − 1,
b(x) = x − q^{−4},
c(x) = (x − q^{−2})(x − q^{−1}).
□

The representation described in Theorem 1 is unique and thus a normal form. In addition, it has c(x) of least degree among all factorizations of r(x) satisfying (8) and (9). A proof of this can be found in [3].

Remark: The factorization of Theorem 1 satisfying (8) and (9) is used by T. Koornwinder [9] in his Maple implementation of a q-analogue of Zeilberger’s algorithm. In a similar context this representation is discussed by P. Paule and V. Strehl in [12] where a different normalization has been chosen.

4 Finding q–hypergeometric solutions

Now we derive the algorithm for finding first-order right divisors of linear q-hypergeometric operators with polynomial coefficients. Any such divisor has a nontrivial kernel in some suitable difference extension ring M (see, e.g., Sec. 5.1), therefore it is permissible to think rather in terms of finding q-hypergeometric solutions y of Ly = 0. Let ε y = r y where r ∈ IF(x), then ε^{i}y = ∏_{j=0}^{i−1} r(q^{j}x)y. We look for r(x) in the normal form described in Theorem 1. After inserting (8) into Ly = 0, clearing denominators and cancelling y we obtain

∑_{i=0}^{ρ} z^{i}f_{i}(x)c(q^{i}x) = 0  (13)

where

f_{i}(x) = p_{i}(x) ∏_{j=0}^{i−1} a(q^{j}x) ∏_{j=i}^{ρ−1} b(q^{j}x).

Since all terms in (13) except for i = 0 are divisible by a(x) it follows that a(x) divides p_{0}(x)c(x) ∏_{j=0}^{ρ−1} b(q^{j}x). Because of (9) and (10), a(x) divides p_{0}(x). Similarly, all terms in (13) except for i = ρ are divisible by b(q^{ρ−1}x), therefore b(q^{ρ−1}x) divides z^{ρ}p_{ρ}(x)c(q^{ρ}x) ∏_{j=0}^{ρ−1} a(q^{j}x). Because of (9) and (11), b(q^{ρ−1}x) divides p_{ρ}(x). Thus we have a finite number of choices for a(x) and b(x).

For each choice of a(x) and b(x), equation (13) is a q-difference equation for the unknown polynomial c(x). However, z ∈ IF is also not known yet. Let u_{ik} denote the coefficient of x^{k} in f_{i}. Since c(0) ≠ 0, we have a_{0} ≠ 0 in (7), hence applying (7) to (13) we obtain

∑_{i=0}^{ρ} u_{i0}z^{i} = 0.  (14)

We may assume that not all u_{i0} are zero, or else we start by first cancelling a power of x from the coefficients of (13). Thus z is a nonzero root of f(z) = ∑_{i=0}^{ρ} u_{i0}z^{i}, and is algebraic over IF.

If n = deg c(x) then by (6),

∑_{i=0}^{ρ} u_{id}z^{i}q^{in} = 0,  (15)

hence w = zq^{n} is a nonzero root of g(w) = ∑_{i=0}^{ρ} u_{id}w^{i}. It follows that q^{n} is a root of p(x) = Resultant_{w}(f(w), g(wx)), thus to obtain an upper bound on n computation in algebraic extensions of IF is not necessary.

In summary, we find the factors of r(x) as follows:

1. a(x) is a monic factor of p_{0}(x),

2. b(x) is a monic factor of p_{ρ}(q^{1−ρ}x),

3. z is a root of Eqn. (14),

4. c(x) is a nonzero polynomial solution of (13).

Then r = z(a/b)(εc/c), and the nonzero y ∈ M satisfying ε y = r y are q-hypergeometric solutions of Ly = 0. Conversely, for any q-hypergeometric solution y of Ly = 0, its consecutiveterm ratio r = ε y/y can be obtained in this way. Our algorithm called qHyper works by finding, for each admissible triple (a(x), b(x), z), a basis of polynomial solutions of the corresponding equation (13).

Alternatively, after finding one q-hypergeometric solution u with εu/u = r, we can divide L by L_{1} = ε − rI to obtain L = L_{2}L_{1}, and use the algorithm recursively on the reduced equation L_{2}z = 0. If z solves the new equation then any solution y of the nonhomogeneous first-order equation

ε y − r y = z  (16)

solves the original equation. To solve (16), we can use the algorithm of Sec. 6. Instead, we can also make the substitution y = uv, and use either the q-analogue of Gosper’s algorithm, or again the algorithm of Sec. 6, on the resulting equation ε v − v = z/(r u). – This process is equivalent to the standard method of reduction of order.

Our Mathematica implementation^{2} of qHyper finds, in its basic form, at least one qhypergeometric solution over Q^{|} (if any such exists). With the option Solutions -> All, it finds a generating set for the space spanned by q-hypergeometric solutions over Q^{|}, and with the option Quadratics -> True, it works over quadratic extension fields of Q^{|}. It returns a list of rational functions r_{1}, r_{2}, …, r_{k} which represent solutions y_{1}, y_{2}, …, y_{k} satisfying εy_{i}/y_{i} = r_{i}.

Example 3 Let us find a first-order right divisor of

L = xε^{3} − q^{3}x^{2}ε^{2} − (x^{2} + q)ε + qx(x^{2} + q)I.

The candidates for a(x) are

1, x, x^{2} + q, x(x^{2} + q),

and the candidates for b(x) are

1, x.

Here we explore only the choice a(x) = x and b(x) = 1. The corresponding equation (13) is, after cancelling one x,

z^{3}q^{3}x^{3}c(q^{3}x) − z^{2}q^{4}x^{3}c(q^{2}x) − z(x^{2} + q)c(qx) + q(x^{2} + q)c(x) = 0,  (17)

whence f(z) = −qz + q^{2} with unique root z = q, and g(w) = q^{3}w^{3} − q^{4}w^{2} with unique nonzero root w = q = zq^{n} = q^{n+1}. It follows that n = 0 is the only possible degree for c. Equation (17) is satisfied by c = 1. Thus we have found r = z(a/b)(εc/c) = qx, and the corresponding right divisor L_{1} = ε − qx of L.

To find other first-order right divisors, the remaining combinations for a(x) and b(x) could be tried. Using our Mathematica implementation to carry this out, it turns out that there are in fact no other such divisors:

In[1]:= qHyper[x y[q^3 x] - q^3 x^2 y[q^2 x] - (x^2 + q) y[q x] +
               q x (x^2 + q) y[x] == 0, y[x],
               Solutions -> All, Quadratics -> True]
Out[1]= {q x}

□

Example 4 Consider the operator L = ε^{2} − (1 + q)ε + q(1 − qx^{2})I. As shown by qHyper,

In[2]:= qHyper[y[q^2 x] - (1 + q) y[q x] + q (1 - q x^2) y[x] == 0,
               y[x], Solutions -> All]

2accessible at the WWW address http://www.mat.uni-lj.si.

 Warning: irreducible factors of degree > 1 in trailing coefficient;
 some solutions may not be found
Out[2]= {}

it has no first-order right divisors over IF = Q^{|}(q). However, allowing quadratic factors to be split,

In[3]:= qHyper[y[q^2 x] - (1 + q) y[q x] + q (1 - q x^2) y[x] == 0,
               y[x], Solutions -> All, Quadratics -> True]
Out[3]= {1 - Sqrt[q] x, 1 + Sqrt[q] x}

we obtain two such divisors, namely ε − (1 ± \sqrt{q}x), over IF = Q^{|}(\sqrt{q}). □

Example 5 The operator L = ε^{2} − (1 + 2x)ε + xI has no first-order right divisors over

IF = Q^{|}(q):

In[4]:= qHyper[y[q^2 x] - (1 + 2 x) y[q x] + x y[x], y[x]]
Out[4]= {}

Here q was considered transcendental over the rational number field Q^{|}. But when q = 2

In[5]:= q = 2;
In[6]:= qHyper[y[q^2 x] - (1 + 2 x) y[q x] + x y[x], y[x]]
Out[6]= {x}

we do get one such divisor over IF = Q^{|}, namely ε − x.

In[7]:= Clear[q]

□

5 Some specific extension rings

5.1 Germs of sequences over IF

Let IF^{IN} be the ring of sequences over IF, where addition and multiplication (“Hadamard product”) are defined componentwise. Let x = (q^{n})_{n=0}^{∞} denote the sequence of powers of q. If E denotes the shift operator on IF^{IN}, i.e., Ea_{n} = a_{n+1}, then Ex = qx. Since λ ∈ IF can be identified with the constant sequence (λ, λ, …), we can regard IF, IF[x] and IF(x) as subrings of IF^{IN}.

Unfortunately, E is not an automorphism of IF^{IN} because it annihilates nonzero sequences of the form (λ, 0, 0, …). To remedy this situation, we identify such sequences with zero; moreover, we identify any two sequences which agree from some point on. Formally we define M as the quotient ring S(IF) = IF^{IN}/J where J is the ideal of sequences with only finitely many nonzero terms. In particular, this means that equalities of the form a_{n} = b_{n} are interpreted as being valid for all but finitely many n (in short: for almost all n). Define ε on S(IF) by requiring that ε(a + J) = Ea + J for all a ∈ IF^{IN}. Then ε is an automorphism of S(IF), and S(IF) is a difference extension ring of IF(x). The elements of S(IF) are called the germs of sequences over IF [15]. To simplify notation, we will identify the germ a+J ∈ S(IF) with its representative sequence a ∈ IF^{IN}.

In this domain the q-difference equation Ly = 0 where y = (y_{n})_{n=0}^{∞} ∈ S(IF), translates into

∑_{i=0}^{ρ} p_{i}(q^{n})y_{n+i} = 0

for almost all n. In particular, the first-order equation ε y = r y where r ∈ IF(x) can be rewritten as

y_{n+1} = r(q^{n})y_{n}.  (18)

Let n_{0} be the largest n ∈ IN such that q^{n} is a pole of r, or −1 if no such n exists. Then, clearly, the sequence

y_{n} = C ∏_{k=n_{0}+1}^{n−1} r(q^{k}),  for n > n_{0},  (19)

where C ∈ IF is an arbitrary constant, satisfies (18) for almost all n. Thus every homogeneous first-order equation has a one-dimensional space of q-hypergeometric solutions in S(IF).

If r(x) factors into linear factors over IF:

r(x) = z \frac{(x − α_{1})(x − α_{2}) ⋯ (x − α_{r})}{(x − β_{1})(x − β_{2}) ⋯ (x − β_{s})} x^{u}

where z, α_{i}, β_{j} ∈ IF, u ∈ ZZ, and α_{i}, β_{j} ≠ 0, q^{k}, for all k ∈ IN, then we can also express the solution with q-shifted factorials as

y_{n} = C \frac{(1/α_{1}; q)_{n}(1/α_{2}; q)_{n} ⋯ (1/α_{r}; q)_{n}}{(1/β_{1}; q)_{n}(1/β_{2}; q)_{n} ⋯ (1/β_{s}; q)_{n}} q^{u\binom{n}{2}} w^{n}

where

w = (−1)^{r+s}z \frac{α_{1}α_{2} ⋯ α_{r}}{β_{1}β_{2} ⋯ β_{s}} ,

and C ∈ IF is an arbitrary constant. This is the reason why q-hypergeometric solutions are considered to be expressible in closed form.

Example 6 q-hypergeometric solutions y ∈ S(IF) of the equation from Example 3 satisfy y_{n+1} = q^{n+1}y_{n}. Hence y_{n} = q^{\binom{n+1}{2}} is a q-hypergeometric solution of that equation in S(IF), that is,

q^{n}y_{n+3} − q^{2n+3}y_{n+2} − q(1 + q^{2n−1})y_{n+1} + q^{n+2}(1 + q^{2n−1})y_{n} = 0

for n ≥ 3.

q-hypergeometric solutions y ∈ S(IF) of the equation from Example 4 satisfy y_{n+1} = (1 ± q^{n+1/2}) y_{n}. Hence y_{n}^{(1)} = (\sqrt{q}; q)_{n} and y_{n}^{(2)} = (−\sqrt{q}; q)_{n} are two linearly independent q-hypergeometric solutions of that equation in S(IF).

Let q = 2. Then q-hypergeometric solutions y ∈ S(IF) of the equation from Example 5 satisfy y_{n+1} = 2^{n}y. Hence y_{n} = 2^{\binom{n}{2}} is a q-hypergeometric solution of that equation in S(IF). □

5.2 Formal power series over IF

Let M = IF[[x]], the ring of formal power series over IF. Note that IF, IF[x], and IF(x) are embedded in M in a natural way. For y(x) = ∑_{k=0}^{∞} y_{k}x^{k} ∈ IF[[x]], define

ε ∑_{k=0}^{∞} y_{k}x^{k} = ∑_{k=0}^{∞} y_{k}q^{k}x^{k}.

Then ε is an automorphism of IF[[x]], and IF[[x]] is a difference extension ring of IF(x). Unlike in S(IF), a homogeneous first-order q-difference equation with rational coefficients does not always have a nonzero solution in IF[[x]].

Theorem 2 The equation y(qx) = r(x)y(x) where r(x) = ∑_{k=0}^{∞} r_{k}x^{k} ∈ IF[[x]] has a nonzero solution y(x) ∈ IF[[x]] if and only if r_{0} = q^{n} for some n ∈ IN.

Proof: Let y(x) = ∑_{k=0}^{∞} y_{k}x^{k} be a solution of y(qx) = r(x)y(x). Then, comparing coefficients of like powers of x, we have

q^{k}y_{k} = ∑_{i=0}^{k} y_{i}r_{k−i}, for k = 0, 1, …,

or, equivalently,

y_{k}(q^{k} − r_{0}) = ∑_{i=0}^{k−1} y_{i}r_{k−i}, for k = 0, 1, ….  (20)

Assume first that r_{0} ≠ q^{k} for all k ∈ IN. Then (20) implies that

y_{0} = 0,
y_{k} = ∑_{i=0}^{k−1} y_{i}r_{k−i}/(q^{k} − r_{0}), for k = 1, 2, ….

From this it follows by induction on k that y_{k} = 0 for all k ∈ IN, hence that y(x) = 0. Now let r_{0} = q^{n} for some n ∈ IN. Then we see as above that y_{k} = 0 for k < n, and

y_{k} = ∑_{i=n}^{k−1} y_{i}r_{k−i}/(q^{k} − q^{n}), for k = n + 1, n + 2, …,  (21)

which is a recurrence allowing us to express all y_{k} with k > n in terms of y_{n}. □

Example 7 In Examples 3 and 5 we have r(x) = qx and r(x) = x, respectively. The condition of Theorem 2 is not fulfilled, hence the corresponding equations have no qhypergeometric solutions in IF[[x]].

In Example 4, r(x) = 1 ± \sqrt{q} x, and the condition of Theorem 2 is fulfilled with n = 0. Using recurrence (21) we find two linearly independent q-hypergeometric solutions in IF[[x]]:

y^{(1)}(x) = ∑_{k=0}^{∞} \frac{(−1)^{k}q^{k/2}}{(q; q)_{k}} x^{k},
y^{(2)}(x) = ∑_{k=0}^{∞} \frac{q^{k/2}}{(q; q)_{k}} x^{k}.

Both solutions are instances of a q-analogue of the exponential function e^{z}, namely e_{q}(z) = ∑_{n=0}^{∞} z^{n}/(q; q)_{n} = 1/(z; q)_{∞} [8, (1.3.15)]. This classical product expansion allows an easy verification of the statement above. □

We remark that Laurent series solutions can be handled in an analogous way. In that case, Theorem 2 still holds, provided that n is allowed to be any integer.

5.3 Basic hypergeometric series

The algorithm qHyper allows us also to find power series solutions in M = IF[[x]] whose coefficients form a q-hypergeometric sequence in S(IF). If y(x) = ∑_{j=0}^{∞} y_{j}x^{j} is such a series then y_{j+1} = r(q^{j})y_{j} for some r(x) ∈ IF(x) and for almost all j ∈ IN. These series are usually called basic hypergeometric series [8].

Let Ly(x) = b(x) where b(x) = ∑_{j=0}^{∞} b_{j}x^{j}. As in (5), we obtain

∑_{j=max{l−d,0}}^{l} ∑_{i=0}^{ρ} c_{i,l−j}y_{j}q^{ij} = b_{l}, for l ≥ 0.  (22)

We separate the cases 0 ≤ l < d and l ≥ d. In the former case, (22) yields initial conditions

∑_{j=0}^{l} y_{j} ∑_{i=0}^{ρ} c_{i,l−j}q^{ij} = b_{l}, for 0 ≤ l < d,  (23)

while in the latter, substitutions m = l − d, s = j − m, and X = q^{m} transform (22) into the associated q-difference equation

∑_{s=0}^{d} y_{m+s} ∑_{i=0}^{ρ} c_{i,d−s}q^{is}X^{i} = b_{m+d}, for m ≥ 0,  (24)

for the unknown sequence (y_{m})_{m=0}^{∞}.

If b(x) = 0 we use qHyper on (24). Among the obtained solutions, we select those which are defined for all m ∈ IN, and satisfy initial conditions (23). – If b(x) ≠ 0, we use the algorithm of Sec. 6 instead.

Example 8 Let us find basic hypergeometric solutions y(x) of

q^{2}x^{2}ε^{3}y + (1 + q)xε^{2}y + (1 − x)εy − y = 0.  (25)

The associated equation (24) in this case is

(q^{2}X − 1)y_{m+2} + (q^{2}(q + 1)X^{2} − qX)y_{m+1} + q^{2}X^{3}y_{m} = 0  (26)

and qHyper finds two solutions:

In[8]:= qHyper[(q^2 X - 1) y[q^2 X] + (q^2 (1 + q) X^2 - q X) y[q X] +
                q^2 X^3 y[X] == 0, y[X], Solutions -> All]
                 2
              q X
Out[8]= {-X, -------}
             1 - q X

Thus the general solution of (26) in S(IF) is y_{m} = C(−1)^{m}q^{\binom{m}{2}} + Dq^{m^{2}}/(q; q)_{m} where C and D are arbitrary constants. Equations (23) imply that C = 0. Hence y(x) = ∑_{m=0}^{∞} q^{m^{2}}x^{m}/(q; q)_{m} is a basic hypergeometric solution of (25).

Note that running qHyper on equation (25) itself we obtain r(x) = −1/x which does not fulfil the condition of Theorem 2. Hence (25) has no q-hypergeometric solution in IF[[x]]. □

6 Nonhomogeneous equations

Consider the problem of finding q-hypergeometric solutions y ∈ M of the nonhomogeneous equation Ly = b where b ∈ M \ {0}. Let ε y = r y where r ∈ IF(x). Then Ly = fy where f = ∑_{i=0}^{ρ} p_{i} ∏_{j=0}^{i−1} ε^{j}r is a rational function of x. This simple fact has two important consequences:

1. b = fy is q-hypergeometric,

2. y = b/f is a rational multiple of b.

Let εb = sb where s ∈ IF(x) is given. We look for y in the form y = fb where f ∈ IF(x) is an unknown rational function. Substituting this into Ly = b gives

∑_{i=0}^{ρ} p_{i} (∏_{j=0}^{i−1} ε^{j}s) ε^{i}f = 1.

Now rational solutions of this equation can be found using the algorithm given in [1]^{3}.

Example 9 Let y(x) ∈ IF[[x]] satisfy

ε^{2}y(x) − (1 − qx)εy(x) + qy(x) = b(x)  (27)

where

b(x) = ∑_{i=0}^{∞} \frac{x^{i}}{(q; q)_{i}} .

3Please note that “for i = 0, 1, …, N” should be replaced by “for i = N, N −1, …, 0” in that algorithm.

Here b(qx) = (1 − x)b(x), as can easily be verified. Thus s(x) = 1 − x and y(x) = f(x)b(x) where f(x) satisfies

(1 − qx)(1 − x)ε^{2}f(x) − (1 − qx)(1 − x)εf(x) + qf(x) = 1

with rational solution f(x) = 1/q. Hence y(x) = b(x)/q is a q-hypergeometric solution of (27) in IF[[x]]. As in Example 7 the result is easily verified by using the product representation of the q-exponential function e_{q}(x) = b(x).

We can also look for basic hypergeometric solutions of (27). The associated nonhomogeneous equation for y_{m} is by (26)

(qX^{2} − X + 1)y_{m+1} + Xy_{m} = \frac{1}{q(q; q)_{m+1}} ,

and we find its q-hypergeometric solutions in S(IF). Here s(X) = (q(q; q)_{m+1})/(q(q; q)_{m+2}) = 1/(1 − q^{m+2}) = 1/(1 − q^{2}X), and the equation for f(X)

\frac{1 − X + qX^{2}}{1 − q^{2}X} εf(X) + Xf(X) = 1

is satisfied by the rational function f(X) = 1 − qX. Thus y_{m} = (1 − qX)/(q(q; q)_{m+1}) = 1/(q(q; q)_{m}), and we find the same solution y(x) = b(x)/q as before. □

The algorithm for finding q-hypergeometric solutions of nonhomogeneous equations can also be used to solve the problem of indefinite q-hypergeometric summation: Given a qhypergeometric sequence b = (b_{n})_{n=0}^{∞} over IF, decide if the telescoping recurrence y_{n+1} −y_{n} = b_{n} has a q-hypergeometric sequence solution (y_{n})_{n=0}^{∞}. If so, the indefinite sum of b can be expressed in closed form, namely, ∑_{j=0}^{n−1} b_{j} = y_{n} − y_{0}. Since we are interested in qhypergeometric solutions, we rewrite the telescoping recurrence as ε y − y = b and use the algorithm of this section to find solutions y ∈ S(IF).

Example 10 To evaluate the sum ∑_{j=0}^{n−1} b_{j} where b_{n} = q^{n}(q; q)_{n}, we look for q-hypergeo-metric solutions y of the nonhomogeneous equation

ε y − y = b.  (28)

Here s = εb/b = q(1 − qx), and f satisfies the equation

q(1 − qx)εf − f = 1

which has a unique rational solution f = −1/(qx). Hence y_{n} = −b_{n}/q^{n+1} satisfies (28), and ∑_{j=0}^{n−1} b_{j} = y_{n} − y_{0} = (1 − (q; q)_{n})/q. □

7 Applications to q-hypergeometric summation

It is well-known that Zeilberger’s “fast” algorithm [18], or the more general WZ-machinery described in [17], does not always deliver a representing difference equation of minimal order for the given sum. For instance, as pointed out in [11] one can prove that the Zeilberger recurrence for the sum expression on the left-hand side of

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}\binom{d k}{n} = (−d)^{n}  (29)

for a fixed positive integer d is of order d−1 instead of order 1 according to its hypergeometric evaluation. Here one applies algorithm Hyper of [13] to the recurrence in order to find its hypergeometric solutions. In this section a brief discussion of applications of qHyper in connection with definite q-hypergeometric summation is given.

7.1 A new q-summation identity

Let d and n be positive integers, then

∑_{k=0}^{n}(−1)^{k}q^{d\binom{n−k}{2}}\left[{n \atop k}\right]_{d}\left[{d k \atop n}\right] = (−1)^{n}q^{(d−1)\binom{n}{2}} \frac{[n]_{d}!}{[n]!}[d]^{n},  (30)

which for q → 1 specializes to identity (29). The proof of (30), an identity we could not find in the literature, is elementary by using

∑_{k=0}^{n}(−1)^{k}q^{d\binom{n−k}{2}}\left[{n \atop k}\right]_{d}(q^{dk})^{l} = \{ \begin{matrix}0 & , if 0 ≤ l ≤ n − 1 \\ q^{d\binom{n}{2}}(q^{d}; q^{d})_{n} & , if l = n \end{matrix}

which follows immediately from (4), and by observing that \left[{d k \atop n}\right] is 1/(q; q)_{n} times a polynomial in q^{dk} of degree n.

Denote by SUM(n) the sum expression on the left-hand side of (30). Applying the q-analogue qZeil of Zeilberger’s algorithm implemented in Mathematica by A. Riese [14] one obtains, for instance, for d = 3 a recursion of order 2. This means, as in the case q → 1, that the minimal order is missed by 1:

In[9]:= qZeil[(-1)^k q^(3 Binomial[n-k,2]) qBinomial[n,k,q^3]*
         qBinomial[3k,n,q], {k,-Infinity,Infinity}, n, 2]
                  -5 + 4 n       -1 + n       -1 + n    -2 + 2 n
Out[9]= SUM[n]==(q        (-1 + q      )(1 + q       + q        )
          n    2 n                        n        -1 + 2 n
>   (1 + q  + q   ) SUM[-2 + n]) / ((1 + q ) (1 - q        )) +
      -2 + 2 n       n    2 n             -1 + 2 n    -1 + 3 n

>   (q        (1 + q   + q   ) (-1 - q + q         + q        )
                               n        -1 + 2 n
>         SUM[-1 + n]) / ((1 + q ) (1 - q         ))

The algorithm qHyper now finds the q-hypergeometric solution of this recurrence (after replacing q^{n} by x, and SUM[n+k] by Y[q^k x]):

In[10]:= % /. {SUM[n + k_.] -> Y[q^k x],  q^(a_. n + b_.) -> x^a q^b};
In[11]:= qHyper[%, Y[x]]
 Warning: irreducible factors of degree > 1 in leading coefficient;
 some solutions may not be found
 Warning: irreducible factors of degree > 1 in trailing coefficient;
 some solutions may not be found
             2             2  2
Out[11]= {-(x  (1 + q x + q  x ))}

This means that for one solution y_{n} = Y (q^{n}), we have

\frac{y_{n+1}}{y_{n}} = −q^{2n}(1 + q^{n+1} + q^{2n+2}) = −q^{2n} \frac{1 − q^{3n+3}}{1 − q^{n+1}} .

From this information together with the initial values one computes as the q-hypergeometric evaluation of the sum the expression on the right-hand side of (30) for d = 3.

7.2 Increased orders

In most instances the orders of the Zeilberger recurrences for q-analogues and their q → 1 specializations are the same. This also applies when Zeilberger’s algorithm fails to deliver the minimal order, for instance, as in the previous example.

But this is not true in general. Running the q-version of Zeilberger’s algorithm on certain q-analogues of classical hypergeometric summation and transformation formulas one observes that the orders increase in comparison to the recurrence orders obtained in the case q → 1. A relatively simple but important example is the following identity due to L. J. Rogers,

∑_{k=−n}^{n}(−1)^{k}q^{k(3k−1)/2}\left[{2n \atop n + k}\right] = \frac{[2n]!}{[n]!}(1 − q)^{n}.  (31)

Besides playing a key role in proving identities of the Rogers-Ramanujan type (Andrews [5]), in the limit as n → ∞ it yields the celebrated Eulerian pentagonal number theorem.

Despite its fundamental importance with respect to q-hypergeometric identities, for q → 1 it specializes to a trivial instance of the binomial theorem,

∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k} = (−1)^{n} ∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k} = δ_{n,0},

which could be treated also with Gosper’s algorithm.

Applying qZeil to the left-hand side of (31) surprisingly results in a q-difference equation of order 3 (!),

In[12]:= qZeil[(-1)^k q^(k(3k-1)/2) qBinomial[2n,n+k,q],
         {k,-Infinity,Infinity}, n, 3]
                          n        n     2    n    2    n
Out[12]= SUM[n] == ((-q + q ) (q + q ) (-q  + q ) (q  + q )
           3    2 n     5    2 n                  11          n
>       (-q  + q   ) (-q  + q   ) SUM[-3 + n]) / q   +  (q - q )
            n     3    2 n    2    3    4    2 n
      (q + q ) (-q  + q   ) (q  + q  + q  + q   ) SUM[-2 + n]
>     ------------------------------------------------------- +
                                     6
                                    q
        2    3    4    3 n    2 + 2 n    1 + 3 n
      (q  + q  + q  - q    - q        - q       ) SUM[-1 + n]
>     -------------------------------------------------------
                                2
                               q

Applying qHyper we find one q-hypergeometric solution of this recurrence (after replacing

q^{n} by x, and SUM[n+k] by Y[q^k x]):
In[13]:= % /. {SUM[n + a_.] -> Y[q^a x],  q^(a_. n + b_.) -> x^a q^b};
In[14]:= qHyper[%, Y[x]]
 Warning: irreducible factors of degree > 1 in trailing coefficient;
 some solutions may not be found
                           2
Out[14]= {(1 + q x) (1 - q x )}

This means that for one solution y_{n} = Y (q^{n}), we have

\frac{y_{n+1}}{y_{n}} = (1 + q^{n+1})(1 − q^{2n+1}).

From this together with the initial values the right-hand side evaluation of (31) is easily computed.

Another way to treat the increase of recurrence orders in the q-case was found by P. Paule [10]. His method of “summing the even part”, or variations of it, consists in rewriting the given sum by exploiting symmetries of the summand. After this preprocessing the qversion of Zeilberger’s algorithm delivers the recursion of minimal order. We give a brief illustrating example. Let f(n, k) denote the summand of the Rogers identity (31). Since ∑_{k} f(n, k) = ∑_{k} f(n, −k), it follows that

∑_{k} f(n, k) = \frac{1}{2} ∑_{k}(f(n, k) + f(n, −k)) = \frac{1}{2} ∑_{k}(1 + q^{k})f(n, k).

The extra factor 1+q^{k} increases the chance that the q-Zeilberger algorithm finds a recurrence of lower order. Indeed, now one gets by applying qZeil the minimal recurrence of order 1.

In[15]:= qZeil[(-1)^k (1+q^k)/2 q^(k(3k-1)/2) qBinomial[2n,n+k,q],
              {k,-Infinity,Infinity}, n, 1]
                         n        -1 + 2 n
Out[15]= SUM[n] == (1 + q ) (1 - q        ) SUM[-1 + n]

Paule’s method is of special importance with respect to the theory of q-WZ pairs [16]. There are various applications, [10] or [14], where “summing the even part” enables one to manufacture the dual or companion identities. We only mention two examples for which the q-Zeilberger algorithm delivers a recurrence of increased order 3, namely the Rogers identity (31) and the q-analogue of Dixon’s formula,

∑_{k}(−1)^{k}q^{k(3k−1)/2}\left[{n + b \atop n + k}\right]\left[{n + c \atop c + k}\right]\left[{b + c \atop b + k}\right] = \frac{[n + b + c]!}{[n]![b]![c]!}.

Despite the fact that Paule’s method applies to most “increased order” cases of definite qhypergeometric sums one finds in standard literature (and also to nontrivial q → 1 examples as recently found by Zeilberger and Petkovšek), the symmetry-preprocessing up to now algorithmically has not been fully understood. For instance, it is not at all obvious how one could apply the method in the case of identity (30). Therefore the algorithm qHyper is currently the only tool that constructively decides about existence of q-hypergeometric evaluation of a definite q-hypergeometric sum for which the q-Zeilberger algorithm delivers a recurrence of order greater than 1.

References

[1] S. A. Abramov, Rational solutions of linear difference and q-difference equations with polynomial coefficients, in: T. Levelt, ed., Proc. ISSAC ’95 (ACM Press, New York, 1995) 285–289.

[2] S. A. Abramov, M. Bronstein and M. Petkovšek, On polynomial solutions of linear operator equations, in: T. Levelt, ed., Proc. ISSAC ’95 (ACM Press, New York, 1995) 290–296.

[3] S. A. Abramov and M. Petkovšek, Finding all q-hypergeometric solutions of q-difference equations, in: B. Leclerc and J.-Y. Thibon, eds., Proc. FPSAC ’95 (Univ. de Marne-la-Vallée, Noisy-le-Grand, 1995) 1–10.

[4] G. E. Andrews, The Theory of Partitions (Addison-Wesley, Reading, Mass., 1976).

[5] G. E. Andrews, q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra (CBMS Regional Conference Series, No. 66, AMS, Providence, R.I., 1986).

[6] M. Bronstein and M. Petkovšek, On Ore rings, linear operators and factorisation, Programmirovanie 1 (1994) 27–45 (also: Research Report 200, Informatik, ETH Zürich).

[7] R. M. Cohn, Difference Algebra (Interscience Publishers, New York, 1965).

[8] G. Gasper and M. Rahman, Basic Hypergeometric Series (Cambridge University Press, Cambridge, 1990).

[9] T. H. Koornwinder, On Zeilberger’s algorithm and its q-analogue: a rigorous description, J. Comp. Appl. Math. 48 (1993) 91–111.

[10] P. Paule, Short and easy computer proofs of the Rogers-Ramanujan identities and of identities of similar type, Electronic J. Comb. 1 (1994) # R10.

[11] P. Paule and M. Schorn, A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, RISC-Linz Report Series No. 95-10, to appear in J. Symb. Comp.

[12] P. Paule and V. Strehl, Symbolic summation – some recent developments, RISC-Linz Report Series No. 95-11, 1995. To appear in: “Computer Algebra in Science and Engineering - Algorithms, Systems, and Applications”, J. Fleischer, J. Grabmeier, F. Hehl, W. Küchlin (eds.), World Scientific, Singapore.

[13] M. Petkovšek, Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symb. Comp. 14 (1992) 243–264.

[14] A. Riese, A Mathematica q-analogue of Zeilberger’s algorithm for proving q-hypergeo-metric identities, Diploma Thesis, University of Linz, Linz, 1995.

[15] R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980) 175–188.

[16] H. S. Wilf and D. Zeilberger, Rational functions certify combinatorial identities, J. Amer. Math. Soc. 3 (1990) 147–158.

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

[18] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990) 207–211.