1
--------------------------------------------------------------------------
2
ZEILBERGER (Version 4.0)
4
--------------------------------------------------------------------------
5
Implementation Zeilberger's algorithm for
6
definite hypergeometric summation and of
7
Gosper's algorithm for indefinite hypergeometric
8
summation in the Maxima computer algebra system.
10
The package also uses Axel Riese's optimization ("Filtering").
12
This version of the package has been tested with 5.9.3 of Maxima.
13
--------------------------------------------------------------------------
15
This package was developed by Fabrizio Caruso
19
J.Kepler Universitaet (Austria)
22
at Dipartimento di Matematica "L. Tonelli",
23
Università di Pisa (Italy)
27
Université de Rennes 1.
29
[Version 4.0] (June 2006)
30
at Dipartimento di Matematica "L. Tonelli",
31
Università di Pisa (Italy)
33
--------------------------------------------------------------------------
34
DESCRIPTION OF THE PROBLEMS
35
--------------------------------------------------------------------------
37
THE INDEFINITE PROBLEM
39
The package provides an implementation of Gosper's algorithm
40
for indefinite hypergeometric summation:
42
Given a hypergeometric term F_k in k we want to find its hypergeometric
43
anti-difference, i.e. a hypergeometric term f_k such that:
48
--------------------------------------------------------------------------
52
The package provides an implementation of Zeilberger's algorithm
53
for definite hypergeometric summation:
55
Given a proper hypergeometric term (in n and k) F_(n,k) and a
56
positive integer d we want to find a d-th order linear
57
recurrence with polynomial coefficients (in n) for F_(n,k)
58
and a rational function R in n and k such that:
60
a_0 F_(n,k) + ... + a_d F_(n+d),k = Delta_K(R(n,k) F_(n,k)),
64
Delta_k is the k-forward difference operator, i.e.,
65
Delta_k(t_k) := t_(k+1) - t_k.
67
--------------------------------------------------------------------------
69
--------------------------------------------------------------------------
71
In order to load the package
72
either load all the ".mac" files manually or
73
first edit the line of "zeilberger.mac" defining
74
the directory ("dir") containing the
75
package files, then load "zeilberger.mac"
76
which will take care of loading and evalutating
77
all the necessary files.
79
--------------------------------------------------------------------------
81
--------------------------------------------------------------------------
83
- AntiDifference(F_k,k)
85
AntiDifference either finds the hypergeometric anti-difference
86
of F_k if it exists, or if it does not exist, it outputs:
89
If the input is not hypergeometric it outputs:
91
--------------------------------------------------------------------------
95
Gosper either finds the rational certificate R(k) for F_k, i.e.
96
a rational function such that:
98
F_k = R(k+1) F_(k+1) - R(k) F_k
100
if it exists, or if it does not exist, it outputs:
103
If the input is not hypergeometric it outputs:
105
---------------------------------------------------------------------------
107
- GosperSum(F_k,k,a,b)
109
GosperSum either sums F_k over the interval [a,b] if
110
F_k has a hypergeometric anti-difference, or
111
if it does not have it, it outpus:
114
If the input is not hypergeometric it outputs:
116
---------------------------------------------------------------------------
118
- parGosper(F_n,k , k , n , d)
120
parGosper tries to find a d-th order recurrence.
121
If it finds one it outputs it in the form (*).
122
If it finds none it outputs the empty solution [].
124
If the input is not proper hypergeometric in k and n it outputs:
125
[NON_PROPER_HYPERGEOMETRIC]
126
---------------------------------------------------------------------------
128
- Zeilberger(F_n,k , k , n)
130
Zeilberger starts by invoking "Gosper" and if it fails
131
tries "parGosper" with order 1 and tries up to
132
the order given by the variable MAX_ORD.
133
If Zeilberger finds a solution before reaching MAX_ORD
134
it stops and yields the solution in the form (*) otherwise
135
it tries a higher oder.
136
If no solution is found it outputs [].
138
If the input is not proper hypergeometric in k and n it outputs:
139
[NON_PROPER_HYPERGEOMETRIC]
141
Remark: "Gosper" is skipped if the setting
142
GOSPER_IN_ZEILBERGER is set to FALSE.
143
--------------------------------------------------------------------------
146
FORM OF THE OUTPUT OF "parGosper" AND "ZEILBERGER"
148
The algorithms yields a sequence:
149
[s_1,s_2, ..., s_m] of solutions.
151
Each solution has the following form:
153
[R(n,k), [a_0, a_1, ..., a_d]]
155
---------------------------------------------
156
AUTHOMATIC PROVERS OF RECURRENCES/IDENTITIES
159
Starting with version 4.0, I have included some routines
160
that produce formal simple human-readable out of the
161
output of "Gosper", "parGosper" and "Zeilberger".
162
This is very simple becase the output contains a
163
so-called "rational certificate"
165
Level of details in the proofs and test:
166
The level of details of the proves depend on the
167
variables "gs_prove_detail" and "zb_prove_detail",
168
whose values can range in the set:
169
{PROOF_SILENT,PROOF_LOW,PROOF_MEDIUM,PROOF_HIGH}.
172
- gs_prove(F_k,k,cert)
174
It produces a proof for the output "cert" of "Gosper(F_k,k)",
175
with level of details depending on the value of "gs_prove_detail".
177
---------------------------------------------------------------------------
179
- zb_meaning(F_n,k,k,n,zb_cert,zb_rec)
181
It spells out the meaning of one of the elements
182
in the output of "parGosper" or "Zeilberger", i.e.
183
something of the form "[zb_cert,zb_rec]"
185
---------------------------------------------------------------------------
187
- zb_prove(F_n,k,k,n,zb_out)
189
It writes a proof and DOES A TEST for all the solutions
190
contained in "zb_out", with level of details depending on the
191
value of "zb_prove_detail".
192
"zb_out" must have the same for as the output of
193
"parGosper" and "Zeilberger".
197
%i30) res : parGosper(binomial(n,k),k,n,1);
199
(%o30) [[---------, [2, - 1]]]
201
(%i31) zb_prove_detail:PROOF_HIGH;
203
(%i32) zb_prove(binomial(n,k),k,n,res);
204
The result contains one recurrence for binomial(n, k) :
206
2 binomial(n, k) - binomial(n + 1, k) =
207
(k + 1) binomial(n, k + 1) k binomial(n, k)
208
-------------------------- - ---------------- ;
211
which we can prove by dividing both members of the equality by binomial(n, k)
212
and checking the resulting equality between rational functions.
213
Namely it is equivalent to test the equality between:
215
2 - --------- and 1 - ---------
221
---------------------------------------------------------------------------
225
It does a test for a list containing
226
possible inputs for "parGosper", i.e.
227
each element of the list is a quadruple
228
of the form: "[F_n,k,k,n,order]".
229
The level of details shown depend on "zb_prove_detail".
232
The new version of the package includes some tests for "zb_test"
233
that contain examples for both "Gosper" and "parGosper" most of which
234
come from real mathematical problems.
235
For example, if you have time
238
or if you have less time
239
"zb_test(EASY_TEST)".
242
--------------------------------------------------------------------------
244
--------------------------------------------------------------------------
246
The package provides many settings set by the
247
following variables whose default values are defined
248
in the file "settings.mac".
250
--------------------------------------------------------------------------
254
maximum order used by Zeilberger [5]
257
further simplification of the solution [FALSE]
260
which solver is used to solve the system
261
in Zeilberger's algorithm [linsolve]
264
warnings during execution [TRUE]
266
gosper_in_Zeilberger :
267
"Zeilberger" tries "Gosper" [TRUE]
270
Solutions by Zeilberger's algorithm
271
involving zero certificate or all identically zero coefficients
272
are also output [TRUE]
274
--------------------------------------------------------------------------
275
Settings related to the provers and test routines
277
The values of the details range in
278
{PROOF_SILENT,PROOF_LOW,PROOF_MEDIUN,PROOF_HIGH}.
280
gs_prove_detail : [PROOF_MEDIUM]
281
Level of details in "gs_prove"
283
zb_prove_detail : [PROOF_LOW]
284
Level of details in "zb_prove" and "zb_test"
286
--------------------------------------------------------------------------
287
Settings related to the modular test
290
modular test for discarting systems with no solutions
291
in "parGosper" and "Zeilberger" [FALSE]
293
modular_linear_solver :
294
linear solver used by the modular test [linsolve]
297
evaluation point at which the variable "n" is evaluated
298
when performing the modular test [BIG_PRIMES[10]]
301
modulo used by the modular test [BIG_PRIMES[1]]
304
threshold for the order for which a modular test
307
--------------------------------------------------------------------------
309
--------------------------------------------------------------------------
311
There are also verbose versions of the commands
312
which are called by adding one of the following prefixes:
314
"Summary" : just a summary at the end is shown
315
"Verbose" : some information in the intermidiate steps
316
"VeryVerbose" : more information
317
"Extra" : even more information including information on
318
the linear system in Zeilberger's algorithm
321
For example: "GosperVerbose", "parGosperVeryVerbose",
322
"ZeilbergerExtra", "AntiDifferenceSummary".
added
removed
share/contrib/Zeilberger/readme.txt
