Special Formal Series Solutions of Linear Operator Equations

Sergei A. Abramov^{∗}

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

                sabramov@cs.msu.su

Marko Petkovšek^{†}

Department of Mathematics University of Ljubljana Jadranska 19, 1111 Ljubljana, Slovenia

                                                marko.petkovsek@fmf.uni-lj.si

Anna Ryabenko^{‡}

Department of Computational Mathematics & Cybernetics, Moscow State University Moscow 119899, Russia

                                    ryabenko@cs.msu.su

Abstract

The transformation which assigns to a linear operator L the recurrence satisfied by coefficient sequences of the polynomial series in its kernel, is shown to be an isomorphism of the corresponding operator algebras. We use this fact to help factoring q-difference and recurrence operators, and to find “nice” power series solutions of linear differential equations.

In particular, we characterize generalized hypergeometric series that solve a linear differential equation with polynomial coefficients at an ordinary point of the equation, and show that these solutions remain hypergeometric at any other ordinary point. Therefore to find all generalized hypergeometric series solutions, it suffices to look at a finite number of points: all the singular points, and a single, arbitrarily chosen ordinary point.

We also show that at a point x = a we can have power series solutions with:

• polynomial coefficient sequence – only if the equation is singular at a + 1,

• non-polynomial rational coefficient sequence – only if the equation is singular at a.

1 Introduction and notation

The method of solving linear differential equations by means of power series has been known for centuries. Here we look at formal series that are based on other polynomial sequences besides the powers, and show how they can be used to reduce questions about operators of different types (e.g., differential, difference, q-difference) to questions about operators of a single type, namely recurrence operators.

We consider a transformation R_{B} which assigns to a linear operator L acting on the polynomial algebra K[x] its induced recurrence operator R_{B}L. The transformation is defined in Section 2. We show that R_{B} is an isomorphism of the corresponding operator algebras. This result is applied in Sections 3, 4, and 5 to the cases of q-difference, recurrence, and differential operators. In particular, we show how transformation R_{B} can help factor these operators. This is important because although general factorization algorithms are known [8], they are still highly impractical.

Subsections 5.1, 5.2, and 5.3 are devoted to the search for “nice” power series solutions in the differential case. We are interested in series with coefficients which are polynomial, rational, or hypergeometric in their subscript, respectively.

∗Supported in part by grant 95-IN-RU-412 from the RFBR and INTASS.

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

‡Supported in part by grant 95-IN-RU-412 from the RFBR and INTASS.

Call a sequence (c_{n})_{n=0}^{∞} hypergeometric if there is a rational function R(x) such that c_{n+1} = R(n)c_{n} for all large enough n. If c_{n} is hypergeometric and eventually nonzero then R(x) is uniquely determined and we call it the consecutive-term ratio of c_{n}. Obviously, a rational sequence is hypergeometric, and the product of hypergeometric sequences is hypergeometric.

Two hypergeometric sequences a_{n} and b_{n} are similar if there is a rational function r(x) such that a_{n} = r(n)b_{n} for all large enough n. A linear combination of pairwise similar hypergeometric terms is obviously hypergeometric. Also, if a_{n} is hypergeometric and k a fixed integer, then a_{n+k} is similar to a_{n}.

A formal power series y = ∑_{n=0}^{∞} c_{n}x^{n} is called a (generalized) hypergeometric series if the sequence of coefficients (c_{n})_{n=0}^{∞} is hypergeometric.

Lemma 1 Let y = ∑_{n=0}^{∞} c_{n}x^{n} be a hypergeometric series, and p(x) a polynomial. Then p(x)y is a hypergeometric series with similar coefficients.

Proof: Let p(x) = ∑_{k=0}^{d} u_{k}x^{k} and p(x)y = ∑_{n=0}^{∞} b_{n}x^{n}. Then

p(x)y = ∑_{k=0}^{d} ∑_{n=0}^{∞} c_{n}u_{k}x^{n+k} = ∑_{n=0}^{∞} x^{n} ∑_{k=0}^{min{n,d}} u_{k}c_{n−k},

so b_{n} = ∑_{k=0}^{d} u_{k}c_{n−k} for n ≥ d. This is a linear combination of hypergeometric terms which are all similar to c_{n}, hence b_{n} is hypergeometric and similar to c_{n}. □

Following [9], we denote the rising and falling factorial powers by

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

respectively.

We use IN to denote the set of nonnegative integers. Throughout the paper, K denotes an arbitrary field of characteristic zero. We denote by E the shift operator on polynomials and rational functions over K, so that Er(x) = r(x + 1), for any r ∈ K(x). Similarly, we denote by E_{n} the shift operator on sequences over K, so that E_{n}a_{n} = a_{n+1} for any sequence ⟨a_{n}⟩_{n=0}^{∞} or ⟨a_{n}⟩_{n∈ZZ}.

A preliminary version of this paper appeared as [5].

2 Compatible bases and transformation R_{B}

Let K be a field of characteristic zero. Denote by K[x] the K-algebra of univariate polynomials over K, and by L_{K[x]} the K-algebra of linear operators L : K[x] → K[x]. Further let B = ⟨P_{n}(x)⟩_{n=0}^{∞} be a sequence of polynomials from K[x] such that

P1. deg P_{n} = n for n ≥ 0,

P2. P_{n} | P_{m} for 0 ≤ n < m.

From P1 it follows that {P_{0}, P_{1}, …} is a basis of K[x].

Definition 1 A basis B of K[x] satisfying P1, P2, and an operator L ∈ L_{K[x]} are compatible if there are A, B ∈ IN, and elements α_{i,n} ∈ K for n ≥ 0 and −A ≤ i ≤ B, such that

LP_{n} = ∑_{i=−A}^{B} α_{i,n} P_{n+i},  (1)

with P_{k} = 0 when k < 0. □

In other words, L is compatible with B if the infinite matrix [α_{i−n,n}]_{i,n∈IN} corresponding to L in basis B is band-diagonal.

Example 1 Let Dp(x) = p′(x) and Ep(x) = p(x + 1). Let P = ⟨P_{n}(x)⟩_{n=0}^{∞} = ⟨x^{n}⟩_{n=0}^{∞} be the power basis. Then DP_{n} = nP_{n−1} and EP_{n} = ∑_{k=0}^{n} \binom{n}{k}P_{k}, so P is compatible with D (take A = 1, B = 0, α_{−1,n} = n, α_{0,n} = 0), but not with E.

On the other hand, let C = ⟨P_{n}(x)⟩_{n=0}^{∞} = ⟨\binom{x}{n}⟩_{n=0}^{∞} be the binomial coefficient basis. Then EP_{n} = P_{n} + P_{n−1} and DP_{n} = ∑_{k=0}^{n−1}(−1)^{n+k}/(k−n)P_{k}, so C is compatible with E (take A = 1, B = 0, α_{−1,n} = α_{0,n} = 1), but not with D.

Now let Lp(x) = xp(x), and take any basis B = ⟨P_{n}(x)⟩_{n=0}^{∞} which satisfies P1 and P2. Then LP_{n} = ∑_{k=0}^{n+1} a_{k}(n)P_{k} for some constants a_{k}(n) ∈ K. Because of P2, ∑_{k=0}^{n−1} a_{k}(n)P_{k} is divisible by P_{n}. Being a polynomial of degree at most n − 1, it must vanish, therefore LP_{n} = a_{n+1}(n)P_{n+1} + a_{n}(n)P_{n}. So any basis B satisfying P1, P2 is compatible with multiplication by the independent variable (take A = 0, B = 1, α_{0,n} = a_{n}(n), α_{1,n} = a_{n+1}(n)). □

Let l_{n} : K[x] → K be linear functionals such that l_{n}(P_{m}) = δ_{mn}. Property P2 implies that l_{n}(P_{k}P_{m}) = 0 when n < max{k, m}. Therefore K[x] naturally embeds into the algebra K[[B]] of formal series of the form

y = ∑_{n=0}^{∞} c_{n}P_{n}(x)  (c_{n} ∈ K),  (2)

with multiplication defined by

(∑_{n=0}^{∞} c_{n}P_{n}(x)) (∑_{n=0}^{∞} d_{n}P_{n}(x)) = (∑_{n=0}^{∞} e_{n}P_{n}(x))

where

e_{n} = ∑_{max{j,k}≤n≤j+k} c_{j}d_{k} l_{n}(P_{j}P_{k}).

If B and L are compatible then L can be extended to K[[B]] by setting

L ∑_{n=0}^{∞} c_{n}P_{n}(x) = ∑_{n=0}^{∞} ∑_{i=−A}^{B} α_{i,n−i}c_{n−i}P_{n}(x) = ∑_{n=0}^{∞} ∑_{i=−B}^{A} α_{−i,n+i}c_{n+i}P_{n}(x)  (3)

with A, B and α_{i,n} as in (1), and c_{n} = 0 when n < 0. Clearly, a formal series y ∈ K[[B]] satisfies Ly = 0 if and only if its coefficient sequence c = ⟨c_{n}⟩_{n∈ZZ} satisfies the recurrence

∑_{i=−B}^{A} α_{−i,n+i}c_{n+i} = 0  (n ≥ 0)  (4)

where, again, c_{n} = 0 when n < 0. Thus relative to the basis B, any operator L compatible with B induces a recurrence operator

R_{B}L = ∑_{i=−B}^{A} α_{−i,n+i}E_{n}^{i}  (5)

where E_{n} is the shift operator w.r.t. n (E_{n}^{k}c_{n} = c_{n+k} for k ∈ ZZ).

Example 2 Using (5) and Example 1 we find that

R_{P}D = (n + 1)E_{n},
R_{C}E = E_{n} + 1.

Also, since x · x^{n} = x^{n+1} and x · \binom{x}{n} = (n + 1)\binom{x}{n+1} + n\binom{x}{n}, we find that

R_{P}x = E_{n}^{−1},
R_{C}x = n(E_{n}^{−1} + 1).  □

Now fix a basis B = ⟨P_{n}(x)⟩_{n=0}^{∞} of K[x] having properties P1, P2, and denote by L_{B} the set of operators L ∈ L_{K[x]} compatible with B.

Proposition 1 Let σ : K[[B]] → K^{ZZ} be the mapping assigning to the formal series y = ∑_{n=0}^{∞} c_{n}P_{n} its coefficient sequence c = ⟨c_{n}⟩_{n∈ZZ} extended by taking c_{n} = 0 whenever n < 0. Then for any L ∈ L_{B},

σ Ly = (R_{B}L) σy.

In other words, the following diagram commutes:

K[[B]] ⟶^{L} K[[B]]
σ ↓  ↓ σ
K^{ZZ}  ⟶^{R_{B}L} K^{ZZ}.

Proof: Let y = ∑_{n=0}^{∞} c_{n}P_{n}(x). Then σ Ly = ⟨∑_{i=−B}^{A} α_{−i,n+i}c_{n+i}⟩_{n∈ZZ} = ⟨∑_{i=−A}^{B} α_{i,n−i}c_{n−i}⟩_{n∈ZZ} =

(R_{B}L) σy. Here the first and last equalities follow from (5) and (3), respectively. □

Corollary 1 For L ∈ L_{B} and y = ∑_{n=0}^{∞} c_{n}P_{n} ∈ K[[B]], we have L ∑_{n=0}^{∞} c_{n}P_{n} = ∑_{n=0}^{∞}((R_{B}L)c)_{n}P_{n}.

Proof: L ∑_{n=0}^{∞} c_{n}P_{n} = Ly = ∑_{n=0}^{∞} σ(Ly)_{n}P_{n} = ∑_{n=0}^{∞}((R_{B}L)σy)_{n}P_{n} = ∑_{n=0}^{∞}((R_{B}L)c)_{n}P_{n}. □

Proposition 2 L_{B} is a K-algebra.

Proof: Let λ_{1}, λ_{2} ∈ K, L_{1}, L_{2} ∈ L_{B}, and

L_{1}P_{n} = ∑_{i=−A_{1}}^{B_{1}} α_{i,n}P_{n+i}, L_{2}P_{n} = ∑_{j=−A_{2}}^{B_{2}} β_{j,n}P_{n+j}.  (6)

Then λ_{1}L_{1} +λ_{2}L_{2} is clearly compatible with B (take A = max{A_{1}, A_{2}}, B = max{B_{1}, B_{2}}), hence it belongs to L_{B}. Also,

(L_{2}L_{1})P_{n} = ∑_{i=−A_{1}}^{B_{1}} α_{i,n}L_{2}P_{n+i} = ∑_{i=−A_{1}}^{B_{1}} ∑_{j=−A_{2}}^{B_{2}} α_{i,n}β_{j,n+i}P_{n+i+j} = ∑_{k=−A_{1}−A_{2}}^{B_{1}+B_{2}} γ_{k,n}P_{n+k}  (7)

where

γ_{k,n} = ∑_{i} α_{i,n}β_{k−i,n+i}.  (8)

Here α_{i,n} and β_{j,n} are considered zero, unless −A_{1} ≤ i ≤ B_{1} and −A_{2} ≤ j ≤ B_{2}. So L_{2}L_{1} is compatible with B (take A = A_{1} + A_{2} and B = B_{1} + B_{2}). Hence L_{2}L_{1} ∈ L_{B}. □

Definition 2 E denotes the K-algebra of recurrence operators of the form

M = ∑_{i=−s}^{r} a_{i}(n)E_{n}^{i}  (9)

with r, s ∈ IN and a_{i} : ZZ → K for −s ≤ i ≤ r. We regard these operators as acting on the K-algebra of two-way infinite sequences K^{ZZ}. □

Theorem 1 The transformation

R_{B} : L_{B} → E

defined in (5), is an isomorphism of K-algebras.

Proof: First we show that R_{B} is a K-algebra homomorphism. Clearly R_{B}(λ_{1}L_{1} + λ_{2}L_{2}) = λ_{1}R_{B}L_{1} + λ_{2}R_{B}L_{2}. Using (5), (7) and (8) we find that

R_{B}(L_{2}L_{1}) = ∑_{k=−B_{1}−B_{2}}^{A_{1}+A_{2}} γ_{−k,n+k}E_{n}^{k} = ∑_{i,k} α_{i,n+k}β_{−k−i,n+k+i}E_{n}^{k}.  (10)

On the other hand, using (5) and (6),

(R_{B}L_{2})(R_{B}L_{1}) = ( ∑_{j=−A_{2}}^{B_{2}} β_{−j,n+j}E_{n}^{j}) ( ∑_{i=−A_{1}}^{B_{1}} α_{−i,n+i}E_{n}^{i})

= ∑_{i,j} β_{−j,n+j}α_{−i,n+i+j}E_{n}^{i+j} = ∑_{i,k} α_{−i,n+k}β_{i−k,n+k−i}E_{n}^{k}

which turns into (10) after replacing i by −i. Hence R_{B}(L_{2}L_{1}) = (R_{B}L_{2})(R_{B}L_{1}).

Consider the mapping S_{B} : E → L_{B} defined as follows. For M ∈ E as given in (9), let S_{B}M = L ∈ L_{B} where

LP_{n} = ∑_{i=−r}^{s} a_{−i}(n + i)P_{n+i}  (n ≥ 0),  (11)

with P_{k} = 0 for k < 0. It is easy to see that S_{B} is the inverse of R_{B}. This proves that R_{B} is one-to-one and onto, and hence a K-algebra isomorphism. □

In the next three sections, we apply these results to the cases of q-difference, recurrence, and differential operators, respectively.

3 q-Difference operators

Let q ∈ K \ {0} be such that q^{n} ≠ 1 for all n ∈ IN \ {0}. Define Q ∈ L_{K[x]} by Qp(x) = p(qx), and consider operators of the form

L = ∑_{k=0}^{r} p_{k}(x)Q^{k}  (12)

where r ∈ IN, p_{k} ∈ K[x], and p_{r} ≠ 0. They form the skew polynomial algebra K[x, Q] with commutation rule Qx = qxQ. As Qx^{n} = q^{n}x^{n}, operator Q is compatible with the power basis P = ⟨x^{n}⟩_{n=0}^{∞} (take A = B = 0, α_{0,n} = q^{n}). To describe transformation R_{P} on K[x, Q], it suffices to give it on the two generators Q and x. Using (5) we have

R_{P} : Q ↦ q^{n} (termwise multiplication by q^{n}),
x ↦ E_{n}^{−1} (back-one shift).

Thus R_{P} maps K[x, Q] into K[q^{n}, E_{n}^{−1}]. For symmetry, write x = q^{n}. Then E_{n}q^{n} = q^{n+1} = qx = Qx. As the coefficients of R_{P}L do not depend on n directly but only on q^{n}, the transformation q^{n} ↦ x, E_{n} ↦ Q embeds R_{P}L into K[x, Q, Q^{−1}]. Now extend R_{P} to a mapping of the skew Laurent-polynomial algebra K[x, x^{−1}, Q, Q^{−1}] into itself by

R_{P} :  Q ↦ x,  Q^{−1} ↦ x^{−1},
x ↦ Q^{−1},  x^{−1} ↦ Q.

In four steps

R_{P} :  Q ↦ x ↦ Q^{−1} ↦ x^{−1} ↦ Q,
x ↦ Q^{−1} ↦ x^{−1} ↦ Q ↦ x,

we are back to where we started, so R_{P} is an automorphism of K[x, x^{−1}, Q, Q^{−1}] of order 4.

Write L ∈ K[x, x^{−1}, Q, Q^{−1}] \ {0} as

L = ∑_{i,k} c_{i,k} x^{i}Q^{k}.  (13)

Then

R_{P}L = ∑_{i,k} c_{i,k}Q^{−i}x^{k} = ∑_{i,k} c_{i,k}q^{−ik}x^{k}Q^{−i} = ∑_{i,k} c̃_{i,k}x^{i}Q^{k}  (14)

where c̃_{i,k} = c_{−k,i}q^{ik}. From (14) we see that for q-difference operators of the form (13) transformation R_{P} has a simple geometric description. Apart from multiplication by certain powers of q, it corresponds to counter-clockwise rotation of the coefficient array c_{i,k} around c_{0,0} by 90^{∘}:

\begin{matrix}c_{i,k} & … & Q^{−1} & Q^{0} & Q^{1} & … \\ ⋮ & & ⋮ & ⋮ & ⋮ \\ x^{−1} & … & c_{−1,−1} & c_{−1,0} & c_{−1,1} & … \\ x^{0} & … & c_{0,−1} & c_{0,0} & c_{0,1} & … \\ x^{1} & … & c_{1,−1} & c_{1,0} & c_{1,1} & … \\ ⋮ & & ⋮ & ⋮ & ⋮ \end{matrix} ⟶^{R_{P}}  \begin{matrix}c̃_{i,k} & … & Q^{−1} & Q^{0} & Q^{1} & … \\ ⋮ & & ⋮ & ⋮ & ⋮ \\ x^{−1} & … & c_{−1,1}q & c_{0,1} & c_{1,1}q^{−1} & … \\ x^{0} & … & c_{−1,0} & c_{0,0} & c_{1,0} & … \\ x^{1} & … & c_{−1,−1}q^{−1} & c_{0,−1} & c_{1,−1}q & … \\ ⋮ & & ⋮ & ⋮ & ⋮ \end{matrix}

Definition 3 The effective order of L is

ρ(L) = max{k ∈ ZZ; c_{i,k} ≠ 0 for some i} − min{k ∈ ZZ; c_{i,k} ≠ 0 for some i},

and the effective degree of L is

δ(L) = max{i ∈ ZZ; c_{i,k} ≠ 0 for some k} − min{i ∈ ZZ; c_{i,k} ≠ 0 for some k}.
□

Obviously, ρ(R_{P}L) = δ(L) and δ(R_{P}L) = ρ(L).

The fact that R_{P} is an automorphism of K[x, x^{−1}, Q, Q^{−1}] can be exploited to find factors of degree 0 and 1 (and any order) for operators in K[x, x^{−1}, Q, Q^{−1}].

Proposition 3 A q-difference operator L ∈ K[x, x^{−1}, Q, Q^{−1}] has a non-trivial left (resp. right) factor L_{1} ∈ K[x, x^{−1}, Q, Q^{−1}] of effective degree d, if and only if the induced operator R_{P}L has a non-trivial left (resp. right) factor M_{1} ∈ K[x, x^{−1}, Q, Q^{−1}] of effective order d.

Proof: If L = L_{1}L_{2} with δ(L_{1}) = d then R_{P}L = (R_{P}L_{1})(R_{P}L_{2}) and ρ(R_{P}L_{1}) = δ(L_{1}) = d. Conversely, if R_{P}L = M_{1}M_{2} with ρ(M_{1}) = d then L = (R_{P}^{−1}M_{1})(R_{P}^{−1}M_{2}) and δ(R_{P}^{−1}M_{1}) = ρ(R_{P}(R_{P}^{−1}M_{1})) = ρ(M_{1}) = d. For right factors the proof is analogous. □

To find factors of L of effective degree 0, find factors of R_{P}L of effective order 0. Write R_{P}L = x^{−a}MQ^{−b} where M = ∑_{k=0}^{r} p_{k}(x)Q^{k} and p_{k}(x) are polynomials. For left factors of effective order 0, compute gcd_{0≤k≤r} p_{k}(x). For right factors of effective order 0, compute gcd_{0≤k≤r} p_{k}(q^{−k}x).

Example 3 Let

L_{1} = Q^{2} − (qx^{2} + 1)Q + qx^{2}, L_{2} = Q^{2} − (q^{3}x^{2} + 1)Q + qx^{2}.

Then

R_{P}L_{1} = x^{2} − (qQ^{−2} + 1)x + qQ^{−2} = (x^{2} − x) − qQ^{−2}(x − 1) = (x − qQ^{−2})(x − 1),
R_{P}L_{2} = x^{2} − (q^{3}Q^{−2} + 1)x + qQ^{−2} = (x^{2} − x) − q(x − 1)Q^{−2} = (x − 1)(x − qQ^{−2}),

giving factorizations

L_{1} = (Q − qx^{2})(Q − 1), L_{2} = (Q − 1)(Q − qx^{2}).
□

To find factors of L of effective degree 1, find factors of R_{P}L of effective order 1 using algorithm qHyper of [4].

4 Recurrence operators

Let E ∈ L_{K[x]} be defined by Ep(x) = p(x + 1), and consider operators of the form

L = ∑_{k=0}^{r} p_{k}(x)E^{k}  (15)

where r ∈ IN, p_{k} ∈ K[x], and p_{r} ≠ 0. They form the skew polynomial algebra K[x, E] with commutation rule Ex = (x + 1)E. As noted in Example 1, the operator E, and hence every operator from K[x, E], is compatible with the binomial coefficient basis C = ⟨\binom{x}{n}⟩_{n=0}^{∞}. To describe R_{C} on K[x, E], it suffices to give it on the two generators E and x. Using (5) we have

R_{C} : E ↦ E_{n} + 1,
x ↦ n(1 + E_{n}^{−1}).

Thus R_{C} maps K[x, E] into K[n, E_{n}, E_{n}^{−1}]. To compute R_{C}^{−1} on R_{C}(K[x, E]), write L ∈ K[x, E] as

L = ∑_{i,k} c_{i,k}\binom{x}{i}E^{k}.  (16)

Note that \binom{x}{i}E^{−i}P_{n}(x) = \binom{x}{i}\binom{x−i}{n} = \binom{n+i}{i}\binom{x}{n+i} = \binom{n+i}{i}P_{n+i}(x), which together with (5) gives

R_{C} : \binom{x}{i}E^{−i} ↦ \binom{n}{i}E_{n}^{−i}.

As R_{C}E^{i} = (E_{n} + 1)^{i}, we have R_{C} : \binom{x}{i} ↦ \binom{n}{i}(1 + E_{n}^{−1})^{i}, therefore

R_{C}L = ∑_{i,k} c_{i,k}\binom{n}{i}(1 + E_{n}^{−1})^{i}(1 + E_{n})^{k} = ∑_{i} \binom{n}{i}(1 + E_{n}^{−1})^{i}r_{i}(E_{n})

where r_{i}(E_{n}) = ∑_{k} c_{i,k}(1 + E_{n})^{k}. So, if M ∈ E and M = ∑_{i} \binom{n}{i}(1 + E_{n}^{−1})^{i}r_{i}(E_{n}), then R_{C}^{−1}M = ∑_{i} \binom{x}{i}r_{i}(E − 1).

For symmetry, we could identify x with n and E with E_{n}. However, we cannot extend R_{C} to K[x, E, E^{−1}] because E^{−1} is not compatible with C: E^{−1}\binom{x}{n} = \binom{x−1}{n} = ∑_{k=0}^{n}(−1)^{n−k}\binom{x}{k}.

It may happen that factoring R_{C}L ∈ K[n, E_{n}, E_{n}^{−1}] ⊂ E is easier than factoring L ∈ K[x, E]. If R_{C}L = M_{2}M_{1} then L = L_{2}L_{1} (where L_{i} = R_{C}^{−1}M_{i}, for i = 1, 2) is a factorization of L in L_{C}. But K[n, E_{n}, E_{n}^{−1}] is larger than R_{C}(K[x, E]), so L_{1}, L_{2} will not necessarily belong to K[x, E]. In fact, they need not even belong to K[x, E, E^{−1}].

Example 4 Let L = R_{C}^{−1}E_{n}^{−1}. Then, using (11), we have LP_{n} = P_{n+1}. As ∑_{k=0}^{x−1} P_{n}(k) = P_{n+1}(x), we see that L acts as the summation operator Lp(x) = ∑_{k=0}^{x−1} p(k). Also, (E − 1)LP_{n} = (E − 1)P_{n+1} = P_{n}, so (E − 1)L − 1 acts as the zero operator on K[x]. If L ∈ K[x, E, E^{−1}] then it is not hard to see that (E − 1)L − 1 ∈ K[x, E, E^{−1}] \ {0}, and, consequently, that its kernel is finite-dimensional. Therefore L ∉ K[x, E, E^{−1}]. □

When L_{1}, L_{2} do belong to K[x, E, E^{−1}], we can factor L for the cost of factoring R_{C}L. In this case the following formulæ are useful to compute the inverse transformation:

R_{C}^{−1} :  E_{n}  ↦ E − 1,
n  ↦ x(1 − E^{−1}),
\binom{n}{i}E_{n}^{−i} ↦ \binom{x}{i}E^{−i}.

Example 5 Let L = (x+4)E^{4}−(7x+24)E^{3}−(x^{2}−8x−28)E^{2}+(6x^{2}+10x−1)E−5(x+1)^{2}. Algorithm Hyper of [10] shows that L has no right or left first-order factors in K(x)[E] where K is any field of characteristic 0, so the full factorization algorithm of [8] needs to be used to check for existence of second-order factors. Instead, we compute here the induced recurrence operator

R_{C}L = (n + 4)E_{n}^{4} − (2n + 8)E_{n}^{3} − (n^{2} + 10n + 20)E_{n}^{2} + (2n^{2} + 3n − 1)E_{n} + (7n^{2} + 8n + 2) + 2n(2n − 1)E_{n}^{−1},

for which Hyper finds the factorization

E_{n}(R_{C}L) = M_{2}M_{1}

where M_{2} = E_{n}^{4} + 2E_{n}^{3} − (n + 1)E_{n}^{2} − (2n + 3)E_{n} − (n + 1) and M_{1} = (n + 1)E_{n} − 2(2n + 1). Thus

L = R_{C}^{−1}(E_{n}^{−1}M_{2})R_{C}^{−1}M_{1}.

Luckily, both R_{C}^{−1}(E_{n}^{−1}M_{2}) and R_{C}^{−1}M_{1} belong to K[x, E, E^{−1}], namely

R_{C}^{−1}(E_{n}^{−1}M_{2}) = E^{3} − E^{2} − (x + 1)E = (E^{2} − E − (x + 1))E,
R_{C}^{−1}M_{1} = (x + 1)E − 3(2x + 1) + 5xE^{−1},

so we have found a factorization L = L_{2}L_{1} where

L_{2} = E^{2} − E − (x + 1), L_{1} = (x + 2)E^{2} − 3(2x + 3)E + 5(x + 1). □

5 Differential operators

Let D ∈ L_{K[x]} be defined by Dp(x) = \frac{d}{dx}p(x), and consider operators of the form

L = ∑_{k=0}^{r} p_{k}(x)D^{k}  (17)

where r ∈ IN, p_{k} ∈ K[x], and p_{r} ≠ 0. They form the Weyl algebra K[x, D] with commutation rule Dx = 1+xD. As noted in Example 1, the operator D, and hence every operator from K[x, D], is compatible with the power basis P = ⟨x^{n}⟩_{n=0}^{∞}. To describe R_{P} on K[x, D], it suffices to give it on the two generators D and x. Using (5) we have

R_{P} : D ↦ (n + 1)E_{n},  (18)
x ↦ E_{n}^{−1}.

For symmetry, we extend R_{P} to the skew Laurent-polynomial ring K[x, x^{−1}, D] by letting R_{P}x^{k} = E_{n}^{−k}, for all k ∈ ZZ. Then R_{P} becomes an isomorphism of K[x, x^{−1}, D] onto K[n, E_{n}, E_{n}^{−1}], the inverse being given by

R_{P}^{−1} : n ↦ xD,
E_{n}^{k} ↦ x^{−k}, for k ∈ ZZ.

Example 6 Let ϑ = xD. Then R_{P}ϑ = E_{n}^{−1}(n + 1)E_{n} = n, hence for any polynomial p ∈ K[x] we have R_{P} : p(ϑ) ↦ p(n). Therefore

p(ϑ) ∑_{n=0}^{∞} c_{n}x^{n} = ∑_{n=0}^{∞} p(n)c_{n}x^{n},  (19)

by Corollary 1. □

In the rest of the section we consider the problem of finding “nice” power series solutions of linear differential equations. Note that for any a ∈ K, the shifted power basis P_{a} = ⟨(x−a)^{n}⟩_{n=0}^{∞} is also compatible with operators from K[x, D]. If

y = ∑_{n=0}^{∞} c_{n}x^{n} ∈ K[[P]]  (20)

is a formal series in basis P, then for any a ∈ K we denote by y_{a} the corresponding formal series having identical coefficients as y, but in basis P_{a}:

y_{a} = ∑_{n=0}^{∞} c_{n}(x − a)^{n} ∈ K[[P_{a}]].  (21)

Our goal is to find all a ∈ K and all formal power series which satisfy Ly_{a} = 0, and whose coefficients c_{n} have a “nice” explicit representation in terms of n. Let

L_{a} = ∑_{k=0}^{r} p_{k}(x + a)D^{k}.  (22)

The following lemma allows us to consider only the basis P_{0} = P.

Lemma 2 Let L, y_{a}, L_{a}, and y be as in (17), (21), (22), and (20), respectively. Then Ly_{a} = 0 if and only if L_{a}y = 0.

Proof: Write q_{i}(x) = p_{i}(x + a). Then

L (x − a)^{n} = ∑_{i} n\underline{i}p_{i}(x)(x − a)^{n−i} = ∑_{i} n\underline{i}q_{i}(x − a)(x − a)^{n−i}

and

L_{a}x^{n} = ∑_{i} n\underline{i}p_{i}(x + a)x^{n−i} = ∑_{i} n\underline{i}q_{i}(x)x^{n−i}.

Comparing these two expressions we see that the infinite matrix representing L in basis P_{a} agrees with that representing L_{a} in basis P. Therefore R_{P_{a}}L = R_{P}L_{a}, hence

L y_{a} = 0 ⇔ (R_{P_{a}}L) c = 0 ⇔ (R_{P}L_{a}) c = 0 ⇔ L_{a}y = 0. □

Write

p_{k}(x + a) = ∑_{i=0}^{d} u_{i,k}x^{i} (0 ≤ k ≤ r)  (23)

where d and r are chosen so that some u_{d,k} and some u_{i,r} are nonzero. Define u_{i,k} = 0 whenever i < 0, i > d, k < 0, or k > r. Then, using (18), we obtain the corresponding recurrence operator

R_{a} = R_{P}L_{a} = ∑_{i,k} u_{i,k}R_{P}x^{i}D^{k} = ∑_{i,k} u_{i,k}E_{n}^{−i}((n + 1)E_{n})^{k} = ∑_{i,k} u_{i,k}E_{n}^{−i}(n + 1)\overline{k}E_{n}^{k}
= ∑_{i,k} u_{i,k}(n − i + 1)\overline{k}E_{n}^{k−i} = ∑_{j,k} u_{k−j,k}(n + j)\underline{k}E_{n}^{j}.  (24)

Lemma 3 Let L_{a} and y be as in (22) and (20), respectively. Then L_{a}y = 0 if and only if the recurrence

∑_{j,k} u_{k−j,k}(n + j)\underline{k}c_{n+j} = 0  (25)

holds for all n ∈ ZZ.

Proof: By (4), (5), and (24), L_{a}y = 0 if and only if (25) holds for all n ≥ 0. Now assume that n < 0, and consider the nonzero terms in the sum in (25). They must have k ≥ j and n + j ≥ 0 lest u_{k−j,k} or c_{n+j} should vanish. But then n + j + 1 ≤ j ≤ k, so

n + j − k + 1 ≤ 0 ≤ n + j,

implying that (n + j)\underline{k} = 0. Thus (25) holds trivially when n < 0. □

Example 7 Let ⟨F_{n}⟩_{n=0}^{∞} be the sequence of Fibonacci numbers defined by F_{0} = F_{1} = 1, F_{n} = F_{n−1} + F_{n−2} for n ≥ 2. To find a homogeneous linear differential equation satisfied by their generating function f(x) = ∑_{n=0}^{∞} F_{n}x^{n}, apply R_{P}^{−1} to a recurrence operator R which annihilates the sequence ⟨F_{n}⟩_{n∈ZZ} where F_{n} = 0 for n < 0. Note that the operator 1 − E_{n}^{−1} − E_{n}^{−2} won’t do because F_{0} = 1 while F_{−1} + F_{−2} = 0. However, R = n(1 − E_{n}^{−1} − E_{n}^{−2}) does annihilate ⟨F_{n}⟩_{n∈ZZ}, and R_{P}^{−1}R = xD(1 − x − x^{2}) = x(1 − x − x^{2})D − x(1 + 2x) indeed annihilates f(x) = 1/(1 − x − x^{2}). □

To avoid negative powers of E_{n}, multiply R_{a} on the left by E_{n}^{b} where −b is the least exponent of E_{n} appearing in R_{a}:

b = − min_{u_{i,k}≠0}(k − i) = − min_{0≤k≤r} (k − deg p_{k}) = max_{0≤k≤r} (deg p_{k} − k) .

Then (25) is equivalent to

∑_{j=0}^{r+b} q_{j}(n)c_{n+j} = 0 (n ∈ ZZ)  (26)

where q_{j}(n) = ∑_{k} u_{k−j+b,k}(n + j)\underline{k}. Note that by the definition of b, the coefficient of c_{n} in (26) is nonzero.

Thus the problem of finding “nice” power series solutions of Ly_{a} = 0 splits into two steps:

S1 Find all candidate values of a for which Ly_{a} = 0 may have solutions of the form (21) with “nice” c_{n}.

S2 For each candidate value of a, find “nice” solutions c = ⟨c_{n}⟩_{n=0}^{∞} of the corresponding recurrence (26).

Once S1 has been solved and the candidate expansion points a have been found, the algorithms of [2], [1], and [10], resp., can be used at each a (assuming there are finitely many of them) to find all polynomial, rational, resp. hypergeometric solutions of the corresponding recurrence (26). In particular, a detailed description of an algorithm to find all hypergeometric series solutions of Ly_{a} = 0 given the expansion point a is presented in [11]. This solves S2.

A short discussion of S1 in the case of hypergeometric coefficients is given in [11, Sec. 3.2], but a completely satisfactory solution has not been provided yet. Here we show how to find all a ∈ K and all solutions (21) of Ly_{a} = 0 for which there exists:

1. a polynomial p ∈ K[x] such that c_{n} = p(n) for all large enough n (subsection 5.1),

2. a rational function r ∈ K(x) such that c_{n} = r(n) for all n ≥ 0 (subsection 5.2),

3. a rational function R ∈ K(x) such that c_{n+1} = R(n)c_{n} for all large enough n (subsection 5.3).

Of course, the first two problems are special cases of the last one, but they are sufficiently interesting to warrant individual treatment. We also show that existence of a power series solution with rational coefficients implies existence of a solution with rational logarithmic derivative.

Let L be as in (17), and a ∈ K. If p_{r}(a) = 0 then L is singular at x = a, and a is a singular point of L. Otherwise a is an ordinary point of L.

If f(x) and g(x) are two formal power series such that f(x) − g(x) is a polynomial, we write f(x) ∼ g(x). In particular, f(x) ∼ 0 iff f(x) is a polynomial.

5.1 Solutions with polynomial coefficients

Let c_{n} = p(n) for some polynomial p ∈ K[x] and for all large enough n. Then, as it is well known, c_{n} satisfies a linear recurrence with constant coefficients, and its generating function (20) is a rational function of x, of the form

y ∼ ∑_{n=0}^{∞} p(n)x^{n} = p(ϑ) ∑_{n=0}^{∞} x^{n} = p(ϑ)\frac{1}{1 − x} = \frac{P (x)}{(1 − x)^{s+1}}  (27)

where ϑ is as in Example 6, P is a polynomial, P (1) ≠ 0, and deg P = s = deg p. By Lemma 4 given in Section 5.3 below, L_{a}y = 0 implies that L_{a} is singular at x = 1, so L is singular at x = a + 1. Thus we have Theorem 2 Let L be a linear differential operator with polynomial coefficients, and c_{n} a polynomial function of n. If a series y_{a} ∼ ∑_{n=0}^{∞} c_{n}(x − a)^{n} satisfies Ly_{a} = 0, then L is singular at x = a + 1.

Therefore to find solutions (21) of Ly_{a} = 0 with polynomial coefficients c_{n}, it suffices to consider all the roots of p_{r}(x + 1) = 0 as candidate expansion points a, and to use the algorithm of [2] at each of them to find polynomial solutions of the corresponding recurrence (26).

5.2 Solutions with rational coefficients

Next we look for rational solutions c_{n} of (26). We request here that there is a rational function r ∈ K(x) such that c_{n} = r(n) for all n ≥ 0. In particular, r(x) can have no nonnegative integer poles. Solutions which are eventually rational are covered in subsection 5.3.

For polynomials f, g ∈ K[x], f ∉ K, g ≠ 0, denote the order of g at f by

ν_{f}(g) = max{k ∈ IN; f^{k} | g}.

Theorem 3 Let y_{n} = p(n)/q(n), with p, q ∈ K[x] relatively prime polynomials, be a rational solution of the recurrence

∑_{i=0}^{s} q_{i}(n)y_{n+i} = h(n) (n ≥ 0)  (28)

where q_{0}, q_{1}, …, q_{s}, h ∈ K[x], and q_{0}, q_{s} ≠ 0. Then, for any irreducible polynomial f ∈ K[x] \ K,

ν_{f}(q) ≤ min {∑_{i=0}^{∞} ν_{E^{i}f}(E^{−s}q_{s}), ∑_{j=0}^{∞} ν_{E^{−j}f}(q_{0})} .

Note that because of characteristic zero, the two sums on the right have only finitely many nonzero terms.

Proof: Let r(n) = y_{n+1}/y_{n}. Write

r = \frac{A}{B} \frac{EC}{C}  (29)

where A, B, C ∈ K[x] and gcd(A, E^{k}B) = gcd(A, C) = gcd(B, EC) = 1 for all k ∈ IN. This is possible for any nonzero rational function r (cf. [10, Lemma 3.1]). Because r = Ey/y and y is rational, [10, Lemma 5.1] implies that there is a polynomial v ∈ K[x] such that

\frac{B}{A} = \frac{Ev}{v} .  (30)

It follows that

\frac{Ey}{y} = \frac{v}{Ev} \frac{EC}{C} ,

hence y = λ C/v for some constant λ. Since by assumption y = p/q with p and q relatively prime, q divides v. Thus ν_{f}(q) ≤ ν_{f}(v).

Rewrite (30) as

Bv = A(Ev).  (31)

It follows that v divides A(Ev), and, using this repeatedly, that v divides A(EA) ⋯ (E^{n−1}A)(E^{n}v) for any positive integer n. Since we work in characteristic 0, v and E^{n}v will be relatively prime for large enough n. Therefore

ν_{f}(v) ≤ ∑_{j=0}^{∞} ν_{f}(E^{j}A) = ∑_{j=0}^{∞} ν_{E^{−j}f}(A).

In an analogous way we obtain from (31) that

ν_{f}(v) ≤ ∑_{i=0}^{∞} ν_{f}(E^{−i−1}B) = ∑_{i=0}^{∞} ν_{E^{i}f}(E^{−1}B).

We claim that A | q_{0} and B | E^{−s+1}q_{s}. Assuming this, the theorem follows.

To prove the claim, note that in the homogeneous case (h = 0) it follows from [10, Theorem 4.1]. In the general case, express all y_{n+i} in (28) as rational multiples of y_{n} = λ C(n)/v(n), use (29), and clear denominators to find that

λ ∑_{i=0}^{s} q_{i} (E^{i}C) (∏_{j=0}^{i−1} E^{j}A) ∏_{j=i}^{s−1} E^{j}B = vh ∏_{j=0}^{s−1} E^{j}B.  (32)

From (31) it follows that A divides v and hence the right side of (32). Note that all terms with i > 0 on the left of (32) contain A as a factor, therefore A divides the term with i = 0 as well:

A | λ q_{0}C ∏_{j=0}^{s−1} E^{j}B.

Because A is relatively prime with C and with all E^{j}B, 0 ≤ j ≤ s − 1, we conclude that A | q_{0}.

Similarly, all terms with i < s on the left of (32), as well as the right side of (32), contain E^{s−1}B as a factor, therefore E^{s−1}B divides the term with i = s as well:

E^{s−1}B | λ q_{s}(E^{s}C) ∏_{j=0}^{s−1} E^{j}A.

As E^{s−1}B is relatively prime with E^{s}C and with all E^{j}A, 0 ≤ j ≤ s − 1, we conclude that E^{s−1}B | q_{s}. □

Theorem 4 Let L = ∑_{k=0}^{r} p_{k}(x)D^{k} be a linear differential operator with polynomial coefficients, and r ∈ K(x) \ K[x] a non-polynomial rational function which has no poles in IN. If the series y_{a} = ∑_{n=0}^{∞} c_{n}(x − a)^{n} where c_{n} = r(n) for all n ∈ IN satisfies Ly_{a} = 0, then L is singular at x = a, and the equation Ly = 0 has a solution with rational logarithmic derivative over K̄, the algebraic closure of K.

Proof: Assume that L is not singular at x = a, hence that p_{r}(a) = u_{0,r} ≠ 0. Then the leading term of (26) is the one with k = r + b, and its leading coefficient is

q_{r+b}(n) = ∑_{k} u_{k−r,k}(n + r + b)\underline{k} = u_{0,r}(n + r + b)\underline{r}.

We are going to use Theorem 3 on recurrence (26). The order of (26) in this case is s = r + b, so q_{s}(n − s) = u_{0,r}n\underline{r}, therefore ν_{E^{i}f}(E^{−s}q_{s}) > 0 for an irreducible f only if f(n) = n − α for some α ∈ IN. As c_{n} has no poles in IN, it follows from Theorem 3 that c_{n} is a polynomial in n. We conclude that (22) can have non-polynomial rational solutions only when L is singular at x = a.

To prove the second assertion, recall that a function f is called d’Alembertian over K if it is annihilated by an operator L = L_{1}L_{2} ⋯ L_{k} where each L_{i} ∈ K(x)[D] is of order one [3]. A d’Alembertian function satisfies f(x) ∈ f_{1}(x) ∫ f_{2}(x) ∫ ⋯ ∫ f_{k}(x)dx ⋯ dx dx where the f_{i} have rational logarithmic derivatives. Let

f(x) = ∑_{n=0}^{∞} \frac{x^{n}}{(n − α)^{k}}

where α ∈ K̄ \ IN. It is easy to see that the operator

L = (D − \frac{1}{1 − x}) (xD − α)^{k}

annihilates f(x), which is consequently d’Alembertian over K̄. Now, if c_{n} is a rational function of n, its partial fraction decomposition

c_{n} = p(n) + ∑_{i=0}^{s} ∑_{j=1}^{d_{i}} \frac{β_{i,j}}{(n − α_{i})^{j}}

together with (27) and the fact that d’Alembertian functions form a ring [6], shows that (20) is d’Alembertian as well. But if L_{a}y = 0 has a d’Alembertian solution then it also has a solution with rational logarithmic derivative [3, Theorem 4], and so does Ly = 0. □

Therefore to find solutions (21) of Ly_{a} = 0 with non-polynomial rational coefficients c_{n}, it suffices to consider the singular points of (17) as candidate expansion points a, and to use the algorithm of [1] at each of them to find rational solutions of the corresponding recurrence (26).

Example 8 The equation

2x(x − 1)y′′(x) + (7x − 3)y′(x) + 2y(x) = 0  (33)

is singular at x = 0 and x = 1. Let us find power series solutions at x = 0. Recurrence (26) in this case is

(n + 1)(2n + 3)c_{n+1} − (n + 2)(2n + 1)c_{n} = 0  (34)

and is satisfied by the rational sequence c_{n} = 2(n + 1)/(2n + 1). Thus (33) has a power series solution with rational coefficients

f(x) = ∑_{n=0}^{∞} \frac{2(n + 1)}{2n + 1}x^{n} = \frac{1}{1 − x} + \frac{1}{2} ∑_{n=0}^{∞} \frac{x^{n}}{n + 1/2}

∈ \frac{1}{1 − x} + \frac{1}{2\sqrt{x}} ∫ \frac{dx}{\sqrt{x}(1 − x)} = \frac{1}{1 − x} + \frac{1}{2\sqrt{x}} log \frac{1 + \sqrt{x}}{1 − \sqrt{x}} + \frac{K}{\sqrt{x}},

which is d’Alembertian. Since f(0) = 2 it follows that f(x) = \frac{1}{1−x} + \frac{1}{2\sqrt{x}} log \frac{1+\sqrt{x}}{1−\sqrt{x}}. Note that (33) is also satisfied by g(x) = 1/\sqrt{x} which has rational logarithmic derivative. □

Remark 1 If, in notation of Theorem 4, c_{n} = r(n) for large enough n but not for all n ∈ IN, then L need not be singular at x = a. For instance, the equation (x − 1)y′′ + y′ = 0 has solution y(x) = − log(1 − x) = ∑_{n=1}^{∞} x^{n}/n with non-polynomial rational coefficients, although it is not singular at x = 0. This is because c_{0} = 0 while r(n) = 1/n has a pole at n = 0. Such solutions are covered in the next subsection. □

5.3 Solutions with hypergeometric coefficients

To find power series solutions with hypergeometric coefficients, instead of (20) and (21) it is more convenient to write

y = ∑_{n=0}^{∞} b_{n} \frac{x^{n}}{n!} ,  (35)

and

y_{a} = ∑_{n=0}^{∞} b_{n} \frac{(x − a)^{n}}{n!}  (36)

respectively, where b_{n} = c_{n}n! is hypergeometric iff c_{n} is. Note that b_{n} is undefined for n < 0. Then, after replacing k with k + j − b and multiplying both sides with (n + b)!, (26) turns into

∑_{j=0}^{r+b} q_{j}(n)b_{n+j} = 0 for large enough n,  (37)

where q_{j}(n) = ∑_{k} u_{k,k+j−b}(n + b)\underline{k}. Since k + j − b ≤ r, it follows that deg q_{j}(n) ≤ r + b − j. In particular, q_{r+b}(n) is a constant polynomial.

Theorem 5 Let x = a be an ordinary point of L = ∑_{k=0}^{r} p_{k}(x)D^{k}, and y_{a} = ∑_{n=0}^{∞} b_{n}(x − a)^{n}/n! a hypergeometric series which satisfies Ly_{a} = 0. Then there are polynomials A, C ∈ K[x] with deg A ≤ 1, such that

b_{n+1} = A(n)\frac{C(n + 1)}{C(n)}b_{n}  (38)

for all large enough n.

Proof: If Ly_{a} = 0 then by Lemma 2, L_{a}y = 0 where L_{a} and y are as in (22) and (35), respectively. By the preceding discussion, b_{n} is a hypergeometric solution of (37).

If b_{n} is eventually zero then the theorem holds trivially. Otherwise b_{n} is eventually nonzero (because it satisfies a homogeneous first-order recurrence with rational coefficients). Let R(n) be the rational function equal to b_{n+1}/b_{n} for all large enough n. As any nonzero rational function, R can be written in the form

R = ζ \frac{A}{B} \frac{EC}{C}  (39)

where ζ ∈ K \ {0}, A, B, C ∈ K[x] are monic, and gcd(A, E^{k}B) = gcd(A, C) = gcd(B, EC) = 1 for all k ∈ IN.

By [10, Theorem 5.1], B divides the leading coefficient of recurrence (37) which is

q_{r+b}(n) = ∑_{k} u_{k,k+r}(n + b)\underline{k} = u_{0,r} = p_{r}(a),

a nonzero constant because x = a is an ordinary point of L. So B = 1, and it remains to show that deg A ≤ 1. Again by [10, Theorem 5.1], ζ is a nonzero root of the algebraic equation

∑_{k=0}^{r+b} α_{k}ζ^{k} = 0,  (40)

where α_{k} is the coefficient of n^{M} in P_{k}(n) = q_{k}(n) ∏_{j=0}^{k−1} E^{j}A, and M = max_{0≤k≤r+b} deg P_{k}. Write δ = deg A. Since deg q_{r+b} = 0 and deg q_{k} ≤ r + b − k for k < r + b, it follows that deg P_{r+b} = (r + b)δ and deg P_{k} ≤ r + b − k(1 − δ) for k < r + b. If δ > 1 then for k < r + b,

deg P_{r+b} − deg P_{k} ≥ (r + b)δ − (r + b − k(1 − δ)) = (δ − 1)(r + b − k) > 0,

so deg P_{k} < deg P_{r+b}. Therefore M = (r + b)δ and all the α’s are zero except α_{r+b}. Hence (40) has no nonzero roots, and (37) has no hypergeometric solution with δ > 1. It follows that deg A = δ ≤ 1. Writing A for ζA in (39) we obtain (38). □

Corollary 2 Let x = 0 be an ordinary point of L, and y = ∑_{n=0}^{∞} b_{n}x^{n}/n! a hypergeometric series solution of Ly = 0. Then y is of one of the forms

a) y ∼ p(x)e^{ζx}, or

b) y ∼ p(x)(1 − ζx)^{α}, or

c) y ∼ p(x)/(1 − ζx)^{s} + q(x) log(1 − ζx),

where p, q ∈ K[x] are polynomials, ζ ∈ K \ {0}, α ∈ K, and s ∈ IN.

Proof: If y is a polynomial, this is trivially true. Otherwise, Theorem 5 implies that for all large enough n, b_{n+1}/b_{n} = ζA(n)C(n + 1)/C(n) where ζ ∈ K \ {0} and either A(n) = 1, or A(n) = n − α for some α ∈ K. We distinguish three cases according to the form of A and the nature of α.

Case a) A(n) = 1 In this case, b(n + 1)/b(n) = ζC(n + 1)/C(n), so b_{n} = λC(n)ζ^{n} where λ is a constant. Hence by (19),

y ∼ λ ∑_{n=0}^{∞} C(n)\frac{(ζx)^{n}}{n!} = λC(ϑ)e^{ζx} = p(x)e^{ζx}  (41)

where p(x) is some polynomial of degree s = deg C(n).

Case b) A(n) = n − α, where α ∉ IN In this case, b(n + 1)/b(n) = ζ(n − α)C(n + 1)/C(n), so b_{n} = λC(n)(−α)\overline{n}ζ^{n} where λ is a constant. Hence by (19),

y ∼ λ ∑_{n=0}^{∞} C(n)\frac{(−α)\overline{n}}{n!} (ζx)^{n} = λC(ϑ) ∑_{n=0}^{∞} \binom{α}{n}(−ζx)^{n} = λC(ϑ)(1 − ζx)^{α} = p(x)(1 − ζx)^{α−s} (42)

where p(x) is some polynomial and deg p = s = deg C.

Case c) A(n) = n − α, with α ∈ IN Here we still have the solution

y ∼ λC(ϑ)(1 − ζx)^{α}

which in this case is simply a polynomial in x, corresponding to s = q = 0. But now there is another hypergeometric solution of (37), namely

b_{n} = λC(n)(n − α − 1)!ζ^{n−α−1}, for n ≥ α + 1,

which, using (19), yields

y ∼ λ ∑_{n=α+1}^{∞} C(n)\frac{(n − α − 1)!}{n!}ζ^{n−α−1}x^{n}

= λC(ϑ) ∑_{n=0}^{∞} \frac{ζ^{n}x^{n+α+1}}{(n + 1)\overline{α+1}}

∈ λC(ϑ) ∫ ∫ ⋯ ∫ \frac{1}{1 − ζx}dx … dx dx

where there are α + 1 integral signs. It is straightforward to verify by induction on k that for any n, k ∈ IN,

\frac{d^{k}}{dx^{k}} ((1 − ζx)^{n} log(1 − ζx)) = ζ^{k}k!(1 − ζx)^{n−k}f_{n,k}(x)  (43)

where

f_{n,k}(x) = \{ \begin{matrix}(−1)^{k}\binom{n}{k}(H_{n} − H_{n−k} + log(1 − ζx)), & k ≤ n \\ (−1)^{n+1}/ (k\binom{k−1}{n}) , & k > n \end{matrix}

and H_{n} = ∑_{k=1}^{n} 1/k. Taking n = α and k = α + 1 in (43), we see that the nested integral of 1/(1 − ζx) has the form P (x) log(1 − ζx) + Q(x) where P and Q are polynomials of degree ≤ α. Finally

y ∼ \frac{p(x)}{(1 − ζx)^{s}} + q(x) log(1 − ζx),  (44)

where p, q are polynomials, deg p ≤ α + s, deg q ≤ α, and s = deg C. In fact, a more careful analysis shows that p(x) is divisible by (1 − ζx)^{t} where t = min{α, s}. □

Lemma 4 Let L = ∑_{k=0}^{r} a_{k}(x)D^{k} be a linear differential operator with polynomial coefficients. If y(x) = p(x)(1 − ζx)^{α} satisfies Ly = 0 where α ∈ K \ IN, ζ ∈ K \ {0}, and p ∈ K[x] is relatively prime with 1 − ζx, then 1 − ζx divides the leading coefficient a_{r}(x) of L.

Proof: By Leibniz’ rule,

Ly(x) = ∑_{k=0}^{r} a_{k}(x) ∑_{j=0}^{k} \binom{k}{j}\frac{d^{k−j}p(x)}{dx^{k−j}}(−ζ)^{j}α\underline{j}(1 − ζx)^{α−j} = 0.  (45)

As α is not a nonnegative integer, α\underline{j} ≠ 0 for 0 ≤ j ≤ k. Multiplying (45) by (1 − ζx)^{r−α} we see that 1 − ζx divides a_{r}(x)p(x) and hence a_{r}(x). □

Lemma 5 Let L = ∑_{k=0}^{r} a_{k}(x)D^{k} be a linear differential operator with polynomial coefficients. If

y(x) = \frac{p(x)}{(1 − ζx)^{s}} + q(x)(1 − ζx)^{t} log(1 − ζx)  (46)

satisfies Ly = 0 where p, q ∈ K[x], q ≠ 0, s, t ∈ IN, ζ ∈ K \ {0}, and q(x) is relatively prime with 1 − ζx, then 1 − ζx divides the leading coefficient a_{r}(x) of L.

Proof: If y is as in (46) then clearly

Ly(x) = A(x) + B(x) log(1 − ζx)

where A, B ∈ K(x) are rational power series. As log(1 − ζx) is not a rational power series, Ly = 0 implies A = B = 0. We distinguish three cases.

Case 1 (t ≥ r): Using (43) and Leibniz’ rule,

B(x) = ∑_{k=0}^{r} a_{k}(x) ∑_{j=0}^{k} \binom{k}{j}\frac{d^{k−j}q(x)}{dx^{k−j}}ζ^{j}j!(−1)^{j}\binom{t}{j}(1 − ζx)^{t−j}.

As B(x) = 0, and all terms with j ≤ r − 1 above contain (1 − ζx)^{t−r+1} as an explicit factor, it follows that the term with j = k = r is also divisible by this factor. Thus 1 − ζx divides a_{r}(x)q(x) and hence a_{r}(x).

Case 2 (t < r, s > 0): In this case we can assume that p(x) is relatively prime with 1 − ζx, and use the fact that A(x) = 0. Consider the exponent of 1 − ζx in the denominators of various contributions to A(x). In those terms arising from applying L to q(x)(1 − ζx)^{t} log(1 − ζx) this exponent is at most r − t, according to (43). On the other hand,

L \frac{p(x)}{(1 − ζx)^{s}} = ∑_{k=0}^{r} a_{k}(x)\frac{p_{k}(x)}{(1 − ζx)^{s+k}}

where p_{k}(x) is a polynomial relatively prime with 1 − ζx, and p_{r} ≠ 0. As s > 0 we have s + r > r − t. It follows that 1 − ζx divides a_{r}(x)p_{r}(x) and hence a_{r}(x).

Case 3 (t < r, s = 0): As Lp(x) is a polynomial, A(x) contains a term which is a constant multiple of a_{r}(x)q(x)/(1 − ζx)^{r−t} while the exponent of 1 − ζx in the denominators of all other terms of A(x) is at most r − t − 1, according to (43). It follows that 1 − ζx divides a_{r}(x)q(x) and hence a_{r}(x). □

Corollary 3 Let x = a be an ordinary point of L, and y_{a} = ∑_{n=0}^{∞} c_{n}(x − a)^{n}/n! a hypergeometric series satisfying Ly_{a} = 0. Then for any other ordinary point x = b of L, there is a hypergeometric series w_{b} = ∑_{n=0}^{∞} d_{n}(x − b)^{n}/n! satisfying Lw_{b} = 0.

Proof: By Lemma 2, Ly_{a} = 0 implies that L_{a}y = 0 where y = ∑_{n=0}^{∞} c_{n}x^{n}/n!, and L_{a} is as in (22). Because x = 0 is an ordinary point of L_{a}, the series y has one of the three forms listed in Corollary 2. Note that all three are d’Alembertian. Let L_{min} ∈ K(x)[D] be the monic operator of minimal order annihilating y. Then L_{min} is a right factor of L_{a} in K(x)[D]. We claim that in each of the three cases, and for any ordinary point b of L, there exists a hypergeometric series of the form w_{c} = ∑_{n=0}^{∞} d_{n}(x − c)^{n}/n! where c = b − a, such that L_{min}w_{c} = 0 and hence that L_{a}w_{c} = 0. By Lemma 2, it then follows that Lw_{c+a} = Lw_{b} = 0 as desired.

To prove the claim, we give L_{min} and w_{c} separately for the three cases of Corollary 2. In each of them, it is easy to check that indeed L_{min}w_{c} = 0. We write z for x − c. In what follows, p_{0}, p, q ∈ K[x] and ζ ∈ K \ {0}.

Case a) y(x) = p_{0}(x) + p(x)e^{ζx} with p ≠ 0: As Lp_{0}(x) is rational while L (p(x)e^{ζx}) is not unless it vanishes, Ly(x) = 0 implies that also L (p(x)e^{ζx}) = 0. Thus we can take p_{0}(x) = 0 and y(x) = p(x)e^{ζx}. Then

L_{min} = D − (\frac{p′(x)}{p(x)} + ζ) ,
w_{c} = p(z + c)e^{ζz}.  (47)

Case b) y(x) = p_{0}(x) + p(x)(1 − ζx)^{α} with α ∈ K \ IN and p ≠ 0: As in case a), we can take p_{0}(x) = 0 and y(x) = p(x)(1 − ζx)^{α}. Then

L_{min} = D − (\frac{p′(x)}{p(x)} − \frac{αζ}{1 − ζx}) ,
w_{c} = p(z + c)(1 − ξz)^{α}  (48)

with ξ = ζ/(1 − ζc).

Case c) y(x) = p_{0}(x) + p(x)/(1 − ζx)^{s} + q(x) log(1 − ζx) with s ∈ IN and q ≠ 0: Here

L_{min} = (D − \frac{g′(x)}{g(x)}) (D − \frac{q′(x)}{q(x)}) ,
w_{c} = p_{0}(z + c) + \frac{p(z + c)}{(1 − ζc)^{s}(1 − ξz)^{s}} + q(z + c) log(1 − ξz)  (49)

with g = q(y/q)′ and ξ = ζ/(1 − ζc).

In cases b) and c), we need to show that 1 − ζc ≠ 0. According to Lemmas 4 and 5, L_{a} is singular at x = 1/ζ. But then L is singular at x = a + 1/ζ, so a + 1/ζ ≠ b because b is an ordinary point of L. Thus 1/ζ ≠ b − a = c and ζc ≠ 1.

In cases a) and b), w_{c} is a polynomial multiple of a hypergeometric series, which by Lemma 1 is again a hypergeometric series. In case c), w_{c} is the sum of two such series. But the coefficients of 1/(1 − ξz)^{s} = ∑_{n=0}^{∞} \binom{n+s−1}{s−1}ξ^{n}z^{n} as well as those of log(1 − ξz) = − ∑_{n=1}^{∞}(ξ^{n}/n)z^{n} are both similar to ξ^{n}, hence, by Lemma 1, so are the coefficients of w_{c} which are thus hypergeometric. □

Therefore the following algorithm will find all solutions (21) of Ly_{a} = 0 with hypergeometric c_{n}:

1. For each singular point a of L, find all solutions y = ∑_{n=0}^{∞} c_{n}x^{n} of L_{a}y = 0 with hypergeometric c_{n}, using the algorithm of [11]. Then the corresponding y_{a} give all the hypergeometric series solutions at x = a.

2. Pick any ordinary point a of L. Find all solutions y = ∑_{n=0}^{∞} c_{n}x^{n} of L_{a}y = 0 with hypergeometric c_{n}, using either the algorithm of [11], or, since these solutions are d’Alembertian, the algorithm of [7], or a custom-designed algorithm for finding solutions of the three types described in Corollary 2. Then the corresponding y_{a} give all the hypergeometric series solutions at x = a. For any other ordinary point b of L, the series w_{c} given in (47), (48), and (49), respectively (with z replaced by x − b and c by b − a), give all the hypergeometric series solutions at x = b.

References

[1] S. A. Abramov, Rational solutions of linear difference and q-difference equations with polynomial coefficients, Progr. and Comp. Software 21 (1995) 273–278.

[2] S. A. Abramov, M. Bronstein, M. Petkovšek, On polynomial solutions of linear operator equations, Proc. ISSAC ’95, T. Levelt, Ed., Montreal, Canada, July 10–12, 1995 (ACM Press, New York 1995) 290–296.

[3] S. A. Abramov, M. Petkovšek, D’Alembertian solutions of linear differential and difference equations, Proc. ISSAC ’94, M. Giesbrecht, Ed., Oxford, England, United Kingdom, July 20–22, 1994 (ACM Press, New York 1994) 169–174.

[4] S. A. Abramov, P. Paule, M. Petkovšek, q-Hypergeometric solutions of q-difference equations, Discrete Math. 180 (1998) 3–22.

[5] S. A. Abramov, M. Petkovšek, Special power series solutions of linear differential equations, Proc. FPSAC ’96, D. Stanton, Ed., Minneapolis, Minnesota, June 25–29, 1996 (Univ. of Minnesota, 1996) 1–8.

[6] S. A. Abramov, E. V. Zima, Minimal completely factorable annihilators, Proc. ISSAC ’97, W. W. Küchlin, Ed., Maui, Hawaii, USA, July 21–23, 1997 (ACM Press, New York 1997) 290–297.

[7] M. Bronstein, Linear differential equations: breaking through the order 2 barrier, Proc. ISSAC ’92, P. S. Wang, Ed., Berkeley CA, USA, July 27–29, 1992 (ACM Press, New York 1992) 42–48.

[8] M. Bronstein, M. Petkovšek, An introduction to pseudo-linear algebra, Theor. Comp. Sci. 157 (1996) 3–33.

[9] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics (Addison-Wesley, Reading, Mass., 1989).

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

[11] M. Petkovšek, B. Salvy, Finding all hypergeometric solutions of linear differential equations, Proc. ISSAC ’93, M. Bronstein, Ed., Kiev, Ukraine, July 6–8, 1993 (ACM Press, New York 1993) 27–33.