Minimal Decomposition of Indefinite Hypergeometric Sums

S.Abramov, M.Petkovšek

July 3, 2001

Abstract

We present an algorithm which, given a hypergeometric term T (n), constructs hypergeometric terms T_{1}(n) and T_{2}(n) such that T (n) = T_{1}(n + 1) − T_{1}(n) + T_{2}(n), and T_{2}(n) is minimal in some sense. This solves the decomposition problem for indefinite sums of hypergeometric terms: T_{1}(n + 1) − T_{1}(n) is the “summable part” and T_{2}(n) the “non-summable part” of T (n).

1 Introduction

A sequence T (n) is a hypergeometric term (or simply a term) if the ratio T (n+1)/T (n) is a rational function of n. We call this function the certificate of T.

The well-known Gosper’s algorithm [5] solves the problem of indefinite hypergeometric summation: Given a hypergeometric term T (n), find another hypergeometric term T_{1}(n) such that

T (n) = T_{1}(n + 1) − T_{1}(n),  (1)

provided that such a term exists. If it does, and if T (k) and T_{1}(k) are defined for k = n_{0}, n_{0} + 1, …, n, then we obtain from (1) the summation identity

∑_{k=n_{0}}^{n−1} T (k) = T_{1}(n) − T_{1}(n_{0}).

If no hypergeometric term T_{1}(n) satisfies (1), we can ask for two hypergeometric terms T_{1}(n) and T_{2}(n) such that

T (n) = T_{1}(n + 1) − T_{1}(n) + T_{2}(n)  (2)

and T_{2}(n) is minimal in some sense. We call this the decomposition problem for indefinite hypergeometric sums. In this case

∑_{k=n_{0}}^{n−1} T (k) = T_{1}(n) − T_{1}(n_{0}) + ∑_{k=n_{0}}^{n−1} T_{2}(k).  (3)

As a special case when T (n) is a rational function of n, the algorithms given in [1, 3, 8] yield rational functions T_{1}(n) and T_{2}(n) such that (2), (3) hold and the denominator of T_{2} is of the least possible degree. These approaches are unified in [6].

Throughout the paper K is a field of characteristic zero, n an indeterminate, and E the shift operator on sequences with elements in K defined by ET (n) = T (n + 1). We write p ⊥ q to indicate that the polynomials p, q ∈ K[n] are relatively prime. The leading coefficient of a rational function is the quotient of the leading coefficients of its numerator and denominator. A rational function is monic if its leading coefficient is 1.

Following [6] we introduce the notion of shift-equivalence among polynomials.

Definition 1 Polynomials p, q ∈ K[n] are shift-equivalent if p = E^{k}q for some k ∈ ℤ. In this case we write p ∼^{sh} q. A monic rational function is shift-homogeneous if all nonconstant irreducible monic factors of its numerator and denominator belong to the same shift-equivalence class.

By grouping together shift-equivalent irreducible monic factors of its numerator and denominator every rational function can be written in the form

R(n) = z R_{1}(n)R_{2}(n) ⋯ R_{k}(n)  (4)

where z ∈ K, k ≥ 0, each R_{i} is a shift-homogeneous rational function, and any two nonconstant monic irreducible factors p of R_{i} and q of R_{j} are pairwise shift-inequivalent whenever i ≠ j. We call (4) a shifthomogeneous factorization of R. It is clear that the shift-homogeneous factorization is unique up to the order of the factors.

Definition 2 Let r, s ∈ K[n]. If r ⊥ E^{k}s for all k ∈ ℤ then the rational function r/s is shift-reduced. If r ⊥ E^{k}r for all k ∈ ℤ \ {0} then the polynomial r is shift-free.

Now we define a normal form for rational functions which reveals the shift structure of the factors. We need this normal form to define a measure of complexity of a hypergeometric term.

Definition 3 Let R ∈ K(n) be a nonzero rational function. If there exist z ∈ K and monic polynomials r, s, u, v ∈ K[n] such that R = z · \frac{r}{s} · \frac{EF}{F} where r/s is shift-reduced, F = u/v and u ⊥ v, then (z, r, s, u, v) is a rational normal form (RNF) of R. The rational function zr/s is the kernel of this RNF.

In [4] it is shown that every nonzero rational function has an RNF, and that regarding uniqueness we have the following results:

Lemma 1 Let R ∈ K(n) be shift-homogeneous. If (1, r, s, u, v) and (1, r_{1}, s_{1}, u_{1}, v_{1}) are two RNF’s of R then r = r_{1} = 1 and deg s = deg s_{1}, or s = s_{1} = 1 and deg r = deg r_{1}.

Theorem 1 Let (z, r, s, u, v) and (z′, r′, s′, u′, v′) be two RNF’s of R ∈ K(n) \ {0}. Then

(i) z = z′,

(ii) deg r = deg r′ and deg s = deg s′,

(iii) there is a one-to-one correspondence f between the multisets of nonconstant irreducible monic factors of r and r′ such that p ∼^{sh} f(p) for all p | r,

(iv) there is a one-to-one correspondence g between the multisets of nonconstant irreducible monic factors of s and s′ such that q ∼^{sh} g(q) for all q | s.

Now we can formulate the decomposition problem for indefinite hypergeometric sums in the following way:

Given a hypergeometric term T, find hypergeometric terms T_{1}, T_{2} such that

T = (E − 1)T_{1} + T_{2}  (5)

and the certificate ET_{2}/T_{2} has an RNF

(z, r, s, u, v)  (6)

with v of minimal degree.

This formulation agrees with the decomposition problem for indefinite sums of rational functions [1, 3, 8] because if T_{2} ∈ K(n) then r = s = 1 and v is the denominator of T_{2}.

Definition 4 If (z, r_{1}, s_{1}, u_{1}, v_{1}) and (z, r_{2}, s_{2}, u_{2}, v_{2}) are two RNF’s for the same rational function we state that the former is simpler than the latter if deg v_{1} < deg v_{2}.

If the terms T, T_{1}, T_{2} satisfy (5) then they are similar, i.e., there exist R_{1}, R_{2} ∈ K(n) such that T_{1} = R_{1}T and T_{2} = R_{2}T (cf. [7, Prop. 5.6.2]).

Definition 5 A rational function F ∈ K(n) is adequate to a hypergeometric term T if the certificate ET/T has an RNF with F as its kernel.

Let T, T_{1}, T_{2} satisfy (5). By the similarity of these terms each rational function that is adequate to one is also adequate to the other two.

We will describe a solution to the decomposition problem in three stages:

(A) We describe an algorithm which, given a term T, constructs terms T_{1}, T_{2} similar to T, and a rational function F adequate to T, T_{1}, T_{2}, such that if one restricts attention to RNF’s with kernel F then T_{1}, T_{2} solve the decomposition problem.

(B) We prove that for any other rational function F′ adequate to T and for any term T′_{1} similar to T, the RNF (with kernel F′) of ET′_{2}/T′_{2} where T′_{2} = T − (E − 1)T′_{1} is not simpler than the RNF of the certificate of T_{2} constructed by the algorithm in (A).

(C) Finally we show how sometimes one can “improve” T_{2} without changing deg v in such a way that deg u in (6) is not too large. In particular, we show how the decomposition algorithm also covers the case when T is summable.

For notational convenience, we sometimes write an RNF of a rational function R as G\frac{EF}{F} where G = z \frac{r}{s}, F = \frac{u}{v}, instead of as (z, r, s, u, v).

2 Regular descriptions of terms

Let D be a rational function and n_{0} ∈ ℤ. Set ∏_{k=n_{0}}^{n_{0}−1} D(k) = 1.

Definition 6 Let n_{0} ∈ ℤ and D, U ∈ K(n). The triple (D, U, n_{0}) regularly describes a term T (n) (in other words this triple is a regular description of T (n)) if for all integer n ≥ n_{0}

• D, U have neither a pole nor a zero,

• T (n) = U(n) ∏_{k=n_{0}}^{n−1} D(k).

If U(n) ∏_{k=n_{0}}^{n−1} D(k) is a regular description of T (n) then the certificate of T (n) is equal to D \frac{EU}{U}. On the other hand, if F \frac{EV}{V} is an RNF of the certificate of T (n) and n_{0} ∈ ℤ is such that for all n ≥ n_{0} the rational functions F, V have neither a pole nor a zero, and T (n) is defined, then the triple

(F, \frac{T (n_{0})}{V (n_{0})}V, n_{0})

regularly describes T (n), and F is shift-reduced in this regular description.

Lemma 2 Let (D, U, n_{0}) regularly describe a term T, n_{1} ≥ n_{0}, and

V (n) = U(n)\frac{T (n_{1})}{U(n_{1})} = U(n) ∏_{k=n_{0}}^{n_{1}−1} D(k).

Then (D, V, n_{1}) regularly describes T.

Proof: A direct check. □

Theorem 2 Given regular descriptions (D_{1}, U_{1}, n_{0}), (D_{2}, U_{2}, n_{1}) of similar terms T_{1}, T_{2}, one can construct

(a) regular descriptions of T_{1}, T_{2} that have the form (D, W_{1}, n_{2}), (D, W_{2}, n_{2}); (b) a regular description of T_{1} + T_{2}.

Proof: Since T_{1} and T_{2} are similar, the ratio of their certificates is of the form ER/R, R ∈ K(n) where R satisfies the equalities T_{1} = RT_{2} and

\frac{D_{1}}{D_{2}} · \frac{E(U_{1}/U_{2})}{(U_{1}/U_{2})} = \frac{ER}{R}.

This implies that

\frac{D_{1}}{D_{2}} = \frac{ES}{S}

for S = RU_{2}/U_{1}. The construction of an RNF of D_{1}/D_{2} yields

\frac{D_{1}}{D_{2}} = \frac{ES′}{S′} ,

where S′ is equal to S up to a constant factor. Setting V = S′U_{1}/U_{2} results in T_{1} = μV T_{2}, μ ∈ K. Take n_{2} ≥ max{n_{0}, n_{1}} such that V has neither a pole nor a zero at any integer n ≥ n_{2}. Then by Lemma 2 there exist α_{1}, α_{2} ∈ K such that (D_{1}, α_{1}U_{1}, n_{2}), (D_{2}, α_{2}U_{2}, n_{2}) regularly describe T_{1} and T_{2}. This implies

α_{1}U_{1}(n_{2}) = μα_{2}V (n_{2})U_{2}(n_{2}),

and we can find μ. Set D = D_{2}, W_{2} = α_{2}U_{2}, W_{1} = μV W_{2}. This gives (a). Now take n_{3} such that W_{1} + W_{2} has neither a pole nor a zero at any integer n ≥ n_{3}. Then by Lemma 2 there exist regular descriptions of the form (D, βW_{1}, n_{3}), (D, βW_{2}, n_{3}), β = ∏_{k=n_{2}}^{n_{3}−1} D(k), of T_{1}, T_{2}. Hence, (D, β(W_{1} + W_{2}), n_{3}) is a regular description of T_{1} + T_{2}. This gives (b). □

Lemma 3 Let the triples (D, U, n_{0}) and (D, U_{1}, n_{0}) regularly describe (similar) terms T and T_{1}. Then the certificate of the term T_{2} = T − (E − 1)T_{1} is

D \frac{EU_{2}}{U_{2}}  (7)

where

U_{2} = U − D(EU_{1}) + U_{1}.  (8)

Proof: For all integer n ≥ n_{0} we have

T_{2}(n) = U(n) ∏_{k=n_{0}}^{n−1} D(k) − (E − 1) (U_{1}(n) ∏_{k=n_{0}}^{n−1} D(k))

= U(n) ∏_{k=n_{0}}^{n−1} D(k) − (EU_{1}(n)) ∏_{k=n_{0}}^{n} D(k)

+ U_{1}(n) ∏_{k=n_{0}}^{n−1} D(k)

= (U(n) − (EU_{1}(n))D(n) + U_{1}(n)) ∏_{k=n_{0}}^{n−1} D(k).

It follows that the values of ET_{2}/T_{2} are equal to the values of (7) for all integer n ≥ n_{0}. This proves the claim. □

Theorem 3 Let the triple (D, U, n_{0}) regularly describe a term T. Let U_{1}, U_{2} ∈ K(n) be such that equality (8) holds. Then there exist terms T_{1}, T_{2} such that T = (E − 1)T_{1} + T_{2}. If U_{i} = 0 then T_{i} = 0, otherwise T_{i} has a regular description of the form (D, βU_{i}, n_{1}), n_{1} ≥ n_{0}, i = 1, 2, β ∈ K.

Proof: Choose n_{1} ≥ n_{0} such that if U_{i} ≠ 0 then U_{i} has neither a pole nor a zero for all n ≥ n_{1}, i = 1, 2. Multiplying (8) by ∏_{k=n_{1}}^{n−1} D(k) we get

U_{2}(n) ∏_{k=n_{1}}^{n−1} D(k) = U(n) ∏_{k=n_{1}}^{n−1} D(k) − (E − 1) (U_{1}(n) ∏_{k=n_{1}}^{n−1} D(k)) .

But

U(n) ∏_{k=n_{1}}^{n−1} D(k) = \frac{1}{∏_{k=n_{0}}^{n_{1}−1} D(k)}T (n).

Hence we can take

T_{1} = βU_{1}(n) ∏_{k=n_{1}}^{n−1} D(k),  (9)

T_{2} = βU_{2}(n) ∏_{k=n_{1}}^{n−1} D(k),  (10)

where β = ∏_{k=n_{0}}^{n_{1}−1} D(k). □

3 General approach and an algorithm

Lemma 4 Let D, U ∈ K(n), D = d_{1}/d_{2}, U = u_{1}/u_{2} where d_{1}, d_{2}, u_{1}, u_{2} ∈ K[n], and D is shift-reduced. Then there exist U_{1}, U_{2} ∈ K(n) such that (8) hold and

U_{2} = \frac{v_{1}}{(E^{−1}d_{1})^{i}d_{2}^{j}v_{2}} ,  (11)

where i, j ∈ {0, 1}, v_{1}, v_{2} ∈ K[n], and for any irreducible p ∈ K[n] dividing v_{2} and any h ∈ ℤ the following conditions are satisfied:

E^{h}p | v_{2} ⇒ h = 0,  (12)
E^{h}p | d_{1} ⇒ h < 0,  (13)
E^{h}p | d_{2} ⇒ h > 0  (14)

(in words, (12) means that v_{2} is shift-free).

Proof: Let q be an irreducible in K[n] and u_{2} = u′_{2}q^{k} where q ⊥ u′_{2} and k > 0. Then there are a, b ∈ K[n] such that

U = \frac{a}{u′_{2}} + \frac{b}{q^{k}} .  (15)

We distinguish two cases.

a) There is an integer h ≤ 0 such that E^{h}q | d_{2}. Let U_{1}′ = E^{−1} (b/(Dq^{k})). Then D(EU_{1}′) = b/q^{k}, so U − D(EU_{1}′) + U_{1}′ can be written as

\frac{c_{0}}{u′_{2}} + \frac{c_{1}}{E^{−1}d_{1}} + \frac{c_{2}}{(E^{−1}q)^{l}}

where l ≤ k, c_{0}, c_{1}, c_{2} ∈ K[n].

b) There is an integer h ≥ 0 such that E^{h}q | d_{1}. Let U_{1}′ = −b/q^{k}. Then U − D(EU_{1}′) + U_{1}′ can be written as

\frac{c_{0}}{u′_{2}} + \frac{c_{1}}{d_{2}} + \frac{c_{2}}{(Eq)^{l}}

where l ≤ k, c_{0}, c_{1}, c_{2} ∈ K[n].

Since D is shift-reduced, at most one of the cases a), b) can occur. Repeating these steps if necessary (using U_{1}′′, U_{1}′′′, …) we obtain a rational function U −DE(U_{1}′ +U_{1}′′ +⋯)+(U_{1}′ +U_{1}′′ +⋯) whose denominator is divisible by at most one polynomial of the form E^{γ}q. If such a γ exists then for p = E^{γ}q we have (12), (13), and (14). Similarly we can proceed with the irreducible factors of u_{2} that are different from E^{σ}q, σ ∈ ℤ.

Suppose that u_{2} is not shift-free. If there is an integer h > 0 such that E^{h}q|u_{2} for some irreducible q and if (15) holds, then we can transform U as it is described in b). Similarly we can use the way described in a) if we have h < 0. □

Using Lemmas 4 and 3 one obtains the terms T_{1} and T_{2} = T − (E − 1)T_{1} with certificates in the form D \frac{EU_{1}}{U_{1}} and D \frac{EU_{2}}{U_{2}} , respectively. The certificate of T_{2} can be rewritten in a simpler form: suppose that U_{2} has the form (11), then we can remove the factors (E^{−1}d_{1})^{i}, d_{2}^{j}, i, j ∈ {0, 1} from the denominator of U_{2}. Since

D \frac{EU_{2}}{U_{2}} = \frac{d_{1} (\frac{E^{−1}d_{1}}{d_{1}} )^{i}}{d_{2} (\frac{Ed_{2}}{d_{2}} )^{j}} \frac{E (\frac{v_{1}}{v_{2}} )}{\frac{v_{1}}{v_{2}}},

by setting

F = \frac{d_{1} (\frac{E^{−1}d_{1}}{d_{1}} )^{i}}{d_{2} (\frac{Ed_{2}}{d_{2}} )^{j}} , V = \frac{v_{1}}{v_{2}} ,

we get the certificate of T_{2} in the form F \frac{EV}{V} . Reformulating properties (12), (13), (14) in terms of F and V, we have the following theorem.

Theorem 4 Let T be a term. Then it is possible to find a term T_{1} similar to T, and a shift-reduced rational function F = f_{1}/f_{2} that is adequate to T, T_{1}, such that the certificate of the term T_{2} = T − (E − 1)T_{1}, written in the RNF with F as the kernel:

F \frac{EV}{V} , V = \frac{v_{1}}{v_{2}} , v_{1} ⊥ v_{2},

has the following properties Pa, Pb:

Pa : v_{2} is shift-free;

Pb : if p is an irreducible from K[n] such that p | v_{2}, then

E^{h}p | f_{1} ⇒ h < 0,  (16)
E^{h}p | f_{2} ⇒ h > 0.  (17)

If we use (10) and thus find a regular description (D, βU_{2}, n_{1}) of T_{2} and if n_{1} is such that F, V have neither a pole nor a zero for all n ≥ n_{1}, then we can get the regular description of T_{2}

(F, \frac{βU_{2}(n_{1})}{V (n_{1})}V, n_{1})  (18)

as well; in so doing we can get U_{2}(n_{1}) from (8):

U_{2}(n_{1}) = U(n_{1}) − D(n_{1})(U(n_{1} + 1) − U_{1}(n_{1})) + U_{1}(n_{1}).  (19)

As the proofs of Lemmas 4 and 3 are constructive, we now describe an algorithm to compute the terms T_{1}, T_{2} mentioned in Theorem 4. In case a) of the proof of Lemma 4 we considered the irreducibles q’s and the integers h’s such that q|u_{2}, E^{h}q|d_{2}, h ≤ 0. All the q’s (say q_{1}, …, q_{κ}) that relate to the minimal possible h can be considered together. Using resultant and gcd techniques, we find the minimal value of h along with q′ = q_{1}^{ν_{1}} … q_{κ}^{ν_{κ}}, q′|u_{2}, ν_{1}, …, ν_{κ} > 0, then compute q̃ = q_{1}^{μ_{1}} … q_{κ}^{μ_{κ}}, where μ_{1}, …, μ_{κ} are maximal possible values such that q_{1}^{μ_{1}} … q_{κ}^{μ_{κ}}|u_{2}. We can use the following simple algorithm pump:

algorithm pump;

input: f, g ∈ K[n], f|g; output: f̃, g̃ ∈ K[n], f|f̃, f̃g̃ = g, f̃⊥ g̃;

f̃:= f; g̃ := g/f̃;

repeat d = gcd(f̃, g̃);

f̃:= f̃d; g̃ := g̃/d; until deg d = 0. return (f̃, g̃).

We can compute (q̃, ũ_{2}) = pump(q, u_{2}) and then use the partial-fraction decomposition

U = \frac{ã}{ũ_{2}} + \frac{b̃}{q̃},  (20)

where ã, b̃ ∈ K[n] for the decomposition (15) (the polynomial part of U can be arbitrarily shared between the terms in the right hand side of (20)). We can similarly proceed in case b) of the proof of Lemma 4 and arrive to the following algorithm dcert:

algorithm dcert;

input: D, U ∈ K(n) where D is shift-reduced; output: U_{1}, F, V ∈ K(n) such that the term T with certificate D \frac{EU}{U} has decomposition T = T_{2} +(E −1)T_{1}, where

• if U_{1} = 0 then T_{1} = 0, otherwise T_{1} has the certificate D \frac{EU_{1}}{U_{1}} ;

• if V = 0 then T_{2} = 0, otherwise T_{2} has the certificate F \frac{EV}{V} , with F, V having properties Pa, Pb of Theorem 4;

U_{1} := 0; U_{2} := U;

u_{2} := denominator(U_{2}); N_{1} := −1; M := −1; R_{1}(m) := Res_{n}(u_{2}(n + m), d_{1}(n)); R(m) := Res_{n}(u_{2}(n + m), u_{2}(n)); if R_{1}(m) has some nonnegative integer root

then N_{1} := max{m : m ∈ ℤ, R_{1}(m) = 0}

    fi;
    fi;

if R(m) has some positive integer root

then M := max{m : m ∈ ℤ, R(m) = 0}

    fi;

N_{1} = max{N_{1}, M};

    for h = N_{1} downto 0 do

q := gcd(u_{2}, E^{−h}d_{1});
if h > 0

                  then

t := u_{2}/q;

q := q gcd(t, E^{−h}t)

           fi;

(q̃, ũ_{2}) := pump(q, u_{2});

represent U_{2} in the form U_{2} = \frac{ã}{ũ_{2}} + \frac{b̃}{q̃},

ã, b̃ ∈ K[n];
U_{1}′ := −b̃/q̃;
U_{2} := U_{2} − D(EU_{1}′) + U_{1}′; U_{1} := U_{1} + U_{1}′
u_{2} := denominator(U_{2});

od;

R_{2}(m) := Res_{n}(u_{2}(n + m), d_{2}(n)); N_{2} := 1; if R_{2}(m) has some nonpositive integer root

then N_{2} := min{m : m ∈ ℤ, R_{2}(m) = 0}

fi;
for h = N_{2} to 0 do

q := gcd(u_{2}, E^{−h}d_{2});

(q̃, ũ_{2}) := pump(q, u_{2});
represent U_{2} in the form U_{2} = \frac{ã}{ũ_{2}} + \frac{b̃}{q̃},
ã, b̃ ∈ K[n];
U_{1}′ := E^{−1}(b̃/(Dq̃));
U_{2} := U_{2} − D(EU_{1}′) + U_{1}′; U_{1} := U_{1} + U_{1}′
u_{2} := denominator(U_{2});

od;

v_{1} := numerator(U_{2}); v_{2} := u_{2}; w_{1} := gcd(E^{−1}d_{1}, v_{2}); v_{2} := v_{2}/w_{1}; f_{1} := (d_{1}/Ew_{1})w_{1}; w_{2} := gcd(d_{2}, v_{2}); v_{2} := v_{2}/w_{2}; f_{2} := (d_{2}/w_{2})Ew_{2}; F := \frac{f_{1}}{f_{2}} ; V := \frac{v_{1}}{v_{2}} . return (U_{1}, F, V).

It is now easy to write down algorithm dterm whose input and output are terms:

algorithm dterm;

input: a term T that is regularly described by the triple (D, U, n_{0}) with the shift-reduced D; output: terms T_{1}, T_{2} such that T = (E − 1)T_{1} + T_{2}. The term T_{2} either equals zero, or has the certificate F \frac{EV}{V} , with F, V having properties Pa, Pb of Theorem 4;

(U_{1}, F, V) := dcert(D, U); if U_{1} = 0

then return (0, T)

fi;

find integer n_{1} ≥ n_{0} s.t. U_{1}(n), and additionally F (n), V (n) in the case V ≠ 0, have neither a pole nor a zero for all n ≥ n_{1}; using (9) to obtain the regular description of the term T_{1}; if V = 0

then return (T_{1}, 0)

fi;

using (18), (19) to obtain the regular description of the term T_{2}; return (T_{1}, T_{2}).

We now prove that if one restricts attention to RNF’s with kernel F then T_{1}, T_{2} solve the decomposition problem (see Theorem 5 below). We will prove in section 4 that these terms give a complete solution to the decomposition problem.

Theorem 5 Let terms T, T_{1}, T′_{1} be such that T_{2} = T − (E − 1)T_{1}, T′_{2} = T − (E − 1)T′_{1}, and let F = f_{1}/f_{2} be a shift-reduced rational function adequate to these terms. Let ET_{2}/T_{2} = F \frac{EV}{V} where F, V ∈ K(n) have properties Pa and Pb of Theorem 4, and ET′_{2}/T′_{2} = F \frac{EV′}{V′}. If V = v_{1}/v_{2} and V′ = v′_{1}/v′_{2} where v_{1}, v_{2}, v′_{1}, v′_{2} ∈ K[n] and v_{1} ⊥ v_{2} then deg v_{2} ≤ deg v′_{2}.

Proof: We have

T′_{2} = T_{2} − (E − 1)(T′_{1} − T_{1}).

Suppose that the certificate of T′_{1} − T_{1} is equal to F \frac{EW}{W} where W = w_{1}/w_{2} and w_{1} ⊥ w_{2}. Then, by Lemma 3,

\frac{v′_{1}}{v′_{2}} = \frac{v_{1}}{v_{2}} − \frac{f_{1}}{f_{2}} \frac{Ew_{1}}{Ew_{2}} + \frac{w_{1}}{w_{2}} .  (21)

Consider an arbitrary irreducible p ∈ K[n] such that p | v_{2}. We set

k = max{α : p^{α} | v_{2}}

and claim that E^{l}p^{k} | v′_{2} for some l ∈ ℤ. Since the pair F, V has property Pa, this claim implies the statement of the theorem. Suppose that p^{k} does not divide v′_{2}. Equation (21) implies that v_{2} and hence p^{k} divides the lcm of v′_{2}, f_{2}Ew_{2}, and w_{2}. By (17) we have p ⊥ f_{2}, therefore p^{k} | Ew_{2} or p^{k} | w_{2}.

Let p^{k} | Ew_{2}. Then

E^{−1}p^{k} | w_{2}.  (22)

Set l = min{m : E^{m}p^{k} | w_{2}}. Evidently E^{l}p^{k} does not divide Ew_{2}. It follows from (22) that l ≤ −1; together with (17) this gives E^{l}p ⊥ f_{2}. As v_{2} is shift-free and p | v_{2}, it follows that E^{l}p^{k} does not divide v_{2}. Therefore (21) implies

E^{l}p^{k} | v′_{2}.  (23)

Let p^{k} | w_{2}. Then

Ep^{k} | Ew_{2}.  (24)

Set l = max{m : E^{m}p^{k} | Ew_{2}}. Evidently E^{l}p^{k} does not divide w_{2}. It follows from (24) that l ≥ 1; together with (16) this gives E^{l}p ⊥ f_{1}. Therefore (21) implies (23) in this case as well. □

Corollary 1 Let F, U, S_{1}, S_{2} ∈ K(n) where F is shift-reduced. Let the rational functions

V_{1} = U − F ES_{1} + S_{1}, V_{2} = U − F ES_{2} + S_{2}

be such that the pairs F, V_{1} and F, V_{2} have properties Pa and Pb of Theorem 4. Then the degrees of the denominators of V_{1} and V_{2} are the same.

4 A verification

If both rational functions F_{1}, F_{2} are adequate to a term T then there exists G ∈ K(n) such that

\frac{F_{1}}{F_{2}} = \frac{EG}{G}.  (25)

Indeed, for some U_{1}, U_{2} ∈ K(n) we have

F_{1} \frac{EU_{1}}{U_{1}} = F_{2} \frac{EU_{2}}{U_{2}} ,

and therefore G = U_{1}^{−1}U_{2}. The case where G ∈ K[n] is of special interest.

Theorem 6 Let F_{1}, F_{2} be rational functions that are adequate to a term T. Let (25) hold with G ∈ K[n]. Let V be such that the pair F_{1}, V has properties Pa and Pb. Then the denominator of V is coprime with G and the pair F_{2}, GV has properties Pa and Pb.

Proof: First we prove that the denominator of V is coprime with G. If they have a common irreducible factor p then the set {ν : E^{ν}p | G} is a non-empty finite set. Suppose that m, M are, resp., the minimal and the maximal elements of this set. Write

W = \frac{G}{EG} = \frac{F_{2}}{F_{1}} = \frac{w_{1}}{w_{2}} , w_{1} ⊥ w_{2}.

Then E^{M+1}p | w_{2} and E^{m}p | w_{1}. We have F_{2} = W F_{1}. As p divides the denominator of V and the pair F_{1}, V has properties Pa and Pb, the numerator of F_{1} is not divisible by E^{M+1}p since M + 1 > 0. Similarly the denominator of F_{1} is not divisible by E^{m}p since m ≤ 0. Therefore the numerator of F_{2} is divisible by E^{m}p while the denominator of F_{2} is divisible by E^{M+1}p. But F_{2} is shift-reduced by Definition 3(ii), a contradiction.

Now we prove that the pair F_{2}, GV has properties Pa and Pb. We have

F_{2} = \frac{G}{EG}F_{1}

and the pair F_{2}, GV has property Pa because the denominator of GV divides the denominator of V. Now we shall be concerned with Pb. Let p be an irreducible from K[n] that divides the denominator of GV and thereby divides the denominator of V. Let E^{h}p, h ≤ 0, divide the denominator of F_{2}. Then E^{h}p does not divide the denominator of F_{1} since the pair F_{1}, V has properties Pa and Pb. The equality (EG)F_{2} = GF_{1} implies that E^{h}p | EG. Set h_{0} = min{ν : E^{ν}p | EG}. Then h_{0} ≤ h ≤ 0 and E^{h_{0}−1}p | G, but E^{h_{0}−1}p does not divide EG. The denominator of F_{1} is not divisible by E^{h_{0}−1}p since the pair F_{1}, V has properties Pa and Pb. Therefore E^{h_{0}−1}p divides the numerator of F_{2}. But as E^{h}p divides the denominator of F_{2}, this contradicts the fact that F_{2} is shift-reduced.

Similarly it can be shown that E^{h}p, h ≥ 0, cannot divide the numerator of F_{2}. □

Lemma 5 Let F, F_{1}, U, U_{1} ∈ K(n), G ∈ K[n] be such that F/F_{1} = EG/G, G ∈ K[n] and F \frac{EU}{U} = F_{1} \frac{EU_{1}}{U_{1}} . Then there exists \overline{G} ∈ K[n] such that \overline{G}U = U_{1} and for any S ∈ K(n) we have

\overline{G}(U − F ES + S) = U_{1} − F_{1}E(\overline{G}S) + \overline{G}S.

Proof: We have

\frac{E(U^{−1}U_{1})}{U^{−1}U_{1}} = \frac{EG}{G}.

It follows from this that there exists α ∈ K such that U^{−1}U_{1} = αG. Set \overline{G} = αG. We get

\frac{E\overline{G}}{\overline{G}}F_{1} = F, U_{1} = \overline{G}U.

Substituting U_{1} for \overline{G}U and (E\overline{G}/\overline{G})F_{1} for F in \overline{G}U − (\overline{G}F)ES + \overline{G}S gives U_{1} − F_{1}E(\overline{G}S) + \overline{G}S. □

Theorem 7 Let F_{1}, F_{2} be rational functions that are adequate to a term T. Let U_{1}, U_{2}, R ∈ K(n) be such that

F_{1} \frac{EU_{1}}{U_{1}} = F_{2} \frac{EU_{2}}{U_{2}} = R.  (26)

For S_{1}, S_{2} ∈ K(n), let

V_{1} = U_{1} − F_{1}ES_{1} + S_{1}, V_{2} = U_{2} − F_{2}ES_{2} + S_{2}  (27)

be such that the pairs F_{1}, V_{1} and F_{2}, V_{2} have properties Pa and Pb. Then the denominators of V_{1} and V_{2} are of the same degree.

Proof: First of all we show that there exists a shift-reduced rational function a/b, such that for the rational functions

F_{0} = \frac{a}{b}, F_{−1} = \frac{E^{−1}a}{b}, F_{−2} = \frac{a}{Eb}, F_{−3} = \frac{E^{−1}a}{Eb}  (28)

the equalities

\frac{F_{i}}{F_{1}} = \frac{EG′_{i}}{G′_{i}} , \frac{F_{i}}{F_{2}} = \frac{EG′′_{i}}{G′′_{i}} , G′_{i}, G′′_{i} ∈ K[n],  (29)

hold for i = −1, −2, −3. It is sufficient to prove the theorem for shift-homogeneous F_{1}, F_{2} which belong to the same shift-homogeneous class. Then, by Lemma 1, either both F_{1} and F_{2} are polynomials, or both F_{1} and F_{2} are reciprocals of polynomials. By Theorem 1(ii) we have

F_{1} = ∏_{i=1}^{τ} E^{h_{i}}p, F_{2} = ∏_{i=1}^{τ} E^{l_{i}}p,  (30)

in the former case, and

F_{1} = \frac{1}{∏_{i=1}^{τ} E^{h_{i}}p}, F_{2} = \frac{1}{∏_{i=1}^{τ} E^{l_{i}}p}.  (31)

in the latter, where p ∈ K[n] is irreducible. In case of (30), set

a = ∏_{i=1}^{τ} E^{max{h_{i},l_{i}}+1}p, b = 1,

and in case of (31), set

a = 1, b = ∏_{i=1}^{τ} E^{min{h_{i},l_{i}}−1}p.

It is easy to see that if F_{0}, F_{−1}, F_{−2}, F_{−3} are defined as in (28) then the equalities (29) hold for some polynomials G′_{i}, G′′_{i}.

Considering the RNF of R with the kernel a/b and using algorithm hgad we can get i, −3 ≤ i ≤ 0, and F, U, V, S ∈ K[n] such that

• F = F_{i};

• R = F \frac{EU}{U}, U = \frac{u_{1}}{u_{2}} , u_{1} ⊥ u_{2};

• V = U − F ES + S;

• the pair F, V has properties Pa and Pb.

Set

G′ = G′_{i}, G′′ = G′′_{i}

for the computed i. By Lemma 5 there exists a polynomial \overline{G}′ such that

\overline{G}′V = \overline{G}′(U − F ES + S) = U_{1} − F_{1}E(\overline{G}′S) + \overline{G}′S.

By Theorem 6 the pair F_{1}, U_{1} − F_{1}E(\overline{G}′S) + \overline{G}′S has properties Pa and Pb and the degree of denominator of \overline{G}′V is equal to the degree of the denominator of V. By Corollary 1 the denominator of V is of the same degree as the denominator of V_{1}, and similarly for the degrees of the denominators of V and V_{2}. The claim follows. □

The following theorem is the main theorem of this section.

Theorem 8 Let T, T_{1}, T′_{1} be similar terms. Let the certificates of the terms T_{2} = T − (E − 1)T_{1}, T′_{2} = T − (E − 1)T′_{1} be written in the form

F \frac{EV}{V} , F′ \frac{EV′}{V′}

with shift-reduced F, F′. Let the pair F, V have properties Pa and Pb. Then the degree of the denominator of V is less than or equal to the degree of the denominator of V′.

Proof: Since ET′_{2}/T′_{2} = F′(EV′/V′), where F′ is shift-reduced, there exists U ∈ K(n) such that ET/T = F′(EU/U). Now applying hgad to the input F′, U yields Ũ, Ṽ ∈ K(n) such that the term T has the decomposition T = (E − 1)T̃_{1} + T̃_{2} where T̃_{1}, T̃_{2} have the certificates F′(EŨ/Ũ) and F′(EṼ /Ṽ), resp. with F′, Ṽ satisfying properties Pa and Pb. From Theorem 7, one concludes that the denominators of V and Ṽ are of the same degree. The claim now follows since it is clear from Theorem 5 that the degree of the denominator of Ṽ is less than or equal to the degree of the denominator of V′. □

5 Remarks on the algorithm and summability

Any algorithm to solve the decomposition problem for rational functions guarantees that if the input rational function T is rational-summable, then it will return a rational function T_{1} such that

T = (E − 1)T_{1}.

It would be logical if an algorithm to solve the same problem for hypergeometric terms follows the same concept. It is clear that by simply applying dterm, one will not achieve this goal. The following theorem will be useful.

Theorem 9 Let T be a summable term, i.e., there exists a term T_{1} such that (E − 1)T_{1} = T. Let the certificates of T, T_{1} be written in the form F \frac{EV}{V} , F \frac{ER}{R} with shift-reduced F. Let the pair F, V have properties Pa and Pb. Then V, R are polynomials.

Proof: Set V = v_{1}/v_{2}, F = f_{1}/f_{2}, v_{1}, v_{2}, f_{1}, f_{2} ∈ K[n]. If (E − 1)T_{1} = T then there exists μ ∈ K such that F E(μR) − μR = V. Set S = μR then

F ES − S = V,  (32)

or equivalently,

v_{2} f_{1} ES − v_{2} f_{2} S = f_{2} v_{1}.  (33)

Since the pair F, V has properties Pa and Pb, the dispersion of the polynomials f_{2}v_{2}, f_{1}v_{2} cannot be a positive integer. Therefore there is no non-polynomial rational function S that satisfies (33) (see [2]). Consequently, S, R ∈ K[n]. It follows from (32) that V ∈ K[n]. □

Consider the algorithm dpol for the case where V ∈ K[n].

algorithm dpol;

input: a term T that is regularly described by the triple (F, V, n_{0}) with F, V having properties Pa, Pb. D is shift-reduced, V ∈ K[n]; output: a term T_{1} such that T = (E − 1)T_{1} if such a term exists and 0 otherwise;

if the equation F Ey − y = V has a polynomial solution then set S to an arbitrary polynomial solution else return 0

    fi;

find integer n_{1} ≥ n_{0} s.t. S(n) has neither a pole

nor a zero for all n ≥ n_{1};

using (9) with D = F, U = S to obtain the regular description of the term T_{1}; return T_{1}.

We now arrive to presenting algorithm hgadddec that solves the additive decomposition problem, and that also includes the recognition of summability.

algorithm hgadddec;

input: a term T that is regularly described by the triple (D, U, n_{0}) with the shift-reduced D; output: terms T_{1}, T_{2} such that T = (E − 1)T_{1} + T_{2}. The term T_{2} either equals zero, or has the certificate F \frac{EV}{V} , with V having the denominator of minimal possible degree. If T is summable then T_{2} = 0;

(T_{1}, T_{2}) := dterm(T) (let (F, V, n_{1}) be the obtained

regular description of T_{2} in the case T_{2} ≠ 0);

if T_{2} = 0 or V ∉ K[n]

then return (T_{1}, T_{2})

    fi;

T_{3} := dpol(T_{2}); if T_{3} = 0

then return (T_{1}, T_{2})

    fi;

construct T′_{1} = T_{1} + T_{3} using Theorem 2(b); return (T′_{1}, 0).

6 A control on the degree of the numerator

So, the denominator of V has the minimal possible degree. How to reduce the degree of the numerator of V to a tolerable size? Recall that when one solves the decomposition problem for indefinite sums of rational functions, it is always possible to have the degree of the numerator less than the degree of the denominator (this is because any rational function is the sum of a polynomial and a proper rational function, and the equation

(E − 1)y = u  (34)

has a polynomial solution for any u ∈ K[n]).

In the hypergeometric case the situation is not so simple. Consider a term which is regularly described by a triple (F, V, n_{0}), V ∈ K[n], D = f_{1}/f_{2}, where D is shift-reduced. If S ∈ K[n] then the rational function

V − \frac{f_{1}}{f_{2}} ES + S

can be represented in the form P/f_{2}, P = f_{2}V − f_{1}ES + f_{2}S ∈ K[n]. We will take into account the denominator f_{2} in P/f_{2} later in this section. Let us first try to find a polynomial S such that the polynomial

f_{2}V − f_{1}ES + f_{2}S  (35)

has a “reasonable” degree. We considered in Section 5 the case where there exists S such that (35) is equal to zero, i.e., the equation

f_{1}Ey − f_{2}y = f_{2}V  (36)

(an analogue of equation (34)) has a polynomial solution. This is the best case. But in any case, we can start a process of searching for a polynomial solution of (36), trying to find the degree and the leading coefficient of y(x), then its next coefficient and so on. This process decreases step-by-step the degree of the right hand side of (36), and stops if either we get a polynomial solution of (35) or the construction of the next coefficient is not possible. So, even if there does not exist a polynomial S such that (35) equals 0, it is possible that we are able to find S such that the degree of (35) is less than the degree of f_{2}V. To be more precise, rewrite (35) as

P = f_{2}V − f_{1}(E − 1)S + (f_{2} − f_{1})S  (37)

and set

M = f_{2}V, T = −f_{1}(E − 1)S + (f_{2} − f_{1})S.

Evidently deg(E − 1)S = deg S − 1, lc ((E − 1)S) = deg S · lc S. By a judicious choice of S we can cancel out some leading terms of M if the degree of M is large enough. The number of those terms depends first of all on the relation between deg(f_{2} − f_{1}) and deg f_{1}:

1. deg(f_{2} − f_{1}) > deg f_{1}. Then deg f_{2} > deg f_{1} and deg T = deg f_{2} + deg S, lc T = lc f_{2} · lc S. We can transform M to P of degree < deg f_{2}.

2. deg(f_{2} − f_{1}) = deg f_{1}. Then deg f_{2} ≤ deg f_{1} and deg T = deg f_{1} + deg S, lc T = lc (f_{2} − f_{1}) · lc S. We can transform M to P of degree < deg f_{1}.

3. deg(f_{2} − f_{1}) < deg f_{1}. Then deg f_{2} = deg f_{1}, lc f_{1} = lc f_{2}.

3a. deg(f_{2} − f_{1}) < deg f_{1} − 1. Then the coefficients of x^{deg f_{1}−1} in f_{1} and f_{2} are equal. We have deg T = deg f_{1} + deg S − 1, lc T = −lc f_{1} · lc S · deg S. We can transform M to P of degree σ < deg f_{1}. (Moreover, if σ = deg(f_{2} − f_{1}), then by applying an additional elimination we can transform P to P′ of degree < deg(f_{2} − f_{1}).)

3b. deg(f_{2} − f_{1}) = deg f_{1} − 1. Then the coefficients of x^{deg f_{1}−1} in f_{1} and f_{2} are not equal. If

−lc f_{1} · deg S + lc (f_{2} − f_{1}) ≠ 0

then

deg T = deg f_{1} + deg S − 1 = deg(f_{2} − f_{1}) + deg S,
lc T = lc S · (−lc f_{1} · deg S + lc (f_{2} − f_{1})).

In such a case if the equation

−lc f_{1} · X + lc (f_{2} − f_{1}) = 0

has no integer root on the segment [0; deg M − deg(f_{2} − f_{1})] or, equivalently, on the segment [0; deg M − deg f_{1} + 1], then we can transform M to P of degree < deg f_{1} − 1. If

−lc f_{1} · τ + lc (f_{2} − f_{1}) = 0

for an integer τ from the segment [0; deg M − deg(f_{2} − f_{1})], then we can transform M to P of degree < deg(f_{2} − f_{1}) + τ + 1, or, equivalently, < deg f_{1} + τ.

Therefore we have the following

Theorem 10 Let M, f_{1}, f_{2} ∈ K[n], f_{2} ≠ 0. Then it is possible to find S ∈ K[n] such that the degree of P = M − f_{1}ES + f_{2}S is less than

λ = \{ \begin{matrix}deg f_{2} & if deg(f_{2} − f_{1}) > deg f_{1}, \\ deg f_{1} & if deg(f_{2} − f_{1}) = deg f_{1} \\ & or deg(f_{2} − f_{1}) < deg f_{1} − 1, \\ deg f_{1} + τ & if deg(f_{2} − f_{1}) = deg f_{1} − 1, \end{matrix}

where in the last case τ is equal to lc (f_{2} − f_{1})/lc f_{1} if this is a nonnegative integer and −1 otherwise.

Observe that if f_{1} = f_{2} = 1, then λ = 0 and P = 0. This is in agreement with the fact that the equation (E − 1)S = V has a polynomial solution when V ∈ K[n].

Thus we can find S such that (35) is equal to a polynomial P whose degree is bounded from above as described in Theorem 10. This implies that

V (n) ∏_{k=n_{0}}^{n−1} F (k) − (E − 1) (S(n) ∏_{k=n_{0}}^{n−1} F (k))

= \frac{P (n)}{f_{2}(n)} ∏_{k=n_{0}}^{n−1} F (k) = \frac{P (n)}{f_{2}(n_{0})} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k + 1)}.

Now suppose that V is a rational function of the form v_{1}/v_{2}. This leads to the expression

f_{2}v_{1} − v_{2}f_{1}ES + v_{2}f_{2}S

instead of (35). We can use the described techniques by considering v_{2}f_{1}, v_{2}f_{2} instead of f_{1}, f_{2}, and obtain S, P such that

f_{2}v_{1} − v_{2}f_{1}ES + v_{2}f_{2}S = P.

In other words,

\frac{v_{1}(n)}{v_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)} − (E − 1) (S(n) ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)})

= \frac{P (n)}{v_{2}(n)f_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)} = \frac{P (n)}{v_{2}(n)f_{2}(n_{0})} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k + 1)}.

Hence we have proven

Theorem 11 Let a term T be regularly described by a triple (f_{1}/f_{2}, v_{1}/v_{2}, n_{0}), i.e.,

T (n) = \frac{v_{1}(n)}{v_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)}.

Then there exists a term T_{1} of the form

T_{1}(n) = S(n) ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)},

S ∈ K[n], such that the term T_{2} = T − (E − 1)T_{1} is of the form

\frac{P (n)}{v_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k + 1)},

where P is a polynomial whose degree is less than

λ = \{ \begin{matrix}deg v_{2} + deg f_{2} & if deg(f_{2} − f_{1}) > deg f_{1}, \\ deg v_{2} + deg f_{1} & if deg(f_{2} − f_{1}) = deg f_{1} \\ & or deg(f_{2} − f_{1}) < deg f_{1} − 1, \\ deg v_{2} + deg f_{1} + τ & if deg(f_{2} − f_{1}) = deg f_{1} − 1, \end{matrix}

where in the last case τ is equal to lc (f_{2} − f_{1})/lc f_{1} if this is a nonnegative integer, and −1 otherwise.

Observe that if f_{1} = f_{2} = 1, then by this theorem deg P < deg v_{2}. This is in agreement with the properties of the decomposition of indefinite sums of rational functions. Considering the relation

\frac{P (n)}{v_{2}(n)f_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)} = \frac{P (n)}{v_{2}(n)f_{2}(n_{0})} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k + 1)},

we now take into account the possible common factors of P (n) and f_{2}(n). Note that if the pair f_{1}/f_{2}, v_{1}/v_{2} has properties Pa and Pb, then the rational function P/v_{2} is in reduced form (i.e., P ⊥ v_{2}) by Theorem 5. However we can try to reduce P/f_{2}. Suppose this gives P′/f′_{2}, f_{2} = f′_{2}f′′_{2}. Then

\frac{P (n)}{v_{2}(n)f_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f_{2}(k)}

= \frac{P′(n)}{v_{2}(n)f′_{2}(n)} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f′_{2}(k)f′′_{2}(k)}

= \frac{P′(n)}{v_{2}(n)f′_{2}(n_{0})} ∏_{k=n_{0}}^{n−1} \frac{f_{1}(k)}{f′′_{2}(k)f′_{2}(k + 1)}.

Doing so as it is described in sections 3 and 5, we get a decomposition T = (E − 1)T_{1} + T_{2}. If T_{2} ≠ 0, then we can try to simplify T_{2} as it was described in this section, applying the control on the degree of the numerator with respect to the term T_{2}: T_{2} = (E − 1)T′ + T′′. After this we can combine the terms T_{1} and T′ together using Theorem 2(b).

These actions can be included into algorithm hgadddec. However, it is worth noting that Theorem 11 does not claim to decrease, or even to preserve, the degree of the numerator of V if it is already small enough.

7 Examples

Example 1 For the hypergeometric term

T = (\frac{1}{n + 1} − \frac{1}{n}) ∏_{k=1}^{n−1} \frac{1}{k + 2},

applying hgadddec results in

T_{1} = \frac{1}{n} ∏_{k=1}^{n−1} \frac{1}{k + 2}, T_{2} = \frac{1}{3} ∏_{k=1}^{n−1} \frac{1}{k + 3}.

Example 2 For the hypergeometric term

T = (\frac{1}{n + 1} − \frac{1}{n} − 1) ∏_{k=1}^{n−1} \frac{1}{k + 2},

applying dterm results in

T_{1} = \frac{1}{n} ∏_{k=1}^{n−1} \frac{1}{k + 2}, T_{2} = − \frac{1}{3}(n + 1) ∏_{k=1}^{n−1} \frac{1}{k + 3}.

From the result shown above, T_{2} is regularly described by the triple (F, V, n_{0}) where

F = \frac{f_{1}}{f_{2}} , f_{1} = 1, f_{2} = n + 3, V = − \frac{1}{3}(n + 1).

Since V ∈ K[n], we apply dpol. The equation

f_{1} Ey − f_{2} y = f_{2} V

has a polynomial solution

y = \frac{1}{3}(n + 3).

Therefore,

T_{2} = (E − 1) (\frac{1}{3}(n + 2) ∏_{k=1}^{n−1} \frac{1}{k + 3}) .

Consequently, T is summable:

T = (E − 1) (\frac{n^{2} + 3 n + 2}{3 n} ∏_{k=1}^{n−1} \frac{1}{k + 3}) .

Example 3 Consider the hypergeometric term

T (n) = \frac{n^{2}}{\binom{2 n}{n}}

which can be written as

\frac{n^{2}}{2} ∏_{k=1}^{n−1} \frac{1/4 k + 1/4}{k + 1/2}.

Applying hgadddec results in T_{1} = 0, and

T_{2} = \frac{v_{1}}{v_{2}} ∏_{k=n_{0}}^{n−1} \frac{f_{1}}{f_{2}} = \frac{n^{2}}{2} ∏_{k=1}^{n−1} \frac{1/4 k + 1/4}{k + 1/2}.

Since deg(f_{2} − f_{1}) = deg(f_{1}) = 1, we are in case 2. An attempt to decrease the degree of v_{1} results in

T = (E − 1) ((−\frac{2}{3} n^{2} − \frac{5}{9} n − \frac{2}{3}) ∏_{k=1}^{n−1} \frac{1/4 k + 1/4}{k + 1/2}) + \frac{5}{54} ∏_{k=1}^{n−1} \frac{k + 1}{4 k + 6}.

Example 4 Consider the hypergeometric term

T (n) = \frac{1}{8} \begin{matrix}(n + 3) & (n + 2) & (n + 4) & (43 n + 35) \\ (2 n + 1) & (2 n + 3) & (2 n + 5) & (2 n + 7) \end{matrix}.

(Note that T is also a rational function of n.) Applying hgadddec results in

T_{1} = −\frac{15}{256} \frac{168 n^{2} + 460 n + 251}{(2 n + 1) (2 n + 3) (2 n + 5)}, T_{2} = \frac{v_{1}}{v_{2}} ∏_{k=n_{0}}^{n−1} \frac{f_{1}}{f_{2}} = \frac{86 n + 457}{256 n + 896} ∏_{k=0}^{n−1} 1.

Since −∞ = deg(f_{2} − f_{1}) < deg(f_{1}) − 1 = −1, we are in case 3a. An attempt to decrease the degree of v_{1} results in

T_{2} = (E − 1) (\frac{43}{128} n) + \frac{156}{256 n + 896}.

Therefore,

T = (E − 1) (\frac{1}{256} \frac{688 n^{4} + 3096 n^{3} + 1436 n^{2} − 5610 n − 3765}{(2 n + 1)(2 n + 3)(2 n + 5)}) + \frac{156}{256 n + 896}.

References

[1] S. A. Abramov. Rational component of the solutions of a first-order linear recurrence relation with a rational right-hand side. Zh. vychisl. mat. mat. fyz., 14:1035–1039, 1975. Transl. in USSR Comput. Math. Phys.

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

[3] S. A. Abramov. Indefinite sums of rational functions. In Proceedings ISSAC’95, 1995, 303–308.

[4] S. A. Abramov and M. Petkovšek. Canonical representations of hypergeometric terms. In Proceedings FPSAC’01, 2001, 1–10.

[5] R. W. Gosper. Decision procedure for indefinite hypergeometric summation. Proc. Natl. Acad. Sci. USA, 75:40–42, 1978.

[6] P. Paule. Greatest factorial factorization and symbolic summation. J. Symb. Comp., 20:235–268, 1995.

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

[8] R. Pirastu and V. Strehl. Rational summation and Gosper-Petkovšek representation. J. Symb. Comp., 20:617–635, 1995.