doc/info/celine.texi

   1 @menu
   2 * Introduction to celine::
   3 @end menu
   4
   5 @node Introduction to celine
   6 @section Introduction to celine
   7
   8 Maxima implementation of Sister Celine's method. Barton Willis wrote this code. It is released under the @uref{https://creativecommons.org/about/cc0,Creative Commons CC0 license}.
   9
  10 Celine's method is described in Sections 4.1--4.4 of the book "A=B", by Marko Petkovsek, Herbert S. Wilf, and Doron Zeilberger.
  11 This book is available at @uref{http://www.math.rutgers.edu/~zeilberg/AeqB.pdf}
  12
  13 Let f = F(n,k). The function celine returns a set of recursion relations for F of the form
  14
  15     p_0(n) * fff(n,k) + p_1(n) * fff(n+1,k) + ... +  p_p(n) * fff(n+p,k+q),
  16
  17 where p_0 through p_p are polynomials. If Maxima is unable to determine that sum(sum(a(i,j) * F(n+i,k+j),i,0,p),j,0,q) / F(n,k)
  18 is a rational function of n and k, celine returns the empty set. When f involves parameters (variables other than n or k), celine
  19 might make assumptions about these parameters. Using 'put' with a key of 'proviso,' Maxima saves these assumptions on the input
  20 label.
  21
  22 To use this function, first load the package integer_sequence, opsubst, and to_poly_solve.
  23
  24 Examples:
  25
  26 @c ===beg===
  27 @c load("integer_sequence")$
  28 @c load("opsubst")$
  29 @c load("to_poly_solve")$
  30 @c load("celine")$
  31 @c celine(n!,n,k,1,0);
  32 @c ===end===
  33 @example
  34 (%i1) load("integer_sequence")$
  35 (%i2) load("opsubst")$
  36 (%i3) load("to_poly_solve")$
  37 (%i4) load("celine")$
  38 @group
  39 (%i5) celine(n!,n,k,1,0);
  40 (%o5)       @{fff(n + 1, k) - n fff(n, k) - fff(n, k)@}
  41 @end group
  42 @end example
  43
  44 Verification that this result is correct:
  45 @c ===beg===
  46 @c load("integer_sequence")$
  47 @c load("opsubst")$
  48 @c load("to_poly_solve")$
  49 @c load("celine")$
  50 @c g1:{fff(n+1,k)-n*fff(n,k)-fff(n,k)};
  51 @c ratsimp(minfactorial(first(g1))),fff(n,k) := n!;
  52 @c ===end===
  53 @example
  54 (%i1) load("integer_sequence")$
  55 (%i2) load("opsubst")$
  56 (%i3) load("to_poly_solve")$
  57 (%i4) load("celine")$
  58 @group
  59 (%i5) g1:@{fff(n+1,k)-n*fff(n,k)-fff(n,k)@};
  60 (%o5)       @{fff(n + 1, k) - n fff(n, k) - fff(n, k)@}
  61 @end group
  62 @group
  63 (%i6) ratsimp(minfactorial(first(g1))),fff(n,k) := n!;
  64 (%o6)                           0
  65 @end group
  66 @end example
  67
  68 An example with parameters including the test that the result of the example
  69 is correct:
  70 @c ===beg===
  71 @c load("integer_sequence")$
  72 @c load("opsubst")$
  73 @c load("to_poly_solve")$
  74 @c load("celine")$
  75 @c e : pochhammer(a,k) * pochhammer(-k,n) / (pochhammer(b,k));
  76 @c recur : celine(e,n,k,2,1);
  77 @c /* Test this result for correctness */
  78 @c first(%), fff(n,k) := ''(e)$
  79 @c makefact(makegamma(%))$
  80 @c minfactorial(factor(minfactorial(factor(%))));
  81 @c ===end===
  82 @example
  83 (%i1) load("integer_sequence")$
  84 (%i2) load("opsubst")$
  85 (%i3) load("to_poly_solve")$
  86 (%i4) load("celine")$
  87 @group
  88 (%i5) e : pochhammer(a,k) * pochhammer(-k,n) / (pochhammer(b,k));
  89                            (a)  (- k)
  90                               k      n
  91 (%o5)                      -----------
  92                               (b)
  93                                  k
  94 @end group
  95 @group
  96 (%i6) recur : celine(e,n,k,2,1);
  97 (%o6) @{fff(n + 2, k + 1) - fff(n + 2, k) - b fff(n + 1, k + 1)
  98  + n ((- fff(n + 1, k + 1)) + 2 fff(n + 1, k) - a fff(n, k)
  99  - fff(n, k)) + a (fff(n + 1, k) - fff(n, k)) + 2 fff(n + 1, k)
 100     2
 101  - n  fff(n, k)@}
 102 @end group
 103 (%i7) /* Test this result for correctness */
 104 (%i8) first(%), fff(n,k) := ''(e)$
 105 @group
 106 (%i9) makefact(makegamma(%))$
 107 (%o9)                           0
 108 @end group
 109 (%i10) minfactorial(factor(minfactorial(factor(%))));
 110 @end example
 111
 112 The proviso data suggests that setting a = b may result in a lower order recursion
 113 which is shown by the following example:
 114 @c ===beg===
 115 @c load("integer_sequence")$
 116 @c load("opsubst")$
 117 @c load("to_poly_solve")$
 118 @c load("celine")$
 119 @c e : pochhammer(a,k) * pochhammer(-k,n) / (pochhammer(b,k));
 120 @c recur : celine(e,n,k,2,1);
 121 @c get('%,'proviso);
 122 @c celine(subst(b=a,e),n,k,1,1);
 123 @c ===end===
 124 @example
 125 (%i1) load("integer_sequence")$
 126 (%i2) load("opsubst")$
 127 (%i3) load("to_poly_solve")$
 128 (%i4) load("celine")$
 129 @group
 130 (%i5) e : pochhammer(a,k) * pochhammer(-k,n) / (pochhammer(b,k));
 131                            (a)  (- k)
 132                               k      n
 133 (%o5)                      -----------
 134                               (b)
 135                                  k
 136 @end group
 137 @group
 138 (%i6) recur : celine(e,n,k,2,1);
 139 (%o6) @{fff(n + 2, k + 1) - fff(n + 2, k) - b fff(n + 1, k + 1)
 140  + n ((- fff(n + 1, k + 1)) + 2 fff(n + 1, k) - a fff(n, k)
 141  - fff(n, k)) + a (fff(n + 1, k) - fff(n, k)) + 2 fff(n + 1, k)
 142     2
 143  - n  fff(n, k)@}
 144 @end group
 145 @group
 146 (%i7) get('%,'proviso);
 147 (%o7)                         false
 148 @end group
 149 @group
 150 (%i8) celine(subst(b=a,e),n,k,1,1);
 151 (%o8) @{fff(n + 1, k + 1) - fff(n + 1, k) + n fff(n, k)
 152                                                      + fff(n, k)@}
 153 @end group
 154 @end example