doc/info/zeilberger.texi

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