/solve_rec.texi/1.7/Tue Jan 16 15:15:10 2007//

Introducedilhaão a solve_rec
============================

solve_rec é um pacote para resolver recorrências lineares com coeficientes polinomiais.

Um ficheiro de domostracedilhaão está disponivel com demo(solve_rec);.

Exemplo:

     (%i1) load("solve_rec")$
     (%i2) solve_rec((n+4)*s[n+2] + s[n+1] - (n+1)*s[n], s[n]);
                                         n
                      %k  (2 n + 3) (- 1)          %k
                        1                            2
     (%o2)       s  = -------------------- + ---------------
                  n     (n + 1) (n + 2)      (n + 1) (n + 2)

Definicedilhaões para solve_rec
===============================

 -- Funcedilhaão: reduce_order (REC, SOL, VAR)

     Reduz a ordem de recorrência linear REC quando uma solucedilhaão particular SOL for conhecida. A recorrência reduzida pode ser usada para pegar outras solucedilhaões.

     Exemplo:

          (%i3) rec: x[n+2] = x[n+1] + x[n]/n;
                                                x
                                                 n
          (%o3)               x      = x      + --
                               n + 2    n + 1   n
          (%i4) solve_rec(rec, x[n]);
          WARNING: found some hypergeometrical solutions!
          (%o4)                    x  = %k  n
                                    n     1
          (%i5) reduce_order(rec, n, x[n]);
          (%t5)                    x  = n %z
                                    n       n

                                     n - 1
                                     ====
                                     \
          (%t6)                %z  =  >     %u
                                 n   /        %j
                                     ====
                                     %j = 0

          (%o6)             (- n - 2) %u     - %u
                                        n + 1     n
          (%i6) solve_rec((n+2)*%u[n+1] + %u[n], %u[n]);
                                               n
                                      %k  (- 1)
                                        1
          (%o6)                 %u  = ----------
                                  n    (n + 1)!

          So the general solution is

                       n - 1
                       ====        n
                       \      (- 1)
                 %k  n  >    -------- + %k  n
                   2   /     (n + 1)!     1
                       ====
                       n = 0

 -- Variável de opcedilhaão: simplify_products
     Valor por omissão: true

     Se simplify_products for true, solve_rec irá tentar simplificar produtos no resultado.

     Veja também: solve_rec.

 -- Funcedilhaão: simplify_sum (EXPR)

     Tenta simplificar todos os somatórios que aparecem na EXPR para uma forma a mais simplificada possível.

     simplify_sum usa os algoritmos de Gosper e de Zeilberger para simplificar somatórios.

     Para usar essa funcedilhaão primeiramente chame o pacote simplify_sum com load(simplify_sum).

     Exemplo:

          (%i1) load("simplify_sum")$
          (%i2) sum(binom(n+k,k)/2^k, k, 0, n) + sum(binom(2*n, 2*k), k, 0, n);
                   n                            n
                  ====                         ====
                  \      binomial(n + k, k)    \
          (%o2)    >     ------------------ +   >    binomial(2 n, 2 k)
                  /               k            /
                  ====           2             ====
                  k = 0                        k = 0
          (%i3) simplify_sum(%);
                                         n
                                        4     n
          (%o3)                         -- + 2
                                        2

 -- Funcedilhaão: solve_rec (EQN, VAR, [INIT])
     Encontra solucedilhaões hipergeométricas para a recorrência linear EQN com coeficientes polinomiais na variável VAR. Argumentos opcionais INIT são as condicedilhaões iniciais.

     solve_rec pode resolver recorrências lineares com coeficientes constantes, encontrando solucedilhaões hipergeométricas para recorrências lineares homogêneas com coeficientes polinomiais, solucedilhaões racionais para recorrências lineares com coeficientes polinomiais e pode resolver recorrências do tipo de Ricatti.

     Note que o tempo de execucedilhaão do algoritmo usado para encontrar solucedilhaões hipergeométricas aumenta exponencialmente com o grau do coeficiente lider e guia.

     Para usar essa funcedilhaão primeiramente chame o pacote solve_rec com load(solve_rec);.

     Exemplo de recorrência linear com coeficientes constantes:

          (%i2) solve_rec(a[n]=a[n-1]+a[n-2]+n/2^n, a[n]);
                                  n          n
                     (sqrt(5) - 1)  %k  (- 1)
                                      1           n
          (%o2) a  = ------------------------- - ----
                 n               n                  n
                                2                5 2
                                                          n
                                             (sqrt(5) + 1)  %k
                                                              2    2
                                           + ------------------ - ----
                                                      n              n
                                                     2            5 2

     Exemplo de recorrência linear com coeficientes polinomiais:

          (%i7) 2*x*(x+1)*y[x] - (x^2+3*x-2)*y[x+1] + (x-1)*y[x+2];
                                   2
          (%o7) (x - 1) y      - (x  + 3 x - 2) y      + 2 x (x + 1) y
                         x + 2                   x + 1                x
          (%i8) solve_rec(%, y[x], y[1]=1, y[3]=3);
                                        x
                                     3 2    x!
          (%o9)                 y  = ---- - --
                                 x    4     2

     Exemplo de recorrência do tipo de Ricatti:

          (%i2) x*y[x+1]*y[x] - y[x+1]/(x+2) + y[x]/(x-1) = 0;
                                      y         y
                                       x + 1     x
          (%o2)         x y  y      - ------ + ----- = 0
                           x  x + 1   x + 2    x - 1
          (%i3) solve_rec(%, y[x], y[3]=5)$
          (%i4) ratsimp(minfactorial(factcomb(%)));
                                             3
                                         30 x  - 30 x
          (%o4) y  = - -------------------------------------------------
                 x        6      5       4       3       2
                       5 x  - 3 x  - 25 x  + 15 x  + 20 x  - 12 x - 1584

     Veja também: solve_rec_rat, simplify_products, e product_use_gamma.

 -- Funcedilhaão: solve_rec_rat (EQN, VAR, [INIT])

     Encontra solucedilhaões racionais para recorrências lineares. Veja solve_rec para uma descricedilhaão dos argumentos.

     Para usar essa funcedilhaão primeirametne chame o pacote solve_rec com load(solve_rec);.

     Exemplo:

          (%i1) (x+4)*a[x+3] + (x+3)*a[x+2] - x*a[x+1] + (x^2-1)*a[x];
          (%o1)  (x + 4) a      + (x + 3) a      - x a
                          x + 3            x + 2      x + 1
                                                             2
                                                         + (x  - 1) a
                                                                      x
          (%i2) solve_rec_rat(% = (x+2)/(x+1), a[x]);
                                 1
          (%o2)      a  = ---------------
                      x   (x - 1) (x + 1)

     Veja também: solve_rec.

 -- Variável de opcedilhaão: product_use_gamma
     Valor por omissão: true

     Quando simplificando produtos, solve_rec introduz a funcedilhaão gama dentro da expressão se product_use_gamma for true.

     Veja também: simplify_products, solve_rec.

 -- Funcedilhaão: summand_to_rec (SUMMAND, K, N)
 -- Funcedilhaão: summand_to_rec (SUMMAND, [K, LO, HI], N)

     Retorna a recorrência satisfeita pelo somatório

               sup
              ====
              \
               >     x
              /
              ====
            k = inf

     onde x é hipergeométrico em K e N. SE INF e SUP forem omitidos, são assumidos como sendo inf = -inf e sup = inf.

     Para usar essa funcedilhaão primeiro chame o pacote simplify_sum com load(simplify_sum).

     Exemplo:

          (%i1) load("simplify_sum")$
          (%i2) summand: binom(n,k);
          (%o2)                           binomial(n, k)
          (%i3) summand_to_rec(summand,k,n);
          (%o3)                      2 sm  - sm      = 0
                                         n     n + 1
          (%i7) summand: binom(n, k)/(k+1);
                                          binomial(n, k)
          (%o7)                           --------------
                                              k + 1
          (%i8) summand_to_rec(summand, [k, 0, n], n);
          (%o8)               2 (n + 1) sm  - (n + 2) sm      = - 1
                                          n             n + 1