share/contrib/Zeilberger/readme.txt

   1 --------------------------------------------------------------------------
   2 ZEILBERGER (Version 4.0)
   3 by Fabrizio Caruso
   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.
   9
  10 The package also uses Axel Riese's optimization ("Filtering").
  11
  12 This version of the package has been tested with 5.9.3 of Maxima.
  13 --------------------------------------------------------------------------
  14
  15 This package was developed by Fabrizio Caruso
  16
  17 [Version 1.0] (~1999)
  18 at RISC-Linz,
  19 J.Kepler Universitaet (Austria)
  20
  21 [Version 2.0] (2004)
  22 at Dipartimento di Matematica "L. Tonelli",
  23 Università di Pisa (Italy)
  24
  25 [Version 3.0] (2005)
  26 at IRMAR,
  27 Université de Rennes 1.
  28
  29 [Version 4.0] (June 2006)
  30 at  Dipartimento di Matematica "L. Tonelli",
  31 Università di Pisa (Italy)
  32
  33 --------------------------------------------------------------------------
  34 DESCRIPTION OF THE PROBLEMS
  35 --------------------------------------------------------------------------
  36
  37 THE INDEFINITE PROBLEM
  38
  39 The package provides an implementation of Gosper's algorithm
  40 for indefinite hypergeometric summation:
  41
  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:
  44
  45 F_k = f_(k+1) - f_k.
  46
  47
  48 --------------------------------------------------------------------------
  49
  50 THE DEFINITE PROBLEM
  51
  52 The package provides an implementation of Zeilberger's algorithm
  53 for definite hypergeometric summation:
  54
  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:
  59
  60 a_0 F_(n,k) + ... + a_d F_(n+d),k = Delta_K(R(n,k) F_(n,k)),
  61
  62 where
  63
  64 Delta_k is the k-forward difference operator, i.e.,
  65 Delta_k(t_k) := t_(k+1) - t_k.
  66
  67 --------------------------------------------------------------------------
  68 LOADING
  69 --------------------------------------------------------------------------
  70
  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.
  78
  79 --------------------------------------------------------------------------
  80 INSTRUCTIONS
  81 --------------------------------------------------------------------------
  82
  83 - AntiDifference(F_k,k)
  84
  85 AntiDifference either finds the hypergeometric anti-difference
  86 of F_k if it exists, or if it does not exist, it outputs:
  87 NO_HYP_ANTIDIFFERENCE
  88
  89 If the input is not hypergeometric it outputs:
  90 NON_HYPERGEOMETRIC
  91 --------------------------------------------------------------------------
  92
  93 - Gosper(F_k,k)
  94
  95 Gosper either finds the rational certificate R(k) for F_k, i.e.
  96 a rational function such that:
  97
  98 F_k = R(k+1) F_(k+1) - R(k) F_k
  99
 100 if it exists, or if it does not exist, it outputs:
 101 NO_HYP_SOL
 102
 103 If the input is not hypergeometric it outputs:
 104 NON_HYPERGEOMETRIC
 105 ---------------------------------------------------------------------------
 106
 107 - GosperSum(F_k,k,a,b)
 108
 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:
 112 NONGOSPER_SUMMABLE
 113
 114 If the input is not hypergeometric it outputs:
 115 NON_HYPERGEOMETRIC
 116 ---------------------------------------------------------------------------
 117
 118 - parGosper(F_n,k,n,d)
 119
 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 [].
 123
 124 If the input is not proper hypergeometric in k and n it outputs:
 125 [NON_PROPER_HYPERGEOMETRIC]
 126 ---------------------------------------------------------------------------
 127
 128 - Zeilberger(F_n,k,n)
 129
 130 - Zeilberger(F_n,k,n,d) [same as "parGosper(F_n,k,n,d)"]
 131
 132 Zeilberger starts by invoking "Gosper" and if it fails
 133 tries "parGosper" with order 1 and tries up to
 134 the order given by the variable MAX_ORD.
 135 If Zeilberger finds a solution before reaching MAX_ORD
 136 it stops and yields the solution in the form (*) otherwise
 137 it tries a higher oder.
 138 If no solution is found it outputs [].
 139
 140 If the input is not proper hypergeometric in k and n it outputs:
 141 [NON_PROPER_HYPERGEOMETRIC]
 142
 143 Remark: "Gosper" is skipped if the setting
 144 GOSPER_IN_ZEILBERGER is set to FALSE.
 145 --------------------------------------------------------------------------
 146
 147 (*)
 148 FORM OF THE OUTPUT OF "parGosper" AND "ZEILBERGER"
 149
 150 The algorithms yields a sequence:
 151 [s_1,s_2, ..., s_m] of solutions.
 152
 153 Each solution has the following form:
 154
 155 [R(n,k), [a_0, a_1, ..., a_d]]
 156
 157 ---------------------------------------------
 158 AUTHOMATIC PROVERS OF RECURRENCES/IDENTITIES
 159
 160
 161 Starting with version 4.0, I have included some routines
 162 that produce formal simple human-readable out of the
 163 output of "Gosper", "parGosper" and "Zeilberger".
 164 This is very simple becase the output contains a
 165 so-called "rational certificate"
 166
 167 Level of details in the proofs and test:
 168 The level of details of the proves depend on the
 169 variables "gs_prove_detail" and "zb_prove_detail",
 170 whose values can range in the set:
 171 {PROOF_SILENT,PROOF_LOW,PROOF_MEDIUM,PROOF_HIGH}.
 172
 173
 174 - gs_prove(F_k,k,cert)
 175
 176 It produces a proof for the output "cert" of "Gosper(F_k,k)",
 177 with level of details depending on the value of "gs_prove_detail".
 178
 179 ---------------------------------------------------------------------------
 180
 181 - zb_meaning(F_n,k,n,zb_cert,zb_rec)
 182
 183 It spells out the meaning of one of the elements
 184 in the output of "parGosper" or "Zeilberger", i.e.
 185 something of the form "[zb_cert,zb_rec]"
 186
 187 ---------------------------------------------------------------------------
 188
 189 - zb_prove(F_n,k,n,zb_out)
 190
 191 - zb_prove(F_n,k,n) [zb_out is computed by "Zeilberger"]
 192
 193 It writes a proof and DOES A TEST for all the solutions
 194 contained in "zb_out", with level of details depending on the
 195 value of "zb_prove_detail".
 196 "zb_out" must have the same for as the output of
 197 "parGosper" and "Zeilberger".
 198
 199 For example:
 200 "
 201 %i30) res : parGosper(binomial(n,k),k,n,1);
 202                                   k
 203 (%o30)                      [[---------, [2, - 1]]]
 204                               n - k + 1
 205 (%i31) zb_prove_detail:PROOF_HIGH;
 206 (%o31)                                 3
 207 (%i32) zb_prove(binomial(n,k),k,n,res);
 208 The result contains one recurrence for  binomial(n, k) :
 209
 210 2 binomial(n, k) - binomial(n + 1, k)  =
 211 (k + 1) binomial(n, k + 1)   k binomial(n, k)
 212 -------------------------- - ---------------- ;
 213           n - k                 n - k + 1
 214
 215 which we can prove by dividing both members of the equality by  binomial(n, k)
 216 and checking the resulting equality between rational functions.
 217 Namely it is equivalent to test the equality between:
 218       n + 1                 k
 219 2 - ---------  and  1 - ---------
 220     n - k + 1           n - k + 1
 221
 222 (%o32)                               true
 223 "
 224
 225 ---------------------------------------------------------------------------
 226
 227 - zb_test(zb_in_lst)
 228
 229 It does a test for a list containing
 230 possible inputs for "parGosper", i.e.
 231 each element of the list is a quadruple
 232 of the form: "[F_n,k,k,n,order]".
 233 The level of details shown depend on "zb_prove_detail".
 234
 235 Remark:
 236 The new version of the package includes some tests for "zb_test"
 237 that contain examples for both "Gosper" and "parGosper" most of which
 238 come from real mathematical problems.
 239 For example, if you have time
 240 try
 241 "zb_test(FULL_TEST)"
 242 or if you have less time
 243 "zb_test(EASY_TEST)".
 244
 245
 246 --------------------------------------------------------------------------
 247 SETTINGS
 248 --------------------------------------------------------------------------
 249
 250 The package provides many settings set by the
 251 following variables whose default values are defined
 252 in the file "settings.mac".
 253
 254 --------------------------------------------------------------------------
 255 General settings
 256
 257 max_ord :
 258 maximum order used by Zeilberger [5]
 259
 260 simplified_output :
 261 further simplification of the solution [FALSE]
 262
 263 linear_solver :
 264 which solver is used to solve the system
 265 in Zeilberger's algorithm [linsolve]
 266
 267 warnings :
 268 warnings during execution [TRUE]
 269
 270 gosper_in_Zeilberger :
 271 "Zeilberger" tries "Gosper" [TRUE]
 272
 273 trivial_solutions :
 274 Solutions by Zeilberger's algorithm
 275 involving zero certificate or all identically zero coefficients
 276 are also output [TRUE]
 277
 278 --------------------------------------------------------------------------
 279 Settings related to the provers and test routines
 280
 281 The values of the details range in
 282 {PROOF_SILENT,PROOF_LOW,PROOF_MEDIUN,PROOF_HIGH}.
 283
 284 gs_prove_detail : [PROOF_MEDIUM]
 285 Level of details in "gs_prove"
 286
 287 zb_prove_detail : [PROOF_LOW]
 288 Level of details in "zb_prove" and "zb_test"
 289
 290 --------------------------------------------------------------------------
 291 Settings related to the modular test
 292
 293 mod_test :
 294 modular test for discarting systems with no solutions
 295 in "parGosper" and "Zeilberger" [FALSE]
 296
 297 modular_linear_solver :
 298 linear solver used by the modular test [linsolve]
 299
 300 ev_point :
 301 evaluation point at which the variable "n" is evaluated
 302 when performing the modular test [BIG_PRIMES[10]]
 303
 304 mod_big_prime :
 305 modulo used by the modular test [BIG_PRIMES[1]]
 306
 307 mod_threshold :
 308 threshold for the order for which a modular test
 309 can be used [4]
 310
 311 --------------------------------------------------------------------------
 312 VERBOSITY LEVELS
 313 --------------------------------------------------------------------------
 314
 315 There are also verbose versions of the commands
 316 which are called by adding one of the following prefixes:
 317
 318 "Summary" : just a summary at the end is shown
 319 "Verbose" : some information in the intermidiate steps
 320 "VeryVerbose" : more information
 321 "Extra" : even more information including information on
 322 the linear system in Zeilberger's algorithm
 323
 324
 325 For example: "GosperVerbose", "parGosperVeryVerbose",
 326 "ZeilbergerExtra", "AntiDifferenceSummary".
 327