doc/info/solve_rec.texi

   1 @menu
   2 * Introduction to solve_rec::
   3 * Functions and Variables for solve_rec::
   4 @end menu
   5
   6 @node Introduction to solve_rec, Functions and Variables for solve_rec, Package solve_rec, Package solve_rec
   7 @section Introduction to solve_rec
   8
   9 @code{solve_rec} is a package for solving linear recurrences with polynomial
  10 coefficients.
  11
  12 A demo is available with @code{demo("solve_rec");}.
  13
  14 Example:
  15
  16 @example
  17 (%i1) load("solve_rec")$
  18 @group
  19 (%i2) solve_rec((n+4)*s[n+2] + s[n+1] - (n+1)*s[n], s[n]);
  20                                     n
  21                  %k  (2 n + 3) (- 1)          %k
  22                    1                            2
  23 (%o2)       s  = -------------------- + ---------------
  24              n     (n + 1) (n + 2)      (n + 1) (n + 2)
  25 @end group
  26 @end example
  27
  28 @opencatbox{Categories:}
  29 @category{Linear recurrences}
  30 @category{Share packages}
  31 @category{Package solve_rec}
  32 @closecatbox
  33
  34 @node Functions and Variables for solve_rec,  , Introduction to solve_rec, Package solve_rec
  35 @section Functions and Variables for solve_rec
  36
  37 @anchor{harmonic_number}
  38 @deffn {Function} harmonic_number (@var{x})
  39 When @var{x} is positive integer @math{n}, @code{harmonic_number} is
  40 the @math{n}'th harmonic number.  More generally,
  41 @code{harmonic_number(x) = psi[0](x+1) + %gamma}.  (See @ref{polygamma}).
  42
  43 @c ===beg===
  44 @c load("simplify_sum")$
  45 @c harmonic_number(5);
  46 @c sum(1/k, k, 1, 5);
  47 @c float(harmonic_number(sqrt(2)));
  48 @c float(psi[0](1+sqrt(2)))+%gamma;
  49 @c ===end===
  50 @example
  51 (%i1) load("simplify_sum")$
  52 @group
  53 (%i2) harmonic_number(5);
  54                                137
  55 (%o2)                          ---
  56                                60
  57 @end group
  58 @group
  59 (%i3) sum(1/k, k, 1, 5);
  60                                137
  61 (%o3)                          ---
  62                                60
  63 @end group
  64 @group
  65 (%i4) float(harmonic_number(sqrt(2)));
  66 (%o4)              %gamma + 0.6601971549171388
  67 @end group
  68 @group
  69 (%i5) float(psi[0](1+sqrt(2)))+%gamma;
  70 (%o5)              %gamma + 0.6601971549171388
  71 @end group
  72 @end example
  73 @end deffn
  74
  75 @anchor{harmonic_to_psi}
  76 @deffn {Function} harmonic_to_psi (@var{x})
  77 Converts expressions with @code{harmonic_number} to the equivalent
  78 expression involving @code{psi[0]} (see @ref{polygamma}).
  79
  80 @c ===beg===
  81 @c load("simplify_sum")$
  82 @c harmonic_to_psi(harmonic_number(sqrt(2)));
  83 @c ===end===
  84 @example
  85 (%i1) load("simplify_sum")$
  86 @group
  87 (%i2) harmonic_to_psi(harmonic_number(sqrt(2)));
  88 (%o2)              psi (sqrt(2) + 1) + %gamma
  89                       0
  90 @end group
  91 @end example
  92 @end deffn
  93
  94 @anchor{reduce_order}
  95 @deffn {Function} reduce_order (@var{rec}, @var{sol}, @var{var})
  96
  97 Reduces the order of linear recurrence @var{rec} when a particular solution
  98 @var{sol} is known. The reduced reccurence can be used to get other solutions.
  99
 100 Example:
 101
 102 @example
 103 @group
 104 (%i3) rec: x[n+2] = x[n+1] + x[n]/n;
 105                                       x
 106                                        n
 107 (%o3)               x      = x      + --
 108                      n + 2    n + 1   n
 109 @end group
 110 @group
 111 (%i4) solve_rec(rec, x[n]);
 112 WARNING: found some hypergeometrical solutions!
 113 (%o4)                    x  = %k  n
 114                           n     1
 115 @end group
 116 @group
 117 (%i5) reduce_order(rec, n, x[n]);
 118 (%t5)                    x  = n %z
 119                           n       n
 120
 121                            n - 1
 122                            ====
 123                            \
 124 (%t6)                %z  =  >     %u
 125                        n   /        %j
 126                            ====
 127                            %j = 0
 128
 129 (%o6)             (- n - 2) %u     - %u
 130                               n + 1     n
 131 @end group
 132 @group
 133 (%i6) solve_rec((n+2)*%u[n+1] + %u[n], %u[n]);
 134                                      n
 135                             %k  (- 1)
 136                               1
 137 (%o6)                 %u  = ----------
 138                         n    (n + 1)!
 139
 140 So the general solution is
 141
 142              n - 1
 143              ====        j
 144              \      (- 1)
 145        %k  n  >    -------- + %k  n
 146          2   /     (j + 1)!     1
 147              ====
 148              j = 0
 149 @end group
 150 @end example
 151
 152 @opencatbox{Categories:}
 153 @category{Package solve_rec}
 154 @closecatbox
 155
 156 @end deffn
 157
 158 @anchor{simplify_products}
 159 @defvr {Option variable} simplify_products
 160 Default value: @code{true}
 161
 162 If @code{simplify_products} is @code{true}, @code{solve_rec} will try to
 163 simplify products in result.
 164
 165 See also: @mrefdot{solve_rec}
 166
 167 @opencatbox{Categories:}
 168 @category{Package solve_rec}
 169 @closecatbox
 170
 171 @end defvr
 172
 173 @anchor{simplify_sum}
 174 @deffn {Function} simplify_sum (@var{expr})
 175
 176 Tries to simplify all sums appearing in @var{expr} to a closed form.
 177
 178 To use this function first load the @code{simplify_sum} package with
 179 @code{load("simplify_sum")}.
 180
 181 Example:
 182
 183 @c ===beg===
 184 @c load("simplify_sum")$
 185 @c sum(binomial(n+k,k)/2^k, k, 1, n) + sum(binomial(2*n, 2*k), k, 1,n);
 186 @c simplify_sum(%);
 187 @c ===end===
 188 @example
 189 (%i1) load("simplify_sum")$
 190 @group
 191 (%i2) sum(binomial(n+k,k)/2^k, k, 1, n) + sum(binomial(2*n, 2*k), k, 1,n);
 192         n                          n
 193        ====                       ====
 194        \     binomial(n + k, k)   \
 195 (%o2)   >    ------------------ +  >    binomial(2 n, 2 k)
 196        /              k           /
 197        ====          2            ====
 198        k = 1                      k = 1
 199 @end group
 200 @group
 201 (%i3) simplify_sum(%);
 202                          2 n - 1    n
 203 (%o3)                   2        + 2  - 2
 204 @end group
 205 @end example
 206
 207 @opencatbox{Categories:}
 208 @category{Package solve_rec}
 209 @category{Sums and products}
 210 @category{Simplification functions}
 211 @closecatbox
 212
 213 @end deffn
 214
 215 @anchor{solve_rec}
 216 @deffn {Function} solve_rec (@var{eqn}, @var{var}, [@var{init}])
 217 Solves for hypergeometrical solutions to linear recurrence @var{eqn} with
 218 polynomials coefficient in variable @var{var}. Optional arguments @var{init}
 219 are initial conditions.
 220
 221 @code{solve_rec} can solve linear recurrences with constant coefficients,
 222 finds hypergeometrical solutions to homogeneous linear recurrences with
 223 polynomial coefficients, rational solutions to linear recurrences with
 224 polynomial coefficients and can solve Ricatti type recurrences.
 225
 226 Note that the running time of the algorithm used to find hypergeometrical
 227 solutions is exponential in the degree of the leading and trailing
 228 coefficient.
 229
 230 To use this function first load the @code{solve_rec} package with
 231 @code{load("solve_rec");}.
 232
 233 Example of linear recurrence with constant coefficients:
 234
 235 @example
 236 @group
 237 (%i2) solve_rec(a[n]=a[n-1]+a[n-2]+n/2^n, a[n]);
 238                         n          n
 239            (sqrt(5) - 1)  %k  (- 1)
 240                             1           n
 241 (%o2) a  = ------------------------- - ----
 242        n               n                  n
 243                       2                5 2
 244                                                 n
 245                                    (sqrt(5) + 1)  %k
 246                                                     2    2
 247                                  + ------------------ - ----
 248                                             n              n
 249                                            2            5 2
 250 @end group
 251 @end example
 252
 253 Example of linear recurrence with polynomial coefficients:
 254
 255 @example
 256 @group
 257 (%i7) 2*x*(x+1)*y[x] - (x^2+3*x-2)*y[x+1] + (x-1)*y[x+2];
 258                          2
 259 (%o7) (x - 1) y      - (x  + 3 x - 2) y      + 2 x (x + 1) y
 260                x + 2                   x + 1                x
 261 @end group
 262 @group
 263 (%i8) solve_rec(%, y[x], y[1]=1, y[3]=3);
 264                               x
 265                            3 2    x!
 266 (%o9)                 y  = ---- - --
 267                        x    4     2
 268 @end group
 269 @end example
 270
 271 Example of Ricatti type recurrence:
 272
 273 @example
 274 @group
 275 (%i2) x*y[x+1]*y[x] - y[x+1]/(x+2) + y[x]/(x-1) = 0;
 276                             y         y
 277                              x + 1     x
 278 (%o2)         x y  y      - ------ + ----- = 0
 279                  x  x + 1   x + 2    x - 1
 280 @end group
 281 (%i3) solve_rec(%, y[x], y[3]=5)$
 282 @group
 283 (%i4) ratsimp(minfactorial(factcomb(%)));
 284                                    3
 285                                30 x  - 30 x
 286 (%o4) y  = - -------------------------------------------------
 287        x        6      5       4       3       2
 288              5 x  - 3 x  - 25 x  + 15 x  + 20 x  - 12 x - 1584
 289 @end group
 290 @end example
 291
 292
 293 See also: @mrefcomma{solve_rec_rat} @mref{simplify_products} and @mrefdot{product_use_gamma}
 294
 295 @opencatbox{Categories:}
 296 @category{Package solve_rec}
 297 @closecatbox
 298
 299 @end deffn
 300
 301 @anchor{solve_rec_rat}
 302 @deffn {Function} solve_rec_rat (@var{eqn}, @var{var}, [@var{init}])
 303
 304 Solves for rational solutions to linear recurrences. See solve_rec for
 305 description of arguments.
 306
 307 To use this function first load the @code{solve_rec} package with
 308 @code{load("solve_rec");}.
 309
 310 Example:
 311
 312 @example
 313 @group
 314 (%i1) (x+4)*a[x+3] + (x+3)*a[x+2] - x*a[x+1] + (x^2-1)*a[x];
 315 (%o1)  (x + 4) a      + (x + 3) a      - x a
 316                 x + 3            x + 2      x + 1
 317                                                    2
 318                                                + (x  - 1) a
 319                                                             x
 320 @end group
 321 @group
 322 (%i2) solve_rec_rat(% = (x+2)/(x+1), a[x]);
 323                        1
 324 (%o2)      a  = ---------------
 325             x   (x - 1) (x + 1)
 326 @end group
 327 @end example
 328
 329
 330 See also: @mrefdot{solve_rec}
 331
 332 @opencatbox{Categories:}
 333 @category{Package solve_rec}
 334 @closecatbox
 335
 336 @end deffn
 337
 338 @anchor{product_use_gamma}
 339 @defvr {Option variable} product_use_gamma
 340 Default value: @code{true}
 341
 342 When simplifying products, @code{solve_rec} introduces gamma function
 343 into the expression if @code{product_use_gamma} is @code{true}.
 344
 345 See also: @mrefcomma{simplify_products} @mrefdot{solve_rec}
 346
 347 @opencatbox{Categories:}
 348 @category{Package solve_rec}
 349 @closecatbox
 350
 351 @end defvr
 352
 353 @anchor{summand_to_rec}
 354 @deffn {Function} summand_to_rec @
 355 @fname{summand_to_rec} (@var{summand}, @var{k}, @var{n}) @
 356 @fname{summand_to_rec} (@var{summand}, [@var{k}, @var{lo}, @var{hi}], @var{n})
 357
 358 Returns the recurrence satisfied by the sum
 359
 360 @example
 361 @group
 362      hi
 363     ====
 364     \
 365      >     summand
 366     /
 367     ====
 368   k = lo
 369 @end group
 370 @end example
 371
 372 where summand is hypergeometrical in @var{k} and @var{n}. If @var{lo} and @var{hi}
 373 are omitted, they are assumed to be @code{lo = -inf} and @code{hi = inf}.
 374
 375 To use this function first load the @code{simplify_sum} package with
 376 @code{load("simplify_sum")}.
 377
 378 Example:
 379
 380 @example
 381 (%i1) load("simplify_sum")$
 382 @group
 383 (%i2) summand: binom(n,k);
 384 (%o2)                           binomial(n, k)
 385 @end group
 386 @group
 387 (%i3) summand_to_rec(summand,k,n);
 388 (%o3)                      2 sm  - sm      = 0
 389                                n     n + 1
 390 @end group
 391 @group
 392 (%i7) summand: binom(n, k)/(k+1);
 393                                 binomial(n, k)
 394 (%o7)                           --------------
 395                                     k + 1
 396 @end group
 397 @group
 398 (%i8) summand_to_rec(summand, [k, 0, n], n);
 399 (%o8)               2 (n + 1) sm  - (n + 2) sm      = - 1
 400                                 n             n + 1
 401 @end group
 402 @end example
 403
 404 @opencatbox{Categories:}
 405 @category{Package solve_rec}
 406 @closecatbox
 407
 408 @end deffn