doc/info/zeilberger.texi.m4

   1 @menu
   2 * Introduction to zeilberger::
   3 * Functions and Variables for zeilberger::
   4 @end menu
   5
   6 @node Introduction to zeilberger, Functions and Variables for zeilberger, Package zeilberger, Package zeilberger
   7 @section Introduction to zeilberger
   8
   9 @code{zeilberger} is an implementation of Zeilberger's algorithm
  10 for definite hypergeometric summation, and also
  11 Gosper's algorithm for indefinite hypergeometric
  12 summation.
  13
  14 @code{zeilberger} makes use of the "filtering" optimization method developed by Axel Riese.
  15
  16 @code{zeilberger} was developed by Fabrizio Caruso.
  17
  18 @code{load ("zeilberger")} loads this package.
  19
  20 @opencatbox{Categories:}
  21 @category{Sums and products}
  22 @category{Share packages}
  23 @category{Package zeilberger}
  24 @closecatbox
  25
  26 @subsection The indefinite summation problem
  27
  28 @code{zeilberger} implements Gosper's algorithm for indefinite hypergeometric summation.
  29 Given a hypergeometric term @math{F_k} in @math{k} we want to find its hypergeometric
  30 anti-difference, that is, a hypergeometric term @math{f_k} such that
  31
  32 m4_displaymath(
  33 <<<F_k = f_{k+1} - f_k.>>>,
  34 <<<@math{F_k = f_(k+1) - f_k}.>>>)
  35
  36 @subsection The definite summation problem
  37
  38 @code{zeilberger} implements Zeilberger's algorithm for definite hypergeometric summation.
  39 Given a proper hypergeometric term (in @math{n} and @math{k})
  40 m4_math(<<<F_{n,k}>>>,<<<@math{F_(n,k)}>>>)
  41 and
  42 a positive integer @math{d} we want to find a @math{d}-th order linear
  43 recurrence with polynomial coefficients (in @math{n}) for
  44 m4_math(<<<F_{n,k}>>>,<<<@math{F_(n,k)}>>>)
  45 and
  46 a rational function @math{R} in @math{n} and @math{k} such that
  47
  48 m4_displaymath(
  49 <<<a_0 \, F_{n,k} + \ldots + a_d \, F_{n+d,k} = \Delta_K \left(R\left(n,k\right) F_{n,k}\right),>>>,
  50 <<<@math{a_0 F_(n,k) + ... + a_d F_(n+d,k) = Delta_k(R(n,k) F_(n,k))},>>>)
  51 where
  52 m4_math(\Delta_k, @math{Delta_k})
  53 is the @math{k}-forward difference
  54 operator, i.e.,
  55 m4_mathdot(
  56 <<<\Delta_k \left(t_k\right) \equiv t_{k+1} - t_k>>>,
  57 <<<@math{Delta_k(t_k) := t_(k+1) - t_k}>>>)
  58
  59 @subsection Verbosity levels
  60
  61 There are also verbose versions of the commands
  62 which are called by adding one of the following prefixes:
  63
  64 @table @code
  65 @item Summary
  66 Just a summary at the end is shown
  67 @item Verbose
  68 Some information in the intermediate steps
  69 @item VeryVerbose
  70 More information
  71 @item Extra
  72 Even more information including information on
  73 the linear system in Zeilberger's algorithm
  74 @end table
  75
  76 For example:@*
  77 @code{GosperVerbose}, @code{parGosperVeryVerbose},
  78 @code{ZeilbergerExtra}, @code{AntiDifferenceSummary}.
  79
  80
  81 @node Functions and Variables for zeilberger, , Introduction to zeilberger, Package zeilberger
  82 @section Functions and Variables for zeilberger
  83
  84 @anchor{AntiDifference}
  85 @deffn {Function} AntiDifference (@math{F_k}, @var{k})
  86
  87 Returns the hypergeometric anti-difference of @math{F_k}, if it exists.@*
  88 Otherwise @code{AntiDifference} returns @code{no_hyp_antidifference}.
  89
  90 @opencatbox{Categories:}
  91 @category{Package zeilberger}
  92 @closecatbox
  93
  94 @end deffn
  95
  96 @anchor{Gosper}
  97 @deffn {Function} Gosper (@math{F_k}, @var{k})
  98 Returns the rational certificate @math{R(k)} for @math{F_k}, that is,
  99 a rational function such
 100 that
 101 m4_mathcomma(<<<F_k = R\left(k+1\right) \, F_{k+1} - R\left(k\right) \, F_k>>>,<<<@math{F_k = R(k+1) F_(k+1) - R(k) F_k}>>>)
 102 if it exists.
 103 Otherwise, @code{Gosper} returns @code{no_hyp_sol}.
 104
 105 @opencatbox{Categories:}
 106 @category{Package zeilberger}
 107 @closecatbox
 108
 109 @end deffn
 110
 111 @anchor{GosperSum}
 112 @deffn {Function} GosperSum (@math{F_k}, @var{k}, @var{a}, @var{b})
 113
 114 Returns the summation of @math{F_k} from @math{@var{k} = @var{a}} to @math{@var{k} = @var{b}}
 115 if @math{F_k} has a hypergeometric anti-difference.
 116 Otherwise, @code{GosperSum} returns @code{nongosper_summable}.
 117
 118 Examples:
 119
 120 @c ===beg===
 121 @c load ("zeilberger")$
 122 @c GosperSum ((-1)^k*k / (4*k^2 - 1), k, 1, n);
 123 @c GosperSum (1 / (4*k^2 - 1), k, 1, n);
 124 @c GosperSum (x^k, k, 1, n);
 125 @c GosperSum ((-1)^k*a! / (k!*(a - k)!), k, 1, n);
 126 @c GosperSum (k*k!, k, 1, n);
 127 @c GosperSum ((k + 1)*k! / (k + 1)!, k, 1, n);
 128 @c GosperSum (1 / ((a - k)!*k!), k, 1, n);
 129 @c ===end===
 130 @example
 131 (%i1) load ("zeilberger")$
 132 @group
 133 (%i2) GosperSum ((-1)^k*k / (4*k^2 - 1), k, 1, n);
 134 Dependent equations eliminated:  (1)
 135                            3       n + 1
 136                       (n + -) (- 1)
 137                            2               1
 138 (%o2)               - ------------------ - -
 139                                   2        4
 140                       2 (4 (n + 1)  - 1)
 141 @end group
 142 @group
 143 (%i3) GosperSum (1 / (4*k^2 - 1), k, 1, n);
 144                                 3
 145                           - n - -
 146                                 2       1
 147 (%o3)                  -------------- + -
 148                                 2       2
 149                        4 (n + 1)  - 1
 150 @end group
 151 @group
 152 (%i4) GosperSum (x^k, k, 1, n);
 153                           n + 1
 154                          x          x
 155 (%o4)                    ------ - -----
 156                          x - 1    x - 1
 157 @end group
 158 @group
 159 (%i5) GosperSum ((-1)^k*a! / (k!*(a - k)!), k, 1, n);
 160                                 n + 1
 161                 a! (n + 1) (- 1)              a!
 162 (%o5)       - ------------------------- - ----------
 163               a (- n + a - 1)! (n + 1)!   a (a - 1)!
 164 @end group
 165 @group
 166 (%i6) GosperSum (k*k!, k, 1, n);
 167 Dependent equations eliminated:  (1)
 168 (%o6)                     (n + 1)! - 1
 169 @end group
 170 @group
 171 (%i7) GosperSum ((k + 1)*k! / (k + 1)!, k, 1, n);
 172                   (n + 1) (n + 2) (n + 1)!
 173 (%o7)             ------------------------ - 1
 174                           (n + 2)!
 175 @end group
 176 @group
 177 (%i8) GosperSum (1 / ((a - k)!*k!), k, 1, n);
 178 (%o8)                  NON_GOSPER_SUMMABLE
 179 @end group
 180 @end example
 181
 182 @opencatbox{Categories:}
 183 @category{Package zeilberger}
 184 @closecatbox
 185
 186 @end deffn
 187
 188 @iftex
 189 @anchor{parGosper}
 190 @deffn {Function} parGosper (@math{F_{n,k}}, @var{k}, @var{n}, @var{d})
 191
 192 Attempts to find a @var{d}-th order recurrence for
 193 @tex
 194 $F_{n,k}$.
 195 @end tex
 196
 197 The algorithm yields a sequence @math{[s_1, s_2, ..., s_m]} of solutions.
 198 Each solution has the form
 199
 200 @tex
 201 $$\left[R\left(n, k\right), \left[a_0, a_1, \ldots, a_d\right]\right].$$
 202 @end tex
 203
 204 @code{parGosper} returns @code{[]} if it fails to find a recurrence.
 205
 206 @opencatbox{Categories:}
 207 @category{Package zeilberger}
 208 @closecatbox
 209
 210 @end deffn
 211 @end iftex
 212
 213 @ifnottex
 214 @anchor{parGosper}
 215 @deffn {Function} parGosper (@math{F_(n,k)}, @var{k}, @var{n}, @var{d})
 216
 217 Attempts to find a @var{d}-th order recurrence for @math{F_(n,k)}.
 218
 219 The algorithm yields a sequence @math{[s_1, s_2, ..., s_m]} of solutions.
 220 Each solution has the form
 221
 222 @math{[R(n, k), [a_0, a_1, ..., a_d]].}
 223
 224 @code{parGosper} returns @code{[]} if it fails to find a recurrence.
 225
 226 @opencatbox{Categories:}
 227 @category{Package zeilberger}
 228 @closecatbox
 229
 230 @end deffn
 231 @end ifnottex
 232
 233 @iftex
 234 @anchor{Zeilberger}
 235 @deffn {Function} Zeilberger (@math{F_{n,k}}, @var{k}, @var{n})
 236
 237 Attempts to compute the indefinite hypergeometric summation of
 238 @tex
 239 $F_{n,k}$.
 240 @end tex
 241
 242 @code{Zeilberger} first invokes @code{Gosper}, and if that fails to find a solution, then invokes
 243 @code{parGosper} with order 1, 2, 3, ..., up to @code{MAX_ORD}.
 244 If Zeilberger finds a solution before reaching @code{MAX_ORD},
 245 it stops and returns the solution.
 246
 247 The algorithms yields a sequence @math{[s_1, s_2, ..., s_m]} of solutions.
 248 Each solution has the form
 249
 250 @tex
 251 $$\left[R\left(n, k\right), \left[a_0, a_1, \ldots, a_d\right]\right].$$
 252 @end tex
 253
 254 @code{Zeilberger} returns @code{[]} if it fails to find a solution.
 255
 256 @code{Zeilberger} invokes @code{Gosper} only if @code{Gosper_in_Zeilberger} is @code{true}.
 257
 258 @opencatbox{Categories:}
 259 @category{Package zeilberger}
 260 @closecatbox
 261
 262 @end deffn
 263 @end iftex
 264
 265 @ifnottex
 266 @anchor{Zeilberger}
 267 @deffn {Function} Zeilberger (@math{F_(n,k)}, @var{k}, @var{n})
 268
 269 Attempts to compute the indefinite hypergeometric summation of @math{F_(n,k)}.
 270
 271 @code{Zeilberger} first invokes @code{Gosper}, and if that fails to find a solution, then invokes
 272 @code{parGosper} with order 1, 2, 3, ..., up to @code{MAX_ORD}.
 273 If Zeilberger finds a solution before reaching @code{MAX_ORD},
 274 it stops and returns the solution.
 275
 276 The algorithms yields a sequence @math{[s_1, s_2, ..., s_m]} of solutions.
 277 Each solution has the form
 278
 279 @math{[R(n,k), [a_0, a_1, ..., a_d]].}
 280
 281 @code{Zeilberger} returns @code{[]} if it fails to find a solution.
 282
 283 @code{Zeilberger} invokes @code{Gosper} only if @code{Gosper_in_Zeilberger} is @code{true}.
 284
 285 @opencatbox{Categories:}
 286 @category{Package zeilberger}
 287 @closecatbox
 288
 289 @end deffn
 290 @end ifnottex
 291
 292
 293 @node General global variables, Variables related to the modular test, Functions and Variables for zeilberger
 294 @section General global variables
 295
 296 @anchor{MAX_ORD}
 297 @defvr {Global variable} MAX_ORD
 298 Default value: 5
 299
 300 @code{MAX_ORD} is the maximum recurrence order attempted by @code{Zeilberger}.
 301
 302 @opencatbox{Categories:}
 303 @category{Package zeilberger}
 304 @closecatbox
 305
 306 @end defvr
 307
 308 @anchor{simplified_output}
 309 @defvr {Global variable} simplified_output
 310 Default value: @code{false}
 311
 312 When @code{simplified_output} is @code{true},
 313 functions in the @code{zeilberger} package attempt
 314 further simplification of the solution.
 315
 316 @opencatbox{Categories:}
 317 @category{Package zeilberger}
 318 @closecatbox
 319
 320 @end defvr
 321
 322 @anchor{linear_solver}
 323 @defvr {Global variable} linear_solver
 324 Default value: @code{linsolve}
 325
 326 @code{linear_solver} names the solver which is used to solve the system
 327 of equations in Zeilberger's algorithm.
 328
 329 @opencatbox{Categories:}
 330 @category{Package zeilberger}
 331 @closecatbox
 332
 333 @end defvr
 334
 335 @anchor{warnings}
 336 @defvr {Global variable} warnings
 337 Default value: @code{true}
 338
 339 When @code{warnings} is @code{true},
 340 functions in the @code{zeilberger} package print
 341 warning messages during execution.
 342
 343 @opencatbox{Categories:}
 344 @category{Package zeilberger}
 345 @closecatbox
 346
 347 @end defvr
 348
 349 @anchor{Gosper_in_Zeilberger}
 350 @defvr {Global variable} Gosper_in_Zeilberger
 351 Default value: @code{true}
 352
 353 When @code{Gosper_in_Zeilberger} is @code{true},
 354 the @code{Zeilberger} function calls @code{Gosper} before calling @code{parGosper}.
 355 Otherwise, @code{Zeilberger} goes immediately to @code{parGosper}.
 356
 357 @opencatbox{Categories:}
 358 @category{Package zeilberger}
 359 @closecatbox
 360
 361 @end defvr
 362
 363 @anchor{trivial_solutions}
 364 @defvr {Global variable} trivial_solutions
 365 Default value: @code{true}
 366
 367 When @code{trivial_solutions} is @code{true},
 368 @code{Zeilberger} returns solutions
 369 which have certificate equal to zero, or all coefficients equal to zero.
 370
 371 @opencatbox{Categories:}
 372 @category{Package zeilberger}
 373 @closecatbox
 374
 375 @end defvr
 376
 377 @node Variables related to the modular test, , General global variables
 378 @section Variables related to the modular test
 379
 380 @anchor{mod_test}
 381 @defvr {Global variable} mod_test
 382 Default value: @code{false}
 383
 384 When @code{mod_test} is @code{true},
 385 @code{parGosper} executes a
 386 modular test for discarding systems with no solutions.
 387
 388 @opencatbox{Categories:}
 389 @category{Package zeilberger}
 390 @closecatbox
 391
 392 @end defvr
 393
 394 @anchor{modular_linear_solver}
 395 @defvr {Global variable} modular_linear_solver
 396 Default value: @code{linsolve}
 397
 398 @code{modular_linear_solver} names the linear solver used by the modular test in @code{parGosper}.
 399
 400 @opencatbox{Categories:}
 401 @category{Package zeilberger}
 402 @closecatbox
 403
 404 @end defvr
 405
 406 @anchor{ev_point}
 407 @defvr {Global variable} ev_point
 408 Default value: @code{big_primes[10]}
 409
 410 @code{ev_point} is the value at which the variable @var{n} is evaluated
 411 when executing the modular test in @code{parGosper}.
 412
 413 @opencatbox{Categories:}
 414 @category{Package zeilberger}
 415 @closecatbox
 416
 417 @end defvr
 418
 419 @anchor{mod_big_prime}
 420 @defvr {Global variable} mod_big_prime
 421 Default value: @code{big_primes[1]}
 422
 423 @code{mod_big_prime} is the modulus used by the modular test in @code{parGosper}.
 424
 425 @opencatbox{Categories:}
 426 @category{Package zeilberger}
 427 @closecatbox
 428
 429 @end defvr
 430
 431 @anchor{mod_threshold}
 432 @defvr {Global variable} mod_threshold
 433 Default value: 4
 434
 435 @code{mod_threshold} is the
 436 greatest order for which the modular test in @code{parGosper} is attempted.
 437
 438 @opencatbox{Categories:}
 439 @category{Package zeilberger}
 440 @closecatbox
 441
 442 @end defvr
 443