share/contrib/Zeilberger/readme.txt

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