D’Alembertian Solutions of Linear Differential and Difference Equations

Sergei A. Abramov

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

                   abramov@sms.ccas.msk.su

Marko Petkovšek

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

                                                            marko.petkovsek@uni-lj.si

Abstract

D’Alembertian solutions of differential (resp. difference) equations are those expressible as nested indefinite integrals (resp. sums) of hyperexponential functions. They are a subclass of Liouvillian solutions, and can be constructed by recursively finding hyperexponential solutions and reducing the order. Knowing d’Alembertian solutions of Ly = 0, one can write down the corresponding solutions of Ly = f and of L^{∗}y = 0.

1 Introduction

Functions with rational logarithmic derivative play an important role in manipulation of differential equations, notably in finding Liouvillian solutions of linear differential equations and in factorization of linear differential operators. As any algorithm for finding solutions of linear differential equations in a certain class of functions, the algorithm for finding solutions with rational logarithmic derivative can be combined with the standard technique of reduction of order (also known as d’Alembert substitution) to yield solutions in a (possibly) larger class of functions which, in this case, we call d’Alembertian functions. They can be described as nested indefinite integrals of functions with rational logarithmic derivative, or equivalently, as functions that are annihilated by products of first-order differential operators. Similar observations can be made in the case of linear difference equations and difference operators where d’Alembertian functions can be described as nested indefinite sums of hypergeometric terms.

Let k be a differential field of characteristic 0 with derivation D. Denote by H(k) the set of all nonzero elements h belonging to some differential extension field K of k and such that Dh/h ∈ k.

Similarly, if k is a difference field of characteristic 0 with shift operator E, we denote by H(k) the set of all nonzero elements h belonging to some difference extension field K of k and such that Eh/h ∈ k.

We use ∫ u to denote the set of all v such that Dv = u. If U is a set of functions, ∫ U denotes the set of all v such that Dv ∈ U. Similarly, ∑ u denotes the set of all v such that Δv = u, and ∑ U denotes the set of all v such that Δv ∈ U, where Δ = E − 1. In particular, ∫ 0 resp. ∑ 0 denotes the set of constants.

Consider the homogeneous equation

Ly = 0  (1)

where L ∈ k[D] is a linear differential operator with coefficients in k. Let ord L = n. If φ ∈ H(k) solves (1) then the substitution

y = φ ∫ u  (2)

leads to an (n − 1)-st order equation for u with coefficients in k. Similarly, if L ∈ k[E] is a linear difference operator with coefficients in k the substitution

y = φ ∑ u  (3)

leads to an (n − 1)-st order equation for u with coefficients in k.

Assume that the new equation is reduced again using its solution φ_{2} ∈ H(k) and so on, until the last d’Alembert substitution connected with φ_{r} ∈ H(k) produces an equation with no solution in H(k). Then a subspace of solutions of (1) has been found, namely

φ_{1} ∫ φ_{2} … ∫ φ_{r} ∫ 0  (4)

in the differential case, and

φ_{1} ∑ φ_{2} … ∑ φ_{r} ∑ 0  (5)

in the difference case. In [Abr93] it was shown that this subspace is independent of the choice of solutions φ_{i}, and that it is equal to the space of all d’Alembertian solutions of (1). Furthermore, (4) and (5) correspond to a factorization

L = L_{r}R_{r}R_{r−1} ⋯ R_{1}  (6)

of L where L_{r} has no first-order right factor, R_{i} are monic first-order operators, and if

h_{i} = φ_{1}φ_{2} ⋯ φ_{i}  (7)

in the differential case, or

h_{i} = E^{i−1}φ_{1}E^{i−2}φ_{2} ⋯ φ_{i}  (8)

in the difference case, then R_{i}h_{i} = 0.

If the equation (1) was reduced by means of φ_{1}, φ_{2}, …, φ_{r} and the last d’Alembert substitution connected with φ_{r} produced an equation M_{r}y = 0, then the general solution of (1) can be written as

φ_{1} ∫ φ_{2} … ∫ φ_{r} ∫ g resp. φ_{1} ∑ φ_{2} … ∑ φ_{r} ∑ g

(9)

where g is the general solution of equation M_{r}y = 0.

The relationship between L_{r} and M_{r} is as follows: Write L ∼ M when there is an element c ∈ k \ {0} such that L = cM. Then M_{r} ∼ L_{r}h_{r} (in the differential case), resp. M_{r} ∼ L_{r}Eh_{r} (in the difference case). Here M_{r}, L_{r}, h_{r} and Eh_{r} are regarded as elements of K[X] where K is an extension ring of k containing h_{r}.

In this paper we give new proofs for some of the results from [Abr93] in the more general setting of linear operators. We attempt to treat differential and difference equations in a unified way. In addition, we show how d’Alembertian solutions of the adjoint equation can be used to construct further solutions of the original equation.

In Section 2 we cite some results on skew polynomial rings. The main result of Section 3 is Theorem 3 which says that whenever an equation has a nonzero d’Alembertian solution then it has a hyperexponential solution (i.e., one satisfying a first-order equation). This is a (modest) analogue of Singer’s theorem saying that when a differential equation has a nonzero Liouvillian solution then it has a solution whose logarithmic derivative is algebraic over the coefficient field [Sin81]. We also show that d’Alembertian functions form a linear space, and give an algorithm to find a basis of all d’Alembertian solutions for the given equation. D’Alembertian solutions of Ly = 0 are used to find solutions of Ly = f in Section 4, and to find those of L^{∗}y = 0 in Section 5.

We will need explicit solutions of first-order nonhomogeneous equations. Let R_{1} ∈ k[D] be a monic differential operator of order 1. Then the general solution of equation R_{1}y = f can be written as

y = h_{1} ∫ \frac{f}{h_{1}}  (10)

where h_{1} ∈ H(k) is such that R_{1}h_{1} = 0. Using (10) repeatedly we see that the general solution of an equation R_{n}R_{n−1} ⋯ R_{1}y = f where R_{n}, R_{n−1}, …, R_{1} ∈ k[D] are monic first-order operators can be written as

y = h_{1} ∫ \frac{h_{2}}{h_{1}} ∫ \frac{h_{3}}{h_{2}} … ∫ \frac{f}{h_{n}}  (11)

where h_{i} ∈ H(k) are such that R_{i}h_{i} = 0.

Similarly, if R_{1} ∈ k[E] is a monic difference operator of order 1, the general solution of equation R_{1}y = f can be written as

y = h_{1} ∑ \frac{f}{Eh_{1}}  (12)

where h_{1} ∈ H(k) is such that R_{1}h_{1} = 0. Using (12) repeatedly we see that the general solution of an equation R_{n}R_{n−1} ⋯ R_{1}y = f where R_{n}, R_{n−1}, …, R_{1} ∈ k[E] are monic first-order operators can be written as

y = h_{1} ∑ \frac{h_{2}}{Eh_{1}} ∑ \frac{h_{3}}{Eh_{2}} … ∑ \frac{f}{Eh_{n}}  (13)

where h_{i} ∈ H(k) are such that R_{i}h_{i} = 0.

2 Algebraic preliminaries

Let k be a field of characteristic zero, X an indeterminate over k, σ a nonzero field-endomorphism of k, and δ : k → k a map satisfying

δ(a + b) = δa + δb and δ(ab) = σ(a) δb + δa b (14)

for any a, b ∈ k. The left skew polynomial ring given by σ and δ is the ring (k[X], +, ·) of polynomials in X over k with the usual polynomial addition, and the multiplication given by

Xa = σ(a)X + δa for any a ∈ k.

To avoid confusing it with the usual commutative polynomial ring k[X], the left skew polynomial ring is denoted k[X; σ, δ]. We will denote by Const_{σ,δ}(k) the constant subfield of k (i.e., the set of all a ∈ k such that σ(a) = a and δa = 0).

Example 1 Let k be a differential field of characteristic 0 with derivation D. Let σ be the identity on k and take δ = D. Then k[X; σ, δ] = k[D], the ring of linear differential operators with coefficients in k. □

Example 2 Let k be a difference field of characteristic 0 with transform (i.e., shift operator) E. Take σ = E and δ = 0. Then k[X; σ, δ] = k[E], the ring of linear difference operators with coefficients in k. □

The ring k[X; σ, δ] has no zero divisors and possesses a right Euclidean division algorithm. For any two nonzero polynomials R, S ∈ k[X; σ, δ], one can compute their greatest common right divisor gcrd(R, S) and their least common left multiple lclm(R, S). We define gcrd(R, S) and lclm(R, S) to be monic. For details, see [Ore33] or [Bro&Pet94].

Definition 1 For R, S ∈ k[X; σ, δ]\{0}, let R/S denote the right quotient of lclm(R, S) by S.

Note that (R/S)S = lclm(R, S) = (S/R)R.

Proposition 1 Let R, S ∈ k[X; σ, δ] \ {0}.

1. deg R/S = deg R − deg gcrd(R, S).

2. If R is irreducible then so is R/S.

3. If R = R_{1}R_{2} ⋯ R_{m} where R_{1}, R_{2}, …, R_{m} ∈ k[X; σ, δ] are monic then R/S = (R_{1}/S_{1})(R_{2}/S_{2}) ⋯ (R_{m}/S_{m}) where S_{j} = S/(R_{j+1}R_{j+2} ⋯ R_{m}), for j = 1, 2, …, m.

For a proof, see [Ore33, Thm. I/16] and [Koo91, pp. 16–20].

Definition 2 A polynomial R ∈ k[X; σ, δ] splits into firstorder factors if deg R = 0, or deg R = d ≥ 1 and there are polynomials R_{1}, R_{2}, …, R_{d} ∈ k[X; σ, δ] such that deg R_{i} = 1 and R = R_{1}R_{2} ⋯ R_{d}.

Corollary 1 Let R, S ∈ k[X; σ, δ] \ {0}. If R splits into first-order factors then so does R/S.

Definition 3 Let R, S ∈ k[X; σ, δ]. R is similar to S if R = S/T for some T ∈ k[X; σ, δ] such that deg gcrd(S, T) = 0.

Note that similar polynomials are of the same degree, and that similarity is a symmetric relation.

Theorem 1 [Ore33, Thm. II/1] Let L ∈ k[X; σ, δ] be monic. If R_{1}R_{2} ⋯ R_{m} and S_{1}S_{2} ⋯ S_{n} are two factorizations of L into irreducible monic factors, then m = n and the factors are similar in pairs.

Corollary 2 Let L ∈ k[X; σ, δ] split into first-order factors. If L_{1} is a right factor of L then L_{1} splits into first-order factors.

In particular, if L, M ∈ k[X; σ, δ] and L splits into firstorder factors then so does gcrd(L, M). An algorithm which computes gcrd(L, M) in factored form (given L in factored form) is described in [Abr93].

3 D’Alembertian subspace

Henceforth we limit our attention to the rings of differential (resp. difference) operators k[X] where X is D (resp. E). Let K be a differential (resp. difference) extension ring of k such that the constant subring Const_{X}(K) is a field. Then any element R ∈ k[X] can be viewed as acting on K, and its kernel Ker R is a linear space over Const_{X}(K). Call K adequate for R if dim Ker R = ord R. It is well known that for any finite set of operators R ⊆ k[X] there is an extension field K of k which is adequate for all R ∈ R. If K is adequate for R and S then Ker R/S = S Ker R (cf. [Koo91]).

Definition 4 Let k be a differential (resp. difference) field of characteristic 0 and y an element of a differential (resp. difference) extension ring K of k. Then y is hyperexponential over k if y ≠ 0 and Ry = 0 for some first-order operator R ∈ k[X]; and d’Alembertian over k if Ry = 0 for some R ∈ k[X] which splits into first-order factors. We will denote the set of all hyperexponential elements over k by H(k), and the set of all d’Alembertian elements over k by A(k).

Theorem 2 Let K be a differential (resp. difference) extension ring of k such that Const_{X}(K) is a field. Then A(k) is a linear space over Const_{X}(K).

Proof: Let a, b ∈ A(k) and λ, μ ∈ Const_{X}(K). Then there are monic operators R and S which split into first-order factors, and satisfy Ra = Sb = 0. Since lclm(R, S) (λa + μb) = 0 and lclm(R, S) = (R/S)S splits into first-order factors by Corollary 1, it follows that λa + μb ∈ A(k). □

Lemma 1 Let L ∈ k[X]. If y ∈ H(k) then Ly = qy for some q ∈ k, and if Ly ≠ 0 then Ly ∈ H(k). If y ∈ A(k) then Ly ∈ A(k).

Proof: If Ry = 0 then (R/L)Ly = (L/R)Ry = 0. As ord R/L ≤ ord R, and since by Corollary 1 R/L splits into linear factors when R does, the lemma follows. □

Theorem 3 Let L ∈ k[X]. If the equation Ly = 0 has a nonzero d’Alembertian solution then it also has a hyperexponential solution.

Proof: Let a ≠ 0 and La = Ra = 0 where R ∈ k[X] splits into linear factors. If M is a minimal operator annihilating a then M is a right factor of both L and R. By Corollary 2, M splits into linear factors. It follows that L has a firstorder right factor, or equivalently, that the equation Ly = 0 has a hyperexponential solution. □

Theorem 4 Let L ∈ k[X]. There are unique operators L_{1}, L_{2} ∈ k[X] such that L = L_{1}L_{2}, L_{1} has no first-order right factor, and L_{2} is monic and splits into first-order factors.

Proof: To prove existence, let L_{2} be a monic right factor of L of largest order which splits into first-order factors. Let L_{1} be the right quotient of L by L_{2}. Then L = L_{1}L_{2} and L_{1} has no first-order right factor.

To prove uniqueness, assume that additionally L = M_{1}M_{2} where M_{1} has no first-order right factor, and M_{2} is monic and splits into first-order factors. If a ∈ Ker L_{2} \ Ker M_{2} then y = M_{2}a is a nonzero d’Alembertian solution of M_{1}y = 0. Then by Theorem 3, M_{1} has a first-order right factor, contrary to the assumption. It follows that Ker L_{2} = Ker M_{2}, hence L_{2} = M_{2} and also L_{1} = M_{1}. □

Assume that there is an algorithm H which takes an operator L ∈ k[X] as input and returns a hyperexponential solution of the equation Ly = 0 if it exists. In the case when k is the field of rational functions F (x) over some field F of characteristic 0 such algorithms are given, e.g., in [Sin91] or [Bro92b] for differential operators, and in [Pet92] for difference operators. We show that algorithm H, used recursively in combination with reduction of order, will construct a basis for the space of all d’Alembertian solutions of Ly = 0. We call this algorithm A.

Algorithm A

INPUT: A nonzero linear operator L ∈ k[X].

OUTPUT: A basis for the space Ker L ∩ A(k).

1. Call H on Ly = 0.

If no hyperexponential solution was found then

return ∅ and stop. Otherwise let y_{1} be a hyperexponential solution

of Ly = 0.

2. Let R_{1} be the monic first-order operator such that

R_{1}y_{1} = 0. Divide L by R_{1} to obtain L = L_{1}R_{1}.

3. Recursively call A on L_{1}. Let the output be {z_{2}, z_{3}, …, z_{m}}.

4. For i = 2, 3, …, m construct solutions y_{i} of R_{1}y_{i} = z_{i}

using (10) and (12). Return {y_{1}, y_{2}, …, y_{m}} and stop.

In step 4, Gosper’s algorithm [Gos78] applied to (12) (resp. its continuous analogue [Alm&Zei90] applied to (10)) may be able to eliminate some summation (resp. integration) signs from the final result.

Theorem 5 Algorithm A returns a basis for the space Ker L ∩ A(k).

Proof: Obviously algorithm A finds a factorization L = L_{m}R_{m}R_{m−1} ⋯ R_{1} where ord R_{i} = 1 and the equation L_{m}y = 0 has no hyperexponential solution, hence by Theorem 3 no nonzero d’Alembertian solution.

We claim that Ker L ∩ A(k) = Ker R_{m}R_{m−1} ⋯ R_{1}. If R_{m}R_{m−1} ⋯ R_{1}a = 0 then La = 0. Conversely, assume that a ∈ A(k) and La = 0 but b := R_{m}R_{m−1} ⋯ R_{1}a ≠ 0. By Lemma 1, b ∈ A(k). Since L_{m}b = La = 0, it follows from the previous paragraph that b = 0, proving the claim.

It is easy to show that R_{j}R_{j−1} ⋯ R_{1}y_{j} = 0 and R_{j−1} ⋯ R_{1}y_{j} ≠ 0 for 1 ≤ j ≤ m. Hence y_{j} ∈ Ker R_{m}R_{m−1} ⋯ R_{1} = Ker L ∩ A(k) for 1 ≤ j ≤ m. Let ∑_{i=1}^{m} α_{i}y_{i} = 0 where α_{i} ∈ Const_{X}(K) for some extension ring K of k. Successively applying R_{j}R_{j−1} ⋯ R_{1} for j = m−1, …, 1 to both sides shows that α_{m} = … = α_{1} = 0. Since dim Ker L ∩ A(k) = dim Ker R_{m}R_{m−1} ⋯ R_{1} = m, the set {y_{1}, y_{2}, …, y_{m}} is a basis for Ker L ∩ A(k). □

Example 3 Let n be a discrete variable and E the shift operator with respect to n. Let the operators from k[E] act on the quotient ring of sequences over k by the ideal of the eventually zero sequences (in other words, two sequences are identified if they agree from some point on). Consider the equation

2(1 + n)^{3}(2 + n)^{2}(3 + n)^{2}(4 + n)^{2}(5 + n)y_{n} −

(2 + n)^{2}(3 + n)^{2}(4 + n)^{2}(5 + n)(2 + 6n + 5n^{2})y_{n+1} +

n(3 + n)^{2}(4 + n)^{2}(5 + n)(1 + 6n + 4n^{2})y_{n+2} +

n(1 + n)(4 + n)^{2}(5 + n)(17 + 4n − n^{2})y_{n+3} − (15)

n(1 + n)(2 + n)(5 + n)(19 + 5n)y_{n+4} + n(1 + n)(2 + n)(3 + n)y_{n+5} = 0 .

Algorithm A, or repeated d’Alembert substitution, produces the general solution of (15) in the form

n! ∑ n ∑ g_{n}  (16)

where g_{n} is the general solution of the third-order equation

2(1 + n)y_{n} − ny_{n+1} − 3y_{n+2} + y_{n+3} = 0  (17)

which has no solution in H(k). Nevertheless, we will show in Section 5 that the general solution of (17), and hence of (15), can be expressed in terms of solutions of a second-order equation. □

4 Nonhomogeneous equations

Consider the equation

Ly = f  (18)

where L ∈ k[X] and ord L = n. Let c be the leading coefficient of L.

Theorem 6 If  L  splits  into  first-order

factors, and φ_{1} ∫ φ_{2} … ∫ φ_{n} ∫ 0 (in the differential case), resp. φ_{1} ∑ φ_{2} … ∑ φ_{n} ∑ 0 (in the difference case) is the general solution of the homogeneous equation Ly = 0 then

φ_{1} ∫ φ_{2} … ∫ φ_{n} ∫ \frac{f}{cφ_{1} ⋯ φ_{n}}  (19)

respectively

φ_{1} ∑ φ_{2} … ∑ φ_{n} ∑ \frac{f}{cE^{n}φ_{1}E^{n−1}φ_{2} … Eφ_{n}}  (20)

is the general solution of (18).

Proof: According to (11), the general solution of (18) is

y = h_{1} ∫ \frac{h_{2}}{h_{1}} ∫ \frac{h_{3}}{h_{2}} … ∫ \frac{f}{ch_{n}}

where, according to (7), h_{i} = φ_{1}φ_{2} ⋯ φ_{i}. This implies (19). In the difference case, we use (13) instead of (11), and (8) instead of (7). □

This approach does not require solving systems of linear algebraic equations (as does the method of variation of constants).

Example 4 Let (n+1)y_{n} −(2n+3)y_{n+1} +(n+2)y_{n+2} = 1. The general solution

∑ \frac{1}{n + 1} ∑ 0

of the corresponding homogeneous equation leads by (20) immediately to the general solution of the original equation:

y_{n} = ∑ \frac{1}{n + 1} ∑ 1 = ∑ (\frac{C_{1}}{n + 1} + 1) = n + C_{1}H_{n} + C_{2}

where H_{n} = ∑_{j=1}^{n} 1/j is the n-th harmonic number, and C_{1}, C_{2} are arbitrary constants. □

Now consider the problem of finding all d’Alembertian solutions of (18) assuming that f satisfies Mf = 0 for some M ∈ k[X]. Then MLy = 0 for any solution y of (18). As in Theorem 4, write ML = BA where A splits into first-order factors, and B has no first-order right factor.

Proposition 2 With the above notation, equation (18) has a d’Alembertian solution if and only if (A/L)f = 0.

Proof: If La = f and a ∈ A(k) then Aa = 0. Hence (A/L)f = (A/L)La = (L/A)Aa = 0. Conversely, if (A/L)f = 0 then f ∈ Ker A/L = L Ker A, hence there is an a ∈ Ker A such that f = La. □

When (A/L)f = 0 it is possible to construct a particular d’Alembertian solution a of (18) by expanding it into a power series around some point which is not a singularity of the equation MLy = 0 (the details will appear in [Abr94b]).

5 Adjoint equations

The adjoint of a linear differential operator is defined by

(∑_{i=0}^{n} c_{i}D^{i})^{∗} = ∑_{i=0}^{n}(−1)^{i}D^{i}c_{i} .

It can be shown that for any L_{1}, L_{2} ∈ k[D],

(L_{1}^{∗})^{∗} = L_{1}, (L_{1}L_{2})^{∗} = L_{2}^{∗}L_{1}^{∗} .  (21)

The adjoint of a linear difference operator is defined by

(∑_{i=0}^{n} c_{i}E^{i})^{∗} = ∑_{i=0}^{n} E^{i}c_{n−i}

when c_{n}, c_{0} ≠ 0. It can be shown that for any L_{1}, L_{2} ∈ k[E],

(L_{1}^{∗})^{∗} = E^{n}L_{1}E^{−n}, (L_{1}L_{2})^{∗} = (E^{n}L_{2}^{∗}E^{−n})L_{1}^{∗} (22)

where n = deg(L_{1}). Hence in both cases left factors of L correspond to right factors of L^{∗}, and vice versa.

Let R_{1} ∈ k[X] be a monic operator of order 1, and h_{1} ∈ H(k) such that R_{1}h_{1} = 0. Then it is easy to see that

R_{1}^{∗} \frac{1}{h_{1}} = 0  (23)

in the differential case, and

R_{1}^{∗} \frac{1}{Eh_{1}} = 0  (24)

in the difference case.

Theorem 7 Let L ∈ k[X], ord L = n, and let c be the leading coefficient of L. Let φ_{1} ∫ φ_{2} … ∫ φ_{n} ∫ 0 (in the differential case), resp. φ_{1} ∑ φ_{2} … ∑ φ_{n} ∑ 0 (in the difference case) be the general solution of equation Ly = 0 in some extension ring K of k. If φ_{1}, φ_{2}, …, φ_{n} ∈ K are invertible, then

\frac{1}{cφ_{n}φ_{n−1} … φ_{1}} ∫ φ_{n} ∫ φ_{n−1} … ∫ φ_{2} ∫ 0 (25)

in the differential case, respectively

\frac{1}{cEφ_{n} … E^{n}φ_{1}} ∑ Eφ_{n} … ∑ E^{n−1}φ_{2} ∑ 0  (26)

in the difference case, is the general solution of the adjoint equation L^{∗}y = 0 in K.

Proof: According to (6),

L = cR_{n}R_{n−1} ⋯ R_{1}

where R_{i} are monic first-order operators such that R_{i}h_{i} = 0, with h_{i} defined by (7) resp. (8).

In the differential case, let h_{i}^{∗} = 1/h_{i}. Then by (23), R_{i}^{∗}h_{i}^{∗} = 0. Since L^{∗} = R_{1}^{∗}R_{2}^{∗} ⋯ R_{n}^{∗}c, the general solution of L^{∗}y = 0 is, by (11),

\frac{h_{n}^{∗}}{c} ∫ \frac{h_{n−1}^{∗}}{h_{n}^{∗}} ∫ … \frac{h_{1}^{∗}}{h_{2}^{∗}} ∫ 0 = \frac{1}{ch_{n}} ∫ \frac{h_{n}}{h_{n−1}} ∫ … \frac{h_{2}}{h_{1}} ∫ 0

which, using (7), gives (25).

In the difference case, L^{∗} = S_{1}S_{2} ⋯ S_{n}c where S_{j} = E^{n−j}R_{j}^{∗}E^{j−n}. The operator S_{j} is not monic but rather has leading coefficient equal to c_{j} = −E^{n−j+2}h_{j}/E^{n−j+1}h_{j}. Let h_{j}^{∗} = 1/Eh_{j} and g_{j} = E^{n−j}h_{j}^{∗}. Then by (24), S_{j}g_{j} = 0.

By a slight generalization of (13) to non-monic factors, the general solution of L^{∗}y = 0 is given by

y = \frac{g_{n}}{c} ∑ \frac{g_{n−1}}{c_{n}Eg_{n}} ∑ \frac{g_{n−2}}{c_{n−1}Eg_{n−1}} … ∑ \frac{g_{1}}{c_{2}Eg_{2}} ∑ 0 .

Substitution of expressions given above for g_{j} and c_{j} together with (8), and absorption of the sign into ∑ 0, now yields (26). □

Example 5 Consider equation (15) again. The adjoint equation of (17)

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

has general solution

\frac{1}{2^{n}} ∑ u_{n} ∑ v_{n} ∑ 0,  (27)

where u_{n} ∑ v_{n} ∑ 0 is the general solution of equation

4y_{n} − 2y_{n+1} − (4 + n)y_{n+2} = 0  (28)

which has no hypergeometric solution. Assume that u_{n} and v_{n} are nonzero for all large enough n. By Theorem 7,

g_{n} = \frac{2^{n}}{(n + 4)v_{n+1}u_{n+2}} ∑ v_{n+1} ∑ u_{n+2} ∑ 0

is the general solution of the second adjoint of (17), hence

n! ∑ n ∑ \frac{2^{n}}{(n + 1)v_{n−2}u_{n−1}} E^{−3} (∑ v_{n+1} ∑ u_{n+2} ∑ 0)

is the general solution of (15). □

Note that this approach is also suitable in the case of a nonhomogeneous equation.

We observe that adjoint equations offer an opportunity to parallelize the solving process. Consider the original equation Ly = 0 together with the adjoint equation L^{∗}y = 0 and begin to search for particular solutions of both of them in parallel. If a particular solution of one of them is found then we reduce the order of the equation and begin to search for particular solutions of the new equation and its adjoint. If some branch of this process leads to an equation of order zero we use formulae (25) and (9) to obtain the general solution of the original equation.

6 Concluding remarks

Call an operator L ∈ k[X] rational if Ker L has a basis in k. If in the definition of complete factorability the factors are required to be both first-order and rational, then all our results remain valid provided that hyperexponential solutions are everywhere replaced by solutions in k, and that in algorithm A, in place of algorithm H an algorithm for finding solutions in k is used. In the case when k = F (x) such algorithms are given in [Abr89] both for differential and for difference equations, and in [Abr&Kva91] and [Bro92a] for differential equations.

References

[Abr89] S.A. Abramov (1989): Rational solutions of linear difference and differential equations with polynomial coefficients, USSR Comput. Maths. Math. Phys. 29, 7–12, transl. from Zl. Vychislit. matem. mat. fiz. 29, 1611–1620.

[Abr&Kva91] S.A. Abramov, K.Yu. Kvashenko (1991): Fast algorithm to search for the rational solutions of linear differential equations, Proc. ISSAC’91, 267–270.

[Abr93] S.A. Abramov (1993): On d’Alembert substitution, Proc. ISSAC’93, 20–26.

[Abr94a] S.A. Abramov (1993): D’Alembert substitution and adjoint equation (computer algebra aspect), Comput. Maths. Math. Phys. 34, no. 7. In print.

[Abr94b] S.A. Abramov (1994): D’Alembertian solutions of nonhomogeneous linear ordinary differential and difference equations. To be published.

[Alm&Zei90] G.Almkvist, D.Zeilberger (1990): The method of differentiating under the integral sign, J. Symb. Comp. 10, 571–591.

[Bro92a] M. Bronstein (1992): On solutions of linear ordinary differential equations in their coefficient field, J. Symb. Comp. 13, 413–439.

[Bro92b] M. Bronstein (1992): Linear differential equations: breaking through the order 2 barrier, Proc. ISSAC’92, 42–48.

[Bro&Pet94] M. Bronstein, M. Petkovšek (1994): On Ore rings, linear operators and factorisation, Programmirovanie 1, no. 1. To appear.

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

[Koo91] R.J. Kooman (1991): Convergence properties of recurrence sequence, Centrum voor Wiskunde en Informatica, CWI Tract 83, Amsterdam.

[Ore33] O. Ore (1933): Theory of non-commutative polynomials, Ann. Maths. 34, 480–508.

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

[Sin81] M.F. Singer (1981): Liouvillian solutions of n-th order homogeneous linear differential equations, Amer. J. Math. 103, 661–681.

[Sin91] M.F. Singer (1991): Liouvillian solutions of linear differential equations with Liouvillian coefficients, J. Symb. Comp. 11, 251–273.