Proof of a Conjecture of Wilf and Zeilberger

S. A. Abramov^{∗}

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

           abramov@ccas.ru

M. Petkovšek^{†}

Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia

                                          marko.petkovsek@uni-lj.si

Abstract

Wilf and Zeilberger conjectured in 1992 that a hypergeometric term is properhypergeometric if and only if it is holonomic. We prove a version of this conjecture in the case of two discrete variables.

1 Introduction

Let K be a field of characteristic zero, n_{1}, …, n_{d} integer-valued variables, and E_{i} the corresponding shift operators, acting on functions of n_{1}, …, n_{d} by E_{i}f(n_{1}, …, n_{i}, …, n_{d}) = f(n_{1}, …, n_{i} + 1, …, n_{d}). A K-valued function T (n_{1}, …, n_{d}) is a hypergeometric term if there are rational functions R_{i} ∈ K(n_{1}, …, n_{d}) such that E_{i}T = R_{i}T, for i = 1, …, d. T (n_{1}, …, n_{d}) is holonomic if partial derivatives of its generating function ∑_{n_{1},...,n_{d}≥0} T (n_{1}, …, n_{d})x_{1}^{n_{1}} ⋯ x_{d}^{n_{d}} lie in a finite-dimensional vector space over the rational function field K(x_{1}, …, x_{d}). A holonomic sequence satisfies a system of homogeneous linear recurrences of a special form. If T is holonomic then its definite sums w.r.t. some of the variables are still holonomic as functions of the remaining variables. If T is also hypergeometric then the holonomic recurrences satisfied by these sums can be found efficiently by means of Zeilberger’s Creative Telescoping algorithm [13, 14, 11].

A function T (n_{1}, …, n_{d}) is a proper-hypergeometric term if it can be expressed as a product of a polynomial with several factorials of linear forms with integer coefficients, their reciprocals, and exponential functions. In [12] it is proved that proper-hypergeometric terms are holonomic. Wilf and Zeilberger conjectured [11, p. 585] that a hypergeometric term is proper if and only if it is holonomic. Their conjecture concerns proper-hypergeometric terms which depend on several discrete and continuous variables. We prove (a slightly modified version of) their conjecture in the case of two discrete variables (d = 2).

∗Partially supported by the French-Russian Lyapunov Institute under grant 98-03.

†Partially supported by MZT RS under grant J2-8549.

Let T (n, k) be a bivariate hypergeometric term which satisfies the hypergeometric recurrences T (n+1, k) = F (n, k)T (n, k) and T (n, k+1) = G(n, k)T (n, k) where F and G are rational functions. If T is nontrivial (meaning that its support cannot be annihilated by a nonzero polynomial) then F and G satisfy the obvious compatibility relation F (x, y)G(x + 1, y) = F (x, y + 1)G(x, y). The cornerstone of our proof is Theorem 8 which says that compatible rational functions F and G can be factored as F (x, y) = F′(x, y)R(x + 1, y)/R(x, y) and G(x, y) = G′(x, y)R(x, y + 1)/R(x, y) where F′ and G′ factor into integer-linear factors (i.e., polynomials of the form ax + by + c where a, b are integers), and R is a rational function. From this we deduce that there is a rational sequence R and a nontrivial proper term T′ such that T is equivalent to the product RT′ (meaning that they satisfy the same hypergeometric recurrences). If, in addition, T is holonomic then (using a variation of rising factorials called the nowhere-zero rising factorials) we show that R itself must be holonomic. This, however, implies that the denominator of R also factors into integer-linear factors. Consequently R, and hence RT′, are proper terms. This yields our main result: Every bivariate holonomic hypergeometric term is equivalent to a nontrivial proper term (Theorem 12).

Throughout the paper, K is a field of characteristic zero, and ℕ denotes the set of nonnegative integers. Following [4], we write p ⊥ q to indicate that polynomials p, q ∈ K[x, y] are relatively prime.

We define the rising factorial (a)_{n} for all a ∈ K and n ∈ ℤ by

(a)_{n} = \{ \begin{matrix}∏_{i=0}^{n−1}(a + i), & n ≥ 0, \\ ∏_{i=1}^{|n|} \frac{1}{a − i}, & n < 0 and a ∉ \{1, 2, …, |n|\}, \\ 0, & otherwise. \end{matrix}

Let Z(a) be the set of all n ∈ ℤ such that (a)_{n} = 0. Obviously,

Z(a) = \{ \begin{matrix}\{n ∈ ℤ; n + a ≤ 0\}, & a ∈ ℤ and a > 0, \\ \{n ∈ ℤ; n + a > 0\}, & a ∈ ℤ and a ≤ 0, \\ ∅, & otherwise. \end{matrix}

Note that (a + n)_{−n} serves as a kind of a pseudo-inverse for (a)_{n}, in the following sense:

• if (a)_{n} ≠ 0 then (a + n)_{−n} = 1/(a)_{n},

• if (a)_{n} = 0 then (a + n)_{−n} = 0.

It is easy to verify that the sequence (a)_{n} satisfies the first-order recurrence

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

for all n ∈ ℤ. We will also need another solution of (1) which is nonzero for all a ∈ K and n ∈ ℤ. We call it the nowhere-zero rising factorial or nrf(a, n). It is defined as the usual rising factorial, except that zero factors are omitted wherever they appear:

nrf(a, n) = \{ \begin{matrix}(a)_{n}, & (a)_{n} ≠ 0, \\ (a)_{1−a}(0)_{a+n}, & a ∈ ℤ and a > 0 and a + n ≤ 0, \\ (a)_{−a}(1)_{a+n−1}, & a ∈ ℤ and a ≤ 0 and a + n > 0. \end{matrix}

Again we have

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

but now

nrf(a + n, −n) = \frac{1}{nrf(a, n)}

for all n ∈ ℤ as well.

Remark 1 Proper hypergeometric terms are usually defined in terms of factorials of complex argument, with z! denoting Γ(z + 1) and 1/z! defined to be zero when z is a negative integer. If n is an integer variable and α ∈ ℂ, we can rewrite the sequence (n + α)! with rising factorials as

(n + α)! = \{ \begin{matrix}α! (α + 1)_{n}, & α ∉ ℤ, \\ (1)_{n+α}, & α ∈ ℤ \end{matrix}  (2)

whenever the left-hand side is defined (i.e., n+α is not a negative integer), and its reciprocal as

\frac{1}{(n + α)!} = \{ \begin{matrix}\frac{(n+α+1)_{−n}}{α!} , & α ∉ ℤ, \\ (n + α + 1)_{−(n+α)}, & α ∈ ℤ. \end{matrix}  (3)

Wilf and Zeilberger [10] associate with (n + α)! its shadow

\frac{(−1)^{n}}{(−n − α − 1)!}

which satisfies the same first-order recurrence w.r.t. n. When α ∉ ℤ the shadow is just a constant-factor multiple of (n + α)! (the constant being −(sin απ)/π), while for α ∈ ℤ the shadow is complementary to (n + α)!, in the sense that the latter is defined when n + α ≥ 0, and the former when n + α < 0.

If we replace the rising factorials in the right-hand side of (2) by their nowhere-zero counterparts, nothing changes for α ∉ ℤ, but for α ∈ ℤ we have instead of (1)_{n+α}

nrf(1, n + α) = \{ \begin{matrix}(1)_{n+α} & = & (n + α)!, & n + α ≥ 0, \\ (0)_{n+α+1} & = & \frac{(−1)^{n+α+1}}{(−n−α−1)!}, & n + α < 0. \end{matrix}

Thus rewriting factorials in terms of the nowhere-zero rising factorials, we either get the factorial itself, or its shadow (perhaps with the opposite sign), whichever is defined. The advantage of rising factorials over ordinary ones is that the former do not rely on the Γfunction, and can be used in any field.

2 Bivariate sequences

By a sequence T (n, k) we mean a function T : ℕ×ℕ → K. We call a set A ⊆ ℕ×ℕ algebraic if there is a polynomial p ∈ K[x, y] \ {0} which vanishes on A. Clearly, if A is algebraic and B is not, then B \ A is not algebraic. Also, a finite union of algebraic sets is algebraic.

Proposition 1 Let F, G ∈ K(x, y) be rational functions which agree on a non-algebraic set B ⊆ ℕ × ℕ. Then F = G.

Proof: Let F = p/q, G = u/v, where p, q, u, v ∈ K[x, y]. The polynomial pv − qu vanishes on the non-algebraic set B, hence it is the zero polynomial, and so F = G. □

Definition 1 (equality modulo an algebraic set) We write T =_{a} T′ if the sequences T (n, k) and T′(n, k) agree outside some algebraic set. A sequence T (n, k) is trivial if T =_{a} 0.

Equality modulo an algebraic set is clearly an equivalence relation. It is also a congruence because T_{1} =_{a} T_{2} and T′_{1} =_{a} T′_{2} imply T_{1} +T′_{1} =_{a} T_{2} +T′_{2} and T_{1}T′_{1} =_{a} T_{2}T′_{2}. Trivial sequences can be described as those with algebraic support. Note however that a nontrivial sequence can vanish on a non-algebraic set.

Example 1 The sequence T (n, k) = \binom{n}{k} is nontrivial because supp T = \{(n, k) ∈ ℕ×ℕ; n ≥ k} is not algebraic. But neither is its complement {(n, k) ∈ ℕ × ℕ; n < k}.

Definition 2 A sequence T (n, k) is a hypergeometric term if there are polynomials f_{0}, f_{1}, g_{0}, g_{1} ∈ K[x, y] \ {0} such that

f_{1}(n, k)T (n + 1, k) = f_{0}(n, k)T (n, k),  (4)
g_{1}(n, k)T (n, k + 1) = g_{0}(n, k)T (n, k)  (5)

for all n, k ∈ ℕ. Two hypergeometric terms T_{1}, T_{2} are equivalent if they satisfy (4) and (5) with the same f_{0}, f_{1}, g_{0}, g_{1}. In this case we write T_{1} ∼ T_{2}.

Clearly the product of two hypergeometric terms is again a hypergeometric term, and if T_{1} ∼ T_{2}, T′_{1} ∼ T′_{2} then T_{1}T′_{1} ∼ T_{2}T′_{2}.

Proposition 2 If T is a hypergeometric term and T′ =_{a} T then T′ is a hypergeometric term and T′ ∼ T.

Proof: Let T satisfy (4), (5) and let p(n, k)T′(n, k) = p(n, k)T (n, k) for all n, k ∈ ℕ. Then

p(n, k)p(n + 1, k)f_{1}(n, k)T′(n + 1, k) = p(n, k)p(n + 1, k)f_{0}(n, k)T′(n, k),  (6)
p(n, k)p(n, k + 1)g_{1}(n, k)T′(n, k + 1) = p(n, k)p(n, k + 1)g_{0}(n, k)T′(n, k)  (7)

for all n, k ∈ ℕ, hence T′ is a hypergeometric term. Clearly T (n, k) also satisfies (6), (7), so T′ ∼ T. □

Identification of bivariate sequences which agree outside an algebraic set is consistent with identification of univariate sequences which agree outside a finite set (cf. [8]). Such identification enables us to regard every rational function R ∈ K(x, y) as a sequence R(n, k), without actually having to specify its values at the singular points of R. Therefore, if T is a hypergeometric term satisfying (4), (5), we can write

T (n + 1, k) =_{a} F (n, k)T (n, k), T (n, k + 1) =_{a} G(n, k)T (n, k),  (8)

where F = f_{0}/f_{1} and G = g_{0}/g_{1}.

Definition 3 Two rational functions F, G ∈ K(x, y) are compatible if they satisfy

F (x, y) G(x + 1, y) = F (x, y + 1) G(x, y).  (9)

Proposition 3 Let T (n, k) be a hypergeometric term which satisfies (8). If T ≠_{a} 0 then

(i) F and G are compatible,

(ii) F and G are unique.

Proof: (i) By (8) we have

T (n + 1, k + 1) = F (n, k + 1)T (n, k + 1) = F (n, k + 1)G(n, k)T (n, k)
= G(n + 1, k)T (n + 1, k) = G(n + 1, k)F (n, k)T (n, k)

for (n, k) outside some algebraic set A. Hence F (n, k + 1)G(n, k) = G(n + 1, k)F (n, k) on supp T \ A. As this is a non-algebraic set, Proposition 1 implies that F (x, y + 1)G(x, y) = G(x + 1, y)F (x, y).

(ii) Assume that in addition to (8), T (n + 1, k) =_{a} F_{1}(n, k)T (n, k) and T (n, k + 1) =_{a} G_{1}(n, k)T (n, k). Then F (n, k) = F_{1}(n, k) and G(n, k) = G_{1}(n, k) on supp T \ A, for some algebraic set A. By Proposition 1, F = F_{1} and G = G_{1}. □

The converse of (i) also holds (see Theorem 9 below).

Obviously every hypergeometric term is equivalent to every trivial term. But when restricted to nontrivial terms, the relation of equivalence ∼ is transitive, and hence indeed an equivalence relation:

Proposition 4 Let T_{1}, T_{2}, T_{3} be hypergeometric terms such that T_{1} ∼ T_{2}, T_{2} ∼ T_{3}. If T_{2} ≠_{a} 0 then T_{1} ∼ T_{3}.

Proof: This follows from Proposition 3(ii). □

Definition 4 Let K((x, y)) denote the field of fractions of the formal power series ring K[[x, y]]. A sequence T (n, k) is holonomic if the set of all partial derivatives of its generating function ∑_{n,k≥0} T (n, k)x^{n}y^{k} spans a finite-dimensional subspace of K((x, y)) over the subield of rational functions K(x, y).

Theorem 1 [5, Thm. 3.7] A sequence T (n, k) is holonomic if and only if there is an s ∈ ℕ such that

(i) there are nonempty sets H_{1}, H_{2} ⊆ {0, …, s}^{2} and polynomials p_{i,j}, q_{u,v} ∈ K[x] \ {0} such that

∑_{(i,j)∈H_{1}} p_{i,j}(n) T (n − i, k − j) = 0,  (10)
∑_{(u,v)∈H_{2}} q_{u,v}(k) T (n − u, k − v) = 0  (11)

for all n, k ≥ s, and (ii) each univariate sequence a_{i}(k) = T (i, k) with 0 ≤ i < s and b_{j}(n) = T (n, j) with

0 ≤ j < s satisfies a homogeneous linear recurrence with polynomial coefficients in k resp. n.

Recurrences of the type (10) and (11) are called k-free and n-free, respectively.

Theorem 2 The product of two holonomic sequences is holonomic.

For a proof, see [5, Thm. 3.8(i)] or [12, Prop. 3.2’].

Definition 5 A sequence T (n, k) is a factorial term if there are u, v ∈ K, p, q ∈ ℕ, α ∈ K^{p+q}, and a, b, c ∈ ℤ^{p+q} such that

T (n, k) = u^{n}v^{k} ∏_{i=1}^{p}(α_{i})_{a_{i}n+b_{i}k+c_{i}} ∏_{i=p+1}^{p+q}(α_{i} + a_{i}n + b_{i}k)_{−(a_{i}n+b_{i}k+c_{i})}  (12)

for all n, k ∈ ℕ.

Definition 6 A sequence T (n, k) is a proper term if there is a polynomial P ∈ K[x, y] and a factorial term T′ such that

T (n, k) = P (n, k) T′(n, k)  (13)

for all n, k ∈ ℕ.

Theorem 3 Every proper term is hypergeometric and holonomic.

Proof: Let T (n, k) be a proper term. Each factor of T (n, k) is hypergeometric, by using (1) repeatedly. Hence T (n, k) is hypergeometric.

Similarly, each factor of T (n, k) satisfies a recurrence with constant coefficients, which is n-free and k-free at the same time. This is clear for the polynomial factor P (n, k) (if r = deg_{n} P (n, k) then Δ_{n}^{r+1}P (n, k) = 0), as well as for the exponential factors u^{n} and v^{k}. If f(n, k) = (α)_{an+bk+c} or f(n, k) = (α + an + bk)_{−(an+bk+c)} then f(n + b, k − a) = f(n, k). Also, by using (1) repeatedly we see that each univariate sequence f_{i}(k) = f(i, k) and f_{j}(n) = f(n, j) satisfies a recurrence with polynomial coefficients. Thus by Theorem 1, each factor of T (n, k) is holonomic, hence by Theorem 2, so is T (n, k). □

For factorial terms, this result can be found in [9], and for proper terms in [12, 11, 7].

Example 2 Consider the sequence

T (n, k) = \{ \begin{matrix}(n − 2k)!, & n > 2k, \\ 3^{k}, & n = 2k, \\ \frac{(−1)^{n−2k}}{(2k−n−1)!}, & n < 2k. \end{matrix}

Then T (n + 1, k) =_{a} (n − 2k + 1)T (n, k) and (n − 2k)(n − 2k − 1)T (n, k + 1) =_{a} T (n, k), so T is hypergeometric. It is also holonomic, because it satisfies condition (i) of Theorem 1 with the recurrence T (n + 4, k + 2) − 4T (n + 2, k + 1) + 3T (n, k) = 0 (condition (ii) is obviously satisfied as well), but it seems unlikely that T is proper. However, note that T is equivalent to the nontrivial proper terms T_{1}(n, k) = (1)_{n−2k} and T_{2}(n, k) = (−1)^{n−2k}(2k − n)_{n−2k+1}.

Note that the definitions of hypergeometric, holonomic, factorial, and proper terms are all symmetric in n and k. Hence if T (n, k) has one of these properties, so does T (k, n), and vice versa.

3 A normal form for rational functions

In this section E denotes the shift operator corresponding to x, so that Ef(x) = f(x + 1) for every f ∈ K(x).

Theorem 4 For every rational function F ∈ K(x) there are polynomials a, b, c ∈ K[x] such that

(i) F = \frac{a}{b} · \frac{Ec}{c},

(ii) a ⊥ E^{k}b for all k ∈ ℕ,

(iii) a ⊥ c and b ⊥ Ec.

For a proof, see [6] or [7]. The original version of this theorem (without (iii)) is due to Gosper [3].

Definition 7 If a, b, c, F satisfy (i) and (ii) of Theorem 4, then (a, b, c) is a polynomial normal form or PNF of F. A PNF which satisfies (iii) of Theorem 4 is strict.

Lemma 1 If (a, b, c) is a strict PNF of p/q where p, q ∈ K[x], then a | p and b | q.

Proof: We have pbc = aqEc, hence a | pbc and b | aqEc. By (ii) and (iii), a ⊥ bc and b ⊥ aEc, so a | p and b | q. □

In place of (ii), we need a somewhat stronger property that a ⊥ E^{k}b for all k ∈ ℤ. To this end we allow c to be a rational function.

Definition 8 A rational function u = a/b where a, b ∈ K[x] is shift-reduced if a ⊥ E^{k}b for all k ∈ ℤ.

Theorem 5 For every rational function F ∈ K(x) there are rational functions u, v ∈ K(x) such that

(i) F = u · \frac{Ev}{v},

(ii) u is shift-reduced.

Proof: If F = 0 take u = 0, v = 1. Otherwise let (a, b, c) be a PNF of F, and (a_{1}, b_{1}, c_{1}) a strict PNF of b/a. We claim that taking u = b_{1}/a_{1}, v = c/c_{1} satisfies (i) and (ii). Indeed,

\frac{b_{1}}{a_{1}} · \frac{E(c/c_{1})}{c/c_{1}} = \frac{b_{1}}{a_{1}} · \frac{c_{1}}{Ec_{1}} · \frac{Ec}{c} = \frac{a}{b} · \frac{Ec}{c} = F,

proving (i). Because a_{1} ⊥ E^{k}b_{1} for k ≥ 0, we have b_{1} ⊥ E^{k}a_{1} for k ≤ 0. By Lemma 1, a_{1} | b and b_{1} | a. As a ⊥ E^{k}b for k ≥ 0, it follows that b_{1} ⊥ E^{k}a_{1} for k ≥ 0 as well, proving (ii). □

Definition 9 If u, v, F are as in Theorem 5, (u, v) is a rational normal form, or RNF, of F.

4 Products of integer-linear polynomials

Lemma 2 Let f ∈ K(x), a ∈ K, a ≠ 0. If f(x + a) = f(x) then f(x) = c ∈ K.

Proof: Write f(x) = p(x)/q(x) where p, q ∈ K[x]. Let x_{0} ∈ K be such that q(x_{0} + ka) ≠ 0 for all k ∈ ℕ. By induction on k, f(x_{0} + ka) = f(x_{0}) for all k ∈ ℕ. Write c = f(x_{0}). Then r(x) = p(x) − c q(x) ∈ K[x] vanishes on {x_{0} + ka; k ∈ ℕ}. In characteristic zero this is an infinite set, hence r is the zero polynomial, and f(x) = c as claimed. □

Lemma 3 Let P ∈ K[x, y], a, b ∈ K, a ≠ 0. If P (x + a, y + b) = P (x, y) then there is a univariate polynomial f ∈ K[x] such that P (x, y) = f(bx − ay).

Proof: By induction on deg_{y} P.

• deg_{y} P = 0: Write P (x, y) = p(x). Then p(x + a) = p(x), so p(x) = c ∈ K by Lemma 2. Take f(x) = c.

• deg_{y} P > 0: By induction on k it follows that P (x + ka, y + kb) = P (x, y) for all k ∈ ℕ. In particular, P (ka, kb) = P (0, 0) for all k ∈ ℕ. Denote w = P (0, 0). Dividing P (x, y)−w by bx−ay in K[x, y] (w.r.t. lexicographic order on monomials with x ≺ y), we have

P (x, y) − w = Q(x, y)(bx − ay) + R(x)  (14)

where Q ∈ K[x, y] and R ∈ K[x]. Also, deg_{y} Q = deg_{y} P −1. Set x = ka and y = kb in (14) to see that R(ka) = 0 for all k ∈ ℕ, hence R(x) = 0 and P (x, y)−w = Q(x, y)(bx− ay). Substituting x+a for x and y+b for y yields P (x, y)−w = Q(x+a, y+b)(bx−ay), so Q(x, y)(bx − ay) = Q(x + a, y + b)(bx − ay). As K[x, y] is an integral domain, Q(x + a, y + b) = Q(x, y). By the induction hypothesis there is a g ∈ K[x] such that Q(x, y) = g(bx − ay). We conclude that P (x, y) = f(bx − ay) where f(x) = xg(x) + w.

□

Corollary 1 Assume that K is algebraically closed. Let P ∈ K[x, y] \ K be irreducible, a, b ∈ K, a ≠ 0. If P (x + a, y + b) = P (x, y) then there are u ∈ K \ {0}, v ∈ K such that P (x, y) = u(bx − ay + v).

Proof: By Lemma 3, there is an f ∈ K[x] such that P (x, y) = f(bx−ay). As P is irreducible, so is f, hence deg f ≤ 1. Thus there are u, w ∈ K such that f(x) = ux+w and, consequently, P (x, y) = u(bx − ay) + w. As P is nonconstant, we have u ≠ 0. Taking v = w/u proves the claim. □

Definition 10 A polynomial p ∈ K[x, y] is integer-linear if p(x, y) = ax + by + c where a, b ∈ ℤ and c ∈ K.

Theorem 6 Let K be algebraically closed, and P ∈ K[x, y]. If for every irreducible factor p of P there are a, b ∈ ℤ, a > 0, such that p(x + a, y + b) also divides P (x, y) then P factors into integer-linear factors.

Proof: By induction on the total degree of P.

• deg P = 0: If P is constant then it is integer-linear.

• deg P > 0: Pick a nonconstant irreducible factor p_{0} of P. Construct a sequence of nonconstant irreducible factors p_{i} of P such that p_{i+1}(x, y) = p_{i}(x + a_{i}, y + b_{i}) where a_{i}, b_{i} ∈ ℤ and a_{i} > 0, for i ≥ 0. As K[x, y] is a unique factorization domain, there are indices i_{0} < j_{0} such that p_{i_{0}} = c p_{j_{0}} for some c ∈ K \ {0}. By definition of p_{i}, it follows that

p_{i_{0}}(x, y) = c p_{i_{0}}(x + A, y + B)  (15)

where A = a_{i_{0}} + a_{i_{0}+1} + ⋯ + a_{j_{0}−1} > 0 and B = b_{i_{0}} + b_{i_{0}+1} + ⋯ + b_{j_{0}−1} are integers. Order monomials lexicographically and compare the leading coefficients in (15) to determine that c = 1. By Corollary 1, there are u, v ∈ K, u ≠ 0, such that p_{i_{0}}(x, y) = u(Bx − Ay + v). Let

P (x, y) = q_{1}(x, y)q_{2}(x, y) ⋯ q_{r}(x, y)

be a factorization of P into irreducibles, and S = {i; q_{i}(x, y) = u(Bx − Ay + w), for some u, w ∈ K, u ≠ 0}. Clearly S ≠ ∅. Write P = QR where Q(x, y) = ∏_{i∈S} q_{i}(x, y). Then Q factors into integer-linear factors and Q ⊥ R. Let p be an irreducible factor of R. Then there are a, b ∈ ℤ, a > 0, such that p(x + a, y + b) also divides P (x, y). If p(x+a, y +b) divides Q(x, y) then p(x+a, y +b) = u(Bx−Ay +w), for some u, w ∈ K, u ≠ 0. But then p | Q which is impossible. Thus p(x + a, y + b) must divide R(x, y). Also, deg R < deg P. By induction hypothesis, R factors into integer-linear factors, hence so does P = QR. □

A different proof using algebraic functions is given in [2, Lemma 3].

5 A structure theorem for hypergeometric terms

The following property of divisibility in K[x, y] will be used without mention.

Proposition 5 Let p, q ∈ K[x, y], p irreducible. Then p | q in K[x, y] if and only if p | q in K(x)[y].

Proof: Let p ∈ K[x, y] be irreducible. The only units of K[x, y] are the nonzero constants, hence p is primitive when considered as an element of K[x][y]. Thus divisibility by p is not affected when the coefficient ring K[x] is replaced by its field of fractions K(x). □

Theorem 7 [1] Let a, b, u, v ∈ K[x] \ {0}, u ⊥ v, r = u/v, p an irreducible factor of v, and

a(x)r(x + 1) = b(x)r(x).  (16)

Then there are m, n ∈ ℕ, m ≥ 1, n ≥ 0, such that p(x+m) divides a(x) and p(x−n) divides b(x).

Proof: Rewrite (16) as

a(x)u(x + 1)v(x) = b(x)u(x)v(x + 1).  (17)

Let m ∈ ℕ, m ≥ 1, be such that p(x + m − 1) divides v(x) but p(x + m) does not. Then (17) implies that p(x + m) | a(x)u(x + 1)v(x). As p(x + m) ⊥ u(x + 1)v(x), it follows that p(x + m) | a(x).

Let n ∈ ℕ, n ≥ 0, be such that p(x − n) divides v(x) but p(x − n − 1) does not. Then (17) implies that p(x − n) | b(x)u(x)v(x + 1). As p(x − n) ⊥ u(x)v(x + 1), it follows that p(x − n) | b(x). □

Theorem 8 Let F, G ∈ K(x, y) be compatible rational functions over an algebraically closed field K. Then there are compatible rational functions F′, G′ ∈ K(x, y) which factor into integer-linear factors, and a rational function R ∈ K(x, y) such that

F (x, y) = F′(x, y)\frac{R(x + 1, y)}{R(x, y)},  (18)
G(x, y) = G′(x, y)\frac{R(x, y + 1)}{R(x, y)}.  (19)

Proof: Take an RNF (G′, R) of G(x, y), considered as a rational function of y over K(x). Then G′(x, y) is shift-reduced w.r.t. y and satisfies (19). Define F′(x, y) so that it satisfies (18). The compatibility condition (9) for F, G implies that

F′(x, y) G′(x + 1, y) = F′(x, y + 1) G′(x, y),  (20)

so F′, G′ are compatible. It remains to show that they factor into integer-linear factors. Write

F′(x, y) = \frac{s(x, y)}{t(x, y)}, G′(x, y) = \frac{u(x, y)}{v(x, y)}  (21)

where s, t, u, v ∈ K[x, y], s(x, y) ⊥ t(x, y), and u(x, y) ⊥ v(x, y + m) for all m ∈ ℤ. We use two lemmas.

Lemma 4 Let F′, G′, s, t, u, v be as in (20), (21). If p ∈ K[x, y] is an irreducible factor of uv then there are A, B ∈ ℤ, A > 0, such that p(x + A, y + B) divides st.

Proof: a) If p | v rewrite (20) as

s(x, y)t(x, y + 1)G′(x + 1, y) = s(x, y + 1)t(x, y)G′(x, y).

By Theorem 7, there is m ∈ ℤ, m ≥ 1, such that

p(x + m, y) | s(x, y)t(x, y + 1).

Then p(x + m, y) | s(x, y) or p(x + m, y − 1) | t(x, y). Take (A, B) = (m, 0) in the former case, (A, B) = (m, −1) in the latter. b) If p | u rewrite (20) as

s(x, y + 1)t(x, y)\frac{1}{G′(x + 1, y)} = s(x, y)t(x, y + 1)\frac{1}{G′(x, y)}.

By Theorem 7, there is m ∈ ℤ, m ≥ 1, such that

p(x + m, y) | s(x, y + 1)t(x, y).

Then p(x + m, y − 1) | s(x, y) or p(x + m, y) | t(x, y). Take (A, B) = (m, −1) in the former case, (A, B) = (m, 0) in the latter. □

Lemma 5 Let F′, G′, s, t, u, v be as in (20), (21) where G′(x, y) is shift-reduced w.r.t. y. If q ∈ K[x, y] is an irreducible factor of st then there is C ∈ ℤ such that q(x, y + C) divides uv.

Proof: a) If q | t rewrite (20) as

u(x, y)v(x + 1, y)F′(x, y + 1) = u(x + 1, y)v(x, y)F′(x, y).

By Theorem 7, there are m, n ∈ ℤ such that

q(x, y + m) | u(x, y)v(x + 1, y) and q(x, y − n) | u(x + 1, y)v(x, y).

Since u/v is shift-reduced w.r.t. y it follows that q(x, y + m) | u(x, y) or q(x, y − n) | v(x, y). Take C = m in the former case, C = −n in the latter.

b) If q | s rewrite (20) as

u(x + 1, y)v(x, y)\frac{1}{F′(x, y + 1)} = u(x, y)v(x + 1, y)\frac{1}{F′(x, y)}.

By Theorem 7, there are m, n ∈ ℤ such that

q(x, y + m) | u(x + 1, y)v(x, y) and q(x, y − n) | u(x, y)v(x + 1, y).

Since u/v is shift-reduced w.r.t. y it follows that q(x, y + m) | v(x, y) or q(x, y − n) | u(x, y). Take C = m in the former case, C = −n in the latter. □

Proof of Thm. 8 (cont’d): If p is an irreducible factor of uv then by Lemma 4, there are A, B ∈ ℤ, A > 0, such that p(x + A, y + B) divides st. By Lemma 5, there is C ∈ ℤ such that p(x + A, y + B + C) divides uv. Hence by Theorem 6, uv factors into integer-linear factors.

If q is an irreducible factor of st then by Lemma 5, there is C ∈ ℤ such that q(x, y + C) divides uv. By Lemma 4, there are A, B ∈ ℤ, A > 0, such that q(x + A, y + B + C) divides st. Hence by Theorem 6, st factors into integer-linear factors.

This shows that u, v, s, t, and hence F′ and G′, factor into integer-linear factors. □

Definition 11 A hypergeometric term T over K is a Z-term over K if the polynomials f_{0}, f_{1}, g_{0}, g_{1} in (4) factor into integer-linear factors.

Corollary 2 Let T (n, k) be a hypergeometric term over an algebraically closed field K. Then there is a rational function R ∈ K(x, y) and a Z-term T′(n, k) such that T (n, k) =_{a} R(n, k)T′(n, k).

Proof: Let F, G ∈ K(x, y) be such that T (n + 1, k) =_{a} F (n, k)T (n, k) and T (n, k + 1) =_{a} G(n, k)T (n, k), and let R, F′, G′ ∈ K(x, y) be the rational functions associated with F, G by Theorem 8. Define

T′(n, k) =_{a} \frac{T (n, k)}{R(n, k)}.

Then T (n, k) =_{a} R(n, k)T′(n, k) and

T′(n + 1, k) =_{a} \frac{T (n + 1, k)}{R(n + 1, k)} =_{a} F (n, k)\frac{R(n, k)}{R(n + 1, k)} · \frac{T (n, k)}{R(n, k)} =_{a} F′(n, k)T′(n, k),

T′(n, k + 1) =_{a} \frac{T (n, k + 1)}{R(n, k + 1)} =_{a} G(n, k)\frac{R(n, k)}{R(n, k + 1)} · \frac{T (n, k)}{R(n, k)} =_{a} G′(n, k)T′(n, k).

As F′, G′ factor into integer-linear factors, T (n, k) is a Z-term. □

6 Existence of hypergeometric solutions

Definition 12 A rational function f ∈ K(x, y) is uniform of type (a, b) if there is a univariate rational function F ∈ K(x) and relatively prime integers a, b such that f(x, y) = F (ax + by).

Lemma 6 Let F, G ∈ K(x, y) be compatible rational functions which are both uniform of type (a, b). Then there exists a nowhere-zero sequence T (n, k) such that T (n + 1, k) =_{a} F (n, k)T (n, k) and T (n, k + 1) =_{a} G(n, k)T (n, k).

Proof: As F, G are uniform of type (a, b), there are univariate rational functions F_{1}, G_{1} ∈ K(x) such that F (x, y) = F_{1}(ax + by) and G(x, y) = G_{1}(ax + by). W.l.g. assume that a > 0 (if a = 0, consider F (y, x) and G(y, x)). Let f(x, y) = F (x − 1, y), g(x, y) = G(x, y − 1), f_{1}(x) = F_{1}(x − a), g_{1}(x) = G_{1}(x − b). Then f(x, y) = f_{1}(ax + by) and g(x, y) = g_{1}(ax + by). As F and G are compatible, we have

f(x, y − 1) g(x, y) = f(x, y) g(x − 1, y).  (22)

Denote by U the set of all integer zeroes and poles of f_{1} and g_{1}, and let

V = U ∪ {0}, m = min V, M = max V.

We distinguish two cases. a) b ≥ 0 : Let

T (n, k) = \{ \begin{matrix}1, & an ≤ M, \\ ∏_{M/a<i≤n} f(i, 0) ∏_{j=1}^{k} g(n, j), & an > M. \end{matrix}

By definition of M, T (n, k) is well-defined and nonzero for all n, k ≥ 0. By construction,

T (n, k) = g(n, k)T (n, k − 1) (an > M, k > 0).  (23)

We claim that

T (n, k) = f(n, k)T (n − 1, k) (an > M + a).  (24)

The proof is by induction on k. For k = 0, (24) holds by construction. For k > 0 we compute

T (n, k) = g(n, k)T (n, k − 1) = g(n, k) \frac{T (n, k − 1)}{T (n − 1, k − 1)}T (n − 1, k − 1)
= g(n, k)\frac{f(n, k − 1)}{g(n − 1, k)}T (n − 1, k) = f(n, k)T (n − 1, k),

using (23), the induction hypothesis, and (22).

Now let p(x) = ∏_{i=a}^{M+a}(ax − i) and q(x) = ∏_{i=0}^{M}(ax − i). Then

p(n)T (n, k) = p(n)f(n, k)T (n − 1, k) (n ≥ 1, k ≥ 0),
q(n)T (n, k) = q(n)g(n, k)T (n, k − 1) (n ≥ 0, k ≥ 1).

Shifting n resp. k by 1, we see that T (n + 1, k) =_{a} F (n, k)T (n, k) and T (n, k + 1) =_{a} G(n, k)T (n, k) as asserted.

b) b < 0 : Let

T (n, k) = \{ \begin{matrix}1, & m ≤ an + bk ≤ M, \\ ∏_{M/a<i≤n} f(i, 0) ∏_{j=1}^{k} g(n, j), & an + bk > M, \\ ∏_{m/b<j≤k} g(0, j) ∏_{i=1}^{n} f(i, k), & an + bk < m. \end{matrix}

By definition of M and m, T (n, k) is well-defined and nonzero for all n, k ≥ 0. By construction,

T (n, k) = f(n, k)T (n − 1, k)  (25)

when an + bk < m, n > 0, and

T (n, k) = g(n, k)T (n, k − 1)  (26)

when an + bk > M, k > 0. We claim that (25) also holds when an + bk > M + a, n > 0, and (26) when an + bk < m + b, k > 0. The proof is by induction on k resp. n.

First, assume that an + bk > M + a. For k = 0, (25) holds by construction. For k > 0 we obtain (25) by the same calculation as in case a), using (26), the induction hypothesis, and (22).

Second, assume that an + bk < m + b. For n = 0, (26) holds by construction. For n > 0 we compute

T (n, k) = f(n, k)T (n − 1, k) = f(n, k) \frac{T (n − 1, k)}{T (n − 1, k − 1)}T (n − 1, k − 1)
= f(n, k)\frac{g(n − 1, k)}{f(n, k − 1)}T (n, k − 1) = g(n, k)T (n, k − 1),

using (25), the induction hypothesis, and (22).

Now let p(x, y) = ∏_{i=m}^{M+a}(ax + by − i) and q(x, y) = ∏_{i=m+b}^{M}(ax + by − i). Then

p(n, k)T (n, k) = p(n, k)f(n, k)T (n − 1, k) (n ≥ 1, k ≥ 0),
q(n, k)T (n, k) = q(n, k)g(n, k)T (n, k − 1) (n ≥ 0, k ≥ 1).

Shifting n resp. k by 1, we see that T (n + 1, k) =_{a} F (n, k)T (n, k) and T (n, k + 1) =_{a} G(n, k)T (n, k). □

Theorem 9 Let F, G ∈ K(x, y) be compatible rational functions. Then there exists a nowhere-zero sequence T (n, k) such that T (n + 1, k) =_{a} F (n, k)T (n, k) and T (n, k + 1) =_{a} G(n, k)T (n, k).

Proof: By Theorem 8, there are compatible rational functions F′, G′ ∈ K(x, y) which factor into integer-linear factors, and a rational function R ∈ K(x, y) such that (18) and (19) hold. Let F′(x, y) = F_{1}(x, y)F_{2}(x, y) ⋯ F_{m}(x, y) and G′(x, y) = G_{1}(x, y)G_{2}(x, y) ⋯ G_{m}(x, y) be factorizations of F and G such that F_{i}, G_{i}, and F_{i}G_{i} are uniform rational functions for 1 ≤ i ≤ m, while F_{i}F_{j}G_{i}G_{j} is not uniform for 1 ≤ i < j ≤ m. Then it follows from the unique factorization of polynomials in K[x, y] that F_{i} and G_{i} are compatible for each i, hence by Lemma 6 there are nowhere-zero sequences T_{i}(n, k) such that T_{i}(n + 1, k) =_{a} F_{i}(n, k)T_{i}(n, k) and T_{i}(n, k + 1) =_{a} G_{i}(n, k)T_{i}(n, k), for i = 1, 2, …, m. Define

T (n, k) = R(n, k) ∏_{i=1}^{m} T_{i}(n, k).

Then T (n, k) vanishes at most on an algebraic set A. Furthermore,

T (n + 1, k) =_{a} R(n + 1, k) ∏_{i=1}^{m} T_{i}(n + 1, k)
=_{a} \frac{R(n + 1, k)}{R(n, k)} ∏_{i=1}^{m} F_{i}(n, k) ∏_{i=1}^{m} T_{i}(n, k) R(n, k) =_{a} F (n, k)T (n, k),
T (n, k + 1) =_{a} R(n, k + 1) ∏_{i=1}^{m} T_{i}(n, k + 1)
=_{a} \frac{R(n, k + 1)}{R(n, k)} ∏_{i=1}^{m} G_{i}(n, k) ∏_{i=1}^{m} T_{i}(n, k) R(n, k) =_{a} G(n, k)T (n, k).

We can redefine T (n, k) on A to make it nowhere-zero, while preserving the validity of these equations. □

7 Holonomic hypergeometric terms

Definition 13 A Z-term T is uniform of type (a, b) if there are univariate rational functions F, G ∈ K(x) and relatively prime integers a, b such that

T (n + 1, k) =_{a} F (an + bk)T (n, k), T (n, k + 1) =_{a} G(an + bk)T (n, k).  (27)

Theorem 10 If K is algebraically closed, any uniform term T (n, k) is equivalent to a nontrivial factorial term.

Proof: Let T (n, k) be a uniform term of type (a, b). W.l.g. assume that T is nontrivial and that a > 0 (if a = 0, consider T (k, n)). As a, b ∈ ℤ are relatively prime, there are c, d ∈ ℤ such that

ac + bd = 1.

Using (27) repeatedly, we find that for fixed u ∈ ℕ,

T (n + u, k) =_{a} F_{u}(an + bk)T (n, k),
T (n − u, k) =_{a} F_{−u}(an + bk)T (n, k),

where F_{u}(x) = ∏_{i=0}^{u−1} F (x + ia) and F_{−u}(x) = 1/ ∏_{i=1}^{u} F (x − ia) are univariate rational functions. Similarly,

T (n, k + u) =_{a} G_{u}(an + bk)T (n, k),
T (n, k − u) =_{a} G_{−u}(an + bk)T (n, k),

where G_{u}(x) = ∏_{j=0}^{u−1} G(x + jb) and G_{−u}(x) = 1/ ∏_{j=1}^{u} G(x − jb) are univariate rational functions. Let

T′(n, k) = T (cn + bk, dn − ak)  (28)

be a K-valued function defined on the integer cone cn + bk ≥ 0, dn − ak ≥ 0. Then

T′(n + 1, k) = T (cn + bk + c, dn − ak + d)
=_{a} F_{c}(n + bd)T (cn + bk, dn − ak + d)
=_{a} F_{c}(n + bd)G_{d}(n)T′(n, k),

T′(n, k + 1) = T (cn + bk + b, dn − ak − a)
=_{a} F_{b}(n − ab)T (cn + bk, dn − ak − a)
=_{a} F_{b}(n − ab)G_{−a}(n)T′(n, k).

Denote f(x) = F_{c}(x + bd)G_{d}(x) and g(x) = F_{b}(x − ab)G_{−a}(x). Then

T′(n + 1, k) =_{a} f(n)T′(n, k),  (29)
T′(n, k + 1) =_{a} g(n)T′(n, k).  (30)

The compatibility condition (9) applied to T reads F (ax + by)G(ax + by + a) = F (ax + by + b)G(ax + by), or, writing x for ax + by,

F (x) = F (x + b)\frac{G(x)}{G(x + a)}.  (31)

If b = 0, (31) and Lemma 2 imply that G(x) is constant. If b > 0 we have

g(x) = F_{b}(x − ab)G_{−a}(x) = \frac{F (x − ab)F (x − ab + a) ⋯ F (x − a)}{G(x − b)G(x − 2b) ⋯ G(x − ab)}
= \frac{F (x − ab + b)F (x − ab + a + b) ⋯ F (x − a + b)}{G(x − b)G(x − 2b) ⋯ G(x − ab + b)G(x)}
= g(x + b)

by using (31) on each factor in the numerator of the first fraction. If b < 0 a similar argument shows that g(x) = g(x + b) as well. Thus in all three cases, g(x) is constant. Factoring f(x) over K we can write

f(x) = u ∏_{i=1}^{p}(x + α_{i}) ∏_{i=p+1}^{p+q}(x + α_{i})^{−1},
g(x) = v,

where u, v ∈ K, p, q ∈ ℕ, and α_{i} ∈ K. Then

H′(n, k) = u^{n}v^{k} ∏_{i=1}^{p}(α_{i})_{n} ∏_{i=p+1}^{p+q}(α_{i} + n)_{−n}  (32)

satisfies the same hypergeometric recurrences (29), (30) as T′(n, k). Using the inverse substitution of (28), we see that T (n, k) = T′(an + bk, dn − ck) is equivalent to H(n, k) = H′(an + bk, dn − ck). But

H(n, k) = (u^{a}v^{d})^{n} (u^{b}v^{−c})^{k} ∏_{i=1}^{p}(α_{i})_{an+bk} ∏_{i=p+1}^{p+q}(α_{i} + an + bk)_{−(an+bk)}

is a factorial term. In (32), when α_{i} ∈ ℤ we are free to replace (α_{i})_{n} by (0)_{α_{i}+n} for α_{i} > 0, and by (1)_{α_{i}+n−1} for α_{i} ≤ 0. We can do likewise with its pseudoinverse (α_{i} + n)_{−n}. By a judicious choice between these alternatives we can always make H(n, k) nontrivial. □

Corollary 3 If K is algebraically closed, any Z-term T (n, k) is equivalent to a nontrivial factorial term.

Proof: W.l.g. assume that T is nontrivial. Let T (n, k) be a Z-term such that T (n + 1, k) =_{a} F (n, k)T (n, k) and T (n, k + 1) =_{a} G(n, k)T (n, k). Let F (x, y) = F_{1}(x, y)F_{2}(x, y) ⋯ F_{m}(x, y) and G(x, y) = G_{1}(x, y)G_{2}(x, y) ⋯ G_{m}(x, y) be factorizations of F and G such that F_{i}, G_{i}, and F_{i}G_{i} are uniform rational functions for 1 ≤ i ≤ m, while F_{i}F_{j}G_{i}G_{j} is not uniform for 1 ≤ i < j ≤ m. It follows from the unique factorization of polynomials in K[x, y] that F_{i} and G_{i} are compatible for each i. Hence by Lemma 6 there are uniform terms T_{i}(n, k) satisfying T_{i}(n + 1, k) =_{a} F_{i}(n, k)T_{i}(n, k) and T_{i}(n, k + 1) =_{a} G_{i}(n, k)T_{i}(n, k). Then T (n, k) ∼ ∏_{i=1}^{m} T_{i}(n, k). As in the proof of Theorem 10, we can achieve that T (n, k) will be nontrivial. Since products of factorial terms are factorial, the claim follows from Theorem 10. □

Corollary 4 If K is algebraically closed, any hypergeometric term T (n, k) is equivalent to R(n, k)T′(n, k) where R ∈ K(x, y) \ {0} is a rational function and T′(n, k) is a nontrivial factorial term.

Proof: W.l.g. assume that T is nontrivial. By Corollary 2, T =_{a} RT′′ where R ∈ K(x, y) and T′′ is a Z-term. By Proposition 2, this implies that T ∼ RT′′. By Corollary 3, T′′ ∼ T′ where T′ is a nontrivial factorial term. Then RT′′ ∼ RT′. As RT′′ ≠_{a} 0, it follows by Proposition 4 that T =_{a} RT′. □

Theorem 11 Assume that K is algebraically closed. If a rational sequence R(n, k) is equivalent to a holonomic hypergeometric term T (n, k) ≠_{a} 0 then the denominator of R factors into integer-linear factors.

Proof: Write R = P/Q where P, Q ∈ K[x, y] and P ⊥ Q. Let Q = V W where V, W ∈ K[x, y] and V is irreducible. We wish to show that V is a constant multiple of an integer-linear polynomial. Denote T′ = T W and R′ = RW = P/V. Then T′ is holonomic hypergeometric, T′ ≠_{a} 0, and T′ ∼ R′. Hence there are F, G ∈ K(x, y) such that both T′ and R′ satisfy (8). By Proposition 1, F (x, y) = R′(x + 1, y)/R′(x, y) and G(x, y) = R′(x, y + 1)/R′(x, y). Thus

T′(n + 1, k) =_{a} \frac{R′(n + 1, k)}{R′(n, k)}T′(n, k),  (33)
T′(n, k + 1) =_{a} \frac{R′(n, k + 1)}{R′(n, k)}T′(n, k).

We claim that

T′(n − i, k − j) =_{a} \frac{R′(n − i, k − j)}{R′(n, k)}T′(n, k)  (34)

for all i, j ≥ 0. The proof is by induction on i + j. If i + j = 0 then i = j = 0 and the claim is trivial. If i + j > 0 assume w.l.g. that i > 0. Then

T′(n − i, k − j) =_{a} \frac{R′(n − i, k − j)}{R′(n − i + 1, k − j)}T′(n − i + 1, k − j)
=_{a} \frac{R′(n − i, k − j)}{R′(n − i + 1, k − j)} \frac{R′(n − i + 1, k − j)}{R′(n, k)}T′(n, k)
=_{a} \frac{R′(n − i, k − j)}{R′(n, k)}T′(n, k),

using (33) and the induction hypothesis.

As T′ is holonomic, Theorem 1 implies that there are polynomials p_{i,j} ∈ K[x] \ {0} and a nonempty set H_{1} ⊆ {0, …, s}^{2} such that

∑_{(i,j)∈H_{1}} p_{i,j}(n) T′(n − i, k − j) =_{a} 0.

Using (34) we see that there is an algebraic set A such that

∑_{(i,j)∈H_{1}} p_{i,j}(n) R′(n − i, k − j) = 0

on supp T′ \ A. As this is non-algebraic, Proposition 1 and R′ = P/V imply that

∑_{(i,j)∈H_{1}} p_{i,j}(x) \frac{P (x − i, y − j)}{V (x − i, y − j)} = 0.  (35)

Pick a pair (i_{0}, j_{0}) ∈ H_{1} and clear denominators in (35). The factor V (x − i_{0}, y − j_{0}) appears explicitly in every term except the one with (i, j) = (i_{0}, j_{0}). Hence V (x − i_{0}, y − j_{0}) which is irreducible divides

p_{i_{0},j_{0}}(x)P (x − i_{0}, y − j_{0}) ∏_{{(i,j)∈H_{1} \atop (i,j)≠(i_{0},j_{0})}} V (x − i, y − j).

If it divides p_{i_{0},j_{0}}(x) then deg_{y} V (x, y) = 0, hence V (x, y) = ux + v for some u, v ∈ K. V (x − i_{0}, y − j_{0}) cannot divide P (x − i_{0}, y − j_{0}) because V | Q and P ⊥ Q. Hence it divides one of V (x − i, y − j) where (i, j) ≠ (i_{0}, j_{0}). But then V (x, y) = V (x + a, y + b) for some a, b ∈ ℤ, not both zero. By Corollary 1, V (x, y) = u(bx − ay + v) for some u, v ∈ K. In both cases, V is a constant multiple of an integer-linear polynomial. As V was an arbitrary irreducible factor of Q it follows that Q factors into integer-linear factors. □

Example 3 In the literature, various rational sequences such as 1/(n^{2} + k^{2}) [11, p. 586], 1/(n^{2} + k) [5, p. 358] and 1/(nk + 1) [4, Exer. 5.107] are shown to be nonholonomic by ad hoc arguments. Using Theorem 11, nonholonomicity of these sequences follows from the fact that their denominators do not factor into integer-linear factors. □

Theorem 12 If K is algebraically closed, any holonomic hypergeometric term T (n, k) is equivalent to a nontrivial proper term.

Proof: W.l.g. assume that T is nontrivial. By Corollary 4, T ∼ RT_{1} where R ∈ K(x, y) \ {0} and T_{1} is a nontrivial factorial term. By changing all rising factorials in T_{1} into their nowherezero counterparts, we obtain an equivalent holonomic sequence T_{2} which is nowhere zero. Then T ∼ RT_{2} and 1/T_{2} is also holonomic. So R ∼ T/T_{2}. Note that T/T_{2} is nontrivial, and holonomic by Theorem 2. Write R = P/Q where P, Q ∈ K[x, y] and P ⊥ Q. By Theorem 11, Q factors into integer-linear factors, hence 1/Q is equal modulo an algebraic set to a factorial term T_{3} which vanishes at most on an algebraic set (write 1/(an+bk+c) = (an+bk+c+1)_{−1} etc.) Thus T ∼ P T_{2}T_{3} which is a nontrivial proper term. □

References

[1] S. A. Abramov, Rational solutions of linear difference and differential equations with polynomial coefficients USSR Comput. Math. Phys. 29, 7–12. Transl. from Zh. vychisl. mat. mat. fyz. 29 (1989), 1611–1620.

[2] S. A. Abramov and H. Q. Le, Applicability of Zeilberger’s algorithm to rational functions, Proc. FPSAC ’00, LNCS, Springer-Verlag 2000, 91–102.

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

[4] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Mass., 2nd ed., 1994.

[5] L. Lipshitz, D-finite power series, J. Algebra 122 (1989) 353–373.

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

[7] M. Petkovšek, H. S. Wilf and D. Zeilberger, A = B, A K Peters, 1996.

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

[9] P. Verbaeten, The automatic construction of pure recurrence relations, Proc. EU-ROSAM ’74, ACM-SIGSAM Bulletin 8 (1974) 96–98.

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

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

[12] D. Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990) 321–368.

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

[14] D. Zeilberger, The method of creative telescoping, J. Symb. Comp. 11 (1991) 195–204.