\documentclass[a4paper]{article}

%I use the follwing packages
%For the Mathematica package I use additionally the array environment

\usepackage{amssymb, amsbsy, epsf}
\usepackage{amsmath, amsthm}

%I use the follwing headings
\pagestyle{headings}

%I resize the paper format
\textwidth=13cm
\textheight=22cm

%I use the following macros

\newcommand{\HNumber}[1]{\text{H}_{#1}}
\newcommand{\HNumberII}[1]{\text{H}^{(2)}_{#1}}
\newcommand{\MathTerm}[1]{{\tt #1}}
\newcommand{\QQ}{\mathbb{Q}}


%I insert my Mathematica package

%*******************************************************************
%*                         Notebook package                        *
%*                               by                                *
%*                         Carsten Schneider                       *
%*                                                                 *
%*                                                                 *
%*                           ALPHA-version 0.1                     *
%*                             30.1.2000                           *
%*******************************************************************

% I use the array package. Do not exchange it.
\usepackage{array}

% Define the font size of the Notebook Output
\def\notebooksize{\normalsize}


%If you want to import graphic uncomment the following two lines or replace
%the suggestion by your own code.
%\usepackage{epsfig}
%\def\mathGraphic#1{\includegraphics{#1}}
%\def\mathGraphic#{\resizebox{4cm}{!}{\includegraphics{w0.eps}}}


% Symbols which are used by Mathematica. Uncomment and extend what you need!

%\def\Angstrom{\relax\ifmmode\Angstroem\else$\Angstroem$\fi}
%\DeclareMathSymbol{\circr}{\mathord}{symbols}{"FE}
%\def\circledR{\relax\ifmmode\tm\else$\circr$\fi}
%\def\DifferentialD{\relax\ifmmode\dd\else$\dd$\fi}
%\def\ExponentialE{\relax\ifmmode\ee\else$\ee$\fi}
%\let\FilledCircle\Circle
%\def\FilledSmallCircle{\relax\ifmmode\bullet\else$\bullet$\fi}
%\let\FilledSquare\Square
%\def\ImaginaryI{\relax\ifmmode\ii\else$\ii$\fi}
%\def\ImaginaryJ{\relax\ifmmode\jj\else$\jj$\fi}
%\let\InvisiblePrefixScriptBase\relax
%\let\InvisibleSpace\relax
%\DeclareMathSymbol{\LeftAngleBracket}{\mathopen}{symbols}{"68}
%\def\LeftBracketingBar{|}
%\let\LeftDoubleBracket\lpart
%\def\LeftDoubleBracketingBar{\relax%
%       \ifmmode\hbox{$\parallel$}\else$\parallel$\fi}
%\DeclareMathSymbol{\leftsk}{\mathopen}{symbols}{"1C}
%\def\LeftSkeleton{\relax\ifmmode\leftsk\else$\leftsk$\fi}
%\def\RawTilde{\symbol{"7E}}
\def\RawWedge{\symbol{"5E}}
%\DeclareMathSymbol{\RightAngleBracket}{\mathopen}{symbols}{"69}
%\def\RightBracketingBar{|}
%\let\RightDoubleBracket\rpart
%\let\RightDoubleBracketingBar\LeftDoubleBracketingBar
%\DeclareMathSymbol{\rightsk}{\mathclose}{symbols}{"1D}
%\def\RightSkeleton{\relax\ifmmode\leftsk\else$\rightsk$\fi}
%\def\SkeletonIndicator{\relax\ifmmode\hbox{-}\else -\relax\fi}
%\DeclareMathSymbol{\tm}{\mathord}{symbols}{"FF}
%\def\Trademark{\relax\ifmmode\tm\else$\tm$\fi}
%\def\VerticalBar{|}
%\def\VerticalSeparator{|}
%\let\VeryThinSpace\,
%\def\RawReturn{\par}
%\def\multsp{\>}

\def\InvisibleSpace{\,}

%Section and chapter stuff

\def\Chapter{\chapter}
\def\Subchapter{\subchapter}
\def\Subsubchapter{\subsubchapter}
\def\Section{\section}
\def\Subsection{\subsection}
\def\Subsubsection{\subsubsection}


% The text functions for Mathematica functions, userfunctions, variables and
% strings.

\def\Mfunction#1{{\InputOutputMode#1}}
\def\Muserfunction#1{{\InputOutputMode#1}}
\def\Mvariable#1{{\InputOutputMode#1}}
\def\Mstring#1{\hbox{#1}}


% The Mathematica array - only matrices with one column are possible.

\def\MathBegin{\begin}
\def\MathEnd{\end}

%\newenvironment{MathArray}[1]{\begin{tabular}[t]{@{$\tt\displaystyle\notebooksize}l@{$}}}{\end{tabular}}

\newenvironment{MathArray}[1]{\MakeTabular{#1}}{\end{tabular}}
\def\MakeTabular#1{\if[#1 \expandafter\MakeTabularWithPos \else \MakeDefaultTabular \fi}
\newcommand{\MakeDefaultTabular}{\begin{tabular}[t]{>{\hspace*{-0.2cm}$\InputOutputMode\displaystyle}l<{$}}}
\newcommand{\MakeTabularWithPos}[3]{\begin{tabular}[c]{>{\hspace*{-0.17cm}$\InputOutputMode\displaystyle}c<{$\hspace*{-0.17cm}}}}


% A counter for the promt. Each coputation step increases the counter
\newcounter{myprompt}
\setcounter{myprompt}{0}

% The Input/Output functions
\def\InputMode{\tt\bf}
\def\OutputMode{\tt}

\newcommand{\dispSFinmath}[1]{\vspace{0.3\parsep}\noindent
\addtocounter{myprompt}{1}\let\InputOutputMode\InputMode
{\notebooksize\sloppy $\hbox{\small{\it In}[\themyprompt]}:=\;${$\displaystyle\InputMode #1$}\sloppy\par}\vspace{0.3\parsep}}

\newcommand{\dispSFoutmath}[1]{\vspace{0.3\parsep}\noindent
\let\InputOutputMode\OutputMode
{\sloppy\notebooksize$\hbox{\small{\it
      Out}[\themyprompt]}=\;$$\displaystyle\OutputMode
  #1$}\sloppy\par\vspace{0.3\parsep}
}

\newcommand{\Print}[1]{\hspace*{1.26cm}\OutputMode\notebooksize #1}

\newcommand{\dispSFPrintmath}[1]{
\let\InputOutputMode\OutputMode
\hspace*{1.26cm}{\tt\notebooksize\OutputMode $#1$}\par}

\def\inlineSFinmath#1{\let\InputOutputMode\OutputMode $\tt\OutputMode #1$}
\def\inlineSFoutmath#1{\let\InputOutputMode\OutputMode $\tt\OutputMode #1$}\def\inlineTFinmath#1{{$\displaystyle #1$}}

\newcommand{\NegativeVeryThinSpace}{} % -3-3+5=1 where the unit is 1/18 quad.


% The cell group

\newenvironment{CellGroup}{
\vspace{1.2\parsep}}{\vspace{1.2\parsep}\par}


%The Notebook environment - avoid indents.

\newenvironment{notebook}{\parindent=0cm}{}


%*********************************************************************
%*                                                                   *
%*                        The Document Part                          *
%*                                                                   *
%*********************************************************************

\begin{document}

\begin{titlepage}

\title{
An Implementation of\\
%\vspace*{0.3cm}
Karr's Summation Algorithm\\
%\vspace*{0.3cm}
in Mathematica\footnote{
This work is supported by the SFB grant F1305 of the Austrian 
``Fonds zur F{\"o}rderung der wissenschaftlichen Forschung'' and by
the DAAD grant ``Doktorandenstipendium im Rahmen des 
gemeinsamen Hochschulsonderprogramms III von Bund und L{\"a}ndern''.}
}
\author{Carsten.Schneider@risc.uni-linz.ac.at}
%\end{center}

\date{}

\end{titlepage}

\maketitle

\begin{abstract}

Implementations of the celebrated Gosper algorithm (1978) for
indefinite summation are 
available on almost any computer algebra platform. We report here about an
implementation of an algorithm by Karr, the most general indefinite summation 
algorithm known. Karr's algorithm is, in a sense, the summation counterpart 
of Risch's algorithm for indefinite integration.
This is the first implementation of this algorithm in a major computer 
algebra system. Our version contains new 
extensions to handle also definite summation problems. 
In addition we provide a feature to find automatically appropriate 
difference field extensions in which a closed form for the summation 
problem exists. 
These new aspects are illustrated by a variety of examples.

%Besides Karr's difference field machinery, our version finds 
%appropriate difference field extensions automatically.
%Furthermore, we generalized Karr's algorithm to deal with
%{\bf definite} summation problems. These new aspects are illustrated by a 
%variety of examples.
%
%There are implementations of the celebrated Gosper algorithm (1978) on almost
%any computer algebra platform. Within my PhD thesis work I implemented 
%{\bf Karr's Summation Algorithm} (1981) in the Mathematica system. 
%This is the first
%implementation of this algorithm in a major computer algebra system. 
%Besides including all the difference-field machinery, this version already 
%contains new extensions in order to handle also {\bf definite} summation 
%problems. The talk introduces this work according a collection of examples.
\end{abstract}

\section{Introduction}

Karr developed an algorithm for {\bf indefinite} summation \cite{karr,karr2} 
based on the theory of difference fields \cite{cohn}. 
He introduced so called $\pi\sigma$-fields, in 
which first order linear difference equations can be solved in full 
generality. 
We implemented this algorithm in the computer algebra system Mathematica and
developed a user interface that dispenses the user from working 
explicitly with difference fields. Instead, the user can handle all 
summation problems in terms of sums and products.

This algorithm cannot only deal with series of hypergeometric terms, like
Gosper's algorithm \cite{gosper,pauleschorn}, 
series with q-hypergeometric terms, 
like \cite{riese}, or holonomic series, like Chyzak's algorithm \cite{chyzak}, 
but with series of terms where for example the harmonic numbers 
can appear in the denominator (see section \ref{powerExp}).

In some cases appropriate difference field extensions are necessary in order 
to find a closed form to a summation problem. 
In many cases our implementation is able to find such
extensions automatically. Therefore one does not have to deal with 
problems concerning difference field extensions. This feature
to find automatic extensions will be demonstrated in section \ref{AutExtSect}.

Finally, we extended Karr's algorithm to handle {\bf definite} summation
problems. The algorithm is generalized so that linear difference
equations of any order can be solved. 
It is also possible to consider field extensions in form of 
algebraic relations, like $((-1)^k)^2=1$.
A rather complex example will illustrate 
how definite summation problems can be solved in our Mathematica 
implementation.

 
This article is based on transparencies \cite{schneider} we used for a 
presentation at the {\em S{\'e}minaire Lotharingien de Combinatoire 43}.
Some further results have been added. 

\vspace*{0.4cm}

The Mathematica package is available in an encoded form by email request to 
{\tt Carsten.Schneider@risc.uni-linz.ac.at}. The Mathematica code of the
package has not been published yet because it is still under construction.  


\section{Karr's indefinite summation algorithm}

\subsection{A first example}

In the book Concrete Mathematics \cite[exercise 6.69]{knuth} the task of finding  
a closed form representation of
$$\sum_{k=1}^{n}k^2\HNumber{n+k},$$
where $\HNumber{n}:=\sum_{k=1}^n\frac{1}{k}$ is the $n$-th harmonic number, 
is posed as a bonus problem.
Knuth's solution to this problem is

$$\frac{1}{3}n\left(n+\frac{1}{2}\right)\left(n+1\right)\left(2\HNumber{2n}-\HNumber{n}\right)-\frac{1}{36}n\left(10n^2+9n-1\right)$$

\noindent
where he remarks

\begin{quote}
{\bf ``It would be nice to automate the derivation of formulas such as this.''}
\end{quote}

The closed form of this bonus problem can be computed by using 
Karr's algorithm.
The implementation is available in form of a Mathematica package, in which 
functions are provided to define a given summation problem 
in the Mathematica environment. 

\begin{CellGroup}
\dispSFinmath{\Mvariable{Problem69}=\Muserfunction{DefineSum}[k\RawWedge
  2\Muserfunction{DefineHNumber}[n+k],\{k,1,n\}]}
\dispSFoutmath{\sum _{k=1}^{n}\big({k^2}\ {\HNumber{k+n}}\big)}
\end{CellGroup}

\noindent
The functions \MathTerm{DefineSum} and
\MathTerm{DefineProduct} are used to define sums and products. 
There are several other functions available, like \MathTerm{DefineHNumber}, 
\MathTerm{DefineBinomial} or \MathTerm{DefinePower} to define harmonic 
numbers, binomials or powers. Additionally, various functions are provided to 
introduce new objects.

Karr's algorithm is applied to the summation problem by calling the function
\MathTerm{KReduce}. Here the solution of Karr's algorithm
is simplified by using the Mathematica function \MathTerm{Simplify}.

\begin{CellGroup}
\dispSFinmath{\Muserfunction{KReduce}[\Mvariable{Problem69}]//\Mfunction{Simplify}}
\dispSFoutmath{-\frac{1}{36}\ n\ (1+n)\ (-1+10\ n+6\ (1+2\ n)\ {H_n}-12\ (1+2\ n)\ {\HNumber{2\ n}})}
\end{CellGroup}

\newpage

\subsection{Indefinite summation and first order linear\\ difference equations}

In this section we will give a rough outline of Karr's approach, which
is based on the theory of difference fields. In the following a 
difference field is considered as a field together with a field 
automorphism\footnote{More precisely, we will consider only a subclass of
  difference fields, so called $\pi\sigma$-fields (see \cite{karr}).}.

A huge class of indefinite summation problems can be formalized 
by first order linear difference equations in difference field settings.
Since Karr's algorithm can solve first order linear difference equations 
in full generality, Karr's algorithm enables to treat this type. 

We will illustrate Karr's approach by the following elementary problem: 
find a closed form of 
$$\sum_{k=0}^n k\, k!.$$

\subsubsection*{A difference field for the problem}
Let $t_1,t_2$ be indeterminates and consider
the field automorphism $\sigma:\QQ(t_1,t_2)\rightarrow\QQ(t_1,t_2)$
induced by
\begin{eqnarray*}
%\sigma(c)&=&c \;\;\;\forall c\in\QQ\\
\sigma(t_1)&=& t_1+1\\
\sigma(t_2)&=& (t_1+1)\,t_2.
\end{eqnarray*}

\noindent
Note that the automorphism acts on $t_1$ and $t_2$ like the 
shift operator $N$
on $n$ and $n!$ via $N n=n+1$ and $N n!=(n+1)\,n!$.

\subsubsection*{A first order difference equation}
The indefinite summation problem can be rephrased in terms of the difference
field $\QQ(t_1,t_2)$ as follows: find a solution $g\in\QQ(t_1,t_2)
$ of 
$$\sigma(g)-g=t_1\, t_2.$$ 
Karr's algorithm computes the solution $g=t_2$ from which 
$$(k+1)! - k! = k\, k!$$ 
immediately follows.

\subsubsection*{The closed form}
By the telescoping trick one obtains the closed form evaluation
$$\sum_{k=0}^n k\, k!=(n+1)!-1.$$

\subsection{Difference field extensions}\label{DFExt}

The goal is to simplify the triple 
sum (note $\HNumber{i}=\sum_{j=1}^i\frac{1}{j}$)
$$\sum_{k=1}^n\sum_{i=2}^k\frac{\HNumber{i}}{i^2-1},$$
by eliminating the outermost sum.
Applying Karr's algorithm on

\begin{CellGroup}
\dispSFinmath{
\MathBegin{MathArray}{l}
\Mvariable{tripleSum}=\Mvariable{DefineSum}[  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \Muserfunction{DefineSum}[\Muserfunction{DefineHNumber}[i]/(i\RawWedge 2-1),\{i,2,k\}],  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \{k,1,n\}]\\
\MathEnd{MathArray}
}
\dispSFoutmath{\sum _{k=1}^{n}\Big(\sum _{i=2}^{k}\Big(\frac{{H_i}}{-1+{i^2}}\Big)\Big)}
\end{CellGroup}

\noindent
one gets

\begin{CellGroup}
\dispSFinmath{\Muserfunction{KReduce}[\Mvariable{tripleSum}]//\Mfunction{Simplify}}
\dispSFoutmath{\MathBegin{MathArray}{l}
\frac{1}{4 n (1+n)}\Big(2 {H_n}-2 n (1+n) H_{n}^{2}+  \\
\noalign{\vspace{2.ex}}
\hspace{3.em} (1+n) \Big(2-n+4 n (1+n) \sum _{{{\iota }_1}=2}^{n}\Big(\frac{{H_{{{\iota }_1}}}}{-1+\iota _{1}^{2}}\Big)\Big)\Big)\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
This means, the triple sum can be expressed in terms of $n$, $\HNumber{n}$ 
and the double sum
\begin{equation}\label{doubleSumInExt}
\sum_{i=2}^n\frac{\HNumber{i}}{i^2-1}.
\end{equation}
Experiences with handling summations of harmonic numbers tell us that
the sum (\ref{doubleSumInExt}) can be expressed by using the
harmonic numbers of second order $\HNumberII{n}=\sum_{i=1}^n\frac{1}{i^2}$.
Karr's algorithm can be forced to use $\HNumberII{n}$, 
which amounts algebraically to an extension of the underlying difference
field, the solution space, by these elements $\HNumberII{n}$.

\begin{CellGroup}
\dispSFinmath{\Muserfunction{KReduce}\big[\Mvariable{tripleSum},\Mvariable{Tower}->\big\{H_{n}^{(2)}\big\}\big]//\Mfunction{Simplify}}
\dispSFoutmath{\MathBegin{MathArray}{l}
\frac{1}{4 (1+n)}  \\
\noalign{\vspace{1.11458ex}}
\hspace{1.em} \big(-2 (3+2 n) {H_n}-2 (1+n) H_{n}^{(2)}+(1+n) \big(3 n+2 (1+n) H_{n}^{(2)}\big)\big)\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
This non-automatic extension was carried out by setting the option 
$\MathTerm{Tower->\{\HNumberII{n}\}}$.


\subsection{The power of Karr's algorithm}\label{powerExp}

Since Karr's algorithm is based on difference fields, arbitrary rational
compositions of sums and products can be treated. As another example 
we consider

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{powerExample}=\Muserfunction{DefineSum}[1/\Muserfunction{DefineSum}[1/i,\{i,1,k\}]/  \\
\noalign{\vspace{0.5ex}}
\hspace{3.em} (1-k*\Muserfunction{DefineSum}[1/i,\{i,1,k\}]),  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \{k,2,n\}]\\
\MathEnd{MathArray}}
\dispSFoutmath{\sum _{k=2}^{n}\Big(\frac{1}{\big(\sum _{i=1}^{k}\big(\frac{1}{i}\big)\big) \big(1-k \sum _{i=1}^{k}\big(\frac{1}{i}\big)\big)}\Big)}
\end{CellGroup}

\noindent
Applying Karr's algorithm leads to the simplified expression

\begin{CellGroup}
\dispSFinmath{\Muserfunction{KReduce}[\Mvariable{powerExample}]}
\dispSFoutmath{-1+\frac{1}{\sum _{{{\iota }_1}=1}^{n}\Big(\frac{1}{{{\iota }_1}}\Big)}}
\end{CellGroup}


\section{Automatic difference field extensions}\label{AutExtSect}

In section \ref{DFExt} it was shown, how a simpler closed form can be found 
by extending the difference field in which one expects to find the solution
for the telescoping problem.

In general, one has to know in advance in which difference field extension
a simple closed form exists. 
To make work easier, the implementation provides the possibility that
appropriate extensions are searched for automatically.

The following two examples show how the automatic extension feature can
be applied to summation problems.

\subsubsection*{Finding a manual extension}

Applying Karr's algorithm on the double sum (\ref{doubleSumInExt}) 

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{doubleSum}=  \\
\noalign{\vspace{0.5ex}}
\hspace{1.em} \Muserfunction{DefineSum}[\Muserfunction{DefineHNumber}[k]/(k\RawWedge 2-1),\{k,2,n\}]\\
\MathEnd{MathArray}}
\dispSFoutmath{\sum _{k=2}^{n}\Big(\frac{{H_k}}{-1+{k^2}}\Big)}
\end{CellGroup}

\noindent
the following result is found with the automatic extension feature:

\begin{CellGroup}
\dispSFinmath{\Muserfunction{KReduce}[\Mvariable{doubleSum},\Mvariable{TowerSuggestion}->\Mvariable{True}]//\Mfunction{Simplify}}
\dispSFoutmath{
\frac{-2 \big(1+4 n+2 {n^2}\big) {H_n}+n (1+n) \Big(7+4 \sum _{{{\iota }_1}=2}^{n}\Big(\frac{-1+2 \iota _{1}^{2}}{2 (-1+{{\iota }_1}) \iota _{1}^{2}}\Big)\Big)}{4 n (1+n)}}
\end{CellGroup}

\noindent
Looking closer at the suggested extension
$$\sum_{i=2}^n\frac{2i-1}{2(i-1)i^2}=\frac{1}{2}\left(\sum_{i=2}^n\frac{1}{i-1}+
\sum_{i=2}^n\frac{1}{i^2}-\sum_{i=2}^n\frac{1}{i}\right)$$
from the partial fraction decomposition one sees immediately that this sum 
can be expressed by the harmonic numbers of
first and second order. This observation justifies the use of the manual
extension $\HNumberII{n}$, as it was done in section \ref{DFExt}.
 
\subsubsection*{Automatic extension in two steps}

The following expression consisting of four nested sums will be simplified by
using Karr's algorithm twice with the automatic extension feature.

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{quadrupleSum}=\Muserfunction{DefineSum}[\Muserfunction{DefineSum}[\Mvariable{DefineSum}[  \\
\noalign{\vspace{0.5ex}}
\hspace{4.em} 1/\Muserfunction{DefineHNumber}[i],\{i,1,k\}],\{k,1,n\}],  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \{n,2,m\}]\\
\MathEnd{MathArray}}
\dispSFoutmath{\sum _{n=2}^{m}\Big(\sum _{k=1}^{n}\Big(\sum _{i=1}^{k}\Big(\frac{1}{{H_i}}\Big)\Big)\Big)}
\end{CellGroup}
\newpage
\noindent
In the first step an expression is found
consisting of terms with at most three nested sums.

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{tripleSum}=  \\
\noalign{\vspace{0.5ex}}
\hspace{1.em} \Muserfunction{KReduce}[\Mvariable{quadrupleSum},\Mvariable{TowerSuggestion}->\Mvariable{True}]//  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \Mvariable{Simplify}\\
\MathEnd{MathArray}}
\dispSFoutmath{\MathBegin{MathArray}{l}
(1+m) \sum _{{{\iota }_1}=1}^{m}\Big(\frac{1}{{H_{{{\iota }_1}}}}\Big)+(1+m) \sum _{{{\iota }_1}=1}^{m}\Big(-\frac{{{\iota }_1}}{{H_{{{\iota }_1}}}}\Big)+  \\
\noalign{\vspace{2.6875ex}}
\hspace{1.em} \sum _{{{\iota }_1}=2}^{m}\Big(\frac{{{\iota }_1} \Big(-1+{{\iota }_1}+{H_{{{\iota }_1}}} \sum _{{{\iota }_2}=1}^{{{\iota }_1}}\Big(\frac{1}{{H_{{{\iota }_2}}}}\Big)\Big)}{{H_{{{\iota }_1}}}}\Big)\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
In the second step Karr's algorithm returns a term 
with at most two nested sums.

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Muserfunction{KReduce}[\Mvariable{tripleSum},  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} m,\Mvariable{TowerSuggestion}->\Mvariable{True},\Mvariable{Level}->2]//  \\
\noalign{\vspace{0.5ex}}
\hspace{1.em} \Mvariable{Simplify}\\
\MathEnd{MathArray}}
\dispSFoutmath{\MathBegin{MathArray}{l}
\frac{1}{2 {H_m}}\Big(2 (-1+m) m+  \\
\noalign{\vspace{2.ex}}
\hspace{3.em} {H_m} \Big(-2+(1+m) (2+m) \sum _{{{\iota }_1}=1}^{m}\Big(\frac{1}{{H_{{{\iota }_1}}}}\Big)+2 (1+m) \sum _{{{\iota }_1}=1}^{m}\Big(-\frac{{{\iota }_1}}{{H_{{{\iota }_1}}}}\Big)-  \\
\noalign{\vspace{1.98958ex}}
\hspace{5.em} \sum _{{{\iota }_1}=2}^{m}\Big(-\frac{(1+{H_{{{\iota }_1}}} (-4+{{\iota }_1})) (-1+{{\iota }_1}) {{\iota }_1}}{{H_{{{\iota }_1}}} (-1+{H_{{{\iota }_1}}} {{\iota }_1})}\Big)\Big)\Big)\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
The higher the value of option \MathTerm{Level} is set, the more the chances 
are increased to find an appropriate extension.  But this also increases the
required time and space resources.


\section{Definite summation}

I have extended Karr's algorithm in order to deal also with 
definite summation. I
will demonstrate some features of my Mathematica package 
with a concrete example. 
In \cite{krattenthaler} the following identity pops up:
\begin{multline}\label{definiteExp}
\sum _{k=1}^{n}\frac{{\HNumber{k}}\ (3+k+n){!}\ {{(-1)}^{{k}}}\ {{(-1)}^{{{-1+n}}}}}{(1+k){!}\ (2+k){!}\ (-k+n){!}}
+\\
\frac{(n){!}}{(3+n){!}}\sum_{k=1}^{n}-\frac{(3+k+n){!}\ {{(-1)}^{{k}}}\
  (1-(2+n)\ {{(-1)}^{{n}}})}{k\ {{(1+k){!}}^2}\ (-k+n){!}}=(2+n)(-1)^n-2.
\end{multline}

\noindent
With my package one not only can prove this identity 
automatically but even is able to {\it find} 
the closed form 
$$(2+n)(-1)^n-2.$$

\newpage

In the following the two sums on the left hand side of (\ref{definiteExp}) 
are considered separately.

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{mySum1}=\Muserfunction{DefineSum}[\Muserfunction{DefinePower}[-1,k]\ \Muserfunction{DefinePower}[-1,n-1] \\
\noalign{\vspace{0.5ex}}
\hspace{3.em} \Muserfunction{DefineFactorial}[n+k+3]/(\Muserfunction{DefineFactorial}[k+1]  \\
\noalign{\vspace{0.5ex}}
\hspace{6.em} \Muserfunction{DefineFactorial}[k+2]\Muserfunction{DefineFactorial}[n-k])  \\
\noalign{\vspace{0.5ex}}
\hspace{3.em} \Muserfunction{DefineHNumber}[k],\{k,1,n\}]  \\
\MathEnd{MathArray}}
\dispSFoutmath{\sum _{k=1}^{n}\Big(\frac{{H_k}\ (3+k+n){!_.}\ {{(-1)}^{{k_.}}}\ {{(-1)}^{{{-1+n}_.}}}}{(1+k){!_.}\ (2+k){!_.}\ (-k+n){!_.}}\Big)}
\end{CellGroup}

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{mySum2}=\Muserfunction{DefineSum}[-\Muserfunction{DefinePower}[-1,k]  \\
\noalign{\vspace{0.5ex}}
\hspace{3.em} \Muserfunction{DefineFactorial}[n+k+3](1-\Muserfunction{DefinePower}[-1,n](n+2))/  \\
\noalign{\vspace{0.5ex}}
\hspace{4.em} (k\ \Muserfunction{DefineFactorial}[k+1]\RawWedge 2\Muserfunction{DefineFactorial}[n-k]),  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \{k,1,n\}]\\
\MathEnd{MathArray}}

\dispSFoutmath{\sum _{k=1}^{n}\Big(-\frac{(3+k+n){!_.}\ {{(-1)}^{{k_.}}}\ (1-(2+n)\ {{(-1)}^{{n_.}}})}{k\ {{(1+k){!_.}}^2}\ (-k+n){!_.}}\Big)}
\end{CellGroup}

\noindent
Especially, in section \ref{mySum1Exp} I will demonstrate the basic 
procedure to solve definite summation problems with my Mathematica package, 
whereas
in section \ref{mySum2Exp} I focus on some technical details 
one has to take into account to find closed forms.

\subsection{A closed form of \MathTerm{mySum1}}\label{mySum1Exp}

\subsubsection*{Finding a recurrence}

First a recurrence is found that is satisfied by \MathTerm{mySum1}.

\begin{CellGroup}
\dispSFinmath{\Mvariable{rec1}=\Muserfunction{GenerateRecurrence}[\Mvariable{mySum1}]//\Mfunction{Simplify}}
\dispSFoutmath{\MathBegin{MathArray}{l}
\big\{n\ (1+n)\ (2+n)\ (3+n)\ (4+n)\ (-1+n)!\   \\
\noalign{\vspace{0.604167ex}}
\hspace{3.em} \big(-(9+2\ n)\ \big(8+6\ n+{n^2}\big)\ \Muserfunction{SUM}[n]+\\
\hspace{5.em}(9+2\ n)\ \big(13+8\ n+{n^2}\big)\ \Muserfunction{SUM}[1+n]+  \\
\noalign{\vspace{0.770833ex}}
\hspace{5.em} \big(30+42\ n+17\ {n^2}+2\ {n^3}\big)\ \Muserfunction{SUM}[2+n]-  \\
\noalign{\vspace{0.770833ex}}
\hspace{5.em} (3+n)\ \big(25+15\ n+2\ {n^2}\big)\ \Muserfunction{SUM}[3+n]\big)==  \\
\noalign{\vspace{0.770833ex}}
\hspace{2.em} 2\ {{(-1)}^n}\ (9+2\ n)\ \big(35+24\ n+4\ {n^2}\big)\ (4+n)!\big\}\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
The idea how to find a recurrence is based on Zeilberger's creative 
telescoping method \cite{zeilberger}. Although Karr's original summation 
algorithm was already capable to carry out creative telescoping, 
nobody has noticed this possibility until now.


\subsubsection*{Solving the recurrence}
In the second step, solutions of the recurrence are computed.
As \MathTerm{mySum1} depends on the harmonic numbers,
it can be expected that the solutions for its recurrence also consist 
of terms of the harmonic numbers. Consequently the solution space is extended
manually via \MathTerm{Tower$->\{\HNumber{n}\}$}.

\newpage

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{recSol1}=\Muserfunction{SolveRecurrence}[\Mvariable{rec1},\Muserfunction{SUM}[n],  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \Mvariable{Tower}->\{\HNumber{n}\}]\\
\MathEnd{MathArray}}
\dispSFoutmath{\MathBegin{MathArray}{l}
\big\{\{0,1\},\big\{0,\frac{3-{n^2}+4\ {H_n}+6\ n\ {H_n}+2\ {n^2}\ {H_n}}{(1+n)\ (2+n)}\big\},\big\{0,\frac{1}{4}\ (2+n)\ {{(-1)}^{{n_.}}}\big\},  \\
\noalign{\vspace{1.44792ex}}
\hspace{-1.em} \big\{1,\frac{\big(16-13\ {n^2}-5\ {n^3}+32\ {H_n}+64\ n\ {H_n}+40\ {n^2}\ {H_n}+8\ {n^3}\ {H_n}\big)\ {{(-1)}^{{n_.}}}}{4\ (1+n)\ (2+n)}\big\}\big\}\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
This has to be interpreted as follows:
Karr's algorithm delivers three linear independent solutions for the  
homogeneous version of the recurrence, namely
\begin{align*}
1, && \frac{3-{n^2}+4\ {\HNumber{n}}+6\ n\ {\HNumber{n}}+2\ {n^2}\ {\HNumber{n}}}{(1+n)\
  (2+n)}, && \frac{1}{4}\ (2+n)\ {{(-1)}^{{n_.}}}
\end{align*}
and one particular solution of the inhomogeneous recurrence itself:
$$\frac{\big(16-13\ {n^2}-5\ {n^3}+32\ {\HNumber{n}}+64\ n\ {\HNumber{n}}+40\ {n^2}\ {\HNumber{n}}+8\
  {n^3}\ {\HNumber{n}}\big)\ {{(-1)}^{{n_.}}}}{4\ (1+n)\ (2+n)}.$$

\subsubsection*{Finding the linear combination}

Finally, the closed form of \MathTerm{mySum1} is that linear combination of the
homogeneous solutions plus the inhomogeneous solution which has exactly 
the same initial values as \MathTerm{mySum1}. This is also computed
automatically: 

\begin{CellGroup}
\dispSFinmath{\Mvariable{solution1}=\Muserfunction{FindLinearCombination}[\Mvariable{recSol1},\Mvariable{mySum1}]}
\dispSFoutmath{\MathBegin{MathArray}{l}
-1-\frac{3-{n^2}+4\ {H_n}+6\ n\ {H_n}+2\ {n^2}\ {H_n}}{(1+n)\ (2+n)}+\frac{1}{4}\ (2+n)\ {{(-1)}^{{n_.}}}+  \\
\noalign{\vspace{1.44792ex}}
\hspace{1.em} \frac{\big(16-13\ {n^2}-5\ {n^3}+32\ {H_n}+64\ n\ {H_n}+40\ {n^2}\ {H_n}+8\ {n^3}\ {H_n}\big)\ {{(-1)}^{{n_.}}}}{4\ (1+n)\ (2+n)}\\
\MathEnd{MathArray}}
\end{CellGroup}


\subsection{A Closed form of \MathTerm{mySum2}}\label{mySum2Exp}

\subsubsection*{Finding a recurrence}

Similar to \MathTerm{mySum1} a recurrence of order $2$ for the
second sum is computed.

\begin{CellGroup}
\dispSFinmath{\Mvariable{rec2}=\Muserfunction{GenerateRecurrence}[\Mvariable{mySum2},\Mvariable{RecOrder}->2]}
\dispSFoutmath{\MathBegin{MathArray}{l}
\big\{-n\ (1+n)\ (3+n)\ (1+3\ {{(-1)}^n}+{{(-1)}^n}\ n)\   \\
\noalign{\vspace{0.604167ex}}
\hspace{4.em} (-1+4\ {{(-1)}^n}+{{(-1)}^n}\ n)\ \big(28+15\ n+2\ {n^2}\big)\ (-1+n)!\ \Muserfunction{SUM}[n]+  \\
\noalign{\vspace{0.604167ex}}
\hspace{3.em} 6\ n\ (1+n)\ {{(3+n)}^2}\ (-1+2\ {{(-1)}^n}+{{(-1)}^n}\ n)\   \\
\noalign{\vspace{0.666667ex}}
\hspace{4.em} (-1+4\ {{(-1)}^n}+{{(-1)}^n}\ n)\ (-1+n)!\ \Muserfunction{SUM}[1+n]+  \\
\noalign{\vspace{0.5ex}}
\hspace{3.em} n\ (1+n)\ (3+n)\ (-1+2\ {{(-1)}^n}+{{(-1)}^n}\ n)\   \\
\noalign{\vspace{0.604167ex}}
\hspace{1.em} (1+3\ {{(-1)}^n}+{{(-1)}^n}\ n)\ \big(10+9\ n+2\ {n^2}\big)\ (-1+n)!\ \Muserfunction{SUM}[2+n]==  \\
\noalign{\vspace{0.666667ex}}
\hspace{2.em} -2\ (-1+2\ {{(-1)}^n}+{{(-1)}^n}\ n)\ (1+3\ {{(-1)}^n}+{{(-1)}^n}\ n)\   \\
\noalign{\vspace{0.604167ex}}
\hspace{3.em} (-1+4\ {{(-1)}^n}+{{(-1)}^n}\ n)\ \big(35+24\ n+4\ {n^2}\big)\ (4+n)!\big\}\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
Here the order of the recurrence we were looking for is specified by the 
option \MathTerm{RecOrder $->$ 2}. By default - as in the previous example for
\MathTerm{mySum1} - the algorithm starts looking for a recurrence of 
order one and increases the order step by step if it does not succeed in 
finding a recurrence of the current order. 

\subsubsection*{Solving the recurrence}

In the second step, the following solutions for the recurrence are found.

\begin{CellGroup}
\dispSFinmath{\MathBegin{MathArray}{l}
\Mvariable{recSol2}=  \\
\noalign{\vspace{0.5ex}}
\hspace{1.em} \Muserfunction{SolveRecurrence}[\Mvariable{rec2},\Muserfunction{SUM}[n],\Mvariable{Tower}->\{\Muserfunction{DefineHNumber}[n]\},  \\
\noalign{\vspace{0.5ex}}
\hspace{2.em} \Mvariable{plusBound}->1,\Mvariable{WithMinusPower}->\Mvariable{True}]\\
\MathEnd{MathArray}}
\dispSFoutmath{\MathBegin{MathArray}{l}
\big\{\{0,2+n-{{(-1)}^{{n_.}}}\},\big\{0,16-6\ {n^2}-{n^3}+  \\
\noalign{\vspace{0.770833ex}}
\hspace{3.em} {{(-1)}^{{n_.}}}+28\ n\ {{(-1)}^{{n_.}}}+23\ {n^2}\ {{(-1)}^{{n_.}}}+8\ {n^3}\ {{(-1)}^{{n_.}}}+{n^4}\ {{(-1)}^{{n_.}}}\big\},  \\
\noalign{\vspace{0.9375ex}}
\hspace{1.em} \big\{1,\frac{1}{28}\ \big(260-150\ {n^2}-39\ {n^3}+336\ {H_n}+  \\
\noalign{\vspace{1.01042ex}}
\hspace{2.em} 616\ n\ {H_n}+336\ {n^2}\ {H_n}+56\ {n^3}\ {H_n}-325\ {{(-1)}^{{n_.}}}+365\ {n^2}\ {{(-1)}^{{n_.}}}+  \\
\noalign{\vspace{0.604167ex}}
\hspace{2.em} 228\ {n^3}\ {{(-1)}^{{n_.}}}+39\ {n^4}\ {{(-1)}^{{n_.}}}-672\ {H_n}\ {{(-1)}^{{n_.}}}-1568\ n\ {H_n}\ {{(-1)}^{{n_.}}}-  \\
\noalign{\vspace{0.604167ex}}
\hspace{2.em} 1288\ {n^2}\ {H_n}\ {{(-1)}^{{n_.}}}-448\ {n^3}\ {H_n}\ {{(-1)}^{{n_.}}}-56\ {n^4}\ {H_n}\ {{(-1)}^{{n_.}}}\big)\big\}\big\}\\
\MathEnd{MathArray}}
\end{CellGroup}

\noindent
To handle this problem, I have generalized Karr's algorithm for 
solving linear difference equations of any order.
For this generalization a denominator bounding is used
which was developed by Bronstein \cite{bronstein}.
Unfortunately, there is still an unsolved problem
concerning degree boundings of some solution parts. 
Nevertheless one can find all possible solutions by an incremental strategy, 
i.e., increasing step by step the degree boundings for each computation 
attempt. 
By increasing the value of the \MathTerm{plusBound} option these boundings are
raised. Consequently the chances are higher to find more solutions. For this
strategy, however, more time and space resources are required.
In this example the value of \MathTerm{plusBound} is set at least as
high as $1$. By default - as in the previous example for
\MathTerm{mySum1} - the value of \MathTerm{plusBound} is set to $1$.

In addition, we have to consider the algebraic relation
$$((-1)^k)^2=1$$
to find all solutions for the recurrence. In order to take care of this,
the option \MathTerm{WithMinusPower} is set to \MathTerm{True}.

\subsubsection*{Finding the linear combination of \MathTerm{mySum2}}

Finally the closed form of \MathTerm{mySum2} can be found as before:

\begin{CellGroup}
\dispSFinmath{\Mvariable{solution2}=\Muserfunction{FindLinearCombination}[\Mvariable{recSol2},\Mvariable{mySum2}]}
\dispSFoutmath{\MathBegin{MathArray}{l}
-(3+n)\ \big(-1+3\ n+2\ {n^2}-\big(-1+6\ n+7\ {n^2}+2\ {n^3}\big)\ {{(-1)}^{{n_.}}}+  \\
\noalign{\vspace{0.770833ex}}
\hspace{3.em} 2\ \big(2+3\ n+{n^2}\big)\ {H_n}\ (-1+(2+n)\ {{(-1)}^{{n_.}}})\big)\\
\MathEnd{MathArray}}
\end{CellGroup}


\subsection{The closed form of \MathTerm{mySum1}+\MathTerm{mySum2}}

In the end, by combining the closed forms of \MathTerm{mySum1} and 
\MathTerm{mySum2} the closed form of the original summation 
problem (\ref{definiteExp}) is computed.

\begin{CellGroup}
\dispSFinmath{\Mvariable{solution1}+\Mvariable{solution2}/((n+1)(n+2)(n+3))//\Mfunction{Simplify}}
\dispSFoutmath{-2+(2+n)\ {{(-1)}^{{n_.}}}}
\end{CellGroup}

\begin{thebibliography}{GKP94}

\bibitem[Bro99]{bronstein}
M.~Bronstein.
\newblock On solutions of linear ordinary difference equations in their
  coefficient field.
\newblock Technical Report 3797, {I}{N}{R}{I}{A} Sophia Antipolis, November
  1999.

\bibitem[Coh65]{cohn}
R.~M. Cohn.
\newblock {\em Difference Algebra}.
\newblock Interscience Publishers, John Wiley \& Sons, 1965.

\bibitem[CS98]{chyzak}
F.~Chyzak and B.~Salvy.
\newblock Non-commutative elimination in ore algebras proves multivariate
  identities.
\newblock {\em J. Symbolic Computation}, 26(2):187--227, 1998.

\bibitem[FK99]{krattenthaler}
M.~Fulmek and C.~Krattenthaler.
\newblock The number of rhombus tilings of a symmetric hexagon which contains a
  fixed rhombus on the symmetric axis, {I}{I}.
\newblock {\em European Journal of Combinatorics}, 1999.
\newblock to appear.

\bibitem[GKP94]{knuth}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics}, chapter 6. Special Numbers, exercise 69,
  page 316.
\newblock Addison Wesley Publishing Company, 2nd edition, 1994.

\bibitem[Gos78]{gosper}
R.~W. Gosper.
\newblock Decision procedures for indefinite hypergeometric summation.
\newblock {\em Proc. Nat. Acad. Sci. U.S.A.}, 75:40--42, 1978.

\bibitem[Kar81]{karr}
M.~Karr.
\newblock Summation in finite terms.
\newblock {\em Journal of the ACM}, 28:305--350, 1981.

\bibitem[Kar85]{karr2}
M.~Karr.
\newblock Theory of summation in finite terms.
\newblock {\em J. Symbolic Computation}, 1:303--315, 1985.

\bibitem[PR97]{riese}
P.~Paule and A.~Riese.
\newblock A {M}athematica q-analogue of {Z}eilberger's algorithm based on an
  algebraically motivated aproach to q-hypergeometric telescoping.
\newblock In M.~Ismail and M.~Rahman, editors, {\em Special Functions, q-Series
  and Related Topics}, volume~14, pages 179--210. Fields Institute Toronto,
  AMS, 1997.

\bibitem[PS95]{pauleschorn}
P.~Paule and M.~Schorn.
\newblock A {M}athematica version of {Z}eilberger's algorithm for proving
  binomial coefficient identities.
\newblock {\em J. Symbolic Computation}, 20:673--698, 1995.

\bibitem[Sch99]{schneider}
C.~Schneider.
\newblock An implementation of {K}arr's summation algorithm in {M}athematica.
\newblock Technical Report SFB 99-15, Johannes Kepler University Linz, August
  1999.

\bibitem[Zei90]{zeilberger}
D.~Zeilberger.
\newblock A fast algorithm for proving terminating hypergeometric identities.
\newblock {\em Discr. Math.}, 80:207--211, 1990.

\end{thebibliography}



\end{document}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
