IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 51 (2013), 1185
ISSN 2232-2094
SOLVING LINEAR RECURRENCE EQUATIONS WITH POLYNOMIAL COEFFICIENTS
Marko Petkovsek Helena Zakrajsek
Ljubljana, February 21, 2013
o
CSI

Solving Linear Recurrence Equations With Polynomial Coefficients
Marko Petkovsek
Faculty of Mathematics and Physics University of Ljubljana Jadranska 19, SI-1000 Ljubljana, Slovenia marko.petkovsek@fmf.uni-lj.si
on
Helena Zakrajsek Faculty of Mechanical Engineering University of Ljubljana Askerceva 6, SI-1000 Ljubljana, Slovenia helena.zakrajsek@fs.uni-lj.si
Abstract
Summation is closely related to solving linear recurrence equations, since an indefinite sum satisfies a first-order linear recurrence with constant coefficients, and a definite proper-hypergeometric sum satisfies a linear recurrence with polynomial coefficients. Conversely, d'Alembertian solutions of linear recurrences can be expressed as nested indefinite sums with hypergeometric summands. We sketch the simplest algorithms for finding polynomial, rational, hypergeometric, d'Alembertian, and Liou-villian solutions of linear recurrences with polynomial coefficients, and refer to the relevant literature for state-of-the-art algorithms for these tasks. We outline an algorithm for finding the minimal annihilator of a given P-recursive sequence, prove the salient closure properties of d'Alembertian sequences, and present an alternative proof of a recent result of Reutenauer's that Liouvillian sequences are precisely the inter-lacings of d'Alembertian ones.
1 Introduction
Summation is related to solving linear recurrence equations in several ways. An indefinite sum
n-1
s(n) = J2 t(k)
CO CO
u
CD CO
u
a
CD U
k=0
o

u
a
CD U
satisfies the nonhomogeneous first-order recurrence equation
s(n + 1) - s(n) = t(n); s(0) = 0, and also the homogeneous second-order recurrence equation
t(n)s(n + 2) —(t(n)+t(n+1))s(n + 1)+t(n+1)s(n) = 0; s(0) = 0, s(1) = t(0). A definite sum
n
s(n) = £ F(n, k)
k=0
where the summand F(n, k) is a proper hypergeometric term:
UA ( )
F(n, k) = P(n,k) j^nl^zk
rij=1(^j )bjn+bj k
with P(n, k) a polynomial in both variables, (z)k the Pochhammer symbol, aj, , z commuting indeterminates, aj, bj G N, and Sj, bj G Z, satisfies a linear recurrence equation with polynomial coefficients in n which can be computed with Zeilberger's algorithm (cf. [41], [42], [29], [11]). So the sum of interest may sometimes be found by solving a suitable recurrence equation.
The unknown object in a recurrence equation is a sequence, by which we mean a function mapping the nonnegative integers N to some algebraically closed field K of characteristic zero. Sequences can be represented in several different ways, among the most common of which are the following:
explicit where a sequence a : N ^ K is represented by an expression e(x) such that a(n) = e(n) for all n > 0,
•	recursive where a sequence a : N ^ K is represented by a function F and by some initial values a(0), a(1),..., a(d — 1) such that
a(n) = F (n, a(n — 1),a(n — 2),...,a(0))	(1)
for all n > d,
•	by generating function where a sequence a : N ^ K is represented by the (formal) power series
Ga(z) = ]T a(n)zn.
I-H
Each of these representations has several variants and special cases. In particular, if a(n) = F(n, a(n — 1), a(n — 2), .. ., a(n — d)) for all n > d, the recursive representation (1) is said to be of order at most d.
Example 1 (Fibonacci numbers)
m
o

I
00
£ CO CO
explicit representation: a(n) = ^	— 2^) ^
• recursive representation: a(n) = a(n — 1) + a(n — 2) (n > 2), a(0) = a(1) = 1
1
1 - z — z2
• generating function: Ga(z) =
From the viewpoint of representation of sequences, solving recurrence equations can be seen as the process of converting one (namely recursive) representation
CD
to another (explicit) representation.
In this paper we survey the properties of several important classes of sequences which satisfy linear recurrence equations with polynomial coefficients, and sketch algorithms for finding such solutions when they exist. In Sections 2 and 3 we review the main results about C-recursive and P-recursive sequences, then we describe algorithms for finding polynomial, rational and hypergeomet-ric solutions in Sections 4 and 5. Difference rings and the Ore algebra of linear difference operators with rational coefficients, together with the outline of a factorization algorithm, are introduced in Sections 6 and 7. In Section 8 we define d'Alembertian sequences and prove their closure properties. Finally, in Section 9, we give an alternative proof of the recent result of Reutenauer [31] that Li-ouvillian sequences are precisely the interlacings of d'Alembertian sequences by showing that the latter enjoy all the closure properties of the former.
CD
2 C-recursive sequences
C-recursive sequences satisfy homogeneous linear recurrences with constant coefficients. Typical examples are geometric sequences of the form a(n) = cqn with c, q G K*, polynomial sequences, their products, and their linear combinations (such as the Fibonacci numbers of Example 1).
Definition 1 A sequence a G KN is C-recursive or C-finite1 if there are d G N and constants ci, C2, ..., c^ G K, c^ = 0, such that
a(n) = ci a(n — 1) + c2 a(n — 2) + • • • + c^ a(n — d)
for all n > d.
The following theorem describes the explicit and generating-function representations of C-recursive sequences. For a proof, see, e.g., [38].
Theorem 1 Let a G KN and Ga(z) =^2a(n)zn. The following are equivalent:
■ I	_
1 C-recursive sequences are also called linear recurrent (or: recurrence) sequences. This CD	neglects sequences satisfying linear recurrences with non-constant coefficients, and may lead
to confusion.
u
a
CD U
c^	1 . r .
1,	a is C-recursive,
r
2,	a(n) ^^ Pi(n) a" for all n G N where Pi G K[x] and ai G K,

P (z)
3, Ga(z) =	where P, Q G K[x], degP < deg Q and Q(0) = 0,
Q(z)
The next two theorems are easy corollaries of Theorem 1.
&
Theorem 2 The set of C-recursive sequences is closed under the following binary operations (a, b) ^ c:
1,	addition: c(n) = a(n) + b(n)
00
2,	(Hadamard or termwise) multiplication: c(n) = a(n)b(n)
o
3,	convolution (Cauchy multiplication): c(n) = "=0 a(«)b(n — i)
4,	interlacing: (c(0), c(1), c(2), c(3), .. .) = (a(0), b(0), a(1), b(1),. ..)
Remark 1 These operations extend naturally to any nonzero number of ,	operands,
Theorem 3 The set of C-recursive sequences is closed under the following unary operations a ^ c:
(N
1,	scalar 'multiplication: c(n) = Aa(n) (A G K)
2,	(left) shift: c(n) = a(n + 1)
4, multisection: c(n) = a(mn + r) (m, r G N, 0 < r < m)
^
That (nonzero) C-recursive sequences are not closed under taking reciprocals is demonstrated, e.g., by a(n) = n + 1 which is C-recursive while its reciprocal b(n) = 1/(n + 1) is not, since its generating function Gb(x) = — ln(1 — x)/x is not a rational function. Of course, there are C-recursive sequences whose reciprocals are C-recursive as well, such as all the geometric sequences.
Question 1. When are a and 1/a both C-recursive?
Theorem 4 The sequences a and 1/a are both C-recursive iff a is the interlacing of one or more geometric sequences,
For a proof, see [26].
u
a
CD U
o

CD
m oo
o
i
3 P-recursive sequences
P-recursive sequences satisfy homogeneous linear recurrences with polynomial coefficients. While most of them lack a simple explicit representation, their generating functions do have a nice characterization in terms of differential equations. There exist also several important subclasses of P-recursive sequences such as polynomial, rational, hypergeometric (Sec. 4), d'Alembertian (Sec. 8), and Liouvillian (Sec. 9) sequences which have nice explicit representations. Figure 1 shows a hierarchy of these subclasses together with some examples. In the rest of the paper, we investigate their properties and sketch algorithms for finding such special solutions of linear recurrence equations with polynomial coefficients, whenever they exist.
^recursive: ]T (-)2 (-+k)
k=0
Liouvillian: n!!
d'Alembertian: n!^^( k1,) hypergeometric: n!	quasirational: -+J + 1
I
rational:	C-recursive: n2- +1
r
polynomial: n +1	geometric: 2-
Figure 1: A hierarchy of P-recursive sequences (with examples)
CO
Definition 2 A sequence a G KN is P-recursive if there are d G N and polynomials p°,pi,... ,pd G K[x], pd = 0, such that
pd(n)a(n + d) + pd-i(n)a(n + d - 1) +-----+ p°(n)a(n) = 0
for all n > 0.
Definition 3 A formal power series f (z) = ^a(n)z- G K[[z]] is D-finite if there exist d G N and polynomials q°, qi, .. . ,qd G K [x], qd = 0, such that
qd(z)f (d)(z) + qd- i(z)f (d-1)(z) + ••• + q°(z)f (z) = 0.
Theorem 5 Let a G KN and Ga(z) = „=° a(n)z-. The following are equivalent:
u
a
CD U
o
cm
cm
2.	multiplication.
3.	convolution,

I
CM 00
$H
a
CD Jh
1.	a is P-recursive,
2.	Ga(z) is D-finite.
For a proof, see [39] or [40]. Theorem 6 P-recursive sequences are closed under the following operations: 1. addition,
4. interlacing,
5. scalar multiplication,
00	shm,
7.	indefinite summation,
8.	multisection.
o
For a proof, see [40]. Question 2. When are a and 1/a are both P-recursive? The answer is given in Theorem 7.
Example 2 The sequences a(n) = n! and b(n) = 1/n! are both P-recursive since a(n + 1) — (n + 1)a(n) = 0 and (n + 1)b(n +1) — b(n) = 0.
Example 3 The sequence a(n) = 2n + 1 is P-recursive (even C-recursive) while its reciprocal b(n) = 1/(2n + 1) is not P-recursive.
Proof: We use the fact that a D-finite function can have at most finitely many singularities in the complex plane (see, e.g., [40]). The generating function
£
G6(z) = £ b(n)zn = £
n=0	n=0 2 + 1
obviously has radius of convergence equal to two. We can rewrite
2n	/	1
z	n	' -	1
Gb(2z) = E^zn = £ 1 —
n=o2n+1 n=ov 2n+1
=	— G6(z).	(2)
^^	1 — z
At z = 1 the function 1/(1 — z) is singular, Gb is regular, so Gb is singular at z = 2. At z = 2 the function 1/(1 — z) is regular, Gb is singular, so Gb is singular at z = 4. At z = 4 the function 1/(1 — z) is regular, Gb is singular, so Gb is singular at z = 8, and so on. By induction on k it follows that Gb(z) is singular
at z = 2k for all k G N, k > 1, hence Gb is not D-finite, and b is not P-recursive. □
o
csr
4 Hypergeometric sequences
Hypergeometric sequences are P-recursive sequences which satisfy homogeneous linear recurrence equations with polynomial coefficients of order one. They can be represented explicitly as products of rational functions, Pochhammer symbols, and geometric sequences. The algorithm for finding hypergeometric solutions of linear recurrence equations with polynomial coefficients plays an important role in other, more involved computational tasks such as finding d'Alembertian or Liouvillian solutions, and factoring linear recurrence operators.
CD
Definition 4 A sequence a G KN is hypergeometric2 if there is an N G N such that a(n) = 0 for all n > N, and there are polynomials p, q G K[n] \ {0} such that
p(n) a(n + 1) = q(n) a(n)	(3)
for all n > 0. We denote by H(K) the set of all hypergeometric sequences in K N.
Clearly, each hypergeometric sequence is P-recursive.
Proposition 1 The set H(K) is closed under the following operations:
1.	multiplication,
2.	reciprocation,
3.	nonzero scalar multiplication,
I
4.	shift,
5. multisection.
oa
Proof: For 1-4, see [29]. For multisection, let a G H(K) satisfy (3) and let b(n) = a(mn + r) where m G N, m > 2, and 0 < r < m. For i = 0,1,..., m — 1, substituting mn + r + i for n in (3) yields
CO
p(mn + r + i) a(mn + r + i + 1) = q(mn + r + i) a(mn + r + i). (4)
Multiply (4) by nj— =op(mn+r+j)Y\j=i+iq(mn+r+j) on both sides to obtain Ihsj = rhsj for i = 0,1,..., m — 1, where
i	m— 1
Ihsj = np(mn + r + j) JJ^ q(mn + r + j) a(mn + r + i + 1),
j=o	j=i+1
i—1	m—1
rhsi = p(mn + r + j) JJ^ q(mn + r + j) a(mn + r + i).
j=o	j=i
2A hypergeometric sequence is also called a hypergeometric term, because the nth term of CD	a hypergeometric series, considered as a function of n, is a hypergeometric sequence in our
sense.
u
a
CD U
o
u
a
CD U
Note that Ihsi = rhsi+1 for i = 0,1,..., m — 2, hence, by induction on i,
rhso = Ihsi for i = 0,1,..., m — 1. In particular, lhsm—1 = rhs0, so
m—1	m—1
|p(mn + r + j)b(n + 1) = q(mn + r + j)b(n),
j=o	j=0
hence b G H(K).	□
Theorem 7 The sequences a and 1/a are both P-recursive iff a is the interlacing of one or more hypergeometric sequences.
For a proof, see [30].
5 Closed-form solutions
In this section, we sketch algorithms for finding polynomial, rational, and hypergeometric solutions of linear recurrence equations with polynomial coefficients.
£
5.1	Recurrence operators
Let E : KN ^ KN be the (left) shift operator acting on sequences by (Ea)(n) = a(n + 1), so that (Eka)(n) = a(n + k) for k G N. For a given d G N and polynomials po,pi,... ,pd G K[n] such that pd = 0, the operator L : KN ^ KN defined by
L = Pk (n) Ek
k=0
is a linear recurrence operator of order d with polynomial coefficients, acting on a sequence a by (La)(n) = ^k=0Pk(n) a(n + k). We denote by K[n](E} the algebra of linear recurrence operators with polynomial coefficients. The commutation rule E • p(n) = p(n +1) E induces the rule for composition of operators:
d	e	de
£ Pk (n)Ek • £ qj (n)Ej = ££pk (n)qj (n + k)Ej+k.
k=0 j=0 k=0 j=0
5.2	Polynomial solutions
Given: L G K[n]{E), L = 0
Find: a basis of the space {y G K[n]; Ly = 0}
HH
Outline of algorithm
1.	Find an upper bound for deg y.
■ I
2.	Use the method of undetermined coefficients.
CD
For more details, see [3], [9], [29].
o
00
CO
5.3 Rational solutions
Outline of algorithm
1.	Find a universal denominator for y.
2.	Find polynomial solutions of the equation satisfied by the numerator of y.
Given: L G K[n]{E), L = 0 Find: a basis of the space {y G K(n); Ly = 0}
For more details, see [4], [6], [22], and [7].
5.4 Hypergeometric solutions
Given: L = Y1=o Pk Ek G K[n] (E), L = 0
Find: a generating set for the linear hull of {y G H(K); Ly = 0}
i—l
Outline of algorithm
1. Construct the "Riccati equation" for r = Ey G K (n):
o
2. Use the ansatz
a Ec
r = z ---
b c
d k-1
YPk H Ejr = 0	(5)
k=0 j=0
with z G K*, a, b, c G K [n] monic, a, c coprime, b, Ec coprime, a, Ek b coprime for all k G N to obtain
d k-1 d-1 Y zkPk (n Ej a) (n Ej b) Ek c = 0.	(6)
k=0 \j=0 J \j=k
3. Construct a finite set of candidates for (a, b, z) using the following consequences of (6):
•	a | po,
•	b | E 1-dpd,
•	Y lc(Pk )zk = 0
0 <k<d deg Pk =m
where Pk = Pk (^=0 Eja) (nd=fc Ejb), m = maxo<k<d deg Pk.
u
a
CD U
o
cm
2 u
CD
00
CO
u
a
CD U
4. For each candidate triple (a, b, z), find polynomial solutions c of the equation
^zfcPfc Ekc = 0.
k=0
For more details, see [28] or [29]. A much more efficient algorithm (although still exponential in deg + deg pd in the worst case) is given in [23] and [16].
Example 4 (Amer. Math. Monthly problem no. 10375) Solve
y(n + 2) - 2(2n + 3)2y(n +1) + 4(n +1)2(2n + 1)(2n + 3)y(n) = 0. (7)
Denote p2(n) = 1, pi(n) = -2(2n + 3)2, and p0(n) = 4(n +1)2(2n +1)(2n + 3). lO	In search of hypergeometric solutions we follow the four steps described above:
1. Riccati equation:
P2(n) r(n + 1)r(n) + pi(n) r(n) + po(n) = 0
o
2. plug in the ansatz:
z2 P2(n) a(n + 1) a(n) c(n + 2)
+ z pi(n) a(n) b(n + 1) c(n + 1) +	Po(n) b(n + 1) b(n) c(n)
3. candidates for (a, b, z):
2
Qï
o
cm CM
•	a(n) | 4(n + 1)2(2n + 1)(2n + 3)
CM
•	b(n) | 1
•	z2 - 8z +16 = (z - 4)2 = 0
CO
Take, e.g., a(n) = (n + 1)(n + |), b(n) = 1, z = 4. 4. equation for c:
(n + 2)c(n + 2) - (2n + 3)c(n + 1) + (n + 1)c(n) = 0 Polynomial solution: c(n) = 1
We have found
y(n + 1)	.	a(n) c(n + 1)
= r(n) = z^^ K ' = (2n + 1)(2n + 2),
y(n)	b(n) c(n)
therefore y(n) = (2n)! is a hypergeometric solution of equation (7).
0
o
ft
o
csr
i
J-H
a
CD U
6 Difference rings
Definition 5 A difference ring is a pair (K, a) where K is a commutative ring with multiplicative identity and a : K ^ K is a ring automorphism. If, in addition, K is a field, then (K, a) is a difference field.
Example 5
•	(K[x], a) with ax = x +1, a|x = id_K is a difference ring.
•	(K(x), a) with ax = x + 1, a|x = id_K is a difference field.
•	(KN, E) is not a difference ring since the shift operator E is not injective on Kn.
lO
For a, b G KN define a ~ b if there is an N G N such that a(n) = b(n) for all n > N. The ring S (K) = KN/ ~ of equivalence classes is the ring of germs of sequences . Let f : KN ^ S(K) be the canonical projection, and a : S(K) ^ S(K) the unique automorphism of S(K) s.t. a o f = f o E. Then (S(K),a) is a difference ring.
To avoid problems with sequences with some undefined terms (such as those given by rational functions with nonnegative integer poles), and to have the advantage of working in a difference ring, we will henceforth work in (S(K), a) rather than in KN (but will still call its elements just "sequences" for short). Consequently we identify sequences which agree from some point on, and our statements may have a finite set of exceptions. The sets K[n], K(n), H(K) all naturally embed into S(K) (e.g., by mapping f G K(n) to the germ of (0, 0,..., 0, f (N), f (N + 1),...} where N is an integer larger than any integer pole of f).
7 An Ore algebra of operators
Instead of linear recurrence operators with polynomial coefficients from K[n](E}, we will henceforth use linear difference operators with rational coeffi-
CO
cients from the algebra K(n)(a}. The rule for composition of these operators follows from the commutation rule a • r(n) = r(n +1) a for all r G K(n). The identity
r(n) ak = (- ak—^ • s(n) aj
Vs(n + k—j) ; v 7
describes how to perform right division of r(n) ak by s(n) aj. Hence there is an algorithm for right division in K(n)(a}:
CD
Theorem 8 For L1,L2 G K(n)(a}, L2 = 0, there are Q,R G K(n)(a} such that
• L1 = QL2 + R,
that
CD
o
CM
ft
o
CM
i
cm 00 cm cm
CO CD
$H
CD CO
Jh
a
CD U
ord R < ord L2 •
As a consequence, the right extended Euclidean algorithm (REEA) can be used cm	to compute a greatest common right divisor (gcrd) and a least common left
multiple (lclm) of operators in K(n)(a), which is therefore a left Ore algebra. In particular, given Li, L2 G K(n)(a), REEA yields S, T, U, V G K(n)(a) such
that
• SLi + TL2 = gcrd(Li,L2)
ULi = VL2 = lclm(L1, L2).
Definition 6 Let a be P-recursive. The unique monic operator Ma G K(n)(a}\ {0} of least order such that Maa = 0 is the minimal operator of a.
LO
Example 6 Let h G H(K) where ah/h = r G K(n)*. Then Mh = a - r.
i—I
Question 3. How to compute Ma for a given P-recursive a?
The outline of an algorithm for solving this problem is given on page 13.
o
Proposition 2 Let a be P-recursive, and L G K(n)(a} such that La = 0. Then L is right-divisible by Ma.
Proof: Divide L by Ma. Then:
L = QMa + R	La = QMaa + Ra	0 = Ra	R = 0
□
Corollary 1 Let L G K(n)(a) and h G H(K) be such that Lh = 0. Then there is Q G K(n)(a) such that L = Q(a — r) where r = ah/h G K(n)*.
Hence there is a one-to-one correspondence between hypergeometric solutions of Ly = 0 and first-order right factors of L having the form a — r with r = 0.
CO
Example 7 (Amer. Math. Monthly problem no. 10375 - continued from Example 4)
L = a2 — 2(2n + 3)2a + 4(n + 1)2(2n + 1)(2n + 3)
We saw in Example 4 that Ly = 0 is satisfied by y(n) = (2n)!. Hence L = QLi where
L1 = a — (2n + 1)(2n + 2), Q = a — (2n + 2)(2n + 3).
o
(Ö u CD
10
00
0 Ö
o
1
CO ^
CO CO
CO CD
$H
CD CO
Operator factorization problem Given: L G K(n)(a) and r G N Find: all Li G K(n)(a) s.t.
•	ord Li = r,
•	L = QL1 for some Q G K(n)(a)
Suppose such L1 exists, and let y(1), y(2),..., y(r) be linearly independent solutions of L1y = 0 in S(K). The Casoratian Cas(y(1), y(2),..., y(r)) is defined
det
y
(1)
(1)
y
(2)
ay
ar-1y(1)
(2)
y
(r)
ay
ar-1y(2)
(r)
ay
ar-1y(r)
Then:
1.	Cas(y(1), y(2),..., y(r)) G H(K),
2.	Cas(y(1), y(2),..., y(r)) = Cas(L1),
3.	from L and r one can construct a linear recurrence with polynomial coefficients satisfied by Cas(L1),
4.	from L and r one can construct linear recurrences with polynomial coefficients satisfied by the coefficients of L1, multiplied by Cas(L1).
Outline of an algorithm to solve the operator factorization problem:
1.	Construct a recurrence satisfied by Cas(L1).
2.	Find all hypergeometric solutions of this recurrence.
3.	Construct recurrences satisfied by the coefficients of L1.
4.	Find all rational solutions of these recurrences.
5.	Select candidates for L1 which right-divide L.
Outline of an algorithm to find the minimal operator of a P-recursive sequence:
Given: L G K (n)(a) and a G S (K ) s.t. La = 0 Find: minimal operator Ma of a
for r = 1, 2,.. ., ord L do:
find all monic L1 G K(n)(a) of order r s.t. 3Q G K(n)(a): L = QL1
for every such L1 do:
if (L1 a)(n) = 0 for ord Q consecutive values of n
then return L1.
In the last line, the ord Q consecutive values of n must be greater than any integer root of the leading coefficient of Q.
u
a
CD U
00 1—1
o
8 D'Alembertian solutions

u
CD
U
a
CD U
Write A = a — 1 for the forward difference operator as usual. If y = a satisfies Ly = 0, then substituting y ^ az where z is a new unknown sequence yields
L' Az = 0
where ord L' = ord L — 1. This is known as reduction of order or d'Alembert substitution [5]. By using this substitution repeatedly we obtain a set of solutions which can be written as nested indefinite sums with hypergeometric summands. These so-called d'Alembertian sequences include harmonic numbers and their generalizations, and play an important role in the theory of Pade approximations (cf. [17], [18]), in combinatorics (cf. [27], [34]) and in particle physics (cf. [1], [12], [2]).
00
8.1 Definition and representation
Definition 7 A sequence a G S(K) is d'Alembertian if there are first-order operators Lj, L2, .. ., Ld G K(n)(a) such that
o
Ld ••• L2L1 a = 0.	(8)
We denote by A(K) the set of all d'Alembertian elements of S(K), and write nd(a) for the least d G N for which (8) holds (the nesting depth of a).
Remark 2 Let a G A(K). Then:
1.	nd(a) =0 if and only if a = 0,
2.	nd(a) = 1 if and only if a G H(K).
00
Example 8
• Harmonic numbers H(n) = -= k are d'Alembertian because £ =
;k= 1 k
1	n + 1\ ,	ww n	( n + 1\ 1
la — —2)(a —1)H(n) = a — —2) nn = a
• Derangement numbers d(n) = n! -=° ( 1 are d'Alembertian because (a+1)(a — (n+1)) d(n) = (a+1)(n+1)!(—= (a+1)( —1)-+1 = 0. Notation: For a G S(K) and A C S(K) we write
^	--1
Sa = {b GS(K); Ab = a} = ^ a(k) + C,
k=°
SA = {b gS(K); Ab G A}
CD
where C G K is an arbitrary constant.
o

CO
5H
a
CD U
Remark 3
1.	A + 1 = a,
2.	AS = 1,
3.	a S = S + 1,
4.	SO = K.
f
{y eS(K); (a - r)y = f} = h S f
Proposition 3 Let r e K(n), ah = rh, and f e S(K). Then
Proof: Assume that (a — r)y = f and write y = hz. Then
f = (a — r)y = (a — r)h z = ahaz — r hz = ah Az, hence Az = f, so z e S—h and y = hz e h Sf. - Conversely,
(a — r)h S-f = ahaSf--rh S-f = ah AS-f = f.
ah	ah	ah	ah
c
Corollary 2
Ker (a — rd) ■■■ (a — r2)(a — ri) = hi S^ S^ ■ ■ ■ S-^ SO (9)
ahi ah2 ahd-i
where ahi = rjhj for i = 1, 2,. .. ,d.
cs
It turns out that for any L e K(n)(a), the space of all d'Alembertian solutions of Ly = 0 is of the form
h1 Sh2 Sh3 ••• Shd SO	(10)
for some d < ord L and h1, h2,... ,hd e H(K ).
Example 9 (Amer. Math. Monthly problem no. 10375 - continued from Example 7)
L = a2 — 2(2n + 3)2a + 4(n +1)2(2n + 1)(2n + 3), L = L2L1,
L1 = a — (2n + 1)(2n + 2), L2 = a — (2n + 2)(2n + 3).
Since L1(2n)! = 0 and L2(2n + 1)! = 0, it follows from (9) that
Ker L = (2n)!S(2n +^S0 = (2n)!S- °
(2n + 2)!	v '' n +1
= (2n)! k+i + = C (2n)! H(n) + D (2n)!
CD	=
where C, D e K are arbitrary constants.
o
u
a
CD U
8.2 Closure properties of A(K)
Definition 8 For operators L, R G K(n){u), denote by L/R the right quotient of lclm(L, R) by R.
Remark 4 Clearly, (L/R)R = lclm(L, R) = (R/L)L.
Example 10 Let Li = a — ri and L2 = a — r<2 be first-order operators. If ri = r2 then L1/L2 = L2/L1 = 1. If ri = r2 it is straightforward to check that
f uri — ur2	, f url — ur2 A, s
a--ri (u — r2) = u--r2 (u — ri),
ri — r2	ri — r2
hence
IO
T ,T <jri - ar^	<jr\ - ar2
L1/L2 = a--ri,	L2/L1 = a--r2.
ri - r2	ri - r2
Lemma 1 Let Li, L2,. .., Lk,R G K(n)(a) be monic first-order operators. Then there are monic operators Ni, N2,. .., Nk,M G K(n)(a) \ {0} of order < 1 such that
MLkLk-i ■■■ Li = NkNk-i ••• NiR. Proof: By induction on k.
k =1: Take Ni = Li/R, M = R/Li. Then MLi = (R/Li)Li = (Li/R)R = NiR.
k > 1: By inductive hypothesis, there are monic operators Nh N2,..., Nk-i, M G K(n)(a) \ {0} of order < 1 such that
C^
MILk-iLk-2 ■■■ Li = Nk-iNk-2 ■■■ NiR.	(11)
C^	I I
Take Nk = Lk/M, M = M/Lk. Then, using (11) in the last line, we obtain
MLkLk-i ■■■ Li = (M/Lk)LkLk-iLk-2 ■■■ Li = (Lk/M)MLk-iLk-2 ■■■ Li = NkMLk-iLk-2 ■■■ Li = NkNk-iNk-2 ■■■ NiR.
Lemma 2 Let Li, L2,..., Lk, Ri, R2,..., Rm G K(n)(a) be monic first-order operators. Then there are monic operators Mi, M2,.. ., Mm, Ni, N2, .. ., Nk G K(n)(a) \ {0} of order < 1 such that
l-H
MmMm-i ■■■ MiLkLk-i ■■■ Li = NkNk-i ■■■ NiRmRm-i ■■■ Ri.
&
Proof: By induction on m.
m = 1: By Lemma 1 applied to Li, L2,..., Lk,Ri, there are Ni, N2,..., Nk and Mi suchthat MiLk Lk-i ■■■ Li = Nk Nk-i ■■■ NiRi.
&
o

CD
00
Jh
a
CD U
m > 1: By inductive hypothesis applied to Ri, R2,..., Rm-i, there are monic operators Mi, M2,..., Mm-i, NVi, N2,..., Nk e K(n)(a) \ {0} of order < 1 such that
Mm-iMm-2 ••• MiLkLk-i ••• Li = V Vk-i ••• ViRm-iRm-2 ••• Ri. (12)
By Lemma 1 applied to N^ N2,..., Nk, Rm, there are Ni, N2,..., Nk and M„ such that
MmNfcNfc_i ••• NNi = NfcNfc_i ••• NiRm,
Jh
hence, by multiplying (12) with Mm from the left, we obtain
MmMm-i ••• MiLkLk-1 Li = MmVkVk-i ••• ViRm-iRm-2 ••• Ri
= V Vk-i ••• Vi Rm Rm -1 ••• Ri.
Proposition 4 A(K) is closed under addition.
Proof: Let a, b G A(K). Then there are monic first-order operators Li, L2,..., Lk, Ri, R2,..., Rm G K(n)(a) such that
LkLk-i ••• Lia = RmRm_i ••• Rib = 0.
By Lemma 2, there are monic operators Mi,..., Mm, Ni,..., Nk G K(n)(a) \ {0} of order < 1 such that
L := MmMm-i ••• MiLk Lk-i ••• Li = N Nk-i ••• NiRmRm-i ••• Ri.
Then La = Lb = 0, so L(a + b) = 0 and a + b G A(K).	□
Proposition 5 A(K) is closed under multiplication.
CO
Proof: Let a, b G A(K). We show that ab G A(K) by induction on the sum of their nesting depths nd(a) + nd(b).
a)	nd(a) = 0 or nd(b) = 0: In this case one of a, b is 0, hence ab = 0 G A(K).
b)	nd(a), nd(b) > 1: By (10) we can write a G hi £h2 £h3 • • • £hd £0 and b G gi £g2 £g3 • • • £ge £0 where hj, gj G H(K), d = nd(a), and e = nd(b). Let ai = h2 Xh3 • • • £hd £0 and bi = g2 £g3 • • • £ge £0, so that a G hi Sai and
CO
b G gi £bi with ai, bi Ç A(K), nd(ai) < nd(a) and nd(bi) < nd(b). Clearly ha G A(K) whenever h G H(K) and a G A(K), hence it suffices to show that (E ai)gi E bi Ç A(K). Using the product rule of difference calculus
Auv = uAv + Am av
and Remark 3 repeatedly, we obtain
A ((£ ai)gi Y bi)
= (£ ai)giA E bi + A((E ai)gi)a E bi = (E ai)gibi + ((E ai)Agi + aiagi)(E bi + bi) = Agi(E ai)£ bi + (gi + Agi)bi E ai + aiagi(E bi + bi)
= Agi(E ai) E bi + agi (ai E bi + bi E ai + aibi).
o
CM
cm £
o
CM
i
cm 00 cm
CO CO
$H
a
CD u
Assume first that g1 = 1. Then A ((J^ a1) b1) = a1 b1 + b1 a1 + a1b1. By inductive hypothesis and from Proposition 4 it follows that a1 ^ b1 + b1 ^ a1 + a1b1 Ç A(K). Therefore there are first-order operators L1,L2,...,Lk G K (n)(a) such that
Lk Lk-1 ••• ¿1A(E a^E b1) = 0,
CD
hence (^ ajJ^ b1 Ç A(K). In the general case, Ag1,ag1 G H(K) now implies A((E a1)g^ b1) Ç A(K). Again we conclude that (£ a1)g^ b1 Ç A(K). □
rO
Proposition 6 A(K) is closed under a and a 1.
Proof: Let a G A(K). Then there are monic first-order operators L1, L2,..., Lk G K(n)(a) such that LkLk-1 ■ ■ ■ L1 a = 0.
By Lemma 1 with R = a, there are monic operators N1, N2,..., Nk, M G K(n)(a) \ {0} of order < 1 such that MLkLk-1 ■ ■ ■ L1 = NkNk-1 ■ ■ ■ N1a. Hence
NkNk-1 ••• N1aa = MLk Lk-1 ••• ¿1a = 0,
so aa G A(K).
From Lk Lk-1 ••• L1a = 0 it follows that LkLk-1 ••• L1a(a-1a) = 0, hence a-1a G A(K) as well.	□
Theorem 9 A(K) is a difference ring.
Proof: This follows from Propositions 4, 5 and 6.	□
Corollary 3 A(K) is the least subring of S(K) which contains H(K) and is closed under a, a-1, and £.
Proof: Denote by HS(K) the least subring of S(K) which contains H(K)
cm	and is closed under a, a , and £.
By Corollary 2, every a G A(K) is obtained from 0 by using £ and multipli-
cation with elements from H(K). Hence A(K) Ç HS(K).
Conversely, A(K) is closed under a and a-1 by Proposition 6, and under £ by Corollary 2. Since A(K) is a subring of S(K) containing H(K), it follows that HS(K) Ç A(K).	□
Proposition 7 A(K) is closed under multisection.
Proof: Let a G A(K). We show that any multisection of a belongs to A(K) by induction on the nesting depth nd(a) of a.
a)	nd(a) = 0: In this case a = 0, so the assertion holds.
b)	nd(a) > 1: By (10) we can write a G hi £h2 £h3 • • • £hd £0 where d = nd(a) and hi, h2,..., hd G H(K). Let h = hi and b = h2 £h3 • • • £hd £0, so that a G h £b where b C A(K) and nd(b) < nd(a).
CD
o
cm
o
CD
■ i-H
u
CD CO
a
CD U
Let c G S(K), defined by c(n) = a(mn + r) for all n G N, where m, r G N, m > 2, 0 < r < m, be a multisection of a. Then for all n G N
mn+r-1
c(n) = a(mn + r) = h(mn + r)	b(k)
k=0
/m—1 n—1	r—1
= h(mn + r) | ^^ b(mj + i) + b(mn + i)
\ ¿=0 j=0 ¿=0
^ /
I m — 1 n — 1	r — 1
— hm,r
y ¿=0 j=0	¿=0
lO
where hm r (n) = h(mn + r) and bm ¿(n) = b(mn + i) for 0 < i < m. Hence
00
/m—1	r—1 \
c	hm,r ( ^ ^ £bm,i I ^ ^ bm,i J
¿=0 ¿=0
8.3 Finding d'Alembertian solutions
where hm r G H(K) C A(K) by Proposition 1, and bm i G A(K) by inductive hypothesis as a multisection of b. Since A(K) is closed under £, addition and multiplication, it follows that c G A(K).	□
o
The following theorem provides a way to find d'Alembertian solutions of Ly = 0.
I
Theorem 10 Ly = 0 has a nonzero d'Alembertian solution if and only if Ly = 0 has a hypergeometric solution.
CM
For a proof, see [10].
Outline of an algorithm for finding the space of all d'Alembertian solutions:
CO
1.	Find a hypergeometric solution h1 of Ly = 0. If none exists then return 0 and stop.
2.	Let L1 = a — ^. Right-divide L by L1 to obtain L = QL1.
3.	Recursively use the algorithm on Qy = 0. Let the output be a.
4.	Return h1 £and stop.
A much more general algorithm which finds solutions in n£*-difference extension fields of (K(n),a) is presented in [32]. For the relevant theory, see [33],
[35], [36], [37].
CD
00 1—1
o
9 Liouvillian solutions
& O
I
00
u
CD
U
a
CD U
Definition 9 L(K ) is the least subring of S (K ) containing H(K ), closed under
•	a, a-1,
•	D,
si
ctf
• interlacing of an arbitrary number of sequences.
u
The elements of L(K) are Liouvillian sequences.
CD
Example 11 The sequence
II J 2fck!, n = 2k, n!! = 1 (2fc + 1)! o; . , I 2^+! , n = 2k +1
is Liouvillian (as an interlacing of two hyper geometric sequences ).
The following theorem provides a way to find Liouvillian solutions of Ly = 0.
o
Theorem 11 Ly = 0 has a nonzero Liouvillian solution if and only if Ly = 0 has a solution which is an interlacing of at most ord L hypergeometric sequences.
For a proof, see [21]. For algorithms to find Liouvillian solutions, see [13], [25], [8], [14], [15], [24], [19], [20].
Theorem 12 A sequence in S(K) is Liouvillian if and only if it is an interlacing of d'Alembertian sequences.
This is proved in [31] as a corollary of the results of [21] obtained by means of Galois theory of difference equations. Here we give a self-contained proof based on closure properties of interlacings of d'Alembertian sequences.
Let A(ao, a1,..., ak-1), or Ak—^aj, denote the interlacing of a0, a1,..., ak-1. By definition of interlacing we have
(A^aj) (n) = A(ao,a1,...,afc_1)(n) = a„ mod k (n div k)
for all n G N, where
n div k =
Lk
n mod k = n —
n
LkJ
k.
Denote temporarily the set of all interlacings of (one or more) d'Alembertian sequences by AL(K). The goal is to prove that AL(K) = L(K).
CO
Proposition 8 AL(K) Ç L(K).
Proof: Since H(K) C L(K) and L(K) is a ring closed under £, we have
A(K) Ç L(K). Since L(K) is closed under interlacing, AL(K) Ç L(K). □
n
o
CM
CM ft
u
CD
lO
00
0 o
cm
1
cm 00 cm
cm £
CO CO
CO CD
Jh
CD CO
Lemma 3 AL(K) is closed under addition and multiplication.
Proof: Let © denote either addition or multiplication in K and S(K). We claim that, for k, m G N and a0, ai,..., ak-i, b0, bi,..., bm-i G A(K), we have
(Ak=01a^ © (A?!^) = ^iHo 1(a£,fe,m © b*,fc,m)
(13)
where for all n G N,
a*,fc,m(n) = a£ mod k(mn + ^ div k), b£,fc,m(n) = mod m(kn + ^ div m).
Indeed, (A^mrHa^fc,™ © bi.fc.m)) (n)
where
od fcm,fc,m(n div km) © 6„ mod fcm,fc,m(n div km) = u © v
u — a(n mod fcm) m0
d k(m(n div km) + (n mod km) div k), V = b(n mod km) mod m(k(n div km) + (n mod km) div m).
From
(n mod km) mod k = (n mod km) mod m = n
m(n div km) + (n mod km) div k
-km -n
km
m
km mod k = n mod k, km mod m = n mod m,
n
k(n div km) + (n mod km) div m = k
km n div k n
km n div m
+
+
n — I t^ I km
L km J
n — t^ km
km
n m
it follows that
u © v = a„ mod k(n div k) © 6„ mod m(n div m)
(Ak-Oaj) (n) © (ASTo1^) (n) = ((A^a,) © (Am^bj)) (n),
proving (13). By Proposition 7, the sequences a£,km and &£,fc,m belong to A(K). Since A(K) is a ring, the right-hand side of (13) is an interlacing of d'Alembertian sequences, and hence so is the left-hand side.	□
Lemma 4 AL(K) is closed under a and a
1
u
a
CD U
n
k
m
o
u
CD
10
00
0 £
o
1
00 ^
CO CO
Proof: Let a°,a1,..., ak-1 be d'Alembertian sequences. Then:
(a (A^)) (n) = (A:
kja^ (n +1)
= 0(n+1) mod k((n + 1)div k)
an mod k+i(n div k), n mod k = k — 1, a0(n div k +1), n mod k = k — 1
an mod k+i(n div k), n mod k = k — 1, (aa0)(n div k),	n mod k = k — 1
= (Ak-j (n)
where
bj =
_ / aj+i, j = k — aao, j = k — 1.
k-1
j=0 j = Ak=obj
By Proposition 6, b°, b1?..., bk-1 are d'Alembertian. So a (A is an interlacing of d'Alembertian sequences. Similarly,
(a-1 (A^)) (n) = (A*-^) (n — 1)
= a(--1)mod k ((n — 1) div k)
a- mod k-1(n div k), n mod k = 0, ak-1(n div k — 1), n mod k = 0
a- mod k-1(n div k), n mod k = 0,
(a-1ak-1)(n div k), n mod k = 0 (Ai^cj) (n)
where
a,--i,
-l
j =0,
a ak-i, j
0.
By Proposition 6, c0,ci,..., ck-i are d'Alembertian. So a i (Ak^aj) =
is an interlacing of d'Alembertian sequences.	□
Lemma 5 AL(K) is closed under S.
Proof: Let a°,a1,..., ak-1 be d'Alembertian sequences. We claim that
(j-1
k-i
£(Ak-iaj) = Ak- [J2 aZat + £ Sa
(14)
CO CD
$H
CD CO
u
a
CD U
c
j
o
5H
CO
a
CD Jh
Indeed, for all n G N,
(E (A*-1",-)) (n)
¿=0" J
-1	n-1
o
0 £=0
]T(Ak-0aj) (i) = ]T "£ mod fc (i div k)
£=0 £=0
(n-1) mod k [^ttJ	k-1	LT-1 J-1
E E "^(j) + EE "^(j) (15)
¿=0	j=0	i=(n-1) mod k + 1 j=0
n mod k-1 LkJ	k-1 |_kJ-1
E E "^(j) + E E "i(j)	(16)
i=0 j=0	i=n mod k j=0
n mod k-1	k-1
E (aEa,) (n div k) + E (Ea,) (n div k)
n
i=n mod k
j-1 k-1
j = 0
Ak-1 ( £+ £Ea, I I (n),
proving (14). Here equality in (15) follows by mapping each i G {0,1,..., n — 1} to the pair (i, j) = (i mod k, i div k) and summing over all the resulting pairs, and equality in (16) follows by noting that when n mod k = 0, we have
(n — 1) mod k = n mod k — 1, (n — 1) div k = n div k,
00
while for n mod k = 0, both (15) and (16) are equal to J2i=o SjUo "¿(j).
Since A(K) is closed under E, a and addition, the right-hand side of (14) is an interlacing of d'Alembertian sequences, and hence so is the left-hand side. □
Lemma 6 AL(K) is closed under interlacing.
CO
Proof: An arbitrary interlacing can be obtained by using addition, shifts, and interlacing of zero sequences with a single non-zero sequence by the formula
A("0,"1,... ,"k-1) = E a*A(0,0,..., 0, ak-1-i).
¿=0
Hence, by Propositions 3 and 4, it suffices to show that AL(K) is closed under interlacing of zero sequences with a single non-zero sequence from AL(K). But this is immediate: Let a0, a1,..., ak-1 be d'Alembertian sequences. Then the
interlacing of m zero sequences with A(a0, a1,..., ak-1)
■ I
A(0,0,..., 0, A("0,"1,...,ak-1)) = A(0,0,..., 0, a0,0, 0,..., 0, a1,..., 0, 0,..., 0, ak-1)
(N
is an interlacing of mk + k d'Alembertian sequences.	□
Proof of Theorem 12. By Proposition 8, it suffices to show that L(K) C AL(K). This is true since by Lemmas 3-6, AL(K) is a subring of S(K) containing H(K) and closed under a, a-i, E and interlacing, while L(K) is the least such ring.	□
<0
References
$H
[1] Ablinger, J., Blumlein, J., Schneider, C.: Harmonic sums and polylog-arithms generated by cyclotomic polynomials, J. Math. Phys. 52, 1-52 (2011)
CD
[2] Ablinger, J., Blumlein, J., Schneider, C.: Analytic and algorithmic aspects of generalized harmonic sums and polylogarithms, submitted, 75 pages (2013)
o
u
a
CD U
[3] Abramov, S.A.: Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations, Moscow Univ. Comput. Math. Cybernet. 3, 63-68 (1989). Transl.
from Vestn. Moskov. univ. Ser. XV. Vychisl. mat. kibernet. 3, 56-60 (1989)
[4] Abramov, S.A.: Rational solutions of linear differential and difference equations with polynomial coefficients, U.S.S.R. Comput. Maths. Math. Phys. 29, 7-12 (1989). Transl. from Zh. vychisl. mat. mat. fyz. 29, 16111620 (1989)
[5] Abramov, S.A.: On d'Alembert substitution, Proc. ISSAC'93, Kiev, 20-26 (1993)
CO
[6]	Abramov, S.A.: Rational solutions of linear difference and q-difference equations with polynomial coefficients, Programming and Comput. Software, 21, 273-278 (1995). Transl. from Programmirovanie 21, 3-11 (1995)
[7]	Abramov, S.A., Barkatou, M.A.: Rational solutions of first order linear difference systems, Proc. ISSAC'98, Rostock, 124-131 (1998)
[8]	Abramov, S.A., Barkatou, M.A., Khmelnov, D.E.: On m-interlacing solutions of linear difference equations, Proc. CASC'09, Kobe, LNCS 5743, Springer, 1-17 (2009)
[9]	Abramov, S.A., Bronstein, M., Petkovsek, M.: On polynomial solutions of linear operator equations, Proc. ISSAC'95, Montreal, 290-296 (1995)
[10]	Abramov, S.A., Petkovsek, M.: D'Alembertian solutions of linear operator equations, Proc. ISSAC'94, Oxford, 169-174 (2004)
[11]	Apagodu, M., Zeilberger, D.: Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Adv. in Appl. Math. 37, 139-152 (2006)
o
CM
cm
(Ö u CD
lO
00
0 Ö
o
cm
1
cm 00 cm cm
£ CO CO
CO CD
Jh
CD CO
12]	Blümlein, J., Klein, S., Schneider, C., Stan, F.: A symbolic summation approach to Feynman integral calculus, J. Symbolic Comput. 47, 12671289 (2012)
13]	Bomboy, R.: Liouvillian solutions of ordinary linear difference equations, Proc. CASC'02, Simeiz (Yalta), 17-28 (2002)
14]	Cha, Y., van Hoeij, M.: Liouvillian solutions of irreducible linear difference equations, Proc. ISSAC'09, Seoul, 87-94 (2009)
15]	Cha, Y., van Hoeij, M., Levy, G.: Solving recurrence relations using local invariants, Proc. ISSAC'10, München, 303-309 (2010)
16]	Cluzeau, T., van Hoeij, M.: Computing hypergeometric solutions of linear recurrence equations, Appl. Algebra Engrg. Comm. Comput. 17, 83-115 (2006)
17]	Driver, K., Prodinger, H., Schneider, C., Weideman, J.A.C.: Pade approximations to the logarithm. II. Identities, recurrences, and symbolic computation, Ramanujan J. 11, 139-158 (2006)
18]	Driver, K., Prodinger, H., Schneider, C., Weideman, J.A.C.: Pade approximations to the logarithm. III. Alternative methods and additional results, Ramanujan J. 12, 299-314 (2006)
19]	Feng, R., Singer, M.F., Wu, M.: Liouvillian solutions of linear difference-differential equations, J. Symbolic Comput. 45, 287-305 (2010)
20]	Feng, R., Singer, M.F., Wu, M.: An algorithm to compute Liouvillian solutions of prime order linear difference-differential equations, J. Symbolic Comput. 45, 306-323 (2010)
21]	Hendriks, P.A., Singer, M.F.: Solving difference equations in finite terms, J. Symbolic Comput. 27, 239-259 (1999)
22]	van Hoeij, M.: Rational solutions of linear difference equations, Proc. ISSAC'98, Rostock, 120-123 (1998)
23]	van Hoeij, M.: Finite singularities and hypergeometric solutions of linear recurrence equations, J. Pure Appl. Algebra 139, 109-131 (1999)
24]	van Hoeij, M., Levy, G.: Liouvillian solutions of irreducible second order linear differential equations, Proc. ISSAC'10, Munchen, 297-301 (2010)
25]	Khmelnov, D.E.: Search for Liouvillian solutions of linear recurrence equations in MAPLE computer algebra system, Program. Comput. Softw. 34, 204-209 (2008)
26]	Larson, R.G., Taft, E.J.: The algebraic structure of linearly recursive sequences under Hadamard product, Israel J. Math. 72, 118-132 (1990)
u
a
CD U
o
CM
CM
u
CD
lO
00
0 o
cm
1
cm 00 cm cm
£ CO CO
CO CD
Jh
CD CO
[27]	Paule, P., Schneider, C.: Computer proofs of a new family of harmonic number identities, Adv. in Appl. Math. 31, 359-378 (2003)
[28]	Petkovsek, M.: Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symbolic Comput. 14, 243-264 (1992)
[29]	Petkovsek, M., Wilf, H.S., Zeilberger, D.: A = B, A K Peters, Wellesley, MA (1996)
[30]	van der Put, M., Singer, M.F.: Galois Theory of Difference Equations, Springer-Verlag, Berlin (1997)
[31]	Reutenauer, C.: On a matrix representation for polynomially recursive sequences, Electron. J. Combin. 19(3), P36 (2012)
[32]	Schneider, C.: The summation package Sigma: underlying principles and a rhombus tiling application, Discrete Math. Theor. Comput. Sci. 6 (electronic), 365-386 (2004)
[33]	Schneider, C.: Solving parameterized linear difference equations in terms of indefinite nested sums and products, J. Difference Equ. Appl. 11, 799821 (2005)
[34]	Schneider, C.: Symbolic summation assists combinatorics, Sem. Lothar. Combin. 56, Art. B56b (electronic), 36 pp. (2006/07)
[35]	Schneider, C.: Simplifying sums in n£*-extensions, J. Algebra Appl. 6, 415-441(2007)
[36]	Schneider, C.: A refined difference field theory for symbolic summation, J. Symbolic Comput. 43, 611-644 (2008)
[37]	Schneider, C.: Structural theorems for symbolic summation, Appl. Algebra Engrg. Comm. Comput. 21, 1-32 (2010)
[38]	Stanley, R.P.: Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge (1997)
[39]	Stanley, R.P.: Differentiably finite power series, European J. Combin. 1, 175 -188 (1980)
[40]	Stanley, R.P.: Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge (1999)
[41]	Zeilberger, D.: A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80, 207-211 (1990)
[42]	Zeilberger, D.: The method of creative telescoping, J. Symbolic Comput. 11, 195-204 (1991)
u
a
CD U