doc/info/de/solve_rec.de.texi

   1 @c -----------------------------------------------------------------------------
   2 @c File     : solve_rec.de.texi
   3 @c License  : GNU General Public License (GPL)
   4 @c Original : solve_rec.texi revision 1.13
   5 @c Date     : 08.11.2010
   6 @c Revision : 25.03.2011
   7 @c
   8 @c This file is part of Maxima -- GPL CAS based on DOE-MACSYMA
   9 @c -----------------------------------------------------------------------------
  10
  11 @menu
  12 * Introduction to solve_rec::
  13 * Functions and Variables for solve_rec::
  14 @end menu
  15
  16 @c -----------------------------------------------------------------------------
  17 @node Introduction to solve_rec, Functions and Variables for solve_rec, solve_rec, solve_rec
  18 @section Introduction to solve_rec
  19 @c -----------------------------------------------------------------------------
  20
  21 @code{solve_rec} is a package for solving linear recurrences with polynomial
  22 coefficients.
  23
  24 A demo is available with @code{demo(solve_rec)}.
  25
  26 Example:
  27
  28 @example
  29 (%i1) load("solve_rec")$
  30 @group
  31 (%i2) solve_rec((n+4)*s[n+2] + s[n+1] - (n+1)*s[n], s[n]);
  32                                     n
  33                  %k  (2 n + 3) (- 1)          %k
  34                    1                            2
  35 (%o2)       s  = -------------------- + ---------------
  36              n     (n + 1) (n + 2)      (n + 1) (n + 2)
  37 @end group
  38 @end example
  39
  40 @c -----------------------------------------------------------------------------
  41 @node Functions and Variables for solve_rec,  , Introduction to solve_rec, solve_rec
  42 @section Functions and Variables for solve_rec
  43 @c -----------------------------------------------------------------------------
  44
  45 @c -----------------------------------------------------------------------------
  46 @deffn {Function} reduce_order (@var{rec}, @var{sol}, @var{var})
  47
  48 Reduces the order of linear recurrence @var{rec} when a particular solution
  49 @var{sol} is known.  The reduced reccurence can be used to get other solutions.
  50
  51 Example:
  52
  53 @example
  54 @group
  55 (%i3) rec: x[n+2] = x[n+1] + x[n]/n;
  56                                       x
  57                                        n
  58 (%o3)               x      = x      + --
  59                      n + 2    n + 1   n
  60 @end group
  61 @group
  62 (%i4) solve_rec(rec, x[n]);
  63 WARNING: found some hypergeometrical solutions!
  64 (%o4)                    x  = %k  n
  65                           n     1
  66 @end group
  67 @group
  68 (%i5) reduce_order(rec, n, x[n]);
  69 (%t5)                    x  = n %z
  70                           n       n
  71
  72                            n - 1
  73                            ====
  74                            \
  75 (%t6)                %z  =  >     %u
  76                        n   /        %j
  77                            ====
  78                            %j = 0
  79
  80 (%o6)             (- n - 2) %u     - %u
  81                               n + 1     n
  82 @end group
  83 @group
  84 (%i6) solve_rec((n+2)*%u[n+1] + %u[n], %u[n]);
  85                                      n
  86                             %k  (- 1)
  87                               1
  88 (%o6)                 %u  = ----------
  89                         n    (n + 1)!
  90
  91 So the general solution is
  92
  93              n - 1
  94              ====        j
  95              \      (- 1)
  96        %k  n  >    -------- + %k  n
  97          2   /     (j + 1)!     1
  98              ====
  99              j = 0
 100 @end group
 101 @end example
 102 @end deffn
 103
 104 @c -----------------------------------------------------------------------------
 105 @anchor{simplify_products}
 106 @defvr {Option variable} simplify_products
 107 Default value: @code{true}
 108
 109 If @code{simplify_products} is @code{true}, @code{solve_rec} will try to
 110 simplify products in result.
 111
 112 See also: @code{solve_rec}.
 113 @end defvr
 114
 115 @c -----------------------------------------------------------------------------
 116 @anchor{simplify_sum}
 117 @deffn {Function} simplify_sum (@var{expr})
 118
 119 Tries to simplify all sums appearing in @var{expr} to a closed form.
 120
 121 To use this function first load the @code{simplify_sum} package with
 122 @code{load("simplify_sum")}.
 123
 124 Example:
 125
 126 @example
 127 (%i1) load("simplify_sum")$
 128 @group
 129 (%i2) sum(binom(n+k,k)/2^k, k, 0, n)
 130                              + sum(binom(2*n, 2*k), k, 0, n);
 131          n                            n
 132         ====                         ====
 133         \      binomial(n + k, k)    \
 134 (%o2)    >     ------------------ +   >    binomial(2 n, 2 k)
 135         /               k            /
 136         ====           2             ====
 137         k = 0                        k = 0
 138 @end group
 139 @group
 140 (%i3) simplify_sum(%);
 141                                n
 142                               4     n
 143 (%o3)                         -- + 2
 144                               2
 145 @end group
 146 @end example
 147 @end deffn
 148
 149 @c -----------------------------------------------------------------------------
 150 @anchor{solve_rec_function}
 151 @deffn {Function} solve_rec (@var{eqn}, @var{var}, [@var{init}])
 152
 153 Solves for hypergeometrical solutions to linear recurrence @var{eqn} with
 154 polynomials coefficient in variable @var{var}.  Optional arguments @var{init}
 155 are initial conditions.
 156
 157 @code{solve_rec} can solve linear recurrences with constant coefficients,
 158 finds hypergeometrical solutions to homogeneous linear recurrences with
 159 polynomial coefficients, rational solutions to linear recurrences with
 160 polynomial coefficients and can solve Ricatti type recurrences.
 161
 162 Note that the running time of the algorithm used to find hypergeometrical
 163 solutions is exponential in the degree of the leading and trailing
 164 coefficient.
 165
 166 To use this function first load the @code{solve_rec} package with
 167 @code{load("solve_rec");}.
 168
 169 Example of linear recurrence with constant coefficients:
 170
 171 @example
 172 @group
 173 (%i2) solve_rec(a[n]=a[n-1]+a[n-2]+n/2^n, a[n]);
 174                         n          n
 175            (sqrt(5) - 1)  %k  (- 1)
 176                             1           n
 177 (%o2) a  = ------------------------- - ----
 178        n               n                  n
 179                       2                5 2
 180                                                 n
 181                                    (sqrt(5) + 1)  %k
 182                                                     2    2
 183                                  + ------------------ - ----
 184                                             n              n
 185                                            2            5 2
 186 @end group
 187 @end example
 188
 189 Example of linear recurrence with polynomial coefficients:
 190
 191 @example
 192 @group
 193 (%i7) 2*x*(x+1)*y[x] - (x^2+3*x-2)*y[x+1] + (x-1)*y[x+2];
 194                          2
 195 (%o7) (x - 1) y      - (x  + 3 x - 2) y      + 2 x (x + 1) y
 196                x + 2                   x + 1                x
 197 @end group
 198 @group
 199 (%i8) solve_rec(%, y[x], y[1]=1, y[3]=3);
 200                               x
 201                            3 2    x!
 202 (%o9)                 y  = ---- - --
 203                        x    4     2
 204 @end group
 205 @end example
 206
 207 Example of Ricatti type recurrence:
 208
 209 @example
 210 @group
 211 (%i2) x*y[x+1]*y[x] - y[x+1]/(x+2) + y[x]/(x-1) = 0;
 212                             y         y
 213                              x + 1     x
 214 (%o2)         x y  y      - ------ + ----- = 0
 215                  x  x + 1   x + 2    x - 1
 216 @end group
 217 (%i3) solve_rec(%, y[x], y[3]=5)$
 218 @group
 219 (%i4) ratsimp(minfactorial(factcomb(%)));
 220                                    3
 221                                30 x  - 30 x
 222 (%o4) y  = - -------------------------------------------------
 223        x        6      5       4       3       2
 224              5 x  - 3 x  - 25 x  + 15 x  + 20 x  - 12 x - 1584
 225 @end group
 226 @end example
 227
 228 See also: @code{solve_rec_rat}, @code{simplify_products}, and
 229 @code{product_use_gamma}.
 230 @end deffn
 231
 232 @c -----------------------------------------------------------------------------
 233 @anchor{solve_rec_rat}
 234 @deffn {Function} solve_rec_rat (@var{eqn}, @var{var}, [@var{init}])
 235
 236 Solves for rational solutions to linear recurrences.  See solve_rec for
 237 description of arguments.
 238
 239 To use this function first load the @code{solve_rec} package with
 240 @code{load("solve_rec");}.
 241
 242 Example:
 243
 244 @example
 245 @group
 246 (%i1) (x+4)*a[x+3] + (x+3)*a[x+2] - x*a[x+1] + (x^2-1)*a[x];
 247 (%o1)  (x + 4) a      + (x + 3) a      - x a
 248                 x + 3            x + 2      x + 1
 249                                                    2
 250                                                + (x  - 1) a
 251                                                             x
 252 @end group
 253 @group
 254 (%i2) solve_rec_rat(% = (x+2)/(x+1), a[x]);
 255                        1
 256 (%o2)      a  = ---------------
 257             x   (x - 1) (x + 1)
 258 @end group
 259 @end example
 260
 261 See also: @code{solve_rec}.
 262 @end deffn
 263
 264 @c -----------------------------------------------------------------------------
 265 @anchor{product_use_gamma}
 266 @defvr {Option variable} product_use_gamma
 267 Default value: @code{true}
 268
 269 When simplifying products, @code{solve_rec} introduces gamma function
 270 into the expression if @code{product_use_gamma} is @code{true}.
 271
 272 See also: @code{simplify_products}, @code{solve_rec}.
 273 @end defvr
 274
 275 @c -----------------------------------------------------------------------------
 276 @anchor{summand_to_rec}
 277 @deffn  {Function} summand_to_rec (@var{summand}, @var{k}, @var{n})
 278 @deffnx {Function} summand_to_rec (@var{summand}, [@var{k}, @var{lo}, @var{hi}], @var{n})
 279
 280 Returns the recurrence sattisfied by the sum
 281
 282 @example
 283 @group
 284      hi
 285     ====
 286     \
 287      >     summand
 288     /
 289     ====
 290   k = lo
 291 @end group
 292 @end example
 293
 294 where summand is hypergeometrical in @var{k} and @var{n}.  If @var{lo} and
 295 @var{hi} are omited, they are assumed to be @code{lo = -inf} and
 296 @code{hi = inf}.
 297
 298 To use this function first load the @code{simplify_sum} package with
 299 @code{load("simplify_sum")}.
 300
 301 Example:
 302
 303 @example
 304 (%i1) load("simplify_sum")$
 305 @group
 306 (%i2) summand: binom(n,k);
 307 (%o2)                           binomial(n, k)
 308 @end group
 309 @group
 310 (%i3) summand_to_rec(summand,k,n);
 311 (%o3)                      2 sm  - sm      = 0
 312                                n     n + 1
 313 @end group
 314 @group
 315 (%i7) summand: binom(n, k)/(k+1);
 316                                 binomial(n, k)
 317 (%o7)                           --------------
 318                                     k + 1
 319 @end group
 320 @group
 321 (%i8) summand_to_rec(summand, [k, 0, n], n);
 322 (%o8)               2 (n + 1) sm  - (n + 2) sm      = - 1
 323                                 n             n + 1
 324 @end group
 325 @end example
 326 @end deffn
 327
 328 @c --- End of file solve_rec.de.texi -------------------------------------------
 329