reduce-historical/r38/doc/manual2/sum.tex

\chapter{SUM: A package for series summation}
\label{SUM}
\typeout{{SUM: A package for series summation}}

{\footnotesize
\begin{center}
Fujio Kako \\ 
Department of Mathematics, Faculty of Science \\
Hiroshima University \\ 
Hiroshima 730, JAPAN \\[0.05in]
e--mail: kako@ics.nara-wu.ac.jp
\end{center}
}
\ttindex{SUM}

\index{Gosper's Algorithm}\index{SUM operator}\index{PROD operator}
This package implements the Gosper algorithm for the summation of series.
It defines operators SUM and PROD.  The operator SUM returns the indefinite
or definite summation of a given expression, and the operator PROD returns
the product of the given expression.  These are used with the syntax:

\vspace{.1in}
\noindent{\tt SUM}(EXPR:{\em expression}, K:{\em kernel},
[LOLIM:{\em expression} [, UPLIM:{\em expression}]]) \\
\noindent{\tt PROD}(EXPR:{\em expression}, K:{\em kernel},
[LOLIM:{\em expression} [, UPLIM:{\em expression}]])

If there is no closed form solution, these operators return the input
unchanged.  UPLIM and LOLIM are optional parameters specifying the lower
limit and upper limit of the summation (or product), respectively.  If UPLIM
is not supplied, the upper limit is taken as K (the summation variable
itself).

For example:

\begin{verbatim}
     sum(n**3,n);

     sum(a+k*r,k,0,n-1);

     sum(1/((p+(k-1)*q)*(p+k*q)),k,1,n+1);

     prod(k/(k-2),k);
\end{verbatim}

Gosper's algorithm succeeds whenever the ratio

\[ \frac{\sum_{k=n_0}^n f(k)}{\sum_{k=n_0}^{n-1} f(k)} \]

\noindent is a rational function of $n$.  The function SUM!-SQ
handles basic functions such as polynomials, rational functions and
exponentials.\ttindex{SUM-SQ}

The trigonometric functions sin, cos, {\em etc.\ }are converted to exponentials
and then Gosper's algorithm is applied.  The result is converted back into
sin, cos, sinh and cosh.

Summations of logarithms or products of exponentials are treated by the
formula:

\vspace{.1in}
\hspace*{2em} \[ \sum_{k=n_0}^{n} \log f(k) = \log \prod_{k=n_0}^n f(k) \]
\vspace{.1in}
\hspace*{2em} \[ \prod_{k=n_0}^n \exp f(k) = \exp \sum_{k=n_0}^n f(k) \]
\vspace{.1in}

Other functions can be summed by providing LET rules which must relate the
functions evaluated at $k$ and $k - 1$ ($k$ being the summation variable).

\begin{verbatim}
operator f,gg;  % gg used to avoid possible conflict with high energy
                % physics operator.

for all n,m such that fixp m let
        f(n+m)=if m > 0 then f(n+m-1)*(b*(n+m)**2+c*(n+m)+d)
                   else f(n+m+1)/(b*(n+m+1)**2+c*(n+m+1)+d);

for all n,m such that fixp m let
        gg(n+m)=if m > 0 then gg(n+m-1)*(b*(n+m)**2+c*(n+m)+e)
                   else gg(n+m+1)/(b*(n+m+1)**2+c*(n+m+1)+e);

sum(f(n-1)/gg(n),n);

     f(n)
---------------
 gg(n)*(d - e)
\end{verbatim}