New Algorithms for Definite Summation and Integration

Frdric Chyzak

Projet Algo -- Inria Rocquencourt

Algorithms Seminar

March 17, 1997

[summary by Bruno Salvy]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
In 1978, W. Gosper gave an algorithm to compute the indefinite sum of an hypergeometric sequence. This algorithm has been incorporated in most computer algebra systems as the basis of their summation routines. Then, in the early 1990's D. Zeilberger applied a version of Gosper's algorithm in a clever way to the efficient calculation of definite sums of hypergeometric sequences. Zeilberger also gave a very general but slow algorithm for the general case of holonomic functions. F. Chyzak shows how Zeilberger's fast algorithm can be extended to a much more general context, including summation and integration of holonomic functions and sequences.



Introduction

F. Chyzak's algorithms [7] aim at computing automatically the right-hand side of identities like the following ones, given their left-hand side:
n
k=1

k
m

Hk
=

n+1
m+1




Hn+1-
1
m+1



,
n
k=0



k
j=0

n
k




3



 
=n23n-1+23n-3n2n-2

2n
n

,
n=0
Hn(x)Hn(y)
un
n!
=
exp


4u(xy-u(x2+y2))
1-4u2



(1-u2)1/2
,

+1


-1
e-pxTn(x)
(1-x2)1/2
dx
=(-1)np In(p),

+


0
xe
-px2
 
Jn(bx)In(cx)dx
=
1
2p
exp


c2-b2
4p



Jn


bc
2p



,

+


0
xJ1(ax)I1(ax)Y0(x)K0(x)dx
=-
ln(1-a4)
2p a2
,
n=0
rn(a,b)zn
(q;q)n
=
1
(az;q)
 
(bz;q)
 
.
More precisely, for indefinite summations or integrations, the output of the algorithm is an expression for the right-hand side in terms of the left-hand side, while in the definite case, these new algorithms will produce a linear operator or a system of linear operators annihilating the right-hand side. From there, the solution can be found by Petkovsek's algorithm [9] in the recurrence case, by its q-version [4, 5] in the q-case, or by algorithms on differential equations [10, 11] in the differential case.

These examples are treated in a unified manner by considering algebras of linear operators 1,...,r with coefficients in a suitable field K. In most applications, these operators are partial differentiations, shifts or q-shifts. Then one considers -finite terms t which are such that the
a t=
a1
 
1
ar
 
r
t,    aiN,     (1)
span a finite-dimensional vector space over K.

Examples are: In the case of shifts, -finite terms corresponding to 1-dimensional vector spaces are exactly the hypergeometric sequences. In the differential case, Zeilberger's holonomic functions [12] are also -finite. The closure properties under sum, product and the i's generalize to this context [8].

1   Indefinite -finite summation and integration

Given a -finite term and a basis b1,...,bN of the vector space generated by its a as in (1), Chyzak's first algorithm finds solutions in this vector space for equations of the form
P(1,...,r) X=B,
where P is a polynomial in K1,...,r, X is the unknown and B is a given element of the vector space. The first step of the algorithm consists in setting
X=f1 b1+...+fNbN
with undeterminate coefficients fi's in K. The left-hand side of the equation is then expressed in the basis of the bi's. Identifying coefficients then yields a system of linear equations satisfied by the fi's. It then suffices to find rational solutions of this system, i.e., solutions in K. Several algorithms developed by S. Abramov and coauthors are available for this purpose, depending on the i's [1, 2, 3, 6].

An important special case of this algorithm is when P=Sn-1, which correspond to indefinite summation. In this setting the problem solved by Gosper's algorithm corresponds to vector spaces of dimension 1, and then a single rational coefficient has to be found.

For instance, consider computing the primitive of the integral cosine,
Ci (z)=
z


0
cos(t)
t
 dt
.
From the differential equation satisfied by cos(t), one readily computes a third order linear differential equation satisfied by Ci. In the algebra  A=Q(z) Dz, we thus work in the vector space generated by Ci,Ci',Ci''. Thus we look for
T=f0Ci+f1Ci'+f2Ci'',    such that     Dz T=Ci.
This leads to a simple system whose only rational solution is
f0(z)=z,    f1(z)=1,    f2(z)=z,
or in other words

Ci(zdz=zCi(z)-sin(z).

2   Definite -finite summation and integration

Zeilberger's algorithms for definite summation and integration are based on creative telescoping. To simplify, we describe this method in the case of summation, i.e. we consider a -finite term tn when 1=Sn is a shift with respect to a variable n, and we want to compute
b
n=a
tn,
or more precisely an operator annihilating this sum.

If we can find two polynomials P and Q in the algebra such that P commutes with n and
P tn=(Sn-1)Q tn,     (2)
then interchanging P and  we get
P
b
n=1
tn=[Q tn]ab.
When moreover the bounds a and b are such that tn and all its a's are zero there (the so-called case of natural boundaries), then this computation has for consequence that the right-hand side telescopes, whence the name of the method.

In the hypergeometric case, Zeilberger's fast algorithm [13] to find P and Q relies on the observation that (2) is equivalent to P tn being Gosper-summable. He then shows that Gosper's algorithm can be extended to handle undeterminate coefficients in P and find conditions on these coefficients for the sum to be hypergeometric. The algorithm then increases the order of P (and consequently the number of indeterminate coefficients) till the extended Gosper algorithm finds a sum. Termination is guaranteed via Bernstein's theory of holonomic functions.

Chyzak's second algorithm is an extension of Zeilberger's algorithm to the more general context of -finite terms. Gosper's algorithm is replaced by the algorithm of the previous section, which is first extended to handle undeterminate coefficients and find conditions on these coefficients for an indefinite -1 to exist in the vector space. Termination is guaranteed only when Bernstein's theory can be invoked.

As an example, consider Neumann's addition theorem on Bessel functions:
J0(z)2+2
k=1
Jk(z)2=1.     (3)
In the algebra  A=Q(z,k) Dz,Sk, the sequence of functions Jk(z)2 satisfies the system


zDz2+(-2k+1)Dz-2Skz+2z,
zDzSk+zDz+(2k+2)Sk-2k,
z2Sk2-4(k+1)2Sk-2z(k+1)Dz+4k(k+1)-z2,
from which follows that Jk(z)2 is -finite and generates a vector space of dimension 3 with basis {Jk(z)2,Sk Jk(z)2,Dz Jk(z)2}. The output of the algorithm is
P=Dz,     Q=
k
z
+
1
2
Dz,
which means that
Dz
k=0
Jk(z)2+[Q Jk(z)2]
 
k=0
=0.
After some rewriting and considering the initial conditions, this is indeed equivalent to (3).

References

[1]
Abramov (S. A.). -- Rational solutions of linear differential and difference equations with polynomial coefficients. USSR Computational Mathematics and Mathematical Physics, vol. 29, n°11, 1989, pp. 1611--1620. -- Translation of the Zhurnal vychislitel'noi matematiki i matematichesckoi fiziki.

[2]
Abramov (S. A.). -- Rational solutions of linear difference and q-difference equations with polynomial coefficients. In Levelt (A.) (editor), Symbolic and algebraic computation. pp. 285--289. -- New York, 1995. Proceedings of ISSAC'95, Montreal.

[3]
Abramov (S. A.) and Kvashenko (K. Yu.). -- Fast algorithms to search for the rational solutions of linear differential equations with polynomial coefficients. In Watt (Stephen M.) (editor), Symbolic and algebraic computation. pp. 267--270. -- New York, 1991. Proceedings of ISSAC'91, Bonn.

[4]
Abramov (Sergei A.), Paule (Peter), and Petkovsek (Marko). -- q-hypergeometric solutions of q-difference equations, 1996.

[5]
Abramov (Sergei A.) and Petkovsek (Marko). -- Finding all q-hypergeometric solutions of q-difference equations. In Leclerc (B.) and Thibon (J. Y.) (editors), Formal power series and algebraic combinatorics. pp. 1--10. -- Universit de Marne-la-Valle, 1995. Proceedings SFCA'95.

[6]
Abramov (Sergei A.) and Zima (Eugene V.). -- A universal program to uncouple linear systems, 1996. Preprint.

[7]
Chyzak (Frdric). -- An extension of Zeilberger's fast algorithm to general holonomic functions. In Formal Power Series and Algebraic Combinatorics. pp. 172--183. -- Wien, Austria, 1997. Also available as INRIA Research Report 3195.

[8]
Chyzak (Frdric) and Salvy (Bruno). -- Non-commutative Elimination in Ore Algebras Proves Multivariate Holonomic Identities. -- Research Report n°2799, Institut National de Recherche en Informatique et en Automatique, February 1996.

[9]
Petkovsek (Marko). -- Hypergeometric solutions of linear recurrences with polynomial coefficients. Journal of Symbolic Computation, vol. 14, 1992, pp. 243--264.

[10]
Petkovsek (Marko) and Salvy (Bruno). -- Finding all hypergeometric solutions of linear differential equations. In Bronstein (Manuel) (editor), ISSAC'93. pp. 27--33. -- New York, July 1993.

[11]
Singer (Michael F.). -- Formal solutions of differential equations. Journal of Symbolic Computation, vol. 10, 1990, pp. 59--94.

[12]
Zeilberger (Doron). -- A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics, vol. 32, n°3, 1990, pp. 321--368.

[13]
Zeilberger (Doron). -- The method of creative telescoping. Journal of Symbolic Computation, vol. 11, 1991, pp. 195--204.

This document was translated from LATEX by HEVEA.