Gosper algorithm

 

• given the sequence , what is the sum

  
  
  

• we know that

• let us assume that is a rational function

• the quotient of two succesive terms of the sequence can be expressed as

  
  
  

• thus, is also a rational function

• on the basis of the following lemma, the quotient can be always written as

  
  
  

• where are polynomials for which for all ( is the greatest common divisor )

• Lemma A rational function can be always written as
  
  where are polynomials in and
  
  

• Theorem Let be a rational function as above. Then

  
  
  

  is a polynomial for which

  
  
  

• Gosper algorithm

        (S(n),b):=GOSPER( a(n))
          [assumes that a(n)/a(n-1) is a rational function,
           if S(n)/S(n-1) is also a rational function then b=true
           and S(n) is computed, otherwise b=false
           algorithms used:
             num(a)        - numerator of the rational function a
             den(a)        - denominator of the ratinal function a
             Res(x, p, q)  - resultant of polynomials p, q with respect to the
                             variable x
             gcd(p,q)      - greatest common divisor of the polynomials p and q
             deg(p(n))     - degree of the polynomial p(n)
             coef(p(n), i) - coefficient of the ith power of n in the polynomial
                             p(n)]
        1. b := true
        2. if a(n) = 0 then S(n) := 0; return fi
        3. p(n) := 1
           q(n) := num(a(n) / a(n-1))
           r(n) := den(a(n) / a(n-1))
        4. while (Res(n, q(n), r(n+j)) has nonnegative integer root j = j0) do
             g(n) := gcd(q(n), r(n+j0))
             q(n) := q(n)/g(n)
             r(n) := r(n)/g(n-j0)
             p(n) := p(n) g(n) g(n-1) ... g(n-j0+1)
           od
        5. lp := deg(q(n+1) + r(n))
           lm := deg(q(n+1) - r(n))
           if lp <= lm then k := deg(p(n))-lm
           else
             k0 := 2 (-lp coef(q, lp) - coef(q, lp-1) + coef(r, lp-1))/
                     (coef(q, lp) + coef(r, lp))
             if (k0 is integer) then k := max(k0, deg(p(n))-lp+1)
             else k := deg(p(n))-lp+1
             fi
           fi
           if k < 0 then b := false; return fi;
        6. solve recurrence relation  p(n)=q(n+1)f(n)-r(n)f(n-1)
           with initial condition     f(1)=p(1)/q(2)
           for f(n)=ck n^k + ... + c0
           if (solution does not exist) then b := false; return fi;
        7. S(n) := q(n+1) a(n) f(n)/p(n);
           return