New Algorithms for Definite Summation and Integration

New Algorithms for Definite Summation and Integration

Frédéric 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:

k=1

æ
è

ö
ø

H_k

æ
è

n+1

m+1

ö
ø

æ
ç
ç
è

H_n+1-

m+1

ö
÷
÷
ø

k=0

æ
ç
ç
è

j=0

æ
è

ö
ø

ö
÷
÷
ø

=n2^3n-1+2³ⁿ-3n2^n-2

æ
è

ö
ø

n=0

H_n(x)H_n(y)

uⁿ

exp

æ
ç
ç
è

4u(xy-u(x²+y²))

1-4u²

ö
÷
÷
ø

(1-u²)^1/2

ó
õ

-1

e^-pxT_n(x)

(1-x²)^1/2

=(-1)ⁿp I_n(p),

ó
õ

+¥

-px²

J_n(bx)I_n(cx)dx

exp

æ
ç
ç
è

c²-b²

ö
÷
÷
ø

J_n

æ
ç
ç
è

ö
÷
÷
ø

ó
õ

+¥

xJ₁(ax)I₁(ax)Y₀(x)K₀(x)dx

ln(1-a⁴)

2p a²

n=0

r_n(a,b)zⁿ

(q;q)_n

(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 ¶₁,...,¶_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=¶

a₁

···¶

a_r

· t, a_iÎN, (1)

span a finite-dimensional vector space over K.

Examples are:

exp(z²) for D_z (derivation) over Q(z) (with dimension 1);
the binomial coefficient (

n

k
) for S_n and S_k (shifts) over Q(n,k) (with dimension 1);
the Bessel J_n(z) functions, the Tchebychev polynomials T_n(z), the Legendre polynomials P_n(z) for S_n (shift) and D_z (derivation) over Q(n,z) (with dimension 2);
the product of Bessel functions J₁(ax)I₁(ax)Y₀(x)K₀(x) for D_a and D_x (derivations) over Q(a,x) (with dimension 16).

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 b₁,...,b_N 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(¶₁,...,¶_r)· X=B,

where P is a polynomial in Ká¶₁,...,¶_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=f₁ b₁+...+f_Nb_N

with undeterminate coefficients f_i's in K. The left-hand side of the equation is then expressed in the basis of the b_i's. Identifying coefficients then yields a system of linear equations satisfied by the f_i'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=S_n-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,

(z)=

ó
õ

cos(t)

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)á D_zñ, we thus work in the vector space generated by Ci,Ci',Ci''. Thus we look for

T=f₀Ci+f₁Ci'+f₂Ci'', such that D_z· T=Ci.

This leads to a simple system whose only rational solution is

f₀(z)=z, f₁(z)=1, f₂(z)=z,

or in other words

ó
õCi(z) dz=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 t_n when ¶₁=S_n is a shift with respect to a variable n, and we want to compute

n=a

t_n,

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· t_n=(S_n-1)Q· t_n, (2)

then interchanging P and å we get

P·

n=1

t_n=[Q· t_n]_a^b.

When moreover the bounds a and b are such that t_n 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· t_n 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:

J₀(z)²+2

k=1

J_k(z)²=1. (3)

In the algebra A=Q(z,k)á D_z,S_kñ, the sequence of functions J_k(z)² satisfies the system

ì
í
î

zD_z²+(-2k+1)D_z-2S_kz+2z,

zD_zS_k+zD_z+(2k+2)S_k-2k,

z²S_k²-4(k+1)²S_k-2z(k+1)D_z+4k(k+1)-z²,

from which follows that J_k(z)² is ¶-finite and generates a vector space of dimension 3 with basis {J_k(z)²,S_k· J_k(z)²,D_z· J_k(z)²}. The output of the algorithm is

P=D_z, Q=

D_z,

which means that

D_z·

k=0

J_k(z)²+[Q·

J_k(z)²]

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-Vallée, 1995. Proceedings SFCA'95.
[6]: Abramov (Sergei A.) and Zima (Eugene V.). -- A universal program to uncouple linear systems, 1996. Preprint.
[7]: Chyzak (Frédéric). -- 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 (Frédéric) 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 L^AT_EX by H^EV^EA.