J. Symbolic Computation (1998) 11, 1–22

Hypergeometric Solutions of Linear Recurrences with Polynomial Coefficients

MARKO PETKOVŠEK

Department of Mathematics, University of Ljubljana, Slovenia

(Received 21 September 1990)

We describe algorithm Hyper which can be used to find all hypergeometric solutions of linear recurrences with polynomial coefficients.

1. Introduction

Let K be a field of characteristic zero. We assume that K is computable, meaning that the elements of K can be finitely represented and that there exist algorithms for carrying out the field operations.

Let K^{IN} denote the ring of all sequences over K, with addition and multiplication defined term-wise. Following Stanley (1980) we identify two sequences if they agree from some point on. Formally, we are working in the quotient ring S_{K} := K^{IN}/J where J is the ideal of sequences with at most finitely many non-zero terms. Hence all equalities of the form L(n) = R(n) are to be interpreted as valid for all large enough n. Accordingly, a sequence is considered non-zero if and only if it has infinitely many non-zero terms.

Definition 1.1. A sequence a ∈ S_{K} will be called polynomial (respectively rational) over K if there is a polynomial f(x) ∈ K[x] (respectively a rational function f(x) ∈ K(x)) such that a(n) = f(n) for all large enough n ∈ IN.

A non-zero sequence a ∈ S_{K} is a hypergeometric term (or simply hypergeometric) over K if there is a rational function r(x) ∈ K(x) such that a(n + 1) = r(n)a(n) for all large enough n ∈ IN. Two hypergeometric terms are similar if their ratio is rational.

We will denote the sets of polynomial, rational, and hypergeometric sequences over K by P_{K}, R_{K}, and H_{K}, respectively. By L(H_{K}) we will denote the linear subspace spanned by H_{K} in the K-linear space S_{K}.

Since two polynomials which agree on infinitely many arguments are identical, the polynomial defining a polynomial sequence is unique, and we will not distinguish between the two. The same goes for rational functions and sequences. In fact, P_{K} is a ring isomorphic to K[x] and R_{K} is a field isomorphic to K(x). It is easy to see that H_{K} is a multiplicative group. For any field F, let F^{∗} denote its multiplicative group. Then f : H_{K} → R_{K}^{∗} defined by f : h(n) ↦ h(n+1)/h(n) is an epimorphism which induces an

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1998 Academic Press Limited

isomorphism between H_{K}/K^{∗} and R_{K}^{∗}. Obviously, similarity is a congruence relation in H_{K} induced by the normal subgroup R_{K}^{∗}.

Example 1.1. Let a(n) = 0, b(n) = 1, c(n) = n^{2}−1, d(n) = 2^{n}, e(n) = 2^{n}−1, f(n) = n!. Then sequences a, b, c are polynomial over K, sequences b, c, d, f are hypergeometric over K, and sequences a, e belong to L(H_{K}) but are not hypergeometric over K.

Let S denote the shift operator in the ring K^{IN}, defined by Sa(n) = a(n + 1). There is a unique endomorphism E of S_{K} such that E(a + J) = Sa + J, for every a ∈ K^{IN}. It is easy to see that E is in fact an automorphism of S_{K}, and thus (S_{K}, E) is an inversive difference ring, according to the definition in Cohn (1965).

Let d be a positive integer and r_{0}(n), r_{1}(n), …, r_{d}(n) sequences from R_{K} such that r_{d} ≠ 0. Then L := ∑_{i=0}^{d} r_{i}E^{i} is a linear recurrence operator with rational coefficients over K. We will be interested in algorithms for finding hypergeometric solutions of equations of the form La = f where L is as above and f ∈ S_{K}.

Clearly, for every linear recurrence operator with rational coefficients there exists a linear recurrence operator with polynomial coefficients having the same kernel. Furthermore, every linear recurrence operator L can be written in the form L = L_{0}E^{m} where L_{0} is an operator with non-zero trailing coefficient. Thus the affine solution space L^{−1}f equals E^{−m}L_{0}^{−1}f, for any f ∈ S_{K}. Therefore we will from now on assume that L is of the form

L := ∑_{i=0}^{d} p_{i}E^{i}  (1.1)

where p_{0}(n), p_{1}(n), …, p_{d}(n) are sequences from P_{K} such that p_{0}, p_{d} ≠ 0. The order of L as defined in (1.1) is d, and its degree is m := max_{0≤i≤d} deg p_{i}(n). With L as in (1.1), the equation

La = 0  (1.2)

is a homogeneous linear recurrence with polynomial coefficients for the unknown sequence a ∈ S_{K}. We will also consider the corresponding non-homogeneous recurrence

La = f  (1.3)

where L is as in (1.1) and f is a given sequence from S_{K}. The order and degree of recurrences (1.2) and (1.3) are defined to be those of L.

Abramov (1989a) gives an algorithm for finding all polynomial solutions of (1.3). Abramov (1989b) does the same for rational solutions. In this paper we present algorithm Hyper which can be used to find all hypergeometric solutions of (1.3). To give some motivation, we describe first an application of algorithm Hyper to definite hypergeometric summation.

The problem of indefinite hypergeometric summation was solved by Gosper (1978) who discovered an algorithm for finding hypergeometric solutions of the non-homogeneous first-order recurrence

a(n + 1) − a(n) = h(n)

where h(n) is a hypergeometric term. In other words, Gosper’s algorithm decides whether the indefinite sum of a hypergeometric term is hypergeometric (apart from an additive constant).

One can ask the same question about definite sums of the form

a(n) = ∑_{k} F (n, k)  (1.4)

where summation ranges over all integers, and the two quotients F (n + 1, k)/F (n, k) and F (n, k + 1)/F (n, k) are rational functions of n and k. Using Bernstein’s theory of holonomic functions, Zeilberger (1990) proved that every a of the form (1.4) satisfies a recurrence of the form (1.2). Zeilberger (1991) gives an algorithm which constructs such a recurrence. Wilf and Zeilberger (1992) generalize this to multiple and/or q-hypergeometric sums. Since algorithm Hyper can be used to obtain a basis for the space of solutions of (1.2) belonging to L(H_{K}), the combination of Zeilberger’s algorithm with Hyper, followed by solving a system of linear algebraic equations gives an algorithm for deciding whether (1.4) is a linear combination of hypergeometric terms.

The overview of the paper is as follows. In order to make the description of Hyper selfcontained, we start in Section 2 by deriving algorithm Poly which finds a basis for the space of polynomial solutions of (1.2). A similar algorithm (but expecting the recurrence to be given in terms of the difference operator Δ) has been developed independently by Abramov (1989a).

Section 3 describes a normal form for rational functions which plays an important role both in Gosper’s algorithm and in algorithm Hyper.

In Section 4 we develop algorithm Hyper which decides existence of hypergeometric solutions of (1.2) over some extension of the coefficient field of (1.2). The algorithm works by constructing a finite set of auxiliary recurrences of order d such that (1.2) has a hypergeometric solution if and only if some auxiliary recurrence has a non-zero polynomial solution. Algorithm Poly is then used on each auxiliary recurrence.

In Section 5 we show how to solve recurrences (1.2) and (1.3) over L(H_{K}). Abramov (1989b) presents an algorithm for finding rational solutions of (1.3). With a simple modification, this algorithm can be used to find hypergeometric solutions of (1.3) when f ≠ 0. Finally, we discuss the necessity to compute in algebraic extensions of the coefficient field of the recurrence in order to find all its hypergeometric solutions.

2. Polynomial solutions

In this section we assume that there exists an algorithm for finding integer roots of polynomials over K. Such a field is called adequate in Abramov (1989a, b). We follow the convention that 0^{0} = 1 and that \binom{n}{k} = 0 when k < 0 or 0 ≤ n < k.

The question of existence of non-zero polynomial solutions of (1.2) reduces to the problem of finding an upper bound N for the possible degrees of such solutions. Once we have N, we can substitute in the recurrence a generic polynomial of degree N for a(n) and solve the resulting system of linear algebraic equations. The following example shows that it is not possible to bound the degree of polynomial solutions of (1.2) in terms of its order and degree.

Example 2.1. For any fixed non-negative integer k, the solutions of

na(n + 1) − (n + k)a(n) = 0

are constant multiples of \binom{n+k−1}{k} which is a polynomial in n of degree k, while the recurrence is of order and degree 1. Similar examples can be constructed for higher-order recurrences.

We consider first the second-order recurrence

p(n)a(n + 2) + q(n)a(n + 1) + r(n)a(n) = 0  (2.1)

where p, q, r are polynomials. Assume that a(n) is a non-zero polynomial solution of (2.1), of unknown degree N. Let m be the degree of (2.1) and

p(n) = u_{0}n^{m} + u_{1}n^{m−1} + u_{2}n^{m−2} + O(n^{m−3}) ,
q(n) = v_{0}n^{m} + v_{1}n^{m−1} + v_{2}n^{m−2} + O(n^{m−3}) ,
r(n) = w_{0}n^{m} + w_{1}n^{m−1} + w_{2}n^{m−2} + O(n^{m−3}) .

By definition of m, at least one of u_{0}, v_{0}, w_{0} is non-zero. Further, let

a(n) = α_{N}n^{N} + α_{N−1}n^{N−1} + α_{N−2}n^{N−2} + O(n^{N−3})

with α_{N} ≠ 0. Then, by the Binomial Theorem,

a(n + 1) = α_{N} (n^{N} + Nn^{N−1} + \binom{N}{2}n^{N−2})
+ α_{N−1} (n^{N−1} + (N − 1)n^{N−2}) + α_{N−2}n^{N−2} + O(n^{N−3})

and

a(n + 2) = α_{N} (n^{N} + 2Nn^{N−1} + 4\binom{N}{2}n^{N−2})
+ α_{N−1} (n^{N−1} + 2(N − 1)n^{N−2}) + α_{N−2}n^{N−2} + O(n^{N−3}) .

We substitute these expansions into (2.1) and equate coefficients of like powers of n. The coefficient of n^{N+m} yields, after cancelling α_{N},

u_{0} + v_{0} + w_{0} = 0 .  (2.2)

If this condition is not fulfilled then (2.1) has no non-zero polynomial solution. Otherwise we proceed with the coefficient of n^{N+m−1}, use (2.2), cancel α_{N}, and find that

(2u_{0} + v_{0})N + u_{1} + v_{1} + w_{1} = 0 .  (2.3)

If 2u_{0} + v_{0} ≠ 0 then (2.3) determines a single possible value for N, and we are done. On the other hand, if

2u_{0} + v_{0} = 0  (2.4)

then we must also have

u_{1} + v_{1} + w_{1} = 0  (2.5)

or else (2.1) has no non-zero polynomial solution. If both (2.4) and (2.5) hold we continue with the coefficient of n^{N+m−2}. Here we find after using (2.2), (2.4), and (2.5), and after cancelling α_{N}, that

u_{0}N^{2} + (2u_{1} − u_{0} + v_{1})N + u_{2} + v_{2} + w_{2} = 0 .  (2.6)

Now u_{0} ≠ 0 or else it would follow from (2.2) and (2.4) that u_{0} = v_{0} = w_{0} = 0, contrary to our assumption. Therefore (2.6) determines at most two possible values for N.

Next we summarize this algorithm and, after giving an example, generalize it to recurrences of arbitrary order.

Algorithm Poly for d = 2

INPUT: Polynomials

p(n) = ∑_{j=0}^{m} u_{j}n^{m−j}, q(n) = ∑_{j=0}^{m} v_{j}n^{m−j}, r(n) = ∑_{j=0}^{m} w_{j}n^{m−j}

with coefficients in K such that at least one of u_{0}, v_{0}, w_{0} is non-zero.

OUTPUT: A basis B for the space of polynomial solutions over K of (2.1).

[1] If u_{0} + v_{0} + w_{0} ≠ 0 then D := ∅ else if u_{0} ≠ w_{0} then D := {N; (u_{0} − w_{0})N + u_{1} + v_{1} + w_{1} = 0} ∩ IN else if u_{1} + v_{1} + w_{1} ≠ 0 then D := ∅ else D := {N; u_{0}N^{2} + (u_{1} − u_{0} − w_{1})N + u_{2} + v_{2} + w_{2} = 0} ∩ IN.

[2] If D = ∅ then B := ∅

else k := max D; find a basis B for the space of polynomial solutions of (2.1) over K of degree at most k, using the method of undetermined coefficients.

[3] Return B and stop.

Example 2.2. The recurrence

n(n + 1)a(n + 2) − 2n(n + 100)a(n + 1) + (n + 99)(n + 100)a(n) = 0

has m = 2, u_{0} = w_{0} = u_{1} = 1, v_{0} = −2, v_{1} = −200, w_{1} = 199, u_{2} = v_{2} = 0, and w_{2} = 9900. Therefore u_{0} + v_{0} + w_{0} = u_{0} − w_{0} = u_{1} + v_{1} + w_{1} = 0, and the possible degrees are among the roots of

N^{2} − 199N + 9900 = 0 ,

which are N = 99 and N = 100. In fact, there exist polynomial solutions both of degree 99 and of degree 100, e.g., \binom{n+98}{99} and \binom{n+98}{100}.

Algorithm Poly for arbitrary d

INPUT: Polynomials

p_{i}(n) = ∑_{j=0}^{m} c_{i,j}n^{m−j}, for i = 0, 1, …, d ,  (2.7)

with coefficients in K such that at least one of c_{i,0}, 0 ≤ i ≤ d, is non-zero.

We assume that c_{i,j} = 0 when j < 0 or j > m.

OUTPUT: A basis B for the space of polynomial solutions over K of (1.2).

[1] Initialize s := −1.

[2] Repeat increment s by 1; for j = 0, 1, …, s compute

b_{j}^{(s)} := ∑_{i=0}^{d} i^{j}c_{i,s−j}  (2.8)

until ∃j ∈ {0, 1, …, s} such that b_{j}^{(s)} ≠ 0.

[3] Let D be the set of non-negative integer roots N of the polynomial

D(N) := ∑_{j=0}^{s} \binom{N}{j}b_{j}^{(s)} .  (2.9)

[4] If D = ∅ then B := ∅

else k := max D; find a basis B for the space of polynomial solutions of (1.2) over K of degree at most k, using the method of undetermined coefficients.

[5] Return B and stop.

We will call D(N) the degree polynomial of (1.2).

To prove correctness of algorithm Poly we must show that the loop in step [2] eventually terminates, that the set D is finite, and that the degree of any non-zero polynomial solution of recurrence (1.2) belongs to D. These facts are established by the following three lemmas.

Lemma 2.1. In algorithm Poly, s ≤ d at all times.

Proof. Assume that at some point s = s_{0}. Then b_{j}^{(s)} = 0 for 0 ≤ j ≤ s < s_{0}. In particular, b_{s}^{(s)} = 0 for 0 ≤ s < s_{0}. If s_{0} > d this implies that

b_{s}^{(s)} = ∑_{i=0}^{d} i^{s}c_{i,0} = 0 , for 0 ≤ s ≤ d .

Since det (i^{s})_{i,s=0}^{d} = V (0, 1, …, d) is a Vandermonde determinant it follows that c_{i,0} = 0 for i = 0, 1, …, d. But these are the coefficients of n^{m} in p_{i}(n), and by our assumption at least one of them is non-zero, a contradiction. □

Lemma 2.2. In algorithm Poly, D is a finite set.

Proof. By Lemma 2.1, the loop in step [2] terminates after at most d + 1 iterations. When this happens at least one of the b_{j}^{(s)} is non-zero, hence the degree polynomial (2.9) does not vanish identically and has a finite set of roots. It follows that D is finite. □

Lemma 2.3. Let s_{0} be the final value of s in algorithm Poly. Let

a(n) = ∑_{k=0}^{N_{0}} α_{k} n^{k}, where α_{N_{0}} ≠ 0  (2.10)

be a polynomial solution of recurrence (1.2). Then

∑_{j=0}^{s_{0}} \binom{N_{0}}{j}b_{j}^{(s_{0})} = 0  (2.11)

where b_{j}^{(s)} is as in (2.8).

Proof. By the Binomial Theorem,

a(n + i) = ∑_{k=0}^{N_{0}} α_{k} ∑_{l=0}^{k} \binom{k}{l}i^{k−l}n^{l} .  (2.12)

We adopt the convention that c_{i,j} = 0 and α_{k} = 0 whenever any of i, j, k are out of bounds indicated in (2.7) and (2.10). By substituting (2.7) and (2.12) into (1.1) we obtain

La = ∑_{i,j,k,l} c_{i,j}α_{k}\binom{k}{l}i^{k−l}n^{m+l−j}

where each summation index ranges over all integers and the order of summation can be chosen arbitrarily. Replacing j by r = m + l − j yields

La = ∑_{r} n^{r} ∑_{k} α_{k} ∑_{l} \binom{k}{l} ∑_{i} i^{k−l}c_{i,m+l−r} .

The coefficient of n^{r} can be written as

∑_{k} α_{k} ∑_{l} \binom{k}{l}b_{j}^{(s)}  (2.13)

where j = k−l and s = k+m−r. By definition of s_{0}, we have b_{j}^{(s)} = 0 for 0 ≤ j ≤ s < s_{0}. By our convention, this also holds when j > s since then c_{i,s−j} = 0. If j < 0 the binomial coefficient in (2.13) is zero; if j ≥ 0 and s < s_{0} then b_{j}^{(s)} = 0. So the inner sum in (2.13) vanishes whenever s < s_{0}, i.e., when k < s_{0} − m + r. On the other hand, α_{k} = 0 for k > N_{0}, hence the terms of the outer sum in (2.13) are zero unless s_{0} − m + r ≤ k ≤ N_{0}. As a consequence, (2.13) is zero unless r ≤ m + N_{0} − s_{0}, so

deg La ≤ m + N_{0} − s_{0} .

Now replace r by t = s_{0} − m + r. Then (2.13) can be rewritten as

∑_{k=t}^{N_{0}} α_{k} ∑_{l} \binom{k}{l}b_{k−l}^{(k−t+s_{0})} .  (2.14)

If La = 0 then (2.14) is zero for all values of t. In particular, for t = N_{0} we have

α_{N_{0}} ∑_{l} \binom{N_{0}}{l}b_{N_{0}−l}^{(s_{0})} = 0 .

After cancelling α_{N_{0}} and replacing l by j = N_{0} − l, this turns into (2.11). □

Remark 2.1. To implement Poly efficiently, we note that equating (2.14) to zero for t = N_{0}, N_{0} − 1, …, 0 gives a system of linear equations for the unknown coefficients α_{N_{0}}, α_{N_{0}−1}, …, α_{0} which is already in triangular form.

Remark 2.2. We can modify Poly so that it will find a basis for the affine space of polynomial solutions of the non-homogeneous recurrence (1.3). Let f = f(n) = ∑_{i=0}^{r} f_{i}n^{i} in (1.3) where r = deg f(n). In the proof of Lemma 2.3 we saw that either deg La = m + N_{0} − s_{0}, or deg La < m + N_{0} − s_{0} and (2.11) holds. Hence either N_{0} = r + s_{0} − m, or N_{0} is a non-negative integer root of the degree polynomial (2.9). Choosing the largest of these values as N_{0}, we find the unknown coefficients α_{i} from

∑_{k=t}^{N_{0}} α_{k} ∑_{l} \binom{k}{l}b_{k−l}^{(k−t+s_{0})} = f_{t+m−s_{0}} , for t = N_{0}, N_{0} − 1, …, 0 ,

which is a triangular system of linear equations.

3. A normal form for rational functions

The following lemma appears in Gosper (1978), though without mentioning properties (AC) and (BC).

Lemma 3.1. Let K be a field of characteristic zero and r(x) a non-zero rational function over K. Then there exists a non-zero constant Z ∈ K and monic polynomials A(x), B(x), and C(x) over K such that

r(x) = Z \frac{A(x)}{B(x)} \frac{C(x + 1)}{C(x)}  (3.1)

where

(i) gcd(A(x), B(x + k)) = 1 for every non-negative integer k, (AB) (ii) gcd(A(x), C(x)) = 1, (AC) (iii) gcd(B(x), C(x + 1)) = 1. (BC)

Proof. Let r(x) = p(x)/q(x) where p, q are polynomials over K with leading coefficients α and β, respectively. Let Z := α/β. Then r(x) ≠ 0 implies p(x) ≠ 0 which implies α ≠ 0 which in turn implies Z ≠ 0.

Denote by R(k) the resultant of p(x) and q(x + k) with respect to x. Let N be the largest non-negative integer root of R(k), or −1 if there is none. Construct polynomials p_{i}(x), q_{i}(x) for −1 ≤ i ≤ N inductively by

p_{−1}(x) = \frac{p(x)}{α}, q_{−1}(x) = \frac{q(x)}{β},

and for 0 ≤ i ≤ N,

s_{i}(x) = gcd(p_{i−1}(x), q_{i−1}(x + i)) ,
p_{i}(x) = \frac{p_{i−1}(x)}{s_{i}(x)} ,
q_{i}(x) = \frac{q_{i−1}(x)}{s_{i}(x − i)} .

Let

A(x) := p_{N}(x) ,
B(x) := q_{N}(x) ,
C(x) := ∏_{i=1}^{N} ∏_{k=1}^{i} s_{i}(x − k) .

Then

Z \frac{A(x)}{B(x)} \frac{C(x + 1)}{C(x)} = \frac{α}{β} \frac{p_{N}(x)}{q_{N}(x)} ∏_{i=1}^{N} ∏_{k=1}^{i} \frac{s_{i}(x − k + 1)}{s_{i}(x − k)}

= \frac{α}{β} \frac{p_{−1}(x)}{∏_{i=0}^{N} s_{i}(x)} \frac{∏_{i=0}^{N} s_{i}(x − i)}{q_{−1}(x)} ∏_{i=1}^{N} \frac{s_{i}(x)}{s_{i}(x − i)}

= \frac{αp_{−1}(x)}{βq_{−1}(x)} = \frac{p(x)}{q(x)} = r(x) .

Polynomials A(x), B(x), C(x) are monic by construction. Now we verify properties (AB), (AC), and (BC).

By definition of p_{k}, q_{k}, and s_{k},

gcd(p_{k}(x), q_{k}(x + k)) = gcd(\frac{p_{k−1}(x)}{s_{k}(x)}, \frac{q_{k−1}(x + k)}{s_{k}(x)}) = 1

for all k such that 0 ≤ k ≤ N. Let 0 ≤ k ≤ i, j ≤ N. Then p_{i}, p_{j} | p_{k} and q_{i}, q_{j} | q_{k}, therefore gcd(p_{i}(x), q_{j}(x + k)) | gcd(p_{k}(x), q_{k}(x + k)). Hence

gcd(p_{i}(x), q_{j}(x + k)) = 1 .  (3.2)

(AB): Setting i = j = N in (3.2), we see that A(x) and B(x + k) are relatively prime for all k such that 0 ≤ k ≤ N. By definition of N this implies that they are relatively prime for all k ≥ 0.

(AC): If A(x) and C(x) have a common factor then so do p_{N}(x) and s_{i}(x − k), for some i and k such that 1 ≤ k ≤ i ≤ N. Then p_{N}(x) and q_{i−1}(x + i − k) have a common factor, too, by definition of q_{i}. But as 0 ≤ i − k ≤ i − 1 < N, this contradicts (3.2).

(BC): If B(x) and C(x + 1) have a common factor then so do q_{N}(x) and s_{i}(x − k), for some i and k such that 0 ≤ k ≤ i − 1 ≤ N − 1. Then q_{N}(x) and p_{i−1}(x − k) have a common factor, too, by definition of p_{i}. Hence q_{N}(x + k) and p_{i−1}(x) have a common factor. But as 0 ≤ k ≤ i − 1 < N, this contradicts (3.2). □

Note that the proof of Lemma 3.1 actually gives an algorithm to compute (3.1). This algorithm utilizes gcd and resultant computations in K[x] and K[x, k], respectively.

Lemma 3.2. Let K be a field of characteristic zero. Let a(x), b(x), and c(x) be polynomials over K such that gcd(a(x), c(x)) = gcd(b(x), c(x + 1)) = 1. If

r(x) = \frac{a(x)}{b(x)} \frac{c(x + 1)}{c(x)}  (3.3)

and C(x) is related to r(x) as in Lemma 3.1, then c(x) divides C(x).

Proof. Use (3.1) to rewrite (3.3) as

ZA(x)b(x)c(x)C(x + 1) = a(x)B(x)C(x)c(x + 1) .  (3.4)

Let

g(x) := gcd(c(x), C(x)) ,  (3.5)
d(x) := c(x)/g(x) ,  (3.6)
D(x) := C(x)/g(x) .  (3.7)

Then gcd(d(x), D(x)) = gcd(a(x), d(x)) = gcd(b(x), d(x+1)) = 1. Cancelling g(x)g(x+1) from (3.4) gives

ZA(x)b(x)d(x)D(x + 1) = a(x)B(x)D(x)d(x + 1) .

It follows that

d(x) | B(x)d(x + 1) ,
d(x + 1) | A(x)d(x) .

Using this repeatedly we obtain

d(x) | B(x)B(x + 1) ⋯ B(x + k − 1)d(x + k) ,
d(x) | A(x − 1)A(x − 2) ⋯ A(x − k)d(x − k) ,

for all k ∈ IN. Since F has characteristic zero gcd(d(x), d(x+k)) = gcd(d(x), d(x−k)) = 1, for all large enough k. It follows that d(x) divides both B(x)B(x + 1) ⋯ B(x + k − 1) and A(x − 1)A(x − 2) ⋯ A(x − k) for all large enough k. But these two polynomials are relatively prime by the assumptions of the Lemma, so d(x) is constant. Hence c(x) divides C(x), by (3.6) and (3.5). □

Corollary 3.1. Factorization (3.1) described in Lemma 3.1 is unique.

Proof. Assume that

r(x) = Z \frac{A(x)}{B(x)} \frac{C(x + 1)}{C(x)} = z \frac{a(x)}{b(x)} \frac{c(x + 1)}{c(x)}  (3.8)

where A, B, C as well as a, b, c are monic polynomials satisfying properties (AB), (AC), and (BC) of Lemma 3.1. Then Z = z. By Lemma 3.2, c(x) divides C(x) and vice versa. As they are both monic, c(x) = C(x). Therefore A(x)b(x) = a(x)B(x). By property (AB) of Lemma 3.1, a(x) divides A(x) and vice versa, so a(x) = A(x) and b(x) = B(x). □

4. Hypergeometric solutions

Let K_{0} be a field of characteristic zero and K an extension field of K_{0}. Given a linear recurrence operator L with polynomial coefficients over K_{0}, we seek solutions of (1.2) which are hypergeometric over K. We will call K_{0} the coefficient field of the recurrence. We assume that there exist algorithms for finding integer roots of polynomials over K and for factoring polynomials over K into factors irreducible over K.

As with polynomial solutions, we consider first the second-order recurrence (2.1). Assume that a(n) is a hypergeometric solution of (2.1). Then there is a rational sequence S(n) such that a(n+1) = S(n)a(n). Substituting this into (2.1) and cancelling a(n) gives

p(n)S(n + 1)S(n) + q(n)S(n) + r(n) = 0 .

Let

S(n) = Z \frac{A(n)}{B(n)} \frac{C(n + 1)}{C(n)}

be the normal form for S(n) described in Lemma 3.1. Then

Z^{2}p(n)A(n+1)A(n)C(n+2)+Zq(n)B(n+1)A(n)C(n+1)+r(n)B(n+1)B(n)C(n) = 0 .

(4.1)

The first two terms contain A(n) as a factor, so A(n) divides r(n)B(n + 1)B(n)C(n). By properties (AB) and (AC) of the normal form, A(n) is relatively prime with C(n), B(n), and B(n + 1), so A(n) divides r(n). Similarly we find that B(n + 1) divides p(n)A(n + 1)A(n)C(n + 2), therefore by properties (AB) and (BC) of the normal form, B(n + 1) divides p(n). This leaves us with a finite set of candidates for A(n) and B(n), namely, the monic factors of r(n) and p(n − 1), respectively. We can cancel A(n)B(n + 1) from the coefficients of (4.1) to obtain

Z^{2} \frac{p(n)}{B(n + 1)}A(n + 1)C(n + 2) + Zq(n)C(n + 1) + \frac{r(n)}{A(n)}B(n)C(n) = 0 .  (4.2)

To determine the value of Z, we consider the leading coefficient of the left-hand side in (4.2) and find out that Z satisfies a quadratic equation with known coefficients. So given the choice of A(n) and B(n), there are at most two choices for Z.

For a fixed choice of A(n), B(n), and Z, we can use algorithm Poly to determine if (4.2) has any non-zero polynomial solution C(n). If yes, we have found a hypergeometric solution of (2.1). If (4.2) has no non-zero polynomial solution whatever the choice of A(n), B(n), and Z, then (2.1) has no hypergeometric solution.

Algorithm Hyper for d = 2

INPUT: Polynomials p(n), q(n), and r(n) over K_{0}; an extension field K of K_{0}.

OUTPUT: A hypergeometric solution of (2.1) over K if it exists; 0 otherwise.

[1] For all monic factors A(n) of r(n) and B(n) of p(n − 1) over K do:

P (n) := (p(n)/B(n + 1))A(n + 1);

Q(n) := q(n);

R(n) := (r(n)/A(n))B(n); m := max{deg P, deg Q, deg R}; let α, β, γ be the coefficients of n^{m} in P, Q, R, respectively;

for all non-zero Z ∈ K such that αZ^{2} + βZ + γ = 0 do:

If the recurrence

Z^{2}P (n)C(n + 2) + ZQ(n)C(n + 1) + R(n)C(n) = 0

has a non-zero polynomial solution C(n) over K then

S(n) := Z(A(n)/B(n))(C(n + 1)/C(n));

return a non-zero solution a(n) of a(n + 1) = S(n)a(n) and stop.

[2] Return 0 and stop.

Example 4.1. The recurrence

(n + 4)a(n + 2) + a(n + 1) − (n + 1)a(n) = 0

appears in Bender and Orszag (1978), p. 43, Example 2.3.5. The monic factors of r(n) are 1 and n + 1 and those of p(n − 1) are 1 and n + 3. Taking A(n) = B(n) = 1 leads to Z = ±1; however, algorithm Poly finds no non-zero polynomial solutions of the auxiliary recurrences. If exactly one of A(n), B(n) is equal to 1, the equation for Z is either Z = 0 or contradictory. Finally, the choice A(n) = n + 1, B(n) = n + 3 leads to Z = ±1 again. For Z = 1, the auxiliary recurrence is

(n + 2)C(n + 2) + C(n + 1) − (n + 3)C(n) = 0

with, up to a constant factor, unique polynomial solution C(n) = 1. This gives S(n) = (n + 1)/(n + 3) and

a(n) = \frac{1}{(n + 1)(n + 2)} .

For Z = −1, the auxiliary recurrence is

(n + 2)C(n + 2) − C(n + 1) − (n + 3)C(n) = 0

with, up to a constant factor, unique polynomial solution C(n) = 2n + 3. This gives S(n) = −((n + 1)/(n + 3))((2n + 5)/(2n + 3)) and

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

Example 4.2. The number d(n) of derangements of a set with n elements satisfies the recurrence

a(n) = (n − 1)a(n − 1) + (n − 1)a(n − 2) .  (4.3)

Taking A(n) = B(n) = 1 yields Z = −1, but the auxiliary recurrence has no non-zero polynomial solution. The remaining choice A(n) = n + 1, B(n) = 1 leads to Z^{2} − Z = 0, so Z = 1. The auxiliary recurrence

(n + 2)C(n + 2) − (n + 1)C(n + 1) − C(n) = 0

has, up to a constant factor, the only polynomial solution C(n) = 1. Then S(n) = n + 1 and, up to a constant factor,

a(n) = n!

is the only hypergeometric solution of (4.3). Using the well-known method of reduction of order, we find another fundamental solution (which happens to be precisely the number of derangements):

d(n) = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} .  (4.4)

Since this is not a constant multiple of n! (although it comes very close, being equal to the integer nearest to n!/e), we have proved that (4.4) is not a hypergeometric term. As the summand in (4.4) does not depend on n this can also be shown by Gosper’s algorithm.

Example 4.3. In van der Poorten (1979), it is shown that the numbers

a(n) = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2}  (4.5)

satisfy the recurrence

(n + 2)^{3}a(n + 2) − (2n + 3)(17n^{2} + 51n + 39)a(n + 1) + (n + 1)^{3}a(n) = 0 . (4.6)

Here all the coefficients are of the same degree, therefore the equation for Z will have no non-zero solution unless A(n) and B(n) are of the same degree as well. But they are both monic factors of (n + 1)^{3}, so they must be equal. Then P (n) = p(n), Q(n) = q(n), R(n) = r(n), and the equation for Z is Z^{2} − 34Z + 1 = 0 with solutions Z = 17 ± 12\sqrt{2}. In both cases the auxiliary recurrence has no non-zero polynomial solutions, proving that (4.6) has no hypergeometric solution. As a consequence, (4.5) is not hypergeometric.

Algorithm Hyper for arbitrary d

INPUT: Polynomials p_{i}(n) over K_{0}, for i = 0, 1, …, d; an extension field K of K_{0}.

OUTPUT: A hypergeometric solution of (1.2) over K if it exists; 0 otherwise.

[1] For all monic factors A(n) of p_{0}(n) and B(n) of p_{d}(n − d + 1) over K do:

P_{i}(n) := p_{i}(n) ∏_{j=0}^{i−1} A(n + j) ∏_{j=i}^{d−1} B(n + j), for i = 0, 1, …, d; m := max_{0≤i≤d} deg P_{i}(n); let α_{i} be the coefficient of n^{m} in P_{i}(n), for i = 0, 1, …, d;

for all non-zero Z ∈ K such that

∑_{i=0}^{d} α_{i}Z^{i} = 0  (4.7)

do:

If the recurrence

∑_{i=0}^{d} Z^{i}P_{i}(n)C(n + i) = 0  (4.8)

has a non-zero polynomial solution C(n) over K then

S(n) := Z(A(n)/B(n))(C(n + 1)/C(n));

return a non-zero solution a(n) of a(n + 1) = S(n)a(n) and stop.

[2] Return 0 and stop.

Theorem 4.1. Let a(n) be a non-zero solution of (1.2) such that a(n + 1) = S(n)a(n) where S(n) is a rational sequence. Let

S(n) = Z \frac{A(n)}{B(n)} \frac{C(n + 1)}{C(n)}  (4.9)

be the normal form described in Lemma 3.1. Let P_{i}(n) and α_{i}, for i = 0, 1, …, d, be defined as in algorithm Hyper. Then ∑_{i=0}^{d} α_{i}Z^{i} = 0, A(n) divides p_{0}(n), B(n) divides p_{d}(n − d + 1), and C(n) satisfies (4.8).

Conversely, if Z is an arbitrary constant, A(n) and B(n) arbitrary sequences, C(n) satisfies (4.8) where P_{i}(n), for i = 0, 1, …, d, is defined as in algorithm Hyper, and a(n + 1) = S(n)a(n) where S(n) is as in (4.9), then a(n) satisfies (1.2).

Proof. From (1.2) and a(n + 1) = S(n)a(n) it follows that

∑_{i=0}^{d} p_{i}(n) (∏_{j=0}^{i−1} S(n + j)) a(n) = 0 ,  (4.10)

hence after cancelling a(n) and using (4.9) we have

∑_{i=0}^{d} p_{i}(n)Z^{i} (∏_{j=0}^{i−1} \frac{A(n + j)}{B(n + j)}) \frac{C(n + i)}{C(n)} = 0 .  (4.11)

Multiplication by C(n) ∏_{j=0}^{d−1} B(n + j) now gives (4.8). All terms of the sum in (4.8) with i > 0 contain the factor A(n), thus A(n) divides the term with i = 0 which is p_{0}(n)C(n) ∏_{j=0}^{d−1} B(n + j). By properties (AB) and (AC) of the normal form, it follows that A(n) divides p_{0}(n). Similarly, B(n + d − 1) divides Z^{d}p_{d}(n)C(n + d) ∏_{j=0}^{d−1} A(n + j), hence by properties (AB) and (BC) of the normal form, B(n + d − 1) divides p_{d}(n), so B(n) divides p_{d}(n − d + 1). Finally, a look at the leading coefficient of the left-hand side of (4.8) shows that ∑_{i=0}^{d} α_{i}Z^{i} = 0.

To prove the converse, we retrace the steps which led from (1.2) through (4.10) and (4.11) to (4.8), in reverse order. □

Remark 4.1. Although the worst-case time complexity of Hyper is exponential in the degree of (1.2), a careful implementation can speed it up in several places. Here we give a few suggestions.

We can reduce the degree of recurrence (4.8) by cancelling the factor A(n)B(n+d−1), as we did in (4.2) for the case d = 2.

Observe that the coefficients of equation (4.7) which determines Z depend only on the difference D(A, B) = deg B(n)−deg A(n) and not on A(n) or B(n) themselves. Therefore it is advantageous to test pairs of factors A(n), B(n) in order of the value of D(A, B).

We can skip those values of D(A, B) for which (4.7) has a single non-zero term and thus no non-zero solution. For example, this happens when deg p_{d}(n) = deg p_{0}(n) ≥ deg p_{i}(n) for 0 ≤ i ≤ d, and D(A, B) ≠ 0. Hence in this case it suffices to test pairs A(n), B(n) of equal degree (cf. Examples 4.1 and 4.3).

We can skip all pairs A(n), B(n) which do not satisfy property (AB) of Lemma 3.1.

Example 4.4. The number i(n) of involutions of a set with n elements satisfies the recurrence

a(n) = a(n − 1) + (n − 1)a(n − 2) .

More generally, let r ≥ 2. The number i_{r}(n) of permutations which contain no cycles longer than r satisfies the recurrence

a(n) = a(n − 1) + (n − 1)a(n − 2) + (n − 1)(n − 2)a(n − 3) + …
+ (n − 1) ⋯ (n − r + 2)(n − r + 1)a(n − r)  (4.12)

(see, e.g., Wimp and Zeilberger (1985)). In Hyper, the degrees of the coefficients of auxiliary recurrences are obtained by adding to the degree sequence of the coefficients of the original recurrence (starting with the leading coefficient) an arithmetic progression with increment D = D(A, B). In case of (4.12), the degree sequence is 0, 0, 1, 2, …, r − 1. Adding to this sequence any arithmetic progression with integer increment D will produce a sequence with a single term of maximum value (the first one if D < 0; the last one if D ≥ 0), implying that (4.7) has a single non-zero term for all choices of A(n) and B(n). Therefore (4.12) has no hypergeometric solution. This example shows that for any d ≥ 2, there exist recurrences of order d without hypergeometric solutions. In particular, for r = 2 this means that the sum

i(n) = ∑_{k} \frac{n!}{(n − 2k)! 2^{k} k!} ,  (4.13)

(see, e.g., Comtet (1974)), is not a hypergeometric term.

Example 4.5. (Gessel et al., 1991) encountered the following sums when evaluating inversion polynomials of plane trees at q = −1 (see their paper for the relevant definitions):

f(n) = ∑_{k=0}^{n} \binom{3k}{k}\binom{3n − 3k}{n − k} ,  (4.14)

g(n) = ∑_{k=0}^{n−1} \binom{3k}{k}\binom{3n − 3k − 2}{n − k − 1} .  (4.15)

As shown by S.B. Ekhad using the algorithm of Zeilberger (1991), Lf = 0 and Mg = 0 where

L = 8(n + 2)(2n + 3)E^{2} − 6(36n^{2} + 99n + 70)E + 81(3n + 2)(3n + 4) ,
M = 16(n + 2)(2n + 3)(2n + 5)E^{3} − 12(2n + 3)(54n^{2} + 153n + 130)E^{2}
+ 324(27n^{3} + 72n^{2} + 76n + 30)E − 2187n(3n + 1)(3n + 2) ,

and E denotes the shift operator. Using Hyper on La = 0 we find that dim(KerL ∩ L(H_{K})) = 1. A fundamental hypergeometric solution is

x(n) = (\frac{27}{4})^{n}

(corresponding to A(n) = B(n) = C(n) = 1, Z = 27/4). Therefore L = L_{1}L_{2} where L_{1} = 2(n + 2)(2n + 3)E − 3(3n + 2)(3n + 4), and

L_{2} = 4E − 27 .  (4.16)

From this we obtain a second fundamental solution

y(n) = x(n) ∑_{k=0}^{n} \frac{\binom{3k}{k}}{3k − 1} (\frac{27}{4})^{−k} .

From f(0) = 1, f(1) = 6 we determine that

f(n) = (x(n) − y(n))/2 .  (4.17)

Also, f(n) satisfies the non-homogeneous first-order recurrence

4f(n + 1) − 27f(n) = −3\frac{\binom{3n+1}{n+1}}{2n + 1} .

Using Hyper on Ma = 0 we find that dim(KerM ∩ L(H_{K})) = 2. Two fundamental hypergeometric solutions are x(n) and

u(n) = \frac{27^{n}}{n\binom{2n}{n}}

(corresponding to A(n) = n, B(n) = n + 1/2, C(n) = 1, Z = 27/4). By means of these solutions we find that M = M_{1}M_{2}L_{2} where L_{2} is as in (4.16), M_{1} = 2(n + 2)(2n + 3)E − 3(3n + 1)(3n + 2), and M_{2} = 2(2n + 3)E − 27n. From this we obtain a third fundamental solution

v(n) = x(n) ∑_{k=0}^{n−1} \frac{\binom{3k}{k}}{2k + 1} (\frac{27}{4})^{−k} .

From g(1) = 1, g(2) = 7, g(3) = 48 we determine that for n ≥ 1,

g(n) = (3x(n) + v(n))/27 .  (4.18)

The fact that u(n) does not appear in (4.18) hints at existence of a second-order recurrence with polynomial coefficients satisfied by g(n). Indeed, we find that T g = 0 where T = 8(n + 1)(2n + 3)E^{2} − 6(36n^{2} + 63n + 31)E + 81(3n + 1)(3n + 2) = T_{1}L_{2}, with T_{1} = 2(n + 1)(2n + 3)E − 3(3n + 1)(3n + 2), and L_{2} as in (4.16). Also, g(n) satisfies the non-homogeneous first-order recurrence

4g(n + 1) − 27g(n) = \frac{\binom{3n}{n}}{2n + 1} .

Observe that (4.17) and (4.18) are identities which express f(n) and g(n) in terms of sums whose summand does not depend on n, in contrast to their definitions in (4.14) and (4.15).

We conclude that neither f(n) nor g(n) belongs to L(H_{K}).

Example 4.6. Consider the recurrence

n(n + 1)a(n + 2) − 2n(n + k + 1)a(n + 1) + (n + k)(n + k + 1)a(n) = 0  (4.19)

over the field Q^{|}(k) where k is transcendental over Q^{|}. Since its degree polynomial D(N) = (N − k)(N − k − 1) has no integer roots, (4.19) has no polynomial solutions. However, Hyper succeeds with Z = 1, A(n) = n + k, B(n) = n, and C(n) any linear polynomial. Thus we find two fundamental hypergeometric solutions, say, (k + 1)\overline{n−1}/(n − 1)! and (k + 2)\overline{n−2}/(n − 2)! where

k\overline{n} = ∏_{i=0}^{n−1}(k + i)

is the rising power. If we substitute a non-negative integer value for k these solutions can be written as \binom{n+k−1}{k} and \binom{n+k−1}{k+1}, respectively. It follows that for every specific nonnegative integer k all solutions of (4.19) are polynomial over Q^{|}; cf. Example 2.2 which is a special case with k = 99.

5. Ramifications of Hyper

5.1. Linear combinations of hypergeometric terms

Sometimes hypergeometric terms are used to define the notion of “closed form”, but this leaves out such nice sequences as 2^{n} − 1. The class L(H_{K}) is larger and has more closure properties than H_{K}, while still being acceptable as a paradigm for “closed form”. Algorithm Hyper can be modified to find a basis for the space of all those solutions of (1.2) which belong to L(H_{K}).

Proposition 5.1. Let L be as in (1.1), and let a be a hypergeometric term such that La ≠ 0. Then La is hypergeometric and similar to a.

Proof. Let r := Ea/a. Then E^{i}a = E^{i−1}(ra) = (E^{i−1}r)(E^{i−1}a) = (∏_{j=0}^{i−1} E^{j}r) a, so

La = ∑_{i=0}^{d} p_{i}E^{i}a = (∑_{i=0}^{d} p_{i} ∏_{j=0}^{i−1} E^{j}r) a

is a non-zero rational multiple of a. □

Proposition 5.2. Every sequence from L(H_{K}) can be written as a sum of pairwise dissimilar hypergeometric terms.

Proof. Since the sum of two similar hypergeometric terms is either hypergeometric or zero, the desired representation can be achieved by grouping together similar terms. □

Theorem 5.1. Let S be a non-empty set of hypergeometric terms. If S is linearly dependent over R_{K} then S contains two similar hypergeometric terms.

Proof. Let S ⊆ H_{K} be linearly dependent over R_{K}. We prove the assertion by induction on |S|.

If |S| = 1 then S is not linearly dependent over R_{K}. If |S| > 1, let S′ = {a_{1}, a_{2}, …, a_{m}} be a minimal subset of S which is linearly dependent over R_{K}. Then there exist non-zero elements r_{1}, r_{2}, …, r_{m} ∈ R_{K} such that ∑_{i=1}^{m} r_{i}a_{i} = 0. Let b_{i} := r_{i}a_{i}, for i = 1, 2, …, m. Then b_{i} ∈ H_{K}, and

∑_{i=1}^{m} b_{i} = 0 .  (5.1)

For i = 1, 2, …, m, let s_{i} := Eb_{i}/b_{i}. Apply E to (5.1), multiply (5.1) by s_{m}, then subtract the resulting equations to find

∑_{i=1}^{m−1}(s_{i} − s_{m})b_{i} = 0 .  (5.2)

If s_{i} = s_{m} for some i then b_{i} and b_{m} are constant multiples of each other, hence a_{i} and a_{m} are similar. Otherwise all terms in (5.2) are hypergeometric. By induction hypothesis there exist j and k, j ≠ k, such that (s_{j} − s_{m})b_{j} and (s_{k} − s_{m})b_{k} are similar. But then so are a_{j} and a_{k}. □

Corollary 5.1. Let L be a linear recurrence operator with polynomial coefficients, and a ∈ L(H_{K}) such that La = 0. If a = ∑_{i=1}^{k} a_{i} where a_{i} are pairwise dissimilar hypergeometric terms then

La_{i} = 0, for i = 1, 2, …, k .

Proof. By Proposition 5.1, for each i there exists a rational sequence r_{i} such that La_{i} = r_{i}a_{i}. Therefore

0 = La = ∑_{i=1}^{k} La_{i} = ∑_{i=1}^{k} r_{i}a_{i} .

Since the a_{i} are pairwise dissimilar Theorem 5.1 implies that r_{i} = 0, for all i. □

Corollary 5.2. Let L be a linear recurrence operator with polynomial coefficients. Then the space KerL ∩ L(H_{K}) has a basis in H_{K}.

Proof. Let a ∈ L(H_{K}) satisfy La = 0. By Proposition 5.2, we can write a = ∑_{i=1}^{k} a_{i} where a_{i} are pairwise dissimilar hypergeometric terms. By Corollary 5.1, each a_{i} satisfies La_{i} = 0. It follows that hypergeometric solutions of (1.2) span the space of solutions from L(H_{K}). To obtain a basis for KerL ∩ L(H_{K}), select a maximal linearly independent set of hypergeometric solutions of (1.2). □

Proposition 5.3. Let r, h, h_{i}, C, C_{i} be non-zero sequences from S_{K} such that

\frac{h(n + 1)}{h(n)} = r(n)\frac{C(n + 1)}{C(n)} ,  (5.3)

\frac{h_{i}(n + 1)}{h_{i}(n)} = r(n)\frac{C_{i}(n + 1)}{C_{i}(n)} , for i = 1, 2, …, k ,  (5.4)

and C is a K-linear combination of C_{i}. Then h is a K-linear combination of h_{i}.

Proof. From (5.3) and (5.4) it follows that there are constants α, α_{i} ∈ K and j_{0} ∈ IN such that

h(n) = α ( ∏_{j=j_{0}}^{n−1} r(j)) C(n)

and

h_{i}(n) = α_{i} ( ∏_{j=j_{0}}^{n−1} r(j)) C_{i}(n) , for i = 1, 2, …, k .

Let C = ∑_{i=1}^{k} λ_{i}C_{i} where λ_{i} ∈ K. Then

h(n) = ∑_{i=1}^{k} α_{i} ( ∏_{j=j_{0}}^{n−1} r(j)) λ_{i}C_{i}(n) = ∑_{i=1}^{k} α\frac{λ_{i}}{α_{i}} h_{i}(n) .

□

Modify Hyper so that it will not stop after finding one hypergeometric solution but will rather test all possible choices of A(n), B(n), and Z. Return all hypergeometric solutions h which satisfy h(n + 1) = S(n)h(n) where S(n) = Z \frac{A(n)}{B(n)} \frac{C(n+1)}{C(n)} and C is a basic polynomial solution found by Poly on the corresponding auxiliary recurrence. From Theorem 4.1, Corollary 5.2, and Proposition 5.3 it follows that this modified algorithm will produce a generating set for the space of solutions which belong to L(H_{K}). In general, this will not be a basis because the same hypergeometric solution may be obtained from several auxiliary recurrences. One can prune this set until it becomes a basis, testing for linear dependence by means of the Casoratian determinant.

Another way to obtain such a basis is to find one hypergeometric solution with Hyper, then reduce the order of the recurrence, recursively find the corresponding basis for the reduced recurrence, and use Gosper’s algorithm to put the antidifferences of these solutions into closed form if possible. This method will actually yield a larger class of solutions (cf. Examples 4.2 and 4.5).

5.2. Non-homogeneous recurrences

In this subsection we show how to solve (1.3) over L(H_{K}) when f ≠ 0.

Proposition 5.4. Up to the order of the terms, the representation of sequences from L(H_{K}) as sums of pairwise dissimilar hypergeometric terms is unique.

Proof. Assume that a_{1}, a_{2}, …, a_{k} and b_{1}, b_{2}, …, b_{m} are pairwise dissimilar hypergeometric terms with

∑_{i=1}^{k} a_{i} = ∑_{j=1}^{m} b_{j} .  (5.5)

Using induction on k + m we prove that k = m and that each a_{i} equals some b_{j}. If k + m = 0 this holds trivially. Let k + m > 0. Then by Theorem 5.1 it follows that k > 0, m > 0, and some a_{i} is similar to some b_{j}. Relabel the terms so that a_{k} is similar to b_{m}, and let h := a_{k} − b_{m}. If h ≠ 0 then we can use induction hypothesis both on ∑_{i=1}^{k−1} a_{i} + h = ∑_{j=1}^{m−1} b_{j} and ∑_{i=1}^{k−1} a_{i} = ∑_{j=1}^{m−1} b_{j} − h, to find that k = m − 1 and k − 1 = m. This contradiction shows that h = 0, so a_{k} = b_{m} and ∑_{i=1}^{k−1} a_{i} = ∑_{j=1}^{m−1} b_{j}. By induction hypothesis, k = m and each a_{i} with 1 ≤ i ≤ k − 1 equals some b_{j} with 1 ≤ j ≤ m − 1. □

If a ∈ L(H_{K}) and La = f then f ∈ L(H_{K}), by Proposition 5.1. Let a = ∑_{j=1}^{m} a_{j} and f = ∑_{j=1}^{k} f_{j} where a_{j} and f_{j} are pairwise dissimilar hypergeometric terms. Without loss of generality assume that there is an l ≤ m such that La_{j} ≠ 0 if and only if j ≤ l. Then by Proposition 5.4, l = k and we can relabel the f_{j} so that

La_{j} = f_{j} , for j = 1, 2, …, k .  (5.6)

By Proposition 5.1, there are non-zero rational sequences r_{j} such that a_{j} = r_{j}f_{j}, for j = 1, 2, …, k. Let s_{j} := Ef_{j}/f_{j}. With L as in (1.1), it follows from (5.6) that r_{j} satisfies

L_{j}r_{j} = 1 , for j = 1, 2, …, k  (5.7)

where

L_{j} = ∑_{i=0}^{d} p_{i} (∏_{l=0}^{i−1} E^{l}s_{j}) E^{i} , for j = 1, 2, …, k .

This gives the following algorithm for solving (1.3) over L(H_{K}):

1. Write f = ∑_{j=1}^{k} f_{j} where f_{j} are pairwise dissimilar hypergeometric terms.

2. For j = 1, 2, …, k, find a non-zero rational solution r_{j} of (5.7) using the algorithm of Abramov (1989b). If none exists for some j then (1.3) has no solution in L(H_{K}).

3. Use Hyper to find a basis a_{1}, a_{2}, …, a_{m} for the space KerL ∩ L(H_{K}).

4. Return ∑_{j=1}^{m} C_{j}a_{j} + ∑_{j=1}^{k} r_{j}f_{j} where C_{j} are arbitrary constants.

Note that step 2 could also be carried out by means of Hyper, since any solution of a non-homogeneous recurrence with hypergeometric right-hand side satisfies a homogeneous recurrence of one-higher order. However, we prefer Abramov’s algorithm for this task in order to avoid exhaustive search for suitable monic factors of the two sentinel coefficients of the recurrence.

It remains to explain how to perform step 1. We need to group together similar hypergeometric terms, so we need to decide if a given hypergeometric term is rational. The following lemma gives an algorithm for this.

Lemma 5.1. Let h ∈ H_{K} and r := Eh/h. Let

r(n) = Z \frac{A(n)}{B(n)} \frac{C(n + 1)}{C(n)}

and

\frac{B(n)}{A(n)} = \frac{a(n)}{b(n)} \frac{c(n + 1)}{c(n)}  (5.8)

be the normal forms for r(n) and B(n)/A(n), as described in Lemma 3.1. Then h ∈ R_{K} if and only if Z = a(n) = b(n) = 1.

Proof. If Z = a(n) = b(n) = 1 then r(n) = c(n)C(n + 1)/(c(n + 1)C(n)), so h(n) = αC(n)/c(n) where α ∈ K is some constant. Hence h is rational.

Conversely, assume that h(n) = p(n)/q(n) where p, q are relatively prime polynomials. Let

\frac{h(n + 1)}{h(n)} = \frac{q(n)}{q(n + 1)} \frac{p(n + 1)}{p(n)} = Z \frac{A(n)}{B(n)} \frac{C(n + 1)}{C(n)}  (5.9)

as in Lemma 3.1. Obviously, Z = 1. By Lemma 3.2, p(n) divides C(n). Write C(n) = p(n)s(n) where s(n) is a polynomial. Then from (5.9)

\frac{B(n)}{A(n)} = \frac{q(n + 1)}{q(n)} \frac{s(n + 1)}{s(n)} .

By Corollary 3.1, normal form (5.8) is unique. So c(n) = q(n)s(n) and a(n) = b(n) = 1.

□

5.3. Computing in algebraic extensions

Observe that all computation in algorithm Poly takes place in the coefficient field K_{0} of the recurrence. Therefore the basic polynomial solutions found by Poly constitute a basis for the space of polynomial solutions over any extension field K of K_{0}.

On the other hand, algorithm Hyper used on (1.2) requires factorization of the leading and trailing coefficients of (1.2), as well as of polynomials encountered in (4.7). This factorization has to be performed in the field K over which we seek hypergeometric solutions.

Example 5.1. The Fibonacci recurrence

a(n + 2) − a(n + 1) − a(n) = 0  (5.10)

has no hypergeometric solution over Q^{|} but it has two basic hypergeometric solutions, (\frac{1+\sqrt{5}}{2})^{n} and (\frac{1−\sqrt{5}}{2})^{n}, over Q^{|}(\sqrt{5}). This is the splitting field of polynomial (4.7) of the recurrence, namely Z^{2} − Z − 1.

Example 5.2. Similarly, the recurrence

a(n + 2) − (2n + 1)a(n + 1) + (n^{2} − 5)a(n) = 0

has no hypergeometric solution over Q^{|} while it has two basic hypergeometric solutions, (+\sqrt{5})\overline{n} and (−\sqrt{5})\overline{n}, over Q^{|}(\sqrt{5}). This time, Q^{|}(\sqrt{5}) is the splitting field of the trailing coefficient of the recurrence, n^{2} − 5.

The proof of correctness of Hyper shows that if (1.2) has a hypergeometric solution in some extension K of the coefficient field K_{0}, then a constant multiple of it belongs to the splitting field of the sentinel coefficients of (1.2) and of polynomials (4.7). Thus computing in the algebraic closure of K_{0} will produce all hypergeometric solutions of recurrences over K_{0}.

However, suppose that a is a sequence over K_{0}. The next theorem shows that to determine if a is hypergeometric over some extension K of K_{0} it is sufficient to answer this question for K = K_{0}.

Theorem 5.2. Let K_{0} be a field of characteristic zero and K an extension field of K_{0}. Let a be a sequence over K_{0}. If a is rational (respectively hypergeometric) over K then a is rational (respectively hypergeometric) over K_{0}.

Proof. Let a(n) = r(n) for n ≥ n_{0} where r is rational over K. Let r = p/q where p and q are polynomials over K of respective degrees k and m, and q is monic. Then

p(n) − a(n)q(n) = 0, for n = n_{0}, n_{0} + 1, …, n_{0} + k + m  (5.11)

is a system of linear equations over K_{0} for the coefficients of p and q. Since (5.11) has a non-trivial solution in K, its determinant is zero. It follows that (5.11) has a non-trivial solution in K_{0}. The number of equations in (5.11) exceeds the degrees of both p or q, therefore any non-trivial solution must have both p and q non-zero. So there are non-zero polynomials p′ and q′ over K_{0} of respective degrees k′ ≤ k and m′ ≤ m such that

p′(n)q(n) − p(n)q′(n) = 0, for n = n_{0}, n_{0} + 1, …, n_{0} + k + m .

The left-hand side is a polynomial of degree not exceeding k + m which has k + m + 1 distinct zeros. It follows that p′q = pq′, so r = p/q = p′/q′ is rational over K_{0}.

If a is hypergeometric over K then Ea/a is rational over K. By the preceding paragraph, Ea/a is rational over K_{0}, hence a is hypergeometric over K_{0}. □

For example, to prove that the sequence of Fibonacci numbers is not hypergeometric over any field of characteristic zero, it suffices to show that (5.10) has no hypergeometric solution over Q^{|}.

It is interesting to observe that in recurrences arising in combinatorics the leading and trailing coefficients often factor completely over Q^{|}; cf. Examples 4.3, 4.4, and 4.5.

Acknowledgements

This work is part of author’s Ph.D. Thesis, Petkovšek (1990). The author wishes to thank his advisor, Dana Scott, as well as Herb Wilf for their invaluable encouragement and support. He is also indebted to Bruce Sagan who corrected several errors in a preliminary version, and to István Nemes for many fruitful discussions.

References

Abramov, S.A. (1989a). Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations. Moscow Univ. Comput. Math. Cybernet. no. 3, 63–68. Transl. from Vestn. Moskov. univ. Ser. XV. Vychisl. mat. kibernet. no. 3, 56–60.

Abramov, S.A. (1989b). Rational solutions of linear differential and difference equations with polynomial coefficients. U.S.S.R. Comput. Maths. Math. Phys. 29 7–12. Transl. from Zh. vychisl. mat. mat. fiz. 29 1611–1620.

Bender, C.M., Orszag, S.A. (1978). Advanced Mathematical Methods for Scientists and Engineers. New

York: McGraw-Hill. Cohn, R.M. (1965). Difference Algebra. New York: Interscience Publishers. Comtet, L. (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions. Dordrecht-

Holland: D. Reidel Publ. Co. Transl. of Analyse Combinatoire, Tomes I et II , Presses Universitaires de France, Paris 1970.

Gessel, I.M., Sagan, B.E., Yeh, Y.-N. (1991). Enumeration of trees by inversions. Submitted. Gosper, R.W., Jr. (1978). Decision procedure for indefinite hypergeometric summation. Proc. Natl. Acad.

Sci. USA 75, 40–42. Petkovšek, M. (1991). Finding Closed-Form Solutions of Difference Equations by Symbolic Methods.

Ph.D. Thesis. Pittsburgh PA: Carnegie Mellon University, CMU-CS-91-103. van der Poorten, A. (1979). A proof that Euler missed… Apéry’s proof of the irrationality of ζ(3). Math.

Intelligencer 1, 195–203. Stanley, R.P. (1980). Differentiably finite power series. European J. Combin. 1, 175–188. Wilf, H.S., Zeilberger, D. (1992). An algorithmic proof theory for hypergeometric (ordinary and “q”)

multisum/integral identities. To appear. Wimp, J., Zeilberger, D. (1985). Resurrecting the asymptotics of linear recurrences. J. Math. Anal. Appl.

111, 162–176. Zeilberger, D. (1990). A holonomic systems approach to special functions identities. J. Comput. Appl.

Math. 32, 321–368. Zeilberger, D. (1991). The method of creative telescoping. J. Symb. Comput. 11, 195–204.