Gosperův algoritmus

• známe posloupnost a_i a máme najít součet
  
  $$S(n)=\sum_{i=1}^n a_i$$
  
  

• víme, že a_i = S(i) - S(i-1)

• předpokládáme, že S(n)/S(n-1) je racionální lomená funkce

• podíl dvou následujících členů posloupnosti lze vyjádřit jako
  
  $$\begin{eqnarray*}\frac{a_n}{a_{n-1}}&=&\frac{S(n)-S(n-1)}{S(n-1)-S(n-2)}\\ &=&\frac{S(n)/S(n-1)-1}{1-S(n-2)/S(n-1)} \end{eqnarray*}$$
  
  

• takže a_n/a_n-1 je také racionální lomená funkce

• na základě následujícího lematu lze tento podíl vždy napsat jako
  
  $$\frac{a_n}{a_{n-1}}=\frac{p(n)q(n)}{p(n-1)r(n)}$$
  
  

• kde p, q, r jsou polynomy takové, že gcd(q(n),r(n+j))=1 , pro všechna j >= 0 ( gcd je největší společný dělitel )

• Lemma Mějme racionální lomenou funkci a(n)/b(n) . Tato funkce může být vždy zapsána jako
  
  $$\frac{a(n)}{b(n)}=\frac{p(n)q(n)}{p(n-1)r(n)},$$
  
  
  kde p, q, r jsou polynomy v n a platí
  
  $$\gcd(q(n),r(n+j))=1, \forall j\geq 0,$$
  
  

• Věta Nechť S(n)/S(n-1) je racionální lomená funkce jako výše. Potom
  
  $$f(n)=S(n)\frac{p(n)}{q(n+1)a_n}$$
  
  
  je polynom vyhovující
  
  p(n)=q(n+1)f(n)-r(n)f(n-1).
  
  

• Gosperův algoritmus

• Algoritmus

        (S(n),b):=GOSPER( a(n))
          [předpokládá, že a(n)/a(n-1) je racionální lomená funkce,
           pokud S(n)/S(n-1) je také racionální funkce je b=true
           a S(n) je spočítáno, jinak b=false
           použité algoritmy:
             num(a)      - čitatel racionální lomené funkce a
             den(a)      - jmenovatel racionální lomené funkce a
             Res(x,p,q)  - resultant polynomů p, q podle proměnné x
             gcd(p,q)    - největší společný dělitel polynomů p, q
             deg(p(n))   - stupeň polynomu p(n)
             cof(p(n),i) - koeficient u i-té mocnimy n v polynomu 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)) má nezáporný celý kořen 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 cof(q,lp)-cof(q,lp-1)+cof(r,lp-1))/
                   (cof(q,lp)+cof(r,lp));
             if (k0 je celé) 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. vyřešit rekurentní vzorec  p(n)=q(n+1)f(n)-r(n)f(n-1)
           s okrajovou podmínkou      f(1)=p(1)/q(2)
           pro f(n)=ck n^k+...+c0
           if (neexistuje řešení) then b:=false; return fi;
        7. S(n):=q(n+1)a(n)f(n)/p(n);
           return