\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: