\documentclass[12pt,reqno]{amsart}

%\let\proof\undefined
%\let\endproof\undefined



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

\usepackage{amssymb, amsbsy, amsfonts,color}
\usepackage{amsmath, amsthm,epsfig}
\usepackage{a4wide}
\usepackage{latexsym}

\allowdisplaybreaks[4]

\input{xy}
\xyoption{all}


\voffset-0.6cm

\textheight=25cm

\numberwithin{equation}{part}


%I use the following headings
%\pagestyle{headings}

%\input macros.tex

\newcommand{\SigmaP}{{\sf Sigma}}
\newcommand{\sigmaSE}{$\Sigma^*$}
\newcommand{\sigmaE}{$\Sigma$}
\newcommand{\piE}{$\Pi$}
\newcommand{\pisiSE}{$\Pi\Sigma^*$}
\newcommand{\sigmaDSE}{$\mathit\Sigma^*$}
\newcommand{\piDE}{$\mathit\Pi$}
\newcommand{\pisiDSE}{$\mathit\Pi\Sigma^*$}
\newcommand{\qBin}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}
\newcommand{\vleq}{\vee{\text{\scriptsize$|$}}}
\newcommand{\SH}{{S}}
\newcommand{\fct}[3]{{#1:#2 \to #3}}
\newcommand{\dfield}[2]{({#1},{#2})}
\newcommand{\HNumber}[1]{H_{#1}}
\newcommand{\HNumberII}[1]{{H}^{(2)}_{#1}}
\newcommand{\HNumberO}[2]{{H}^{({#1})}_{#2}}

\newcommand{\const}[2]{{\rm const}_{#2}{#1}}
\newcommand{\notion}[1]{{\it #1}}
\newcommand{\vect}[1]{\boldsymbol{#1}}
\newcommand{\vecT}[1]{({#1})}
\newcommand{\Pochhammer}[2]{(#1)_{#2}}
\newcommand{\AddBinom}[2]{\begin{Bmatrix}#1\\#2\end{Bmatrix}}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\detB}[1]{\det\big(#1\big)}
\newcommand{\Mat}[1]{\big(#1\big)}


\newcommand{\VV}{\mathbb{V}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}

\newcounter{linectr}
\newenvironment{myEnumerate}{\begin{list}{(\arabic{linectr})}{\usecounter{linectr}
\labelwidth1ex\itemsep0ex\labelsep1ex\leftmargin2ex\parskip0.0cm\topskip0cm\partopsep0cm
\listparindent0ex}}{\end{list}}

\newenvironment{myQuote}{\begin{list}{\labelitemi}{\leftmargin0.3cm\labelsep0.0cm\labelwidth0.0cm\rightmargin0.3cm}\item[]\sf\small}{\end{list}\normalsize}

\newcommand{\SExample}[1]{\begin{center}
\hspace*{-0.2cm}\fcolorbox[rgb]{0,0,0}{1,1,1}{\hspace*{0.15cm}
\begin{minipage}{15.8cm}{\bf Sigma session.} #1\end{minipage}}
\end{center}}

\newcommand{\myBox}[1]{{\begin{center}
\fcolorbox[rgb]{0,0,0}{1,1,1}{
\begin{minipage}{15.7cm}\small#1\end{minipage}}
\end{center}
}}


\newenvironment{TRemark}{\begin{trem}}{\qed\end{trem}}
\newenvironment{SRemark}{\noindent{\bf Sigma manual.}}{\medskip}
\newenvironment{Remark}{\begin{Rem}}{\qed\end{Rem}}
\newenvironment{Proof}[1]{\noindent Proof: #1}{\qed}

\theoremstyle{plain}
%\newtheorem*{Theorem}{Theorem}
%\newtheorem{Lemma}{Lemma}[section]
%\newtheorem{Corollary}{Corollary}[section]
%\newtheorem{Proposition}{Proposition}[section]
%\newtheorem{Conjecture}{Conjecture}[section]
\theoremstyle{definition}
%\newtheorem{Definition}{Definition}[section]
%\newtheorem{Notation}{Notation}[section]
\newtheorem{exam}{Example}[section]
\newtheorem{sexam}{Sigma~session}
\newtheorem{trem}{{Technical~remark}}
%\newtheorem{Rem}{Remark}[section]
%\newtheorem{Assumption}{Assumption}[section]
%\newtheorem{Algorithm}{Algorithm}[section]
%\newtheorem{Specification}{Specification}[section]
%\newtheorem{Situat}{Situatation}[section]



\newenvironment{Example}{\begin{exam}}{\qed\end{exam}}


\makeatletter
% #1: pre length
% #2: post length
% #3: content
\def\@problemhead#1#2#3{%
 \par\kern-\parskip\kern#1
 \vbox\bgroup
 \hbox to\hsize{\hrulefill\raise1pt\hbox{\fbox{$\mathstrut$ #3\ }}\hrulefill}%
 \kern#2\par\kern-\parskip
}
% #1: pre length
% #2: post length
\def\@problemtail#1#2{%
 \par\kern-\parskip\kern#1
 \hbox to\hsize{\hrulefill}
 \egroup
 \kern#2\par\kern-\parskip
}
\newenvironment{ProblemSpec}[1]{\@problemhead{2pt}{0pt}{#1}\small}{\@problemtail{-8pt}{2pt}}
\makeatother


\newcounter{mmacnt}
\def\restartmma{\setcounter{mmacnt}{0}}
\restartmma \catcode`|=\active
\def|#1|{\mathrm{#1}}
\catcode`|=12
\newenvironment{mma}{
 \par\smallskip
 \catcode`|=\active
 \parskip=0pt\parindent=0pt % locally
 \small
 \def\In##1\\{%
   \def\linebreak{\hfill\break\null\qquad}%
   \refstepcounter{mmacnt}
   \hangindent=2.5em\hangafter=0
   \leavevmode
   \llap{\tiny\sffamily In[\arabic{mmacnt}]:=\kern.5em}%
   \mathversion{bold}\footnotesize$\tt\bf\displaystyle##1$\normalsize
   \mathversion{normal}\par
 }%
 \def\Print##1\\{%
   \def\linebreak{\hfill\break}%
   \hangindent=2.5em\hangafter=0
   \leavevmode\footnotesize ##1\par}%
 \def\Out##1\\{%
   \def\linebreak{$\hfill\break\null\hfill$}%
   \kern\abovedisplayskip\par
   \hangindent=2.5em\hangafter=0
   \leavevmode
   \llap{\tiny\sffamily Out[\arabic{mmacnt}]=\kern.5em}
   \footnotesize$\displaystyle\tt##1$\normalsize\hfill\null\par
   \kern\belowdisplayskip
 }%
 \def\Warning##1##2\\{%
   \def\linebreak{\hfill\break}%
   \hangindent=2.5em\hangafter=0
   \leavevmode
   {\scriptsize##1 : ##2}\par}%
}{%
 \par\smallskip
}

\newcommand{\myIn}[1]{{\sffamily In[#1]}}
\newcommand{\myOut}[1]{{\sffamily Out[#1]}}

\def\MLabel#1{{\refstepcounter{mmacnt}\label{#1}}\addtocounter{mmacnt}{-1}}

\newcommand{\MText}[1]{\textbf{\ttfamily#1}}




\title{Symbolic Summation Assists Combinatorics}



\author{Carsten Schneider}
\address{Research Institute for Symbolic Computation\\
J. Kepler University Linz\\
A-4040 Linz, Austria}
\email{Carsten.Schneider@risc.uni-linz.ac.at}
\thanks{Supported by the SFB-grant F1305 and the grant P16613-N12
of the Austrian FWF}

%\keywords{...}


\begin{document}


\begin{abstract}
We present symbolic summation tools in the context of difference
fields that help scientists in practical problem solving. Throughout
this article we present multi-sum examples which are related to
combinatorial problems.
\end{abstract}


\maketitle


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 56 \rms (2007), Article~B56b\hfill}
\def\thepage{}
%
%

\vspace*{-0.5cm}

\section{Introduction}
At the $56^\text{th}$ S\'eminaire Lotharingien de Combinatoire I
presented in a series of talks the summation package
\SigmaP~\cite{Schneider:04c}. Starting with Karr's summation
algorithm~\cite{Karr:81,Karr:85,Schneider:00}, the discrete analogue
of Risch's integration algorithm~\cite{Risch:69,Risch:70}, I
developed various extensions and generalizations to tackle
non-trivial multi-sum problems. In this survey article, which is
based on this presentation, I illustrate all these new features. The
article consists of three parts. Each of them can be considered
independently.

\smallskip

In the {\it first part} we introduce the summation principles of
\SigmaP: ``telescoping'', ``creative
telescoping''~\cite{Zeilberger:91}, and ``solving recurrences''.
Multi-sum examples
from~\cite{Andrews:85,Graham:94,Zhang:99,Krattenthaler:00,Schneider:06a,Schneider:06b,Schneider:06c}
illustrate all these techniques.

In the {\it second part} we explain how the summation principles are
formulated in difference fields and we demonstrate how the
underlying algorithms work. We present our algorithmic
extensions~\cite{Schneider:T01,Schneider:04a,Schneider:04b,Schneider:05a,Schneider:05b,Schneider:05c,Schneider:05f,Schneider:06d,Schneider:06e,Schneider:06f}.

In the {\it third part} we show how \SigmaP\ can be applied for even
a wider class of multi-sums which covers big parts of
$\partial$-finite and holonomic
sequences~\cite{Zeilberger:90a,Chyzak:98,Chyzak:00}. Examples
from~\cite{Abramowitz:65,AequalB,Schneider:05e} illustrate how our
methods~\cite{Schneider:05d} find recurrences for such sums. We
demonstrate that one can derive also differential equations with
these techniques.

\smallskip

I am very grateful to Volker~Strehl and Christian~Krattenthaler who
gave me the opportunity to present my work at the S\'eminaire
Lotharingien de Combinatoire. I would like to thank the referee for
his very careful reading and his valuable comments and suggestions.

\vspace*{0.7cm}

\setcounter{part}{1}

\noindent{\bf\Large Part 1. Symbolic summation methods and
applications}

\vspace*{0.3cm}

Inspired by~\cite{AequalB} the summation package \SigmaP\ is based
on the paradigms of telescoping, creative telescoping, and solving
recurrences. We show in the frame of \SigmaP\ how one can apply
these summation principles to attack multi-sum problems.

\vspace*{-0.4cm}

\section{The summation principles}\label{Sec:Paradigms}

\noindent Given an indefinite sum $\displaystyle
S(n)=\sum_{k=0}^nf(k)$ we are interested in solving the following
problem.

\vspace*{-0.2cm}

\begin{ProblemSpec}{Telescoping}
\noindent{\bf Given} $f(k)$; {\bf find} $g(k)$ such that

\vspace*{-0.4cm}

\begin{equation}\label{Equ:SeqTele}
g(k+1)-g(k)=f(k).
\end{equation}
\end{ProblemSpec}

\noindent Then summing~\eqref{Equ:SeqTele} over $k$ (under the
assumption that~\eqref{Equ:SeqTele} holds for all $0\leq k\leq n$)
gives
$$g(n+1)-g(0)=\sum_{k=0}^nf(k).$$
There are various algorithms on the market for such input sequences
$f(k)$, like Gosper's algorithm~\cite{Gosper:78} for hypergeometric
terms\footnote{$f(k)$ is hypergeometric (resp. $q$-hypergeometric),
if $\frac{f(k+1)}{f(k)}$ is a rational function in $k$ (resp. in
$q^k$).}; for theoretical insight see~\cite{Paule:95} and for
implementations see~\cite{PauleSchorn:95,Koepf:95,Abramov:04}.
Similarly, there are variations for $q$-hy\-pergeometric
terms~\cite{Koornwinder:93,PauleRiese:97,Koepf:99}, or
generalizations for the mixed case~\cite{Bauer:99}.

More generally, the summation package~\SigmaP\ can deal with
rational expressions in terms of indefinite nested sums and
products. The underlying telescoping
algorithms~\cite{Schneider:04a,Schneider:05f,Schneider:06f} extend
Karr's summation algorithm~\cite{Karr:81}.

\SExample{Consider the indefinite sum $S(n)=\sum_{k=m}^nf(k)$ with
the summand $f(k)=\qBin{k}{m}q^k\sum_{i=1}^k\frac{q^i}{1-q^i}$;
$\qBin{k}{m}$ denotes the $q$-binomial. Then we can simplify $S(n)$
as follows. After loading \SigmaP\ into the computer algebra system
Mathematica

\begin{mma}
\In << Sigma.m \\
\Print Sigma - A summation package by Carsten Schneider
\copyright\ RISC-Linz\\
\end{mma}

\noindent we insert $S(n)$({\tt=mySum}):

\begin{mma}
\In mySum = SigmaSum[SigmaqBinomial[q, k, m]SigmaPower[q,k]\newline
\hspace*{1cm}SigmaSum[SigmaPower[q,i]/(1 - SigmaPower[q, i]),
\{i,1,k\}], \{k, m, n\}]\\
\Out \sum_{k=m}^n\qBin{k}{m}q^k\sum_{i=1}^k\frac{q^i}{1-q^i}\\
\end{mma}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL CARSTEN SCHNEIDER}{\SMALL SYMBOLIC SUMMATION ASSIST COMBINATORICS}
%
%



\begin{SRemark}
The basic functions {\tt SigmaSum} and {\tt SigmaProduct} are used
to describe all indefinite nested sums and products that can be
expressed in our setting. Additional functions, like {\tt
SigmaPower}, {\tt SigmaBinomial}, or {\tt SigmaqBinomial} are just
shortcuts. E.g., our q-binomial can be described by
$\qBin{k}{m}=\prod_{i=m+1}^k\frac{1-\prod_{j=1}^iq}{1-\prod_{j=1}^iq^i/q^m}$
for $k\geq m$.
\end{SRemark}

\noindent Then we find the following closed form by the function
call

\begin{mma}\MLabel{MMA:qIndef}
\In SigmaReduce[mySum]\\
\Out \frac{q^m}{(q
q^m-1)^2}\Big(q(q^n-q^m)+(qq^m-1)(qq^n-1)\sum_{i=1}^n\frac{q^i}{1-q^i}\Big)\qBin{n}{m}\\
\end{mma}

\vspace*{-0.2cm}

Internally, \SigmaP\ computes
$$g(k)=\frac{q^m-q^k}{(q
q^m-1)^2}\Big(-qq^m+(1-qq^m)\sum_{i=1}^k\frac{q^i}{1-q^i}\Big)\qBin{k}{m}$$
which satisfies~\eqref{Equ:SeqTele} for all $m\leq k\leq n$. Note
that the correctness can be verified independently of the
computation steps. Namely, by using the relations
$\sum_{i=1}^{k+1}\frac{q^i}{1-q^i}=\sum_{i=1}^k\frac{q^i}{1-q^i}+\frac{qq^{k}}{1-qq^k}$
and $\qBin{k+1}{m}=\frac{1-qq^k}{1-qq^k/q^{m}}\qBin{k}{m}$ we can
verify with simple polynomial arithmetic that~\eqref{Equ:SeqTele}
holds for all $0\leq m\leq k\leq n$. Hence
summing~\eqref{Equ:SeqTele} over $k$ produces
$$\sum_{k=m}^n\qBin{k}{m}q^k\sum_{i=1}^k\frac{q^i}{1-q^i}=q^m\qBin{n+1}{m+1}
\Big(\sum_{i=1}^{n+1}\frac{q^i}{1-q^i}-\frac{q^{m+1}}{1-q^{m+1}}\Big)$$
which is equivalent to~\myOut{\ref{MMA:qIndef}}; compare
identity~\cite[(2.5)]{Andrews:85}. Multiplying by $1-q$ and sending
$q$ to $1$ yields the identity~\cite[(6.70)]{Graham:94}
$$\sum_{k=m}^n\tbinom{k}{m}H_k=\binom{n+1}{m+1}\Big(H_{n+1}-\frac{1}{m+1}\Big)$$
where $H_k=\sum_{i=1}^k\frac{1}{i}$ denotes the harmonic numbers.
}

In most cases one fails to find such a $g(k)$. If $f(k)$ depends on
an additional parameter $n$, we can apply a more flexible paradigm.


\begin{ProblemSpec}{Zeilberger's creative telescoping}
\noindent{\bf Given} $f(n,k)$ and $\delta\in\NN$; {\bf find}
$c_0(n),\dots,c_{\delta}(n)$, free of $k$, and $g(n,k)$ such that
\begin{equation}\label{Equ:SeqCrea}
g(n,k+1)-g(n,k)=c_0(n)f(n,k)+\dots+c_{\delta}(n)f(n+\delta,k).
\end{equation}
\end{ProblemSpec}


\noindent With creative telescoping we can attack definite sums as
follows: Given a sum $S(n)=\sum_{k=0}^mf(n,k)$ where $m$ might
depend linearly on $n$, find a solution $c_0(n),\dots,c_{\delta}(n)$
and $g(n,k)$ of~\eqref{Equ:SeqCrea}; here one usually starts with
$\delta=0$ (which is nothing else than telescoping), and increases
$\delta$ step by step. If one finds such a solution
for~\eqref{Equ:SeqCrea} which holds for all $0\leq k\leq n$, then
summing~\eqref{Equ:SeqCrea} over $k$ gives a recurrence relation of
the form
\begin{equation*}
q(n)=c_0(n)S(n)+\dots+c_{\delta}(n)S(n+\delta).
\end{equation*}

As it turns out, all the telescoping algorithms mentioned above can
be extended to creative telescoping. This was observed the first
time by Zeilberger~\cite{Zeilberger:91} for Gosper's algorithm; for
theoretical insight see~\cite{PauleStrehl:95} and for
implementations and additional details
see~\cite{PauleSchorn:95,Abramov:04,Gerhard:04}. For the
$q$-hypergeometric, the mixed and the holonomic case
see~\cite{Koornwinder:93,PauleRiese:97,Koepf:99,Bauer:99,Chyzak:00};
different generalizations can be found in~\cite{Kauers:06}.

Moreover, as recognized in~\cite{Schneider:00}, Karr's algorithm and
all our extensions can be used for creative telescoping; see
Sections~\ref{Sec:CreaTeleAlg} and~\ref{Sec:CreaRefined}.

\medskip

%\begin{SExample}%\label{Exp:HBExp}
\SExample{Consider the definite sum $S(n)$ given by
\begin{mma}
\In hSum=\sum_{k=0}^n\binom{n}{k}H_k;\\
\end{mma}

\noindent where the binomial $\binom{n}{k}$ is interpreted as
$\prod_{i=1}^k\frac{n+1-i}{i}$. By typing in

\begin{mma}\MLabel{MMA:HBRec}
\In hRec=GenerateRecurrence[hSum]\\
\Out\{4(1+n) SUM[n]-2(3+2n)SUM[n+1]+(2+n)SUM[n+2]==1\}\\
\end{mma}

\noindent we compute the recurrence {\tt hRec} for $S(n)=${\tt
SUM[n]}. Note that by the proof certificate
\begin{mma}\MLabel{MMA:hSumVSpace}
\In CreativeTelescoping[hSum][[2]]\\
\Out\{4\,(1+n),-2\,(3+2\,n),2+n,\tfrac{(1+n)\,(-2+k-n+(2\,k-2\,k^2+k\,n)H_k)\,\binom{n}{k})}{(1-k+n)\,(2-k+n)}\}\\
\end{mma}
\noindent we can conclude that the recurrence is correct: Given
$f(n,k):=\binom{n}{k}H_k$ and
\begin{equation}\label{Equ:HCreaSol}
\begin{aligned}
c_0(n)&:=4\,(1+n),\quad c_1(n):=-2\,(3+2\,n),\quad c_2(n):=2+n,\\
g(n,k)&:=\tfrac{(1+n)\,(-2+k-n+(2\,k-2\,k^2+k\,n)H_k)\,\binom{n}{k})}{(1-k+n)\,(2-k+n)},
\end{aligned}
\end{equation}
we show that~\eqref{Equ:SeqCrea} with $\delta=2$ holds for all
$0\leq k\leq n$ as follows. Represent in~\eqref{Equ:SeqCrea} the
expressions $g(n,k+1)$ and $f(n+i,k)$ for $i=1,2$ in terms of $H_k$
and $\binom{n}{k}$. This is possible by $H_{k+1}=H_k+1/(k+1)$ and
the fact that $\binom{n}{k}$ is hypergeometric in $n$ and $k$. E.g.,
we can write $g(n,k+1)=\frac{(n+1)(nH_k-2kH_k-1)}{n-k+1}$. Given
this representation, verify~\eqref{Equ:SeqCrea} by polynomial
arithmetic. Summing~\eqref{Equ:SeqCrea} over $k$
gives~\myOut{\ref{MMA:HBRec}}.

\medskip

Similarly, we can compute for the following $q$-version of $S(n)$ a
recurrence:

\begin{mma}\MLabel{MMA:qHSum}
\In qhSum=\sum_{k=0}^nq^{k(k-1)/2}\qBin{n}{k}\sum_{i=1}^k\frac{q^i}{1-q^i};\\
\end{mma}


\begin{mma}\MLabel{MMA:qHBRec}
\In qhRec=GenerateRecurrence[qhSum]\\
\Out
\{\left(q^{n+1}+q\right)\left(q^{n+1}-1\right)\left(q^{n+1}+1\right)SUM[n]-\newline
\hspace*{1cm}\left(q^{n+1}+1\right)\left(2q^{n+2}-q-1\right)SUM[n+1]+\left(q^{n+2}-1\right)SUM[n+2]==-q^{2n+3}\}\\
\end{mma}
}
%\vspace*{-0.6cm}
%\end{SExample}

\medskip

\noindent{\it Remark.} For the general input class of \SigmaP\ no
criteria are known which guarantee the existence of a creative
telescoping solution~\eqref{Equ:SeqCrea} for sufficiently large
$\delta$. So far there is only one way: try it out. For
($q$-)hypergeometric terms necessary and sufficient conditions are
available; see~\cite{Abramov:03b,Abramov:05,Chen:05}. Restricting to
proper hypergeometric terms upper bounds for $\delta$ are known
which guarantee solutions; see~\cite[Thm.~4.4.1]{AequalB}
and~\cite{Zeilberger:05b}.


\medskip


In many applications a recurrence is just the desired result, see
e.g.~\myOut{\ref{MMA:PadeRec}}. If one is interested in a more
explicit representation, the following attempt might help.

\begin{ProblemSpec}{Solving recurrences}
\noindent{\bf Given} a recurrence

\vspace*{-0.55cm}

\begin{equation}\label{Equ:SeqRec}
a_0(n)S(n)+\dots+a_{r}(n)S(n+r)=f(n);
\end{equation}
{\bf find} a particular solution $p(n)$ and solutions of the
homogeneous version, say $h_1(n),\dots,h_{d}(n)$.
\end{ProblemSpec}

\noindent If we compute sufficiently\footnote{If $a_0(n)$,
$a_{r}(n)$ have only finitely many zeros, there are exactly $r$
linearly independent solutions of~\eqref{Equ:SeqRec} with $f(n)=0$,
see~\cite[Thm.~8.2.1]{AequalB}; here we identify sequences, if they
agree from some point on.} many solutions, we can find constants
$k_0,\dots,k_{d}$ such that $S(i)=k_0h_0(i)+\dots+
k_{d}h_{d}(i)+p(i)$ holds for $i\in\{0,\dots,{d}-1\}$. This implies
that
\begin{equation}\label{Equ:SeqLinComb}
S(n)=k_0h_0(n)+\dots+k_{d}h_{d}(n)+p(n),\quad n\geq0.
\end{equation}

\SExample{
%\begin{SExample}%\label{Exp:Exp:HBExp2}
We solve the recurrence {\tt hRec} from~\myOut{\ref{MMA:HBRec}} by
typing in

\begin{mma}\MLabel{MMA:hRecSolve}
\In recSol = SolveRecurrence[hRec[[1]], SUM[n]]\\
\Out
\{\{0,\prod_{i=1}^n2\},\{0,\Big(\prod_{i=1}^n2\Big)\sum_{i=1}^n\frac{1}{i}\},\{1,-\Big(\prod_{i=1}^n2\Big)\sum_{i=1}^n\frac{1}{i\prod_{j=1}^i2}\}\}\\
\end{mma}

\vspace*{-0.2cm}

\begin{SRemark}
The~$0$s in the first two entries tell us that $h_0(n)=2^n$ and
$h_1(n)=2^n\sum_{i=1}^nH_n$ are solutions of the homogeneous version
of {\tt hRec}, and the~$1$ in the third entry indicates that
$p(n)=-2^n\sum_{i=1}^n\frac{1}{2^ii}$ is a particular solution of
{\tt hRec} itself.
\end{SRemark}

\noindent Finally, using the first two initial values we combine the
solutions in the form~\eqref{Equ:SeqLinComb}:

\begin{mma}
\In FindLinearCombination[recSol,hSum,2]\vspace*{-0.1cm}\\
\Out\Big(\prod_{i=1}^n2\Big)\sum_{i=1}^n\frac{1}{i}-\Big(\prod_{i=1}^n2\Big)\sum_{i=1}^n\frac{1}{i\prod_{j=1}^i2}\\
\end{mma}

\noindent This leads to~\cite[Equ.~(39)]{Schneider:03}

\vspace*{-0.3cm}

\begin{equation}\label{Equ:BHId}
\sum_{k=0}^n\binom{n}{k}H_k=2^nH_n-2^n\sum_{i=1}^n\frac{1}{2^i i}.
\end{equation}
\noindent Completely analogously we solve the recurrence {\tt qhRec}
from~\myOut{\ref{MMA:qHBRec}} by the function call

\begin{mma}\MLabel{MMA:hqRecSolve}
\In recSol = SolveRecurrence[qhRec[[1]], SUM[n]]\\
\Out \{\{0,\prod_{i=1}^n\frac{q+q^i}{q}\},
\{0,\Big(\prod_{i=1}^n\frac{q+q^i}{q}\Big)\sum_{i=1}^n\frac{q^i}{1-q^i}\},
\{1,-\Big(\prod_{i=1}^n\frac{q+q^i}{q}\Big)\sum_{i=1}^n\frac{q^i}{(1-q^i)
\prod_{j=1}^i\frac{q+q^j}{q}}\}\}\\
\end{mma}

\vspace*{-0.1cm}

\noindent and find the following combination for our
sum~\myIn{\ref{MMA:qHSum}}:

\begin{mma}
\In FindLinearCombination[recSol,qhSum,2]\\
\Out
\Big(\prod_{i=1}^n\frac{q+q^i}{q}\Big)\sum_{i=1}^n\frac{q^i}{1-q^i}
-\Big(\prod_{i=1}^n\frac{q+q^i}{q}\Big)\sum_{i=1}^n\frac{q^i}{(1-q^i)\prod_{j=1}^i\frac{q+q^j}{q}}\\
\end{mma}

\noindent With the $q$-shifted factorial
$(-1,q)_n=\prod_{i=1}^n\frac{q+q^i}{q}$ we arrive at the identity
\begin{equation}
\sum_{k=0}^nq^{\tbinom{k}{2}}\qBin{n}{k}\sum_{i=1}^k\frac{q^i}{1-q^i}=(-1,q)_n\left(\sum_{i=1}^n\frac{q^i}{1-q^i}-\sum_{i=1}^n\frac{q^i}{(-1,q)_i(1-q^i)}\right);
\end{equation}
note that we rediscover identity~\eqref{Equ:BHId} by multiplying it
with $1-q$ and sending $q$ to $1$.

}

In \SigmaP\ the coefficients $a_i(n)$ and the inhomogeneous part
$f(n)$ of the recurrence~\eqref{Equ:SeqRec} can be rational
expressions in terms of nested sums and products. Given such a
recurrence, we can find the class of d'Alembertian
solutions~\cite{Abramov:94}, a subclass of Liouvillian
solutions~\cite{Singer:99}; typical examples are given
in~\myOut{\ref{MMA:hRecSolve}} and~\myOut{\ref{MMA:hqRecSolve}}.
Here the crucial point is that those solutions are indefinite nested
sums and products which fit in the input class of our telescoping
algorithms. Hence, given such a
representation~\eqref{Equ:SeqLinComb}, \SigmaP\ can help to simplify
its right-hand side. If we are lucky, we can end up with a ``closed
form'' for $S(n)$.


\smallskip

The interaction of the different summation principles for a definite
sum can be summarized by the Sigma-summation
spiral~\cite{Schneider:04c}: \small
$$\xymatrix@R=1.6cm@C=0.1cm{
&\txt{definite sum} \ar @/^1.5pc/[rd]|<(.55){\txt{creative telescoping}}&\\
\txt{simplified solutions}\ar @/^1.5pc/[ru]|<(.3){\txt{combination
of solutions}} &&\txt{recurrence}\ar @/^1.5pc/[ld]|<(.3){\txt{solving}}\\
&\txt{d'Alembertian solutions}\ar
@/^1.5pc/[lu]|<(.5){\txt{telescoping}}& }$$ \normalsize


\section{Applications of the Sigma-summation spiral}

Subsequently, we will illustrate all the aspects from
Section~\ref{Sec:Paradigms} by concrete examples.

\subsection{Quadratic Pad\'e approximation}
In~\cite{Weideman:05} A. Weideman looks for polynomials $r_n(x)$,
$s_n(x)$ and $t_n(x)$ with degree at most $n$ such that
\begin{equation}\label{Equ:PadeApp}
r_n(x)\,(\log x)^2+s_n(x)\,\log(x)+t_n(x)=O((x-1)^{3n+2}).
\end{equation}
He discovers that those polynomials can be written as a linear
combination of the polynomials
\begin{align*} A_n(x)=\sum_{k=0}^n \binom{n}{k}^3
(-x)^k,\; B_n(x)=\sum_{k=0}^n \Big[ \frac{d}{dk}
\binom{n}{k}^3\Big](-x)^k,\; C_n(x)=\sum_{k=0}^n \Big[
\frac{d^2}{dk^2} \binom{n}{k}^3 \Big]  (-x)^k.
\end{align*}
Evaluations at $x=1$ and $n=0,1,...$ show empirically how the
polynomials $A_n(x)$, $B_n(x)$ and $C_n(x)$ must be combined to get
$r_n(x)$, $s_n(x)$ and $t_n(x)$. To obtain a rigorous proof for the
guessed representation, it turns out that one has to show the key
identity
\begin{equation}\label{Equ:PadeIIId}
\sum_{k=0}^n(-1)^k\binom{n}{k}^3\Big(
3(H_{n-k}-H_k)^2+H_{n-k}^{(2)}+H_{k}^{(2)}\Big)=0;
\end{equation}
$H_k^{(2)}=\sum_{i=1}^k\frac{1}{i^2}$ are the harmonic numbers of
second order. In~\cite{Schneider:06a} \SigmaP\ played the main role
in proving this identity: Namely, we can compute the following
recurrence

\begin{mma}\MLabel{MMA:PadeRec}
\In GenerateRecurrence[\sum_{k=0}^n(-1)^k\binom{n}{k}^3\Big(
3(H_{n-k}-H_k)^2+H_{n-k}^{(2)}+H_{k}^{(2)}\Big)]\\
\Out \{(n+2)^2{SUM}[n+2]+3 (3 n+2)(3 n+4) {SUM}[n]==0\}\\
\end{mma}

\noindent for the left-hand side of~\eqref{Equ:PadeIIId}. Since this
sum is zero for $n=0,1$, it must evaluate to zero for all $n\geq0$.
We remark that together with the creative telescoping solution given
in~\cite{Schneider:06a} the correctness of the recurrence can be
checked as for~\eqref{Equ:HCreaSol}.

\noindent Later C.~Krattenthaler~\cite{Kratt:03} derived a
non-algorithmic proof based on differentiation and hypergeometric
transformations. W.~Chu~\cite{Chu:05} presents different techniques
to show~\eqref{Equ:PadeIIId}.


As illustrated in~\cite{Schneider:06b} we cannot only prove
identity~\eqref{Equ:PadeIIId}, but we can discover it. To be more
precise, we find with our machinery the identities

\vspace*{-0.5cm}

\begin{align}
\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3 H_kH_{2n-k}
=&\tfrac{(3n)!(-1)^n}{n!n!n!}\frac{1}{12}\big(3 H_n^2-6 H_nH_{3n}+3
H_{3n}^2+H_n^{(2)}\nonumber\\[-0.3cm]
&+12H_{2n}(H_{2n}+H_n-H_{3n})+4 H_{2n}^{(2)}-3
H_{3n}^{(2)}\big),\label{PadeIII:Id1}\\[-0.1cm]
\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3
H_k^2=&\tfrac{(3n)!(-1)^n}{n!n!n!}\frac{1}{12}\big(3H_n^2-6 H_n H_{3n}+3
H_{3n}^2-H_n^{(2)}\nonumber\\[-0.3cm]
&+12H_{2n}(H_{2n}+H_n-H_{3n})+2 H_{2n}^{(2)}-3H_{3n}^{(2)}\big),\label{PadeIII:Id2}\\[-0.1cm]
\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3H^{(2)}_k
=&\frac{1}{2}\tfrac{(3n)!(-1)^n}{n!n!n!}(H^{(2)}_n+H^{(2)}_{2n}).\label{PadeIII:Id3}
\end{align}

\vspace*{-0.1cm}

\noindent Then it is easy to see that the right combination of these
sums, see~\eqref{Equ:PadeIIId}, evaluates to zero. E.g., we discover
identity~\eqref{PadeIII:Id1} as follows. Given the sum

\vspace*{-0.1cm}

\begin{mma}\MLabel{MMA:PadeIIIFindSum}
\In {mySum}=\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3 H_{k}H_{2n-k};\\
\end{mma}

\vspace*{-0.1cm}

\noindent we compute the recurrence relation

\begin{mma}\MLabel{MMA:GenRecDeptNumber}
\In rec=GenerateRecurrence[mySum,SimplifyByExt \rightarrow DepthNumber][[1]]\vspace*{-0.1cm}\\
\Out -18(n+1)^2(n+2)(2n+1)^2(2n+3)(3n+1)^2(3n+2)^2(108n^3+495n^2+752
n+378){SUM}[n]+\newline
6(n+1)^3(n+2)(2n+1)(2n+3)(3888n^7+29484n^6+92250n^5+153369n^4+145192n^3+77561n^2+21420n+2316){SUM}[n+1]+
2(n+1)^3(n+2)^4(2n+1)(2n+3)^2 (108n^3+171n^2+86n+13){SUM}[n+2]
\newline \vspace*{-0.2cm}\hspace*{-0.5cm}==\Big(2519424
n^{11}+26873856
   n^{10}+126618552 n^9+347114322
   n^8+613953513 n^7+734258088n^6+\newline
\hspace*{0.5cm}  604816090 n^5+342574260
   n^4+130558875 n^3+31842320 n^2+4469856
   n+273984\Big)\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3\\
\end{mma}

\vspace*{-0.1cm}

\begin{SRemark}
With the option {\tt SimplifyByExt$\to$DepthNumber} we search for a
recurrence with sum extensions which have less objects in the
summand than the input summand. In our case we find a recurrence of
order two by using the sum
$e(n)=\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3$. Without this option,
i.e., without using $e(n)$, we compute a rather big recurrence
relation of order $3$.
\end{SRemark}

Since the automatically found sum $e(n)$ is definite, it does not
fit into the input class of recurrences that \SigmaP\ can handle.
But with our machinery, as described above, we find
$e(n)=\frac{(-1)^n(3n)!}{{n!}^3}$ which is a particular instance of
Dixon's identity~\cite{Dixon:03}; see
also~\cite[Example~6.4.4]{AequalB}. Hence, we can simplify the
recurrence by replacing $e(n)$ with $\frac{(-1)^n(3n)!}{{n!}^3}$:

\begin{mma}
\In
{rec=rec/.}\textstyle\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^3\to\frac{(-1)^n(3n)!}{{n!}^3};\\
\end{mma}

\noindent This recurrence can be handled with \SigmaP. Namely, we
compute the solutions


\begin{mma}\MLabel{MMA:PadeRecSol}
\In {recSol = SolveRecurrence[rec, SUM[n]]}\\
\Out \{\{0,\frac{(-1)^n(3n)!}{{n!}^3}\},
\{0,\frac{(-1)^n(3n)!}{{n!}^3}\sum_{k=1}^n\frac{108 k^3-153 k^2+68
k-10}{k (2 k-1)(3 k-2) (3 k-1)}\},\{1,
\frac{1}{18}\frac{(-1)^n(3n)!}{{n!}^3}\vspace*{-0.2cm}\newline
\hspace*{-1.2cm}\text{\tiny$\sum_{k=1}^n$}\tfrac{-4860 k^6+13770
k^5-15849 k^4+9504k^3-3148 k^2+550 k-40+(k (2 k-1) (3 k-2) (3 k-1)
\left(108
   k^3-153 k^2+68 k-10\right))\displaystyle\text{\tiny$\sum_{i=1}^k$}\tfrac{108 i^3-153 i^2+68 i-10}{i (2 i-1)(3 i-2) (3 i-1)}}{k^2 (2 k-1)^2
(3 k-2)^2 (3 k-1)^2}\}\}\\
\end{mma}

\vspace*{-0.2cm}

\noindent Here it is important to mention that this type of
solutions (d'Alembertian solutions) are just in the input class of
\SigmaP's telescoping algorithms; we get the following
simplification:


\begin{mma}\MLabel{MMA:PadeRecSolSimpl}
\In {recSol = SigmaReduce[recSol, n,
SimplifyByExt\to Depth]}\\
\Out \{\{0,\frac{(-1)^n(3n)!}{{n!}^3}\},
\{0,\frac{(-1)^n(3n)!}{{n!}^3}\sum_{k=1}^n\frac{108 k^3-153 k^2+68
k-10}{k (2 k-1)(3 k-2) (3 k-1)}\},\vspace*{-0.1cm}\newline
\{1,\frac{1}{36}\frac{(-1)^n(3n)!}{{n!}^3}\Big(\Big(\sum_{i=1}^n\tfrac{108
i^3-153 i^2+68 i-10}{i (2 i-1)(3 i-2) (3
i-1)}\Big)^2+\sum_{k=1}^n\tfrac{1944
k^6-5508k^5+6399 k^4-3960 k^3+1388 k^2-260 k+20}{k^2 (2 k-1)^2(3 k-2)^2 (3 k-1)^2}\Big)\}\}\\
\end{mma}

\begin{SRemark}
With the option {\tt SimplifyByExt$\to$Depth} we look for
appropriate sum extensions in order to reduce the nested depth; see
Section~\ref{SubSec:RefinedTeles}. E.g., the second sum
in~\myOut{\ref{MMA:PadeRecSolSimpl}} has been computed in order to
represent the expression in~\myOut{\ref{MMA:PadeRecSol}} by single
nested sums.
\end{SRemark}



\noindent Using the first two initial values we combine the
solutions to represent~\myIn{\ref{MMA:PadeIIIFindSum}} as follows.

\begin{mma}\MLabel{MMA:PadeBadClForm}
\In {closedForm = FindLinearCombination[recSol, mySum, 2]}\\
\Out
\frac{1}{36}\frac{(-1)^n(3n)!}{{n!}^3}\Big(\Big(\sum_{i=1}^n\tfrac{108
i^3-153 i^2+68 i-10}{i (2 i-1)(3 i-2) (3
i-1)}\Big)^2+\sum_{k=1}^n\tfrac{1944
k^6-5508k^5+6399 k^4-3960 k^3+1388 k^2-260 k+20}{k^2 (2 k-1)^2(3 k-2)^2 (3 k-1)^2}\Big)\\
\end{mma}

\noindent Next, we split our sums so that their denominators consist
of irreducible polynomials:

\begin{mma}
\In {closedForm = SigmaReduce[closedForm, n,
SimpleSumRepresentation\to True]}\\
\Out
\frac{(-1)^n(3n)!}{{n!}^3}\Big(-\frac{1}{4}\sum_{k=1}^n\frac{1}{(3k-1)^2}
-\frac{1}{4}\sum_{k=1}^n\frac{1}{(3k-2)^2}
+\frac{1}{3}\sum_{k=1}^n\frac{1}{(2k-1)^2}
+\frac{5}{36}\sum_{k=1}^n\frac{1}{k^2}+\newline
\hspace*{1cm}\Big(\frac{5}{6}\sum_{k=1}^n\frac{1}{k}
+\sum_{k=1}^n\frac{1}{2k-1}-\frac{1}{2}\sum_{k=1}^n\frac{1}{2k-2}-\frac{1}{12}\sum_{k=1}^n\frac{1}{2k-3}\Big)^2\Big)\\
\end{mma}

\noindent By some cosmetic rewriting we end up with the right-hand
side of~\eqref{PadeIII:Id1}:


\begin{mma}
\In {closedForm = SigmaReduce[closedForm, n,Tower\to\{H_n,H_{2
n},H_n^{(2)},H_{2n}^{(2)},H_{3 n},H_{3 n}^{(2)}\}]}\\
\Out \frac{(-1)^n(3n)!}{{n!}^3}\frac{1}{12}\Big(3 H_n^2+12 H_{2 n}
   H_n+12 H_{2 n}^2+3 H_{3 n}^2+\left(-6
   H_n-12 H_{2 n}\right) H_{3
   n}+H_n^{(2)}+4 H_{2 n}^{(2)}-3 H_{3n}^{(2)}\Big)\\
\end{mma}

\subsection{A variation of Calkin's sum}\label{Sec:VarCalkin}
Alternating versions of Calkin's identity~\cite{Calkin:94}

\vspace*{-0.3cm}

\begin{equation}\label{Calkin3Id}
\sum_{k=0}^n\bigg(\sum_{j=0}^k\binom{n}{j}\bigg)^3=
\frac{n}{2}\,8^n+8^n-\frac{3\,n}{4}\,2^n\,\binom{2\,n}{n}
\end{equation}
have been considered in~\cite{Zhang:99}. We supplement this
collection with the following sum.
\begin{mma}
\In mySum=\sum_{k=0}^{2n}(-1)^k\Big(\sum_{j=0}^k\binom{2n}{j}\Big)^3;\\
\end{mma}
\noindent Following our \SigmaP-spiral we compute a recurrence

\begin{mma}
\In rec=GenerateRecurrence[mySum][[1]]\\
\Out=(2 n+3)(11 n+3)(n+1)^2SUM[n+2]+\left(946 n^4+2799
   n^3+2907 n^2+1252 n+180\right)SUM[n+1]+\newline
\hspace*{-1cm}96n(3n+1)(3 n+2)(11n+14)SUM[n]==16 \left(5005
n^4+16897 n^3+20210
   n^2+9884n+1512\right)\Bigg(\sum_{k=0}^{2n}\binom{2n}{k}\Bigg)^3\\
\end{mma}

\vspace*{-0.6cm}

\begin{mma}
\In rec=rec/.\textstyle\Big(\sum_{k=0}^{2n}\binom{2n}{k}\Big)^3\to64^n;\\
\end{mma}

\noindent solve the recurrence in terms of d'Alembertian solutions

\begin{mma}\MLabel{MMA:Calkin3}
\In recSol = SolveRecurrence[rec, SUM[n]]\\
\Out \{\{0,\prod_{i=2}^n-\frac{32 (i-1)}{2
i-1}\},\{0,\Big(\prod_{i=2}^n-\frac{32 (i-1)}{2
i-1}\Big)\sum_{i=1}^n\frac{i^3 (11
i-8)\prod_{j=1}^i\frac{3(2j-1)(3j-2)(3j-1)}{32 j^3}}{(2 i-1)(3i-2)(3i-1)}\},\{1,\frac{64^n}{2}\}\}\\
\end{mma}


\vspace*{-0.2cm}

\noindent and combine the solutions


\begin{mma}
\In FindLinearCombination[recSol, mySum, n, 2, MinInitialValue\to1]\\
\Out \frac{64^n}{2}+\frac{64}{3}\Big(\prod_{i=2}^n-\frac{32 (i-1)}{2
i-1}\Big)\sum_{i=1}^n\frac{i^3 (11
i-8)\prod_{j=1}^i\frac{3(2j-1)(3j-2)(3j-1)}{32 j^3}}{(2 i-1)(3i-2)(3i-1)}\\
\end{mma}

\noindent Finally, after some rewriting we arrive, for $n\geq1$, at
the identity
\begin{equation}
\sum_{k=0}^{2\,n}(-1)^k \bigg(\sum_{j=0}^k
  \binom{2\,n}{j}\bigg)^3=\frac{64^n}{2}-\frac{(-1)^n}{16\,n}
\frac{64^n}{\binom{2\,n}{n}}
\sum_{i=0}^{n-1}(3+11\,i)\binom{2\,i}{i}^2\binom{3\,i}{i}64^{-i}.
\end{equation}




\subsection{A problem from the SLC'06}

At the SLC'06 Wenchang Chu showed in his talk various harmonic
number identities of the type~\eqref{PadeIII:Id1},
\eqref{PadeIII:Id2}, \eqref{PadeIII:Id3}  which he produced by
differentiating the Dougall-Dixon formula. Since he could not find
an evaluation of the sum
$S(n):=\sum_{k=0}^{2n+1}(-1)^k\binom{2n+1}{k}^3H^{(2)}_k$ in terms
of harmonic numbers, he posed this problem to \SigmaP. After some
seconds of computations \SigmaP\ could give the following answer:
\begin{equation}
S(n)=
\frac{(-1)^n(6n+1)(n!)^3(6n)!}{2(2n+1)^2((2n)!)^3(3n)!}\Big(-2+\sum_{i=1}^n\frac{(72i^2+36i+5)((2i)!)^3((3i)!)^2}{2i(2i+1)(6i+1)(i!)^6(6i)!}\Big);
\end{equation}
observe that the sum on the right-hand side cannot be expressed by
harmonic numbers. The derivation of the identity is based on the
\SigmaP-spiral: First we compute a recurrence
\begin{multline*}
-12 (2 n+3) (6 n+5) (6 n+7)(n+1)^3 S(n) -4 (2 n+3)^3
(n+1)^3S(n+1)\\[-0.2cm]
=3 (3 n+1) (3 n+2) \left(72 n^2+180
n+113\right)\frac{(-1)^n(3n)!}{(n!)^3},$$
\end{multline*}
then we solve this recurrence and find its right-hand side.




\subsection{A problem from rhombus tilings}\label{SubSec:Rhombus}

Define
\begin{align*}
S_n&:=\sum_{k=0}^{n-1}\frac{{(-1)}^{n+k}(n+k+4)!H_{k+1}}{(k+2)!
(k+3)!(n-k-1)!}&\text{and}&& T_n&:=\sum_{k=0}^{n-1}\frac{{(-1)}^k
(n+k+4)!}{(k+1){(k+2)!}^2(n-k-1)!}.
\end{align*}
Then in about four pages of highly non-trivial transformations the
following evaluation has been found
in~\cite[Lemma~26]{Krattenthaler:00}:
\begin{align*}
S_n&=\frac{-5-3 n}{(1+n)(2+n)}-2H_{n}+
(-1)^n\Big(\frac{5+2n-2n^2-n^3}{(1+n)(2+n)}+2(2+n) H_{n}\Big),\\
T_n&=1-9n-9n^2-2n^3+2(1+n)(2+n)(3+n){H_n}-(-1)^n.
\end{align*}
This finally shows that
$S_n+\frac{(1-{(-1)}^n(n+2))n!}{(n+3)!}T_n=(-1)^n(n+2)-2.$

As illustrated in~\cite{Schneider:04c} \SigmaP\ finds these results
in a straightforward manner by following the \SigmaP-spiral. Here it
is worthwhile to mention that $(-1)^n$ pops up with the algebraic
relation $((-1)^n)^2=1$; for more details see
Sections~\ref{SubSec:Pi} and~\ref{SubSec:AlgebraicExt}.



\subsection{Evaluation of a quadruple sum}

In 2004 Doron Zeilberger sent an email to Robin Pemantle and Herbert
Wilf with Cc to me:

\begin{myQuote}
Robin and Herb,\\
I am willing to bet that Carsten Schneider's SIGMA
package for handling sums with harmonic numbers (among others) can
do it in a jiffy. I am Cc-ing this to Carsten.\\
Carsten: please do it, and Cc- the  answer to me. -Doron
\end{myQuote}

\noindent Of course, I and \SigmaP\ were eager to win the bet for
Doron. So, ``we'' looked at Robin's problem attached in this email
which reads as follows:

\begin{myQuote}
I have a sum that, when I evaluate numerically, looks suspiciously
like it comes out to exactly 1. Is there a way I can automatically
decide this? The sum may be written in many ways, but one is:
\begin{equation*}
S:=\sum_{j,k =1}^\infty\frac{H_j (H_{k+1}-1)}{jk(k+1)(j+k)}.
\end{equation*}
\end{myQuote}

\noindent One week later I could reply~\cite{Schneider:05g}: the sum
is not exactly 1, but
\begin{equation}\label{Equ:ZetaEv}
S=- 4\zeta(2)-2\zeta(3)+4\zeta(2)\zeta(3)+2\zeta (5)=0.999222...
\end{equation}
Whereas the full details are given in~\cite{Schneider:06c} we
present here only the \SigmaP-part. Take the truncated version

\vspace*{-0.7cm}

$$S(a,b)=\sum_{k=1}^b\frac{H_{k+1}-1}{k(k+1)}
   \sum_{j=1}^a\frac{H_j}{j(j+k)},$$
i.e., $S=\lim_{a,b\rightarrow\infty}S(a,b)$. Then \SigmaP\ can find
a more appropriate sum representation of the inner sum following the
\SigmaP-spiral. Namely, we compute a recurrence

\begin{mma}
\In {rec=GenerateRecurrence[\sum_{j=1}^a\frac{H_j}{j(j+k)}, k][[1]]}\\
\Out (k+1) (a+k+1) (a+k+2)k^2 SUM[k]
-(k+1)^2(a+k+1)(a+k+2)(2k+1)SUM[k+1]+\newline
\hspace*{1cm}(k+1)^2(k+2)(a+k+1)(a+k+2)SUM[k+2]==a(a+k+2)+(-a-1) (k+1) H_a\\
\end{mma}

\noindent solve the recurrence

\begin{mma}\MLabel{MMA:0999RecSol}
\In {recSol=SolveRecurrence[rec, SUM[k]]}\\
\Out \{\{0,\frac{1}{k}\},\{0,\frac{
\sum_{i=2}^{k}\tfrac{1}{i-1}}{k}\},
\{1,\frac{1}{k}\sum_{j=2}^k\frac{\sum_{i=2}^{j}
\tfrac{-(a+1)H_a(i-1)+a(a+i)}{(-1+{i})(-1+a+{i})(a+ {i})}}{j-1}
\}\\
\end{mma}

\vspace*{-0.2cm}

\noindent simplify the solutions

\begin{mma}\MLabel{MMA:Zero9}
\In {SigmaReduce[recSol, k, SimpleSumRepresentation\to True, SimplifyByExt\to Depth]}\\
\Out
\{\{0,\frac{1}{k}\},\{0,\frac{\sum_{i=2}^{k}\frac{1}{i-1}}{k}\},
\{1,\frac{H_a}{(a+1)k}-\frac{(kH_a-1)}{k^2}\sum_{i=1}^k\frac{1}{a+i}-\frac{1}{k}\sum_{i=1}^k\frac{1}{i}\sum_{j=1}^i\frac{1}{a+j}+\newline
\hspace*{1cm}\frac{\sum_{i=2}^{k}\frac{1}{(i-1)^2}+
\big(\sum_{i=2}^{k}\frac{1}{i-1}\big)^2}{2k}
\}\\
\end{mma}

\vspace*{-0.2cm}

\noindent and combine the solutions to get the identity
\begin{equation*}
\sum_{j=1}^a\frac{H_j}{j(j+k)}=
\frac{kH_k^2-2H_k+kH^{(2)}_k+2kH^{(2)}_a}{2k^2}
-\frac{(kH_a-1)}{k^2}\sum_{i=1}^k\frac{1}{a+i}-\frac{1}{k}\sum_{i=1}^k\frac{1}{i}\sum_{j=1}^i\frac{1}{a+j}.
\end{equation*}
By simple limit considerations it follows
$\lim_{a,b\rightarrow\infty}S'(a,b)=S$ for
\begin{equation*}
S'(a,b):=\sum_{k=1}^b\frac{H_{k+1}-1}{k(k+1)}
   \frac{kH_k^2-2H_k+kH^{(2)}_k+2kH^{(2)}_a}{2k^2}.
\end{equation*}
\SigmaP\ can simplify $S'(a,b)$ further to
$S'(a,b)=A(a,b)+B(a,b)+C(a,b)$ where
\begin{align*}
A(a,b):=&\frac{1}{2{(b+1)}^2}\Big(6H_b+ 4bH_b+4H_b^2 +3bH_b^2+
   H_b^3+bH_b^3-6bH^{(2)}_a\\
&\quad\quad\quad+2H_b H^{(2)}_a+2bH_b H^{(2)}_a-2H^{(2)}_b-
7bH^{(2)}_b+H_bH^{(2)}_b+
   bH_bH^{(2)}_b\Big),\\
B(a,b):=&-\frac{2b^2}{{(b+1)}^2}\Big(H^{(2)}_a+H^{(2)}_b\Big),\\
C(a,b):=&(H^{(2)}_a-1)\sum_{i=1}^{b}\frac{H_i}{i^2}-\sum_{i=1}^{b}
   \frac{H_i^2}{i^3}+ \frac{1}{2}\sum_{i=1}^{b}\frac{H_i^3}{i^2}
   +\frac{1}{2}\sum_{i=1}^{b}\frac{H_iH^{(2)}_i}{i^2}.
\end{align*}
Since $\lim_{a,b\rightarrow\infty}A(a,b)=0$ and
$\lim_{a,b\rightarrow\infty}B(a,b)=-4\zeta(2)$, we get
$$S=\lim_{a,b\rightarrow\infty}S'(a,b)=-4\zeta(2)+\lim_{a,b\rightarrow\infty}C(a,b).$$
Now we can use, e.g.~\cite{Borwein:96,Flajolet:98}, and find
$\sum_{i=1}^{\infty}\frac{H_i}{i^2}=2\zeta(3)$,
$\sum_{i=1}^{\infty}\frac{H_i^2}{i^3} =-
\zeta(2)\zeta(3)+\frac{7}{2}\zeta(5)$,
$\sum_{i=1}^{\infty}\frac{H_i^3}{i^2}=\zeta(2)\zeta(3)+10\zeta(5)$,
and $\sum_{i=1}^{\infty}\frac{H_iH^{(2)}_i}{i^2}
=\zeta(2)\zeta(3)+\zeta(5)$. This proves~\eqref{Equ:ZetaEv}.

\smallskip

In~\cite{Prodinger:05} a computer-free proof is given. Conversely,
in~\cite{Schneider:06c} we show that the evaluation of such sums can
be handled by a more systematic approach to computer-proofs.

\vspace*{1cm}

\newpage

\stepcounter{part}

\noindent{\bf\Large Part 2. Summation in difference fields}

\vspace*{0.5cm}

This part is directed to readers, who are curious how \SigmaP\
works. In Sections~\ref{Sec:TeleInDFExp}--\ref{SubSec:AlgSketch} we
describe our (creative) telescoping method, which is the basis of
all our extensions and variations. By concrete examples we focus on
two main aspects: First, we explain how nested multi-sums can be
formulated in the so-called \pisiSE-fields. Given these notions we
can specify precisely, what type of nested multi-sums \SigmaP\ can
handle and where \SigmaP\ might run into problems. Second, we
demonstrate how the telescoping algorithm works.

Finally, in Section~\ref{Sec:Generalizations} we give an overview of
all summation problems that \SigmaP\ can handle.

\section{Concrete examples for telescoping and creative
telescoping}\label{Sec:TeleInDFExp}

We illustrate the basic strategy of our (creative) telescoping
method: (1)~Rephrase the problem in terms of difference fields,
(2)~apply the corresponding algorithm in the given difference field,
and (3)~interpret this result to get a solution for the original
problem. All other algorithms, see
Section~\ref{Sec:Generalizations}, follow the same strategy.


\subsection{A telescoping example} Given
$f(k)=H_k$, find a solution for~\eqref{Equ:SeqTele}. In order to
accomplish this task, \SigmaP\ constructs a difference field in
which the summation objects and the action of the shift operator
$\SH$ w.r.t.\ $k$  can be described properly. In our case, take the
rational function field $\FF:=\QQ(k)(h)$ over the rational numbers
$\QQ$ where $h$ represents $H_k$. Moreover, take the automorphism
$\fct{\sigma}{\FF}{\FF}$ defined by $\sigma(c)=c$ for all $c\in\QQ$
and
\begin{equation}\label{ExpHShift}
\begin{aligned}
\sigma(k)&= k+1&&\longleftrightarrow& \SH\,k&=k+1,\\
\sigma(h)&= h+\frac{1}{k+1}&&\longleftrightarrow&
\SH\,H_k&=H_k+\frac{1}{k+1}.
\end{aligned}
\end{equation}
By construction $\sigma$ reflects the action of the shift operator
on $k$ and $H_k$ in the field $\FF$. In a nutshell, our summation
objects are represented in difference fields.

\medskip

\noindent {\it Definition.} A difference field
$\dfield{\FF}{\sigma}$ is a field $\FF$ plus a field automorphism
$\fct{\sigma}{\FF}{\FF}$; in this article we restrict to fields of
characteristic zero.

\medskip

\noindent Next, we solve~\eqref{Equ:SeqTele} in our difference field
$\dfield{\FF}{\sigma}$, i.e., we look for a $g\in\FF$ such that
\begin{equation}\label{Equ:ExpTeleInQ(k)(h)}
\sigma(g)-g=h.
\end{equation}
In Section~\ref{SubSec:TeleAlg} we show how \SigmaP\ computes the
solution
\begin{equation}\label{Equ:ExpgSol}
g=(h-1)k\in\FF.
\end{equation}
Rephrasing the result in terms of our summation objects, we obtain
the solution $g(k)=(H_k-1)k$ for~\eqref{Equ:SeqTele}. By telescoping
we get $\sum_{k=1}^nH_k=(H_{n+1}-1)(n+1)$.

\medskip

Summarizing, telescoping~\eqref{Equ:SeqTele} can be formulated in a
difference field $\dfield{\FF}{\sigma}$ as follows:

\begin{ProblemSpec}{Telescoping in difference fields}
\noindent{\bf Given} $f\in\FF$ where $f$ represents $f(k)$; {\bf
find} $g\in\FF$ with
\begin{equation}\label{Equ:ExpTeleInF}
\sigma(g)-g=f.
\end{equation}
\end{ProblemSpec}


\subsection{A creative telescoping example} In order to get
the solution~\eqref{Equ:HCreaSol}, we proceed as follows. First, we
construct a difference field $\dfield{\FF}{\sigma}$ in which we can
describe $f(n,k)=\binom{n}{k}H_k$ with the shift $\SH$ in $k$.
Namely, take the rational function field $\FF:=\QQ(n)(k)(h)(b)$ with
the automorphism $\fct{\sigma}{\FF}{\FF}$ given by $\sigma(c)=c$ for
all $c\in\QQ(n)$ and
\begin{equation}\label{ExpBHShift}
\begin{aligned}
\sigma(k)&= k+1&&\longleftrightarrow&\SH\,k&=k+1,\\
\sigma(h)&= h+\frac{1}{k+1}&&\longleftrightarrow&\SH\,H_k&=H_k+\frac{1}{k+1},\\
\sigma(b)&=\frac{n-k}{k+1}\,b&&\longleftrightarrow&\SH\,\binom{n}{k}&=\frac{n-k}{k+1}\binom{n}{k}.
\end{aligned}
\end{equation}
Now observe that one can also represent $f(n+i,k)$ for $i\geq0$ in
$\FF$, e.g.,
\begin{equation}\label{Equ:fN+1DF}
\begin{aligned}
f(n,k)=\HNumber{k}\,\binom{n}{k}&\quad\longleftrightarrow\quad h\,b=:f_0\\
f(n+1,k)=
\frac{(n+1)\,\HNumber{k}\,\binom{n}{k}}{n+1-k}&\quad\longleftrightarrow\quad
\frac{(n+1)\,h\,b}{n+1-k}=:f_1\\
 f(n+2,k)=
\frac{(n+1)\,(n+2)\,\HNumber{k}\,\binom{n}{k}}{(n+1-k)\,(n+2-k)}
&\quad\longleftrightarrow\quad
\frac{(n+1)\,(n+2)\,h\,b}{(n+1-k)\,(n+2-k)}=:f_2.
\end{aligned}
\end{equation}

\noindent Then the creative telescoping problem~\eqref{Equ:SeqCrea}
with $\delta=2$ can be formulated in $\dfield{\FF}{\sigma}$ as
follows:\\
FIND $c_0,c_1,c_2\in\QQ(n)$ and $g\in\FF$ such that
\begin{equation}\label{Equ:hSumCreaEqu}
\sigma(g)-g=c_0f_0+c_1f_1+c_2f_2.
\end{equation}
\SigmaP\ computes the solution
\begin{align*}
c_0&:=4\,(1+n),& c_1&:=-2\,(3+2\,n),& c_2&:=2+n,&
g&:=\tfrac{(1+n)\,(-2+k-n+(2\,k-2\,k^2+k\,n)h)\,b)}{(1-k+n)\,(2-k+n)};
\end{align*}
representing this result in terms of $\binom{n}{k}$ and $H_k$
gives~\eqref{Equ:HCreaSol}.

\smallskip

Observe that the shift operator $\SH$ and automorphism $\sigma$ keep
$n$ fixed, i.e., $n$ is a constant. More generally, let
$\dfield{\FF}{\sigma}$ be a difference field. Then the set of
constants is defined by
$$\const{\FF}{\sigma}:=\{c\in\FF|\sigma(c)=c\}.$$
Since $\const{\FF}{\sigma}$ is a sub-field of $\FF$, we call
$\const{\FF}{\sigma}$ also the \notion{constant field} of
$\dfield{\FF}{\sigma}$; it is easy  to see that the rational numbers
$\QQ$ must be contained in $\const{\FF}{\sigma}$.\\
E.g., for the difference field $\dfield{\QQ(k)(h)}{\sigma}$ the
constant field is $\QQ$ and for $\dfield{\QQ(n)(k)(h)}{\sigma}$ the
constant field is $\QQ(n)$; see Section~\ref{SubSec:PiSigma}.


For a given difference field $\dfield{\FF}{\sigma}$ with constant
field $\KK$ creative telescoping reads as follows:

\medskip

\begin{ProblemSpec}{Creative telescoping in difference fields}
\noindent{\bf Given} $f_0,\dots,f_{\delta}\in\FF$ where $f_i$
corresponds to $f(n+i,k)$; {\bf find} $c_i\in\KK$, not all zero, and
$g\in\FF$ with
\begin{equation}\label{Equ:CreaProblemDF}
\sigma(g)-g=c_0\,f_0+\dots+c_{\delta}\,f_{\delta}.
\end{equation}
\end{ProblemSpec}

\medskip

Subsequently we explain in details how the ideas from above can be
handled by the computer: we show how one can represent $f(k)$ (resp.
$f(n+i,k)$ for $i=0\dots\delta$) in a difference field and we
present an algorithm for (creative) telescoping. As it turns out,
the construction of an appropriate difference field and telescoping
are closely related.

\section{A constructive theory of \pisiSE-extensions}\label{SubSec:PiSigma}

In \SigmaP\ the automatic construction of difference fields relies
on the fact that indefinite nested sums and products can be adjoined
step by step in form of difference field extensions.

\medskip

\noindent{\it Definition.} Let $\dfield{\EE}{\sigma}$ and
$\dfield{\FF}{\sigma'}$ be difference fields. We call
$\dfield{\EE}{\sigma}$ a \notion{difference field extension} of
$\dfield{\FF}{\sigma'}$ if $\EE$ is a field extension of $\FF$ and
$\sigma'(g)=\sigma(g)$ for all $g\in\FF$. Since $\sigma'$ and
$\sigma$ agree on $\FF$, we do not distinguish between the two
automorphisms $\sigma$ and $\sigma'$ anymore.

\medskip

\noindent We can construct a difference field for $f(k)$ (resp.~ for
$f(n,k)$) where we follow the rule that inner objects of a sum or
product come first. E.g., for $f(n,k)=H_k\binom{n}{k}$ we start with
$\dfield{\QQ(n)}{\sigma}$ where $\const{\QQ(n)}{\sigma}=\QQ(n)$ and
we adjoin the objects in the order $\stackrel{(1)}\rightarrow
k\stackrel{(2)}\rightarrow H_k\stackrel{(3)}\rightarrow\binom{n}{k}$
as follows.

\begin{myEnumerate}
\item $k$ with $\SH k=k+1$: Take the rational function field
$\QQ(n)(k)$ and extend $\sigma$ to the automorphism
$\fct{\sigma}{\QQ(n)(k)}{\QQ(n)(k)}$ with $\sigma(k)=k+1$. We obtain
the difference field $\dfield{\QQ(n)(k)}{\sigma}$.

\item $H_k$ with $\SH H_k=H_k+\frac{1}{k+1}$: Take the rational
function field $\QQ(n)(k)(h)$ and extend the automorphism from
$\fct{\sigma}{\QQ(n)(k)}{\QQ(n)(k)}$ to
$\fct{\sigma}{\QQ(n)(k)(h)}{\QQ(n)(k)(h)}$ with
$\sigma(h)=h+\frac{1}{k+1}$. We get the difference field
$\dfield{\QQ(n)(k)(h)}{\sigma}$.

\item $\binom{n}{k}$ with $\SH \binom{n}{k}=\frac{n-k}{k+1}\binom{n}{k}$: Take the
rational function field $\QQ(n)(k)(h)(b)$ and construct the
difference field extension $\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ of
$\dfield{\QQ(n)(k)(h)}{\sigma}$ with $\sigma(b)=\frac{n-k}{k+1}\,b$.
We arrive at the difference field $\dfield{\QQ(n)(k)(h)(b)}{\sigma}$
with~\eqref{ExpBHShift} and represent $f(n,k)$ with $h\,b$.
\end{myEnumerate}

Following this construction, one obtains difference fields in which
one can formulate rational expressions in terms of nested sums and
products. There is only one drawback:
\begin{center}
{\it Life gets difficult when one wishes to tackle telescoping and
creative telescoping;}
\end{center}
\noindent see Technical~remark~\ref{Remark:PiSiForAlg}. Thus, we
refine our construction with Karr's
\pisiSE-theory~\cite{Karr:81,Karr:85}: during the construction one
is not allowed to extend the constant field.

\medskip

\noindent{\it Definition.} A difference field extension
$\dfield{\FF(t)}{\sigma}$ of $\dfield{\FF}{\sigma}$ is called a
\notion{\sigmaDSE-extension} (resp.\ a \notion{\piDE-extension}) if
$t$ is transcendental over $\FF$, $\sigma(t)=t+a$ (resp.\
$\sigma(t)=a\,t$) for some $a\in\FF^*$, and
$\const{\FF(t)}{\sigma}=\const{\FF}{\sigma}$. A
\notion{\pisiDSE-extension} is a \piE- or a \sigmaSE-extension. A
\notion{\pisiDSE-field} $\dfield{\KK(t_1)\dots(t_e)}{\sigma}$ over
$\KK$ is a tower of \pisiSE-extensions starting with the constant
field $\KK$.

\medskip

\noindent As it turns out, the extensions in
$\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ are all \pisiSE-extensions (see
below). This means that $\const{\QQ(n)(k)(h)(b)}{\sigma}=\QQ(n)$. In
particular, $\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ is a \pisiSE-field
over $\QQ(n)$. Similarly, $\dfield{\QQ(k)(h)(b)}{\sigma}$
with~\eqref{ExpBHShift} is a \pisiSE-field over $\QQ$. Moreover, all
the examples in Part~1, except in Sections~\ref{Sec:VarCalkin}
and~\ref{SubSec:Rhombus}, can be formalized in \pisiSE-fields.

\begin{TRemark}
Karr defines \sigmaE-extensions~\cite{Karr:81,Karr:85} which are of
the form $\sigma(t)=\alpha\,t+\beta$ and which must satisfy rather
technical side conditions. Restricting to the sum case ($\alpha=1$),
we obtain exactly the class of \sigmaSE-extensions.
\end{TRemark}

Subsequently, we present methods that construct a \pisiSE-field for
a given expression in terms of nested sums and products.



\subsection{\sigmaSE-extensions}\label{SubSec:Sigma}

The following beautiful result is a direct consequence of Karr's
theory~\cite{Karr:81}. For an explicit proof
see~\cite[Cor.~2.2.4]{Schneider:T01}.

\medskip

\noindent{\bf $\Sigma$-Theorem.} Let $\dfield{\FF(t)}{\sigma}$ be a
difference field extension of $\dfield{\FF}{\sigma}$ with
$\sigma(t)=t+f$ for some $f\in\FF$; note that $t$ might be algebraic
or transcendental over $\FF$. Then this extension is a
\sigmaSE-extension if and only if there is no $g\in\FF$ with
$\sigma(g)=g+f$.

\medskip

With this result we can easily show that the constructed difference
field $\dfield{\QQ(k)(h)}{\sigma}$ with~\eqref{ExpHShift} is a
\pisiSE-field. Consider the difference field extension
$\dfield{\QQ(k)}{\sigma}$ of $\dfield{\QQ}{\sigma}$. Since $\QQ$ is
the constant field, there is no $g\in\QQ$ with $\sigma(g)=g+1.$
Thus, $\dfield{\QQ(k)}{\sigma}$ is a \sigmaSE-extension of
$\dfield{\QQ}{\sigma}$. Similarly, by using e.g.\ Gosper's algorithm
or the \SigmaP-package, one can check that there is no $g\in\QQ(k)$
with $\sigma(g)=g+\frac{1}{k+1}.$ Hence, $(\QQ(k)(h),\sigma)$ is a
\sigmaSE-extension of $\dfield{\QQ(k)(h)}{\sigma}$. Analogously, one
can check that $\dfield{\QQ(n)(k)(h)}{\sigma}$
with~\eqref{ExpHShift} is a tower of \sigmaSE-extensions.

Here is an example where the construction from above fails: We
cannot construct a \sigmaSE-extension
$\dfield{\QQ(k)(h)(t)}{\sigma}$ of $\dfield{\QQ(k)(h)}{\sigma}$ with
the shift-behavior $\sigma(t)=t+h$. This follows by the
$\Sigma$-Theorem and the fact that there is the
solution~\eqref{Equ:ExpgSol} for $\sigma(g)-g=h$. Luckily, there is
no need to adjoin a new variable $t$: if we need $t$ with
$\sigma(t)=t+h$, then take $t:=g$.


\medskip

In general, suppose we are given a sum $T(k)=\sum_{i=0}^kF(i)$ and a
difference field $\dfield{\FF}{\sigma}$ in which we can represent
$F(k)$ with $f\in\FF$. Due to the telescoping algorithm for
\pisiSE-fields (see Section~\ref{SubSec:AlgSketch}), only the
following two situations can occur during the construction of a
\pisiSE-field in which one can represent the sum $T(k)$ with
$$T(k+1)=T(k)+F(k+1):$$
\begin{myEnumerate}
\item We find a $t\in\FF$ with
\begin{equation}\label{Equ:SumExtDF}
\sigma(t)=t+\sigma(f).
\end{equation}
Then we can represent $T(k)$ by $t$ in $\FF$ with the desired
shift-behavior~\eqref{Equ:SumExtDF}.
\item We show that there is no $t\in\FF$ with~\eqref{Equ:SumExtDF}.
Then by the $\Sigma$-Theorem we can adjoin the sum $T(k)$ in form of
the \sigmaSE-extension $\dfield{\FF(t)}{\sigma}$ of
$\dfield{\FF}{\sigma}$ with~\eqref{Equ:SumExtDF}.
\end{myEnumerate}

\medskip

\noindent SUMMARY: We can always represent a rational expression of
indefinite nested sums in form of a tower of \sigmaSE-extensions.
Together with the telescoping algorithm for \pisiSE-fields, see
Section~\ref{SubSec:AlgSketch}, the whole construction mechanism
turns out to be algorithmic.


\subsection{\piE-extensions}\label{SubSec:Pi}

For \piE-extensions Karr provides the following
result~\cite[Thm.~2]{Karr:81}.

\medskip

\noindent{\bf $\Pi$-Theorem.} Let $\dfield{\FF(t)}{\sigma}$ be a
difference field extension of $\dfield{\FF}{\sigma}$ with
$t\notin\FF$ and $\sigma(t)=a\,t$ for some $a\in\FF^*$; note that
$t$ might be algebraic or transcendental over $\FF$. Then this
extension is a \piE-extension if and only if there are no $r>0$ and
$g\in\FF^*$ with
\begin{equation}\label{Equ:ProdCheck}
\sigma(g)=a^rg.
\end{equation}


\noindent Motivated by this result, Karr developed an
algorithm~\cite{Karr:81} which solves the following problem: Given a
\pisiSE-field $\dfield{\FF}{\sigma}$, decide if there are $r>0$ and
$g\in\FF^*$ with~\eqref{Equ:ProdCheck}. Summarizing, one can check
algorithmically if an extension over a given \pisiSE-field is a
\piE-extension.

\medskip

E.g., consider the difference field
$\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ from the beginning of
Section~\ref{SubSec:PiSigma}. Since $\dfield{\QQ(n)(k)(h)}{\sigma}$
is a \pisiSE-field, we can apply Karr's algorithm and show that
there is no $g\in\QQ(n)(k)(h)$ and $r>0$ with

\vspace*{-0.5cm}

$$\sigma(g)=\left(\frac{n-k}{k+1}\right)^r g.$$
Thus, by the \piE-Theorem it follows that the difference field
extension $\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ of
$\dfield{\QQ(n)(k)(h)}{\sigma}$ is a \piE-extension. Summarizing, we
can represent our summand $f(n,k)=\binom{n}{k}H_k$ by $b\,h$ in the
\pisiSE-field $\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ in a completely
automatic fashion.

Finally, we compute the shift relations in~\eqref{Equ:fN+1DF} as
follows. From~\eqref{ExpBHShift} we get
$$\SH\binom{n+1}{k}=\frac{n+1-k}{k+1}\binom{n+1}{k}.$$
With the algorithm from Section~\ref{SubSec:AlgSketch} we compute
for
\begin{equation}\label{Equ:HomFirstOrder}
\sigma(g)=\frac{n+1-k}{k+1}g.
\end{equation}
the general solution $g=c\,\frac{(n+1)}{n+1-k}b$ with $c\in\QQ(n)$.
Hence, we get $\binom{n+1}{k}=c\,\frac{(n+1)}{n+1-k}\binom{n}{k}$;
checking the initial value $k=0$, shows that $c=1$. Therefore we can
represent $\binom{n+1}{k}$ by $g$, and we find
$\frac{(n+1)}{n+1-k}\binom{n}{k}H_k$ for $f(n+1,k)$. Similarly, we
can proceed with $f(n+2,k)$. Summarizing, we derive the
\pisiSE-field $\dfield{\QQ(n)(k)(h)(b)}{\sigma}$ with the
representations~\eqref{Equ:fN+1DF} completely algorithmically.

\medskip

\noindent{SUMMARY:} Express a product in a given \pisiSE-field, or,
if this is not possible, try to adjoin it in the form of a
\piE-extension. But, be careful: This construction might fail!

\medskip

E.g. we cannot express $(-1)^k$ with a \piE-extension: for $g=1$ and
$r=2$ we have $\sigma(g)=(-1)^rg.$ Hence, by the \piE-Theorem there
is no \piE-extension $(\QQ(P),\sigma)$ of $\dfield{\QQ}{\sigma}$
with $\sigma(P)=-P.$ Note that such elements can be only expressed
in rings, since we have zero-divisors, like
$$(1-(-1)^k)(1+(-1)^k)=(1-(-1)^{2k})=0.$$
Luckily, a big class of products can be expressed by
\piE-extensions. E.g., in~\cite{Schneider:05c} we show that any
hypergeometric term can be represented by a \piE-extension over the
constant field; there is only one {\it exceptional case}: a
hypergeometric term which can be written in the form $r(n)\alpha^n$
where $r(n)$ is a rational function and $\alpha$ is a root of unity;
see, e.g., identity~\eqref{Equ:NoPiE}.


\section{The basic algorithm}\label{SubSec:AlgSketch}

We present a simplified version~\cite{Schneider:05a} of Karr's
algorithm~\cite{Karr:81}.

\subsection{Telescoping}\label{SubSec:TeleAlg}

Our algorithm finds the solution~\eqref{Equ:ExpgSol}
for~\eqref{Equ:ExpTeleInQ(k)(h)} in three reduction steps.

\medskip

\noindent{\it1. Denominator bounding:} COMPUTE a polynomial
$d\in\QQ(k)[h]^*$ such that
\begin{align*}
\forall
g\in\QQ(k)(h):\quad\sigma(g)-g=h\quad\Rightarrow\quad&g\,d\in\QQ(k)[h].
\end{align*}
Given such a denominator bound $d\in\QQ(k)[h]^*$, one only has to
find the ``numerator'', i.e., to find $g'\in\QQ(k)[h]$ with
$\sigma(\frac{g'}{d})-\frac{g'}{d}=h$. Observe that this is
equivalent to finding all solutions $g'$ of the first order linear
difference equation
\begin{equation}\label{Equ:FirstOrderDE}
a_1\sigma(g')+a_0g'=h
\end{equation}
for the given $a_1=\frac{1}{\sigma(d)}$ and $a_0=-\frac{1}{d}$. In
our concrete case we compute the denominator bound $d=1$;
see~\cite{Bron:00,Schneider:04b}. Thus \eqref{Equ:FirstOrderDE} is
nothing else than our original problem~\eqref{Equ:ExpTeleInQ(k)(h)}
with $g$ replaced by $g'$. We proceed with the second step.

\medskip


\noindent{\it2. Degree bounding:} COMPUTE $b\geq0$ with the
following property:
$$\forall g\in\QQ(k)[h]:\quad \sigma(g)-g=h\quad \Rightarrow\quad\deg(g)\leq
b.$$

\noindent In our particular case we compute the degree bound $b=2$;
for more details see~\cite{Schneider:05b}.


\begin{TRemark}\label{Remark:PiSiForAlg}
At this point we heavily depend on the fact that
$\dfield{\QQ(k)(h)}{\sigma}$ is a \sigmaSE-extension of
$\dfield{\QQ(k)}{\sigma}$. We motivate this fact by the following
considerations.\\
Suppose we are given a difference field extension
$\dfield{\FF(t)}{\sigma}$ of $\dfield{\FF}{\sigma}$ where $t$ is
transcendental over $\FF$ and $\sigma(t)=\alpha\,t+\beta$ for some
$\alpha\in\FF^*$ and
$\beta\in\FF$; let $f\in\FF(t)$. Then the following holds:\\
{\it If our extension is not a \pisiSE-extension and if there is a
solution $g_0\in\FF(t)$ for~\eqref{Equ:ExpTeleInF}, then there is no
denominator bound and degree bound
for~\eqref{Equ:ExpTeleInF}.}\\
This can be seen as follows. Since our extension is not a
\pisiSE-extension, we can take a
$v\in\const{\FF(t)}{\sigma}\setminus\const{\FF}{\sigma}$, i.e.,
$v\in\FF(t)\setminus\FF$ with $\sigma(v)=v$; observe that
$\sigma(v^r)=\sigma(v)^r=v^r$ for any $r\geq0$. Hence,
$$\sigma(g_0+v^r)-(g_0+v^r)=\sigma(g_0)-g_0=f.$$
Therefore we can increase in $g_0+v^r$ either the degree of the
numerator or the degree of the denominator (or both) by increasing
$r$. Thus, either the denominator bound or the degree bound cannot
exist. Similarly, by taking $1/v$ we can guarantee that neither
bound
exists.\\
Conversely, if $\dfield{\FF(t)}{\sigma}$ is a \pisiSE-extension of
$\dfield{\FF}{\sigma}$, such bounds exist. Furthermore, they can be
computed, if $\dfield{\FF}{\sigma}$ is a \pisiSE-field;
see~\cite{Karr:81,Bron:00,Schneider:04b,Schneider:05b}.
\end{TRemark}



\noindent{\it3. Polynomial solutions:} FIND all the coefficients in
\begin{equation}\label{Equ:gAnsatzforTele}
g=g_2\,h^2+g_1\,h+g_0\in\QQ(k)[h]
\end{equation}
such that~\eqref{Equ:ExpTeleInQ(k)(h)} holds. Graphically the
computations can be illustrated as follows:

\smallskip

\footnotesize \xymatrix@!R=0.1cm@C0cm{
\text{\footnotesize$\begin{array}{l}\big[\sigma(g_2)\big(h+\frac{1}{k+1}\big)^2+\sigma(g_1h+g_0)\big]-\big[g_2\,h^2+g_1h+g_0\big]=h\end{array}$}&\ar[dr]^-{\text{\footnotesize coeff. comp.}}\\
&&\text{$\sigma(g_2)-g_2=0$}\ar[dl]_-{\text{\scriptsize$g_2=c\in\QQ$}}\\
\hspace*{2cm}\sigma(g_1\,h+g_0)-(g_1\,h+g_0)=h-c\big[\frac{2h(k+1)+1}{(k+1)^2}\big]&\ar[dr]^<>(0.8){\text{\footnotesize coeff. comp.}}&\\
&&\text{\footnotesize$\sigma(g_1)-g_1=1-c\,\tfrac{2}{k+1}$}\ar[dl]^<>(-0.1){\text{\scriptsize\hspace*{1cm}$c=0$,
$\begin{array}{l}g_1=k+d\\d\in\QQ\end{array}$}}\\
\hspace*{1.8cm}\text{\footnotesize$d=0$,$\begin{array}{l}g_0=-k+e\\
e\in\QQ\end{array}$}\leftarrow\text{\footnotesize$\sigma(g_0)-g_0=-1-d\frac{1}{k+1}$}&}
\normalsize


\noindent First, we plug the possible
solution~\eqref{Equ:gAnsatzforTele}
into~\eqref{Equ:ExpTeleInQ(k)(h)} and obtain the equation
\begin{equation}\label{Equ:g2Problem}
\big[\sigma(g_2)\big(h+\frac{1}{k+1}\big)^2+\sigma(g_1h+g_0)\big]-\big[g_2\,h^2+g_1h+g_0\big]=h.
\end{equation}
By coefficient comparison of the leading terms we get the condition
\begin{equation}\label{Equ:Constrg2}
\sigma(g_2)-g_2=0
\end{equation}
for $g_2$. This means that $g_2=c\in\QQ$ where the constant $c$ is
not determined yet. We substitute this partial result
into~\eqref{Equ:g2Problem} and get
\begin{equation}\label{Equ:g1Problem}
\sigma(g_1\,h+g_0)-(g_1\,h+g_0)=h-c\big[\frac{2h(k+1)+1}{(k+1)^2}\big].
\end{equation}
Thus we have to find $g_0,g_1\in\QQ(k)$ and $c\in\QQ$
with~\eqref{Equ:g1Problem}. We repeat this strategy: By coefficient
comparison of the leading terms in~\eqref{Equ:g1Problem} we get the
constraint
\begin{equation}\label{Equ:Constrg1}
\sigma(g_1)-g_1=1-c\,\tfrac{2}{k+1}
\end{equation}
for $g_1\in\QQ(k)$. Solving this problem we find the generic
solution $c=0$ and $g_1=k+d$ for some constant $d\in\QQ$. If we
repeat these ideas, see the diagram, we obtain the constraint
\begin{equation}\label{Equ:Constrg0}
\sigma(g_0)-g_0=-1-d\frac{1}{k+1}
\end{equation}
for $g_0\in\QQ(k)$. This gives $d=0$ and $g_0=-k+e$ for some
constant $e\in\QQ$. Hence, we obtain the general solution $g=kh-k+e$
with $e\in\QQ$; by setting $e=0$, we arrive at~\eqref{Equ:ExpgSol}.

\medskip

Since we want to turn this reduction strategy into an algorithm, we
need algorithms for the ``coefficient
problems''~\eqref{Equ:Constrg2},\eqref{Equ:Constrg1},
and~\eqref{Equ:Constrg0} in the difference field
$\dfield{\QQ(k)}{\sigma}$.

More generally, suppose we are given a \pisiSE-extension
$\dfield{\FF(t)}{\sigma}$ of $\dfield{\FF}{\sigma}$. Then solving
the telescoping problem~\eqref{Equ:ExpTeleInF} with our three
reduction steps leads to coefficient problems of the following form.

\myBox{\noindent{\bf Given} $f_1,\dots,f_{\delta}\in\FF$,
$a_0,a_1\in\FF$; {\bf find} all
$(c_1,\dots,c_{\delta})\in\KK^{\delta}$ and $h\in\FF$ with
\begin{equation}\label{Equ:FiPLDE}
a_1\,\sigma(h)-a_0\,h=c_1\,f_1+\dots+c_{\delta}\,f_{\delta}.
\end{equation}}

\begin{TRemark}
{\bf(1)}~Since
$\VV:=\{(c_1,\dots,c_{\delta},g)\in\KK^{\delta}\times\FF|\eqref{Equ:FiPLDE}\text{
holds}\}$ is a vector space over $\KK$ with dimension
$\leq\delta+1$, problem~\eqref{Equ:FiPLDE} can be solved by finding
a basis of $\VV$.

\noindent{\bf(2)}~Let $\dfield{\FF}{\sigma}$ be itself a
\pisiSE-field over $\KK$, i.e., $\FF=\KK(t_1)\dots(t_e)$ is a tower
of \pisiSE-extensions. Then in~\cite{Schneider:05a} we work out that
problem~\eqref{Equ:FiPLDE} can be solved as above: Compute a
denominator bound $d\in\KK(t_1)\dots(t_{e-1})[t_e]$,
see~\cite{Bron:00,Schneider:04b}, then bound the degree of the
possible numerators, see~\cite{Schneider:05b}, and afterwards
extract the coefficients of the numerator by solving problems of the
type~\eqref{Equ:FiPLDE} in $\KK(t_1)\dots(t_{e-1})$. Hence we can
reduce problem~\eqref{Equ:FiPLDE} in $\KK(t_1)\dots(t_e)$ to several
problems of~\eqref{Equ:FiPLDE} in the smaller field
$\KK(t_1)\dots(t_{e-1})$. By recursion, we end up at the base
case~\eqref{Equ:FiPLDE} with $\FF=\KK$ which can be solved with
linear algebra.
\end{TRemark}

\noindent SUMMARY: There is an algorithm that solves
problem~\eqref{Equ:FiPLDE} for a given \pisiSE-field
$\dfield{\FF}{\sigma}$.

\subsection{Creative telescoping}\label{Sec:CreaTeleAlg}

The key observation is that problem~\eqref{Equ:FiPLDE} covers
creative telescoping~\eqref{Equ:CreaProblemDF}. Hence, applying our
algorithm from Section~\ref{SubSec:TeleAlg} we get a creative
telescoping algorithm for \pisiSE-fields.

%\begin{TRemark}
%In~\myOut{\ref{MMA:hSumVSpace}} we output a basis for the vector
%space
%$\{(c_0,c_1,c_2,g)\in\QQ(n)^{2}\times\QQ(n)(k)(h)(b)|\eqref{Equ:hSumCreaEqu}\text{
%holds}\}$.
%\end{TRemark}

\subsection{Solving first order linear difference
equations}\label{Sec:FirstOrderRec} Solving first order linear
difference equations is contained in problem~\eqref{Equ:FiPLDE}.
E.g., we can compute with our algorithm the solution
$g=\frac{(n+1)}{n+1-k}b$ for the homogeneous
equation~\eqref{Equ:HomFirstOrder}. More generally, our algorithm
can solve recurrences of the form~\eqref{Equ:SeqRec} with order
$r=1$ where $a_0(n)$, $a_1(n)$ and $f(n)$ can be indefinite nested
sum-product expressions.


\section{Generalizations}\label{Sec:Generalizations}

By variations and generalizations of our telescoping algorithm we
can solve the following summation problems in \SigmaP.


\subsection{Refined (creative) telescoping}\label{SubSec:RefinedTeles}
\hspace*{0.1cm}
\begin{ProblemSpec}{Refined Telescoping}
\noindent{\bf Given} $f(k)$; {\bf find} $g(k)$ and $f'(k)$ such that
\begin{equation}\label{Equ:RefinedTele}
f(k)=g(k+1)-g(k)+f'(k)
\end{equation}
where $f'(k)$ is simpler than $f(k)$.
\end{ProblemSpec}

\noindent Given such a solution, one finds (under the assumption
that~\eqref{Equ:RefinedTele} holds for all $0\leq k\leq n$) the
identity
$$\sum_{k=0}^nf(k)=g(n+1)-g(0)+\sum_{k=0}^nf'(k).$$
Subsequently, we suppose that we are given a \pisiSE-field
$\dfield{\FF(t)}{\sigma}$ where we can represent $f(k)$ by
$f\in\FF(t)$; see Section~\ref{SubSec:PiSigma}. Then we can handle
the following variations of ``simpler''.

\subsubsection{Degree optimal w.r.t\ the top extension}
\myBox{{\bf Given} $f\in\FF(t)$; {\bf find} $(f',g)\in\FF(t)^2$ such
that
\begin{equation}\label{Equ:RefineTele}
\sigma(g)-g+f'=f
\end{equation}
where in $f'$ the degrees of the numerator and denominator
polynomials are minimal.}

\noindent Reinterpreting $f'$ and $g$ as sequences $f'(k)$ and
$g(k)$ solves~\eqref{Equ:RefinedTele} where the sum or product $t$
occurs with optimal degree in the numerator and denominator of
$f'(k)$.

\medskip

\noindent The rational case ($\FF(t)=\KK(t)$ with $\sigma(t)=t+1$)
has been considered in~\cite{Abramov:75,Paule:95,Pirastu:95a}. In
\SigmaP\ the general case of \pisiSE-fields can be handled; see
\cite{Schneider:06f}. E.g., with the option {\tt
SimplifyByExt$\to$DepthNumberDegree} our solver finds the following
simplifications:

\begin{mma}
\In{SigmaReduce[\sum_{k=2}^n\frac{2-k H_k+H_k^4-k
H_k^5}{H_k-kH_k^2}, SimplifyByExt\to DepthNumberDegree]}\\
\Out\sum_{k=2}^n\frac{k^2+2H_k}{k^2H_k}
+(n+1)H_n^3-(2n+1)\big(\tfrac{3}{2}H_n^2-3H_n\big)-\frac{3}{2}(4n+1)+\tfrac{1}{H_n}\\
\In{SigmaReduce[\sum_{k=1}^{n}H_k^4, SimplifyByExt\to DepthNumberDegree]}\\
\Out\sum_{k=1}^n\frac{2H_kk-2k-1}{k^3}+
(n+1) H_n^4-2 (2 n+1) H_n^3+6 (2 n+1)H_n^2-12(2 n+1) H_n+24n\\
\end{mma}

\noindent Note that the found sums can be simplified further to
$$\sum_{k=2}^n\frac{k^2+2H_k}{k^2H_k}=\sum_{k=1}^n\frac{1}{H_k}+2H^{(2)}_n-3,\quad\sum_{k=1}^n\frac{2H_kk-2k-1}{k^3}=-H^{(3)}_n-2H^{(2)}_n+2\sum_{k=1}^n\frac{H_k}{k^2}.$$

\medskip

 \noindent{\it Remark:} The analogous problem for
\piE-extensions has been considered in~\cite{Schneider:05c} which
generalizes hypergeometric results
from~\cite{Abramov:02,Abramov:03a}:

\myBox{{\bf Given} $f\in\FF(t)$; {\bf find} $(f',g)\in\FF(t)^2$ with
$f=\frac{\sigma(g)}{g}f'$ where in $f'$ the degrees of the numerator
and denominator polynomials are minimal.}

\noindent Reinterpreting $f'$ and $g$ as sequences $f'(k)$ and
$g(k)$, we get, with some mild extra conditions, the product
representation
$\prod_{k=1}^nf(k)=\frac{g(n+1)}{g(1)}\prod_{k=1}^nf'(k)$. Examples
are
\begin{gather}
\prod_{k=1}^n\tfrac{(-k-1)(k+7)}{(k+4)^2}=\tfrac{4}{35}\,\tfrac{(n+5)(n+6)(n+7)}{(n+2)(n+3)(n+4)}\,{(-1)^n},\label{Equ:NoPiE}\\
\prod_{k=1}^n\tfrac{(k+3)(H_k(k+1)+1)^2(H_k(k+2)(k+1)+2k+3)}{(k+1)^2H_k(H_k(k+3)(k+2)(k+1)+3(k+4)k+11)}=\tfrac{11}{6}\tfrac{(n+3)(n+2)(H_n(n+1)+1)^2}{(n+1)(H_n(n+3)(n+2)(n+1)+3(n+4)n+11)}\,{\prod_{k=1}^nH_k}.\nonumber
\end{gather}
\normalsize

\subsubsection{Simpler w.r.t.\ the depth}
\myBox{{\bf Given} $f\in\FF$; {\bf find} $(f',g)\in\FF^2$
with~\eqref{Equ:RefineTele} where the nested depth of the sums and
products in $f'$ is minimal.}

\noindent Reinterpreting $f'$ and $g$ as sequences $f'(k)$ and
$g(k)$ solves~\eqref{Equ:RefinedTele} where only those sums and
products of $f(k)$ occur in $f'(k)$ which make the depth of $f'(k)$
optimal.

\medskip

\noindent This mechanism~\cite{Schneider:04a} is activated by
setting the option {\tt SimplifyByExt$\to$Depth}:

\begin{mma}\MLabel{MMA:DepthSimpleExp}
\In{SigmaReduce[\sum_{k=1}^{n}H_k^2H_k^{(2)}, SimplifyByExt\to Depth]}\\
\Out\frac{1}{3}\sum_{i=1}^n\frac{1}{i^3}
-\frac{1}{3}H_n^3+\left((n+1)H_n^{(2)}+1\right) H_n^2 +(2n+1)\left(1-H_n\right)H_n^{(2)}-2H_n\\
\end{mma}
\noindent Note that in \myOut{\ref{MMA:DepthSimpleExp}} we find the
sum extension $H^{(3)}_n=\sum_{i=1}^n\frac{1}{i^3}$ in order to
represent $\sum_{k=1}^{n}H_k^2H_k^{(2)}$ in terms of sums with depth
$1$. For further examples see~\myIn{\ref{MMA:PadeRecSolSimpl}},
\myIn{\ref{MMA:Zero9}}, or
\begin{gather*}
\sum_{k=1}^nH_k^3=(n+1)H_n^3-\frac{3}{2}(2n+1)H_n^2+3(2n+1)H_n-6n+\frac{1}{2}{H^{(2)}_n},\\
\sum_{k=0}^n\left(\sum_{i=0}^k\binom{m}{i}\right)^2=
(m-n)\binom{m}{n}\sum_{i=0}^n\binom{m}{i}-\frac{m-2n-2}{2}\left(\sum_{i=0}^n\binom{m}{i}\right)^2
-\frac{m}{2}{\sum_{i=0}^n\binom{m}{i}^2}.
\end{gather*}
Note that the last expression can be simplified further to
$\frac{n4^n}{2}+4^n-\frac{n}{2}\binom{2n}{n}$ if $m=n$;
see~\cite{Hirschhorn:96,Andrews:99}.


\medskip

\noindent More generally, in~\cite{Schneider:05f} we solve the
following problem: \myBox{{\bf Given} $f\in\FF$; {\bf find} a tower
of \pisiSE-extensions\footnote{The nested depths of the extensions
$t_i$ are smaller than the depth of any element in $f$.}
$\dfield{\FF(t_1)\dots(t_e)}{\sigma}$ over $\dfield{\FF}{\sigma}$
and $(f',g)\in\FF(t_1)\dots(t_e)^2$ with~\eqref{Equ:RefineTele}
where $f'$ has minimal depth.}

\noindent Reinterpreting $f'$ and $g$ as sequences $f'(k)$ and
$g(k)$ solves~\eqref{Equ:RefinedTele} where the nested depth of the
sums and products occurring in $f'(k)$ are optimal. With \SigmaP\ we
find \small
$$\sum_{k=1}^n\Big(\sum_{j=1}^k
\tfrac{H^{(2)}_j}{j^3}\Big)^2=-({H^{(2)}_n}^2+{H^{(4)}_n})\sum_{j=1}^n
\tfrac{H^{(2)}_j}{j^3}+(n+1)\Big(\sum_{j=1}^n
\tfrac{H^{(2)}_j}{j^3}\Big)^2+{\sum_{j=1}^n\tfrac{{H^{(2)}_j}\big((jH^{(2)}_j)^2
-{H^{(2)}_j}+j^2{{H^{(4)}_j}}\big)}{j^5}},
$$
\normalsize
\begin{equation}\label{Equ:DoubleExtForDepth}
\sum_{k=1}^n\frac{1}{k^3}\sum_{j=1}^k\frac{H_j}{j^2}=
{H^{(3)}_n}\sum_{j=1}^n\frac{H_j}{j^2}-
\sum_{j=1}^n\dfrac{H_j(j^3{H^{(3)}_j}-1)}{j^5}.
\end{equation}
E.g., for~\eqref{Equ:DoubleExtForDepth} we compute the extensions
$H^{(3)}_n$ and $\sum_{j=1}^n{H_j(j^3{H^{(3)}_j}-1)}/{j^5}$ in order
to reduce the 3-nested sum on the left-hand side to an expression
with at most 2-nested sums.



\subsubsection{Creative telescoping}\label{Sec:CreaRefined}
The refined telescoping algorithms
from~\cite{Schneider:04a,Schneider:05f} can be carried over to
creative telescoping:

\myBox{{\bf Given} $\delta\geq0$ and $f_i\in\FF$; {\bf find}
$(f',g)\in\FF^2$ and $c_i\in\const{\FF}{\sigma}$ such that
$$\sigma(g)-g+f'=c_0f_0+\dots+c_{\delta}f_{\delta}$$
where $f'$ is nicer than the $f_i$.}

\noindent E.g., by using the option {\tt SimplifyByExt->DepthNumber}
in {\tt GenerateRecurrence} one looks for an $f'$ where the number
of used objects are smaller than the objects occurring in the $f_i$.
Typical examples can be found in~\myIn{\ref{MMA:GenRecDeptNumber}}
or in~\cite{Schneider:02,Schneider:03,Schneider:06b}.


\subsection{Solving linear difference equations of higher order}\label{SubSec:HOLDE}

The recurrence solver in \SigmaP\ works as follows. Given a
recurrence~\eqref{Equ:SeqRec}, \SigmaP\ represents the coefficients
$a_i(n)$ and the inhomogeneous part $f(n)$ in a \pisiSE-field
$\dfield{\FF}{\sigma}$ with $a_i,f\in\FF$; see
Section~\ref{SubSec:PiSigma}. We call $\dfield{\FF}{\sigma}$ also
the \notion{coefficient field} of the given recurrence. Then there
are various options how to continue.

\subsubsection{Solutions in the coefficient
field}\label{Sec:CoefFieldSol}

%In general we are interested in the following problem.

\myBox{{\bf Given} $f,a_0,\dots,a_{r}\in\FF$; {\bf find} all
$g\in\FF$ with
\begin{equation}\label{Equ:LDE}
a_r\,\sigma^{r}(g)+\dots+a_{0}\,g=f.
\end{equation}}
\noindent Then rephrasing the elements $g\in\FF$ to sequences $g(k)$
produces solutions for the recurrence~\eqref{Equ:SeqRec}.


\smallskip

\noindent There are such solvers for the rational case and the
$q$-rational case,
see~\cite{Abramov:89b,Abramov:89a,Petkov:92,Abramov:95b,Abramov:95a,AequalB,vanHoeij:98,
Abramov:98}. Also in \SigmaP\ such an efficient solver is available:
a typical example is the first homogeneous solution in the
result~\myOut{\ref{MMA:0999RecSol}}.

More generally, \SigmaP\ contains methods for
\pisiSE-fields~\cite{Schneider:05b}. With our solver we compute,
e.g., the particular solution in the
result~\myOut{\ref{MMA:Calkin3}}. Similarly, given

\begin{mma}\MLabel{MMA:GenRecSol}
\In rec=-n (n+1) H_n((n+1)
H_n+1){F}[n]+n(n+1)(2H_n+1)(n+1)H_n+1){F}[n+1]-\newline
\hspace*{4cm}n (n+1) H_n\left(n+(n+1)H_n+2\right){F}[n+2]==H_n((n+1) H_n+1);\\
\end{mma}

\vspace*{-0.05cm}

\noindent we can compute a particular solution:

\vspace*{-0.05cm}

\begin{mma}\MLabel{MMA:PartRecH}
\In{SolveRecurrence[rec,F[n],Extension\to None]}\\
\Out\{\{1,\frac{nH_n-1}{n}\}\}\\
\end{mma}

\vspace*{-0.3cm}

\begin{TRemark}\label{Remark:PLDEM}
In~\cite{Schneider:05b} we generalize the telescoping algorithm from
Section~\ref{SubSec:AlgSketch} to solve problem~\eqref{Equ:LDE} for
a \pisiSE-field $\dfield{\FF(t)}{\sigma}$. Here the following
remarks are in place:
\begin{myEnumerate}
\item[{\it Reduction 1:}] Denominator bounds can be computed
for \sigmaSE-extensions. For \piE-extensions it can be determined up
to a factor of the form $t^l$ with $l\in\NN_0$;
see~\cite{Bron:00,Schneider:04b}.

\item[{\it Reduction 2:}] Degree bounds can be computed for several
special cases~\cite{Schneider:05b}. In~\cite{Schneider:T01} a method
has been developed that can compute degree bounds for
\sigmaSE-extensions. So far,  I did not find a proof for
termination.

\item[{\it Reduction 3:}] The coefficient problems are of the
following type.
\end{myEnumerate}
\myBox{\noindent{\bf Given} $a_0,\dots,a_{r}\in\FF$ and
$f_1,\dots,f_{\delta}\in\FF$; {\bf find} all $g\in\FF$ and
$\vecT{c_1,\dots,c_{\delta}}\in\KK^{\delta}$ such that
\begin{equation}\label{Equ:PLDE}
a_r\,\sigma^{r}(g)+\dots+a_0\,g=
c_1\,f_1+\dots+c_{\delta}\,f_{\delta}.
\end{equation}}
Note that
$\VV:=\{(c_1,\dots,c_{\delta},g)\in\KK^{\delta}\times\FF|\eqref{Equ:PLDE}\text{
holds}\}$ is a vector space over $\KK$ with dimension
$\leq\delta+r$. Notice that problem~\eqref{Equ:FiPLDE} is a special
case of~\eqref{Equ:PLDE} with $r=1$. E.g.,
in~\myOut{\ref{MMA:hRecSolve}},\myOut{\ref{MMA:hqRecSolve}},\myOut{\ref{MMA:PadeRecSol}},
\myOut{\ref{MMA:0999RecSol}} we output bases of such vector spaces
with $\delta=1$, $r=2$.

In order to solve problem~\eqref{Equ:PLDE}, we apply the three
reduction steps recursively as in the telescoping algorithm. Here we
emphasize the following result: Although there are open subproblems
in the reduction steps~1 and~2, it has been shown
in~\cite{Schneider:05a} that there is a recursive enumeration
procedure that eventually outputs all solutions for a given
equation~\eqref{Equ:PLDE}. Further investigations are going
on~\cite{Bron:05,Petkovsek:06} to overcome these open problems.
\end{TRemark}


\noindent SUMMARY: The methods for the ``master
problem''~\eqref{Equ:PLDE} are the algorithmic heart of \SigmaP. All
the other problems treated here, such as (creative) telescoping and
solving recurrences, can be reduced to it.

\smallskip

As one can see in~\myOut{\ref{MMA:PartRecH}}, we missed the
homogeneous solutions of the recurrence. The problem is that we
searched for solutions only in the coefficient field
``$\QQ(n,H_n)$'' given by~\myIn{\ref{MMA:GenRecSol}}. In order to
extend the search space, the following possibilities are available.



\subsubsection{Manual extensions}

The coefficient field can be extended manually by using the option
{$\tt Tower\to\{ext_1,\dots,ext_e\}$}. This feature might be useful,
if one has additional insight, i.e., one expects that certain sums
or products should occur in the solution.

\subsubsection{Automatic extensions}\label{LDEExtSol}

\SigmaP\ finds certain type of solutions for~\eqref{Equ:SeqRec}, or
it outputs that solutions of such type do not exist. We focus on the
following problem.

\begin{ProblemSpec}{Find solutions by extensions}
\noindent{\bf Given}~\eqref{Equ:SeqRec}; {\bf find} all solutions of
the form

\vspace*{-0.4cm}

\begin{equation}\label{DefOfDAlembertSol}
h(n)\sum_{k_1=0}^nb_1(k_1)\sum_{k_2=0}^{k_2}
b_2(k_2)\dots\sum_{k_s=0}^{k_{s-1}}b_s(k_s).
\end{equation}

\vspace*{0.2cm}

\end{ProblemSpec}

\medskip

\noindent$\bullet$~{\it Sum solutions.} Sum solutions are of the
form~\eqref{DefOfDAlembertSol} where the $b_i(k_i)$ and $h(n)$ can
be represented in the given coefficient field
$\dfield{\FF}{\sigma}$. In other words, the $b_i(k_i)$ and $h(n)$
are expressions in terms of the objects given in $a_i(n)$ and
$f(n)$; for examples see~\myOut{\ref{MMA:PadeRecSol}}
and~\myOut{\ref{MMA:0999RecSol}}.

\begin{TRemark}
{\bf(1)}~Any solution, that can be represented in a tower of
\sigmaSE-extensions, can be represented by a sum solution of the
form~\eqref{DefOfDAlembertSol};
see~\cite[Thm.~4.5.4]{Schneider:T01}.\\
{\bf(2)}~If there exists a sum solution~\eqref{DefOfDAlembertSol},
then the expression $h(n)$ must be a solution of the homogeneous
version of~\eqref{Equ:SeqRec}; see~\cite[Thm.
4.5.1]{Schneider:T01}.\\ {\bf(3)}~Sum-solutions are obtained by
factorizing the linear difference equation as much as possible into
first order linear right factors over the given difference
field/ring. Then each factor corresponds basically to one indefinite
summation quantifier; see~\cite{Abramov:94,Schneider:T01}. If one
fails to split off such a first order factor, there is still hope to
continue. Namely, if one finds a product solution of the remaining
difference equation, then this corresponds exactly to one additional
factor. Hence, product extensions can lead to a refined
factorization, and therefore can produce additional solutions of a
given linear difference equation.
\end{TRemark}

\noindent SUMMARY: We find all solutions in terms of indefinite sum
expressions by looking for all sum solutions. If there is no
homogeneous solution in the coefficient field
$\dfield{\FF}{\sigma}$, like in~\myOut{\ref{MMA:PartRecH}}, there is
no sum solution at all. Luckily, product extensions can contribute
to finding additional sum solutions,
see~\myOut{\ref{MMA:hRecSolve}}, \myOut{\ref{MMA:hqRecSolve}},
or~\myOut{\ref{MMA:Calkin3}}.

\medskip


\noindent$\bullet$~{\it Product solutions.} Given a recurrence with
rational coefficients in $\KK(n)$, there are algorithms,
like~\cite{Petkov:92} or~\cite{vanHoeij:99}, that can compute the
so-called hypergeometric solutions; for $q$-hypergeometric solutions
see~\cite{Abramov:98}. Typical examples are the first entry
in~\myOut{\ref{MMA:hRecSolve}} for the hypergeometric case and
in~\myOut{\ref{MMA:hqRecSolve}} for the $q$-hypergeometric case.

A generalized version of the algorithms~\cite{Petkov:92,Abramov:98}
is implemented in \SigmaP\ for \pisiSE-fields. E.g. for our
recurrence from~\myIn{\ref{MMA:GenRecSol}} we compute the following
product solution:

\begin{mma}
\In{SolveRecurrence[rec, F[n],Extension\to PRODS]}\vspace*{-0.2cm}\\
\Out\{\{1,\frac{nH_n-1}{n}\},\{0,\prod_{i=2}^n\frac{-1+iH_i}{-1+i+iH_i}\}\}\\
\end{mma}

\vspace*{-0.3cm}

\noindent Using this product extension we can completely solve the
recurrence with sum solutions:

\begin{mma}\MLabel{MMA:recHPS}
\In{recSol=SolveRecurrence[rec,F[n],Tower\to\{\prod_{i=2}^n\tfrac{-1+iH_i}{-1+i+iH_i}\}, Extension\to SUMS]}\vspace*{-0.3cm}\\
\Out\{\{1,\frac{nH_n-1}{n}\},\{0,\prod_{i=2}^n\frac{-1+iH_i}{-1+i+iH_i}\},
\{0,\prod_{i=2}^n\frac{-1+iH_i}{-1+i+iH_i}\sum_{i=1}^n\frac{-1+H_ii}{-1+i+H_ii}\prod_{j=2}^i\frac{-1+j+jH_j}{-1+jH_j}\}\}\\
\end{mma}

\noindent$\bullet$~{\it d'Alembertian solutions.}
In~\myOut{\ref{MMA:recHPS}} we have computed solutions of the
type~\eqref{DefOfDAlembertSol} where the $b_i(k_i)$ and $h(n)$ can
be either elements from the coefficient field, or products over such
elements from $\FF$. Such type of solutions are also called
d'Alembertian solutions~\cite{Abramov:94}, a subclass of Liouvillian
solutions~\cite{Singer:99}.

With the option {\tt Extension$\to$dAlembert} we can compute all
such solutions in one stroke. E.g., we solve our
recurrence~\myIn{\ref{MMA:GenRecSol}} at once with
\begin{mma}
\In SolveRecurrence[rec,F[n],Extension\to dAlembert]\\
\Out\{\{1,\frac{nH_n-1}{n}\},\{0,\prod_{i=2}^n\frac{-1+iH_i}{-1+i+iH_i}\},
\{0,\prod_{i=2}^n\frac{-1+iH_i}{-1+i+iH_i}\sum_{i=1}^n\frac{-1+H_ii}{-1+i+H_ii}\prod_{j=2}^i\frac{-1+j+jH_j}{-1+jH_j}\}\}\\
\end{mma}

\noindent Note that {\tt Extension$\to$dAlembert} is the default
option in {\tt SolveRecurrence}, i.e., in the computation
steps~\myIn{\ref{MMA:hRecSolve}},
\myIn{\ref{MMA:hqRecSolve}},\myIn{\ref{MMA:PadeRecSol}},\myIn{\ref{MMA:Calkin3}},\myIn{\ref{MMA:0999RecSol}}
the d'Alembertian-machinery was activated.




\begin{TRemark}
Since problem~\eqref{Equ:PLDE} occurs as a subproblem in the
algorithms for sum-solutions and product-solutions, the open
problems listed in Technical~remark~\ref{Remark:PLDEM} are relevant
here; further investigations are going
on~\cite{Bron:05,Petkovsek:06}. Note that we can find all such
solutions by recursive enumeration.
\end{TRemark}

\noindent SUMMARY: \SigmaP\ can find all d'Alembertian solutions. If
\SigmaP\ fails to find any product solution (including solutions in
the coefficient field $\FF$) for a given recurrence, then there does
not exist a d'Alembertian solution at all. In this case \SigmaP's
weapons are exhausted.

\medskip




\subsection{Algebraic extensions}\label{SubSec:AlgebraicExt}

In various summation problems, like in Sections~\ref{Sec:VarCalkin}
and~\ref{SubSec:Rhombus}, the algebraic term $(-1)^n$ with
$((-1)^n)^2=1$ pops up. As shown in Section~\ref{SubSec:Pi}, such an
object can be formulated only in rings with zero-divisors. In
\SigmaP\ our methods for problem~\eqref{Equ:PLDE} have been extended
for such algebraic extensions;
see~\cite[Section~3.6]{Schneider:T01}.



\subsection{Unspecified sequences}

In joint work with Manuel Kauers~\cite{Schneider:06d,Schneider:06e}
\SigmaP\ has been extended as follows. Our summation objects can be
represented in a tower of \pisiSE-extensions over a free difference
field~\cite{Cohn:65}. More precisely, take the field
$\FF:=\KK(\dots,x_{-1},x_0,x_1,\dots)$ with infinitely many
variables $x_i$ and define the field automorphism
$\fct{\sigma}{\FF}{\FF}$ by $\sigma(c)=c$ for all $c\in\KK$ and
$\sigma(x_i)=x_{i+1}$ for $i\in\ZZ$. Then given this difference
field $\dfield{\FF}{\sigma}$ we extend it with a tower of
\pisiSE-extensions, say $\dfield{\FF(t_1)\dots(t_e)}{\sigma}$.

For such a difference field we managed to carry over all the
summation algorithms mentioned earlier. In order to apply this
machinery, we have to load in

\begin{mma}
\In << Free.m \\
\Print Free.m - Solver for PLDEs over the free difference field by
Manuel Kauers \copyright\ RISC-Linz\\
\end{mma}

\noindent \noindent As carried out in detail in~\cite{Schneider:06d}
we can find the identity~\cite[Equ.~(5)]{Schneider:06d}
$$\sum_{k=1}^nk^2\sum_{i=1}^k
X_i=\tfrac{1}{6}\Bigl(n(n+1)(2n+1)\sum_{k=1}^n X_k-\sum_{k=1}^nk X_k
+3\sum_{k=1}^n k^2X_k-2\sum_{k=1}^n k^3X_k\Bigr)$$ where $X_i$ stand
for a generic/unspecified sequence. More precisely, we compute the
right-hand side by simply executing our telescoping-solver:

\begin{mma}
\In{SigmaReduce[\sum_{k=1}^nk^2\sum_{i=1}^k X[i],SimpleSumRepresentation\to True]}\\
\Out \frac{1}{6}\Bigl(n(n+1)(2n+1)\sum_{k=1}^n X[k]-\sum_{k=1}^nk
X[k] +3\sum_{k=1}^n k^2X[k]-2\sum_{k=1}^n k^3X[k]\Bigr)\\
\end{mma}

\noindent As observed in~\cite{Schneider:06d} we can now specialize
this identity and get, for instance with $X_k=\frac{1}{n+k}$ and $
H_{n+k}=H_n+\sum_{i=1}^k \frac{1}{n+i}$ the identity~\cite[Bonus
problem 6.69]{Graham:94}:
$$\sum_{k=1}^nk^2H_{n+k}=\tfrac13n(n+\tfrac12)(n+1)(2H_{2n}-H_n)-\tfrac1{36}(10n^2+9n-1).$$
Similarly, we find

\vspace*{-0.5cm}

$$\sum_{k=1}^na^k\sum_{j=1}^kX_j=
\frac{1}{a-1}\big(a^{n+1}\sum_{k=1}^nX_k-\sum_{k=1}^na^kX_k\big),\quad
a\neq1$$ which generalizes the
identity~\cite[Equ.~(7)]{Schneider:06d}. With $X_j:=\frac{1}{j}$ we
get
$$\sum_{k=1}^na^kH_k=\frac{1}{a-1}\Big[a^{n+1}H_n-\sum_{k=1}^n\frac{a^k}{k}\Big]$$
and with $X_j=\tbinom{m}{j-1}$, $a=-1$, and $n:=m+1$ we
rediscover~\cite{Zhang:99}:
$$\sum_{k=0}^m(-1)^{k+1}\sum_{j=0}^k\tbinom{m}{j}=\frac{1}{2}(-1)^{m+1}2^m.$$
Observe that for $a=1$ we derive a different version,
namely~\cite[Equ.~(5)]{Schneider:06d}:
$$\sum_{k=1}^n\sum_{j=1}^k X_j=(n+1)\sum_{k=1}^nX_k-\sum_{k=1}^n k X_k.$$
For $X_j:=\frac{1}{j^2}$ we find
$\sum_{k=1}^nH^{(2)}_k=(n+1)H^{(2)}_n-H_k$ and for
$X_j=\tbinom{m}{j}$ we get
\begin{align*}
\sum_{k=0}^n\sum_{j=0}^k\tbinom{m}{j}&=(n+1)\sum_{k=0}^n\binom{m}{k}-\sum_{k=0}^nk\binom{m}{k}
=\frac{1}{2}(m-n)\binom{m}{n}+(2n-m+2)\sum_{i=0}^n\binom{m}{i}.
\end{align*}
If $m=n$, we get $\frac{n+2}{2}2^n$;
see~\cite{Hirschhorn:96,Andrews:99}. Further identities are given
in~\cite{Schneider:06d,Schneider:06e}.

\newpage

\stepcounter{part} \noindent{\bf\Large Part 3. Multi-summation and
applications}

\vspace*{0.5cm}

There are various approaches for multi-summation available. As
illustrated in the first two parts, the {\it difference field
approach} enables one to handle a rather general class of nested
multi-sums. Zeilberger's holonomic systems
approach~\cite{Zeilberger:90a} was an important breakthrough for
another class of multi-sums. This work forms a common framework for
the Sister Celine/WZ-method and the holonomic/$\partial$-finite
function approach.
%In all the algorithms the
%basic idea is to compute a recurrence for a multi-sum by solving a
%system of linear equations. By holonomic theory or by analyzing the
%linear algebra problem, one can show that the existence of such a
%solution always exist, if the order of the desired recurrence is
%chosen high enough.\\

{\it The Sister Celine/WZ-Method:}~Following Sister Celine
Fasenmyer's PhD--thesis~\cite{Celine:45} and
D.~Zeilberger/H.~Wilf~\cite{Wilf:92} one computes suitable
recurrences for hypergeometric summands by setting up a system of
linear equations; the summand-recurrence can then be transformed to
a recurrence for the corresponding hypergeometric multi-sum. An
efficient machinery has been developed by
Wegschaider~\cite{Wegschaider:97} where ideas of Sister
Celine/Wilf/Zeilberger are combined in a non-trivial manner with
results of Verbaeten~\cite{Verbaeten:74} and its simplification
presented in~\cite{Hornegger:92}. For a $q$-version
see~\cite{Riese:03}. Related approaches
are~\cite{Chen:06,Zeilberger:06}.

{\it The holonomic/$\partial$-finite function approach:} Pioneering
work of the holonomic/$\partial$-finite approach has been done in
\cite{Chyzak:98}. In particular, in~\cite{Chyzak:00} Zeilberger's
algorithm~\cite{Zeilberger:91} has been generalized to general
holonomic and $\partial$-finite functions. This method treats also
multiple sum (and multiple integration) problems.

{\it A new Sigma approach:} In~\cite{Schneider:05d} it has been
shown that Chyzak's approach~\cite{Chyzak:00} can be substantially
simplified, if one attacks multi-sum problems in a slightly
restricted way. Moreover, it turns out that one can bring Karr's
\pisiSE-world and Chyzak's approach under one umbrella. This leads
to a rather general and surprisingly efficient machinery which has
been implemented in \SigmaP. Subsequently, we shall illustrate our
``\SigmaP\ approach'' by various concrete examples. In addition to
the results~\cite{Schneider:05d}, we show in
Section~\ref{Sec:CreaTeleMethodDEDeFinite} that our method can be
also used to compute differential equations for such general
multi-sums.


\section{The basic idea for telescoping}\label{Sec:TeleDeFinite}

We consider the following problem from~\cite{Schneider:06g} which
arose in joint cooperation with the JKU-Finite Element group. Find a
closed form for the hypergeometric multi-sum
$$S(n)=\sum_{k=1}^n\frac{2k+1}{k+1}\sum_{j=0}^k\frac{\Pochhammer{-k}{j}\Pochhammer{k+1}{j}\Pochhammer{2}{k}}{j!k!\Pochhammer{2}{j}}\left(\frac{1-x}{2}\right)^j;$$
here we use the standard Pochhammer symbol
$(a)_j=\prod_{i=1}^j(a+i-1)$. Subsequently, we denote the inner sum
in $S(n)$ with $P(k)$; note that $P(k)$ are the Jacobi-polynomials
$P^{(\alpha,\beta)}_k(x)$ for the specific choice
$(\alpha,\beta)=(1,-1)$.

First notice that we cannot apply our (creative) telescoping
algorithm presented earlier to the summand $\frac{2k+1}{k+1}P(k)$.
To see this, we compute a recurrence for $P(k)$:

\begin{mma}\MLabel{MMA:JabociRec}
\In{recP = GenerateRecurrence[\sum_{j=0}^k\frac{\Pochhammer{-k}{j}\Pochhammer{k+1}{j}\Pochhammer{2}{k}}{j!k!\Pochhammer{2}{j}}\left(\frac{1-x}{2}\right)^j][[1]]/.SUM\to P}\\
\Out P[k+2]==\frac{(2k+3)x}{k+2}P[k+1]-\frac{k}{k+1}P[k]\\
\end{mma}

\noindent Then we show with \SigmaP\ that there are no d'Alembertian
solutions, i.e., we cannot represent $P(k)$ in terms of a
\pisiSE-field. In particular, we cannot
simplify~\myOut{\ref{MMA:JabociRec}} to a first order recurrence.
Summarizing, we cannot handle the sum $S(n)$ with the tools
presented so far.

Motivated by such examples, we extended \SigmaP\ in order to handle
also multi-sums where the inner sum is described by recurrences of
higher order. E.g., using~\myOut{\ref{MMA:JabociRec}} we can
simplify

\begin{mma}
\In {mySum}=\sum_{k=1}^n\frac{2k+1}{k+1} P[k];\\
\end{mma}

\noindent with our generalized telescoping solver as follows.

\begin{mma}\MLabel{MMA:SigmaReduceGeneral}
\In SigmaReduce[mySum,\{recP,P[k]\}]\\
\Out\frac{(3x-2)P[1]}{2(x-1)}-\frac{P[2]}{x-1}-\frac{n\,{P}[n]}{(n+1)(x-1)}+\frac{{P}[n+1]}{x-1}\\
\end{mma}

\noindent With $P(1)=x+1, P(2)=\frac{3}{2} x (x+1)$ we arrive at the
identity~\cite[Equ.~(16)]{Schneider:06g}
\begin{equation}\label{Equ:JacobiId}
S(n)=-\frac{x+1}{x-1}-\frac{n
P(n)}{(n+1)(x-1)}+\frac{P(n+1)}{x-1},\quad\quad n\geq1.
\end{equation}


\subsection{Verification}\label{Sec:IndefVeri}
The result~\myOut{\ref{MMA:SigmaReduceGeneral}} can be produced by
summing the telescoping equation
\begin{equation}\label{Equ:TeleJacobi}
g(k+1)-g(k)=\frac{2k+1}{k+1}P(k)
\end{equation}
with the computed solution
\begin{equation}\label{Equ:JacobiTeleSol}
g(k)=\frac{1+k-x-2kx}{(x-1)(k+1)}P(k)+\frac{1}{x-1}P(k+1).
\end{equation}
Note that the correctness of~\eqref{Equ:TeleJacobi} can be verified
independently of the computational steps: Represent $P(k+2)$ in
$g(k+1)$ as a linear combination of $P(k)$ and $P(k+1)$ by using the
relation~\myOut{\ref{MMA:JabociRec}}. Then
verify~\eqref{Equ:TeleJacobi} by polynomial arithmetic.

\subsection{The method}\label{Sec:TeleMethodDeFinite}
We consider the following telescoping problem:\\
{Given}~\myOut{\ref{MMA:JabociRec}}, {find}
$g(k)=g_0(k)P(k)+g_1(k)P(k+1)$ with unknown coefficients $g_0(k)$
and $g_1(k)$ such that~\eqref{Equ:TeleJacobi} holds. This problem is
equivalent to finding $g_0(k)$ and $g_1(k)$ with
\begin{equation}\label{Equ:gConstrained0}
\Big[g_0(k+1)P(k+1)+g_1(k+1)P(k+2)\Big]-\Big[g_0(k)P(k)+g_1(k)P(k+1)\Big]=\frac{2k+1}{k+1}P(k).
\end{equation}
Applying the relation~\myOut{\ref{MMA:JabociRec}} and collecting
terms w.r.t.\ $P(k)$ and $P(k+1)$ we get equivalently
\begin{multline}\label{Equ:gConstrained}
P(k)\big[-\frac{k}{k+1}g_1(k+1)-g_0(k)-\frac{2k+1}{k+1}\big]\\
+P(k+1)\big[{g_0(k+1)+\frac{(2k+3)x}{k+2}g_1(k+1)-g_1(k)}\big]=0.
\end{multline}
Hence, if $g_0(k)$ and $g_1(k)$ satisfy
\begin{align}\label{Equ:Jacobig0}
g_0(k)&=-\frac{k}{k+1}g_1(k+1)-\frac{2k+1}{k+1},\\
\label{Equ:gOneDirection2}
g_0(k+1)&+\frac{(2k+3)x}{k+2}g_1(k+1)-g_1(k)=0,
\end{align}
then~\eqref{Equ:gConstrained0} and~\eqref{Equ:gConstrained} hold.
Note that the other direction might not hold in general, but in our
concrete case it does; see
Technical~remark~\ref{Remark:DeFiniteRemark}.1. Finally, by taking
the shifted version of~\eqref{Equ:Jacobig0} we can
rewrite~\eqref{Equ:gOneDirection2} in the form of the linear
difference equation
\begin{equation}\label{Equ:Jacobig1}
-\frac{k+1}{k+2}g_1(k+2)+\frac{(2k+3)x}{k+2}g_1(k+1)-g_1(k)
=\frac{2k+3}{k+2}.
\end{equation}
Summarizing, if $g_0(k)$ and $g_1(k)$ satisfy~\eqref{Equ:Jacobig0}
and~\eqref{Equ:Jacobig1}, $g(k)=g_0(k)P(k)+g_1(k)P(k+1)$ is a
solution of~\eqref{Equ:TeleJacobi} and~\eqref{Equ:gConstrained0}.
Now observe that~\eqref{Equ:Jacobig1} is a linear recurrence in
$g_1(k)$. Hence we can run \SigmaP's recurrence solver and compute
the solution $g_1(k)=\frac{1}{x-1}$. Finally,
$g_0(k)=\frac{1+k-x-2kx}{(x-1)(k+1)}$ is determined
by~\eqref{Equ:Jacobig0}. We end up with our
solution~\eqref{Equ:JacobiTeleSol}.

%\begin{Remark}\label{Remark:OneWay}
%In general, \eqref{Equ:gConstrained} does not
%imply~\eqref{Equ:Jacobig0} and~\eqref{Equ:gOneDirection2}, and
%hence~\eqref{Equ:Jacobig0} and~\eqref{Equ:Jacobig0} might not hold.
%In our concrete case it does: With our algorithms, see
%Section~\ref{LDEExtSol}, we can check that $P(k)$ cannot be
%expressed by a hypergeometric term, i.e., $P(k)$ does not satisfy a
%recurrence of order one. Thus, $P(k)$ and $P(k+1)$ are linearly
%independent, which shows that~\eqref{Equ:gConstrained}
%implies~\eqref{Equ:Jacobig0} and~\eqref{Equ:gOneDirection2}.
%\end{Remark}

\medskip

In general, we obtain a method for the following telescoping
problem:

\begin{ProblemSpec}{Telescoping with a recurrence}
\noindent{\bf Given} $f(k):=h_0(k)P(k)+\dots+h_s(k)P(k+s)$ and
\begin{equation}\label{Equ:RecForTeleDFinite}
P(k+s+1)=a_0(k)P(k)+\dots+a_{s}(k)P(k+s);
\end{equation}
{\bf find} a solution for~\eqref{Equ:SeqTele} which is of the form
\begin{equation}\label{Equ:DFinitegTeleSol}
g(k)=g_0(k)P(k)+\dots+g_s(k)P(k+s).
\end{equation}
\end{ProblemSpec}

\noindent Namely, by inserting~\eqref{Equ:DFinitegTeleSol} with the
unknown coefficients $g_r(k)$ in~\eqref{Equ:SeqTele} and doing
coefficient comparison we find, as above, the following coupled
system; see~\cite[Lemma~1]{Schneider:05d}:
\begin{align}
g_0(k)&=a_0(k)\,g_s(k+1)-h_0(k),\label{Equ:g0ForDeFinite}\\
g_r(k)&=g_{r-1}(k+1)+a_r(k)\,g_s(k+1)-h_r(k),\quad\quad1\leq r\leq
s.\label{Equ:giForDeFinite}
\end{align}
This means that any solution $g_0(k),\dots,g_{s}(k)$ of this system
produces a solution~\eqref{Equ:DFinitegTeleSol}
for~\eqref{Equ:SeqTele}. Now the crucial step is that this system
can be uncoupled, once and for all, and we obtain, in addition, the
following linear difference equation for
$g_s(k)$~\cite[Lemma~2]{Schneider:05d}:
\begin{equation}\label{Equ:DEForDeFinite}
\sum_{j=0}^s
a_{s-j}(k+j)g_s(k+j+1)-g_s(k)=\sum_{j=0}^sh_{s-j}(k+j)\\
\end{equation}
Summarizing, we arrive at the following method:\\
1.~FIND a solution $g_s(k)$ for~\eqref{Equ:DEForDeFinite}; this is a particular instance of problem~\eqref{Equ:LDE}.\\
2.~COMPUTE $g_0(k)$ by~\eqref{Equ:g0ForDeFinite}; then compute the
remaining $g_1(k),\dots,g_{s-1}(k)$ by~\eqref{Equ:giForDeFinite}.

\begin{TRemark}\label{Remark:DeFiniteRemark}
{\bf(1)}~If $g(k)=g_0P(k)+\dots+g_s(k)P(k+s)$ is a solution
of~\eqref{Equ:SeqTele}, we cannot guarantee that the $g_r(k)$
satisfy the system~\eqref{Equ:g0ForDeFinite},
\eqref{Equ:giForDeFinite}, \eqref{Equ:DEForDeFinite}. Hence, our
method might fail, although there exists a solution of the
form~\eqref{Equ:DFinitegTeleSol}. This can be only guaranteed, if
the recurrence order of~\eqref{Equ:RecForTeleDFinite} is minimal.
E.g., the recurrence~\myOut{\ref{MMA:JabociRec}} has minimal order.
This implies that $P(k)$ and $P(k+1)$ are linearly independent.
Thus~\eqref{Equ:gConstrained}
implies~\eqref{Equ:Jacobig0} and~\eqref{Equ:gOneDirection2}.\\
{\bf(2)}~We can apply this method for all input terms $h_i(k)$ and
$a_i(k)$ for which one has solvers for~\eqref{Equ:DEForDeFinite} or
equivalently for~\eqref{Equ:LDE}. In the \SigmaP-package the
$h_i(k)$ and $a_i(k)$ can be any expression represented in a
\pisiSE-field. Furthermore, in~\cite{Schneider:05d} we allow that
the recurrence~\eqref{Equ:RecForTeleDFinite} might have an
inhomogeneous part.
\end{TRemark}


\section{The basic idea for creative telescoping}

In~\cite{AequalB} the following identity pops up:
\begin{equation}\label{Equ:AequalBDSum}
\sum_{k=0}^{n}\sum_{j=0}^{n}(-1)^{n+k+j}\binom{n}{k}\binom{n}{j}\binom{n+k}{k}\binom{n+j}{j}\binom{2n-j-k}{n}=\sum_{k=0}^n\binom{n}{k}^4.
\end{equation}
As observed in~\cite{Schneider:05d} \SigmaP\ can prove this identity
by a slight generalization of the techniques presented in
Section~\ref{Sec:TeleDeFinite}. First, we compute a recurrence in
$k$ for the inner sum $P(n,k)$:

\begin{mma}
\In{innerSum=}\sum_{j=0}^{n}(-1)^{n+k+j}\binom{n}{k}\binom{n}{j}\binom{n+k}{k}\binom{n+j}{j}\binom{2n-j-k}{n};\\
\end{mma}

\begin{mma}\MLabel{MMA:innerSumK}
\In {recK = GenerateRecurrence[innerSum, k][[1]]/.SUM\to P}\\
\Out P[k+2]==\tfrac{(n-k)^3 (1+k+n) (2+k+n)}{{(1+k)}^2 {(2+k)}^2
(k-3n)}P[k] + \tfrac{{(1+k)}^2 (2+k+n) (k+2k^2-3n-6kn+ 3n^2
)}{{(1+k)}^2{(2+k)}^2 (k-3n)}P[k+1]\\
\end{mma}

\noindent Besides this we compute a recurrence with one shift in $n$
and the remaining shifts in $k$:


\begin{mma}\MLabel{MMA:innerSumOneN}
\In recKN=GenerateRecurrence[innerSum,
k,OneShiftIn\to n][[1]]/.SUM\to P\\
\Out P[n+1,k]==\frac{{(1+k)}^2 (-1+k-3n)(6- 8k+3k^2+12n-8kn+
6n^2)}{{(1-k+n)}^3 {(1+n)}^2}P[k+1]+\newline
\tfrac{-(1+k+n)(-5k+12k^2-10k^3+3k^4+3n-32kn+42k^2n-16k^3n +
15n^2-57kn^2+33k^2n^2+ 21n^3-30kn^3+9n^4)}{{(1-k+n)}^3
{(1+n)}^2}P[k]\\
\end{mma}

\noindent{\it Remark.} Given the summand $f(n,k,j)$, set up the
creative telescoping equation
\begin{multline}\label{Equ:CreaOneShiftMore}
g(n,k,j+1)-g(n,k,j)\\
=c_0(n,k)f(n,k,j)+c_1(n,k)f(n,k+1,j)+c_2(n,k)f(n+1,k,j)
\end{multline}
and solve the underlying problem~\eqref{Equ:CreaProblemDF} where
$f_0,f_1,f_2$ correspond to $f(n,k,j),f(n,k+1,j),f(n+1,k,j)$,
respectively. Summing the resulting
equation~\eqref{Equ:CreaOneShiftMore} over $k$
gives~\myOut{\ref{MMA:innerSumOneN}}.

\medskip

\noindent Finally, we compute a recurrence for the sum on the
left-hand side of~\eqref{Equ:AequalBDSum} as follows:

\begin{mma}\MLabel{MMA:A=BRec}
\In{GenerateRecurrence[\sum_{k=0}^{n}P[k], n, {{recK, P[k]}}, recKN]}\\
\Out\{-4(1+n) (3+4n) (5+4n) {SUM}[n]- 2(3+2n) (7+9n+3n^2)
{SUM}[1+n]+ {(2+n)}^3 SUM[2+n]==0\}\\
\end{mma}

\noindent We remark that Chyzak's general holonomic approach (which
takes $2300$s) and Weg\-schaider's implementation (which takes
$510$s) are much slower on that; we need only $12$s on the same
machine.

To this end, we can compute with \SigmaP\ the same recurrence for
the right-hand side of~\eqref{Equ:AequalBDSum}. Since both sides
of~\eqref{Equ:AequalBDSum} agree at $n=0,1$, equality follows for
all $n\geq0$.


\subsection{Verification}\label{Sec:DefVeri}
The correctness of~\myOut{\ref{MMA:A=BRec}} follows by
\begin{equation}\label{Equ:feCrea}
g(n,k+1)-g(n,k)=c_0(n)P(n,k)+c_1(n)P(n+1,k)+c_2(n)P(n+2,k)
\end{equation}
and the proof certificate
\begin{equation}\label{Equ:CSolA=B}
\begin{aligned}
c_0(n)&=4(n+1)^3(4n+3)(4n+5),&c_2(n)&=-(n+1)^2(n+2)^3,\\
c_1(n)&=2(n+1)^2(2n+3)\left(3n^2+9n+7\right),
\end{aligned}
\end{equation}
and
\begin{equation}\label{Equ:gSolA=B}
g(n,k)=g_0(n,k)P(n,k)+g_1(n,k)P(n,k+1)
\end{equation}
where the rational functions $g_i(n,k)$ in $n$ and $k$ are derived
in Example~\ref{Exp:A=BFinal}; the explicit expression can be found
in~\cite[p.~763]{Schneider:05d}. The correctness
of~\eqref{Equ:feCrea} can be verified for all $0\leq k\leq n$ as
follows. Rewrite the expression $P(n,k+2)$ in $g(n,k+1)$ in terms of
$P(n,k)$ and $P(n,k+1)$ by using the
relation~\myOut{\ref{MMA:innerSumK}}. Similarly, rewrite the
expression $P(n+1,k)$ in~\eqref{Equ:feCrea} in the form of a linear
combination of $P(n,k)$ and $P(n,k+1)$ by using the
relation~\myOut{\ref{MMA:innerSumOneN}}. Moreover, express
$P(n+2,k)$ in~\eqref{Equ:feCrea} by a linear combination in
$P(n+1,k)$ and $P(n+1,k+1)$ which itself can be expressed by a
linear combination in $P(n,k)$ and $P(n,k+1)$ by using the ``rewrite
rules''~\myOut{\ref{MMA:innerSumK}}
and~\myOut{\ref{MMA:innerSumOneN}}. Then the correctness
of~\eqref{Equ:feCrea} follows by polynomial arithmetic.
Summing~\eqref{Equ:feCrea} over $k$
produces~\myOut{\ref{MMA:A=BRec}}.

\subsection{A method for recurrences}\label{Sec:CreaTeleMethodDeFinite}
We present the following strategy from~\cite{Schneider:05d} to
compute a recurrence for a hypergeometric double sum
\begin{equation*}
S(n)=\sum_{k}\sum_{j}h(n,k,j)
\end{equation*}
where $h(n,k,j)$ is hypergeometric in $n$, $k$ and $j$. We start
with the inner sum $P(n,k)=\sum_{j}h(n,k,j)$. If one is lucky, one
can compute with \SigmaP\ not only a recurrence in $k$, say
\begin{equation}\label{Equ:KShiftDefinite}
P(n,k+s+1)=a_0(n,k)P(n,k)+\dots+a_{s}(n,k)P(n,k+s),
\end{equation}
but also a recurrence with one shift in $n$ and the remaining shifts
in $k$, like
\begin{equation}\label{Equ:NKShiftDefinite}
P(n+1,k)=b_0(n,k)P(n,k)+\dots+b_s(n,k)P(n,k+s);
\end{equation}
examples are~\myIn{\ref{MMA:innerSumK}}
and~\myIn{\ref{MMA:innerSumOneN}}. In~\cite{Paule:06a} an existence
theory is presented which closely relates to the situation of
Zeilberger's algorithm. This question is analysed further
in~\cite{SchneiderP:06a}.

\medskip

\noindent Given such a recurrence
system~\eqref{Equ:KShiftDefinite},\eqref{Equ:NKShiftDefinite}, our
creative telescoping problem reads as follows.

\begin{ProblemSpec}{Creative telescoping with a recurrence system}
\noindent {\bf Given} $\delta\in\NN$ and
$f(n,k):=h_0(n,k)P(n,k)+\dots+h_s(n,k)P(n,k+s)$
plus~\eqref{Equ:KShiftDefinite}
and~\eqref{Equ:NKShiftDefinite};\\
{\bf find} a solution $c_0(n),\dots,c_{\delta}(n)$, not all zero,
and $g(n,k)$ for~\eqref{Equ:SeqCrea} where $g(n,k)$ is of the form
\begin{equation}\label{Equ:DFinitegCreaTeleSol}
g(n,k)=g_0(n,k)P(n,k)+\dots+g_s(n,k)P(n,k+s).
\end{equation}
\end{ProblemSpec}
\noindent Summing~\eqref{Equ:DFinitegCreaTeleSol} over $k$ gives,
with some extra conditions, a recurrence of the
form~\eqref{Equ:SeqRec}.


\begin{Example}
Take $f(n,k)=P(n,k)$ with~\eqref{Equ:KShiftDefinite}
and~\eqref{Equ:NKShiftDefinite} where the $a_i(k)$ and $b_i(k)$ are
given by~\myOut{\ref{MMA:innerSumK}}
and~\myOut{\ref{MMA:innerSumOneN}}, respectively. We look for
$c_0(n), c_1(n),c_2(n)$ and~\eqref{Equ:gSolA=B}
with~\eqref{Equ:feCrea}.
\end{Example}

\noindent Given the two relations~\eqref{Equ:KShiftDefinite}
and~\eqref{Equ:NKShiftDefinite}, the terms
$P(n+i,k),\dots,P(n+i,k+s)$ in $f(n+i,k)$ can be expressed by a
linear combination in $P(n,k),\dots,P(n,k+s)$. E.g., if $s=1$ and
$i=2$, \small
\begin{align}
P(n+2&,k)\stackrel{\eqref{Equ:NKShiftDefinite}}{=}b_0(n+1,k)P(n+1,k)+b_1(n+1,k)P(n+1,k+1)\nonumber\\
\stackrel{\eqref{Equ:NKShiftDefinite}}{=}&b_0(n+1,k)\big[b_0(n,k)P(n,k)+b_1(n,k)P(n,k+1)\big]\nonumber\\
&+b_1(n+1,k)\big[b_0(n,k+1)P(n,k+1)+b_1(n,k+1)P(n,k+2)\big]\nonumber\\
\stackrel{\eqref{Equ:KShiftDefinite}}{=}&P(n,k)\big[b_0(n+1,k)b_0(n,k)+b_1(n+1,k)b_1(n,k+1)a_0(n,k)\big]\nonumber\\
&+P(n,k+1)\big[b_0(n+1,k)b_1(n,k)
+b_1(n+1,k)\big(b_0(n,k+1)+b_1(n,k+1)a_1(n,k)\big)\big].\label{Equ:GetCoefForf2}
\end{align}
\normalsize Subsequently, denote $f(n+i,k)$ by $f_i(k)$; from now on
we suppress the parameter~$n$. Then by the above considerations the
expressions $f_0(k):=f(n,k),\dots,f_{\delta}(k):=f(n+{\delta},k)$
can be set up in the form
\begin{equation}\label{Equ:ParaDFiniteF}
\begin{array}[c]{l}f_0(k):=h^{(0)}_0(k)P(k)+\dots+h^{(0)}_s(k)P(k+s)\\
\hspace*{1.1cm}\vdots\\
f_{\delta}(k):=h^{({\delta})}_0(k)P(k)+\dots+h^{({\delta})}_s(k)P(k+s).\end{array}
\end{equation}

\begin{Example}[Cont.]
Write $f_0(k):=f(n,k)$, $f_1(k):=f(n+1,k)$ and $f_2(k):=f(n+2,k)$ in
the form~\eqref{Equ:ParaDFiniteF}, i.e., set $h^{(0)}_0(k):=1$ and
$h^{(0)}_1(k):=0$, take $h^{(1)}_i(k):=b_i(n,k)$ for $i=0,1$, and
define $h^{(2)}_0(k)$ and $h^{(2)}_1(k)$ by the coefficients of
$P(n,k)$ and $P(n,k+1)$ in~\eqref{Equ:GetCoefForf2}.
\end{Example}

Consequently, our creative
telescoping problem can be stated in the following form.\\
{\bf Given}~\eqref{Equ:ParaDFiniteF}
and~\eqref{Equ:RecForTeleDFinite}; {\bf find}
$g(k)=g_0(k)P(k)+\dots+g_s(k)P(k+s)$ and $c_0,\dots,c_{\delta}$ with
\begin{equation}\label{Equ:ParaTeleForDeFinite}
g(k+1)-g(k)=c_0f_0(k)+\dots+c_{\delta}f_{\delta}(k).
\end{equation}

\begin{Example}[Cont.]
Finding solutions $c_0,c_1,c_2$ and $g(k)=g_0(k)P(k)+g_1(k)P(k+1)$
for~\eqref{Equ:ParaTeleForDeFinite} is equivalent to looking for
solutions $c_0(n),c_1(n),c_2(n)$ and~\eqref{Equ:gSolA=B}
for~\eqref{Equ:feCrea}.
\end{Example}


\noindent KEY OBSERVATION: By replacing $f(k)$ with
$c_0f_0(k)+\dots+c_{\delta}f(k)$ in our telescoping method from
Section~\ref{Sec:TeleMethodDeFinite} we get the following method to
find a solution for~\eqref{Equ:ParaTeleForDeFinite}.\\
1.~FIND a solution $c_0,\dots,c_{\delta}$ and $g_s(k)$ for
$$\sum_{j=0}^s
a_{s-j}(k+j)g_s(k+j+1)-g_s(k)=\sum_{i=0}^{\delta}c_i\sum_{j=0}^sh^{(i)}_{s-j}(k+j);$$
this is a particular instance of problem~\eqref{Equ:PLDE}.\\
2. COMPUTE the remaining $g_0(k),\dots,g_{s-1}(k)$ by
\begin{gather*}
g_0(k)=a_{0}(k)g_s(k+1)-\sum_{i=0}^{\delta}c_ih^{(i)}_0(k),\\
g_r(k)=g_{r-1}(k+1)+a_{r}(k)g_s(k+1)-\sum_{i=0}^{\delta}c_ih^{(i)}_r(k),\quad\quad
0<r<s.
\end{gather*}

\begin{Example}[Cont.]\label{Exp:A=BFinal}
We set up our parameterized linear difference equation
\begin{multline*}
-\tfrac{(k-n+1)^3(k+n+2)(k+n+3)}{(k+2)^2(k+3)^2(k-3n+1)}g_1(k+2)+
\tfrac{(k+n+2)\left(2k^2-6nk+k+3n^2-3n\right)}{(k+2)^2(k-3n)}g_1(k+1)-g_1(k)\\
=c_0\phi_0(k)+c_1\phi_1(k)+c_2\phi_2(k)
\end{multline*}
where $\phi_i(n,k):=\sum_{j=0}^sh^{(i)}_{s-j}(k+j)$ are rational
functions in $n,k$. \SigmaP\ computes~\eqref{Equ:CSolA=B} and \small
\begin{multline*}
g_1(k)=\Big(k^2(k+1)^2(-k+3n+1)(17
n^6-121kn^5+161n^5+225k^2n^4-944kn^4\\
+625n^4-177k^3n^3+1389k^2n^3-2901kn^3+1271n^3+61k^4n^2-808k^3n^2+3174k^2n^2\\
-4386kn^2+1426n^2-7k^5n+182k^4n-1220k^3n+3183k^2n-3260kn+836n-10k^5\\
+136k^4-610k^3+1182k^2-952k+200)\Big)\Big/((-k+n+1)^3(-k+n+2)^3);
\end{multline*}
\normalsize we set
$g_0(k):=a_{0}(k)g_1(k+1)-\sum_{i=0}^{2}c_ih^{(i)}_0(k)$ and get the
solution~\eqref{Equ:gSolA=B} for~\eqref{Equ:feCrea}.
\end{Example}

\noindent We emphasize that the sketched double-sum approach can be
carried over to general multi-sums; for more details
see~\cite[Section~4]{Schneider:05d}.

\subsection{A method for differential equations}\label{Sec:CreaTeleMethodDEDeFinite}
By a slight variation of our method~\cite{Schneider:05d}, see
Section~\ref{Sec:CreaTeleMethodDeFinite}, one can compute linear
differential equations for a sum
\begin{equation}\label{Equ:DoubleSumDE}
S(z)=\sum_{k}\sum_{j}h(z,k,j)
\end{equation}
where $h(z,k,j)$ is hypergeometric in $k$ and $j$ and
$\frac{d}{dz}h(z,k,j)/h(z,k,j)$ is a rational function in $z,k,j$.
E.g., consider the following identities which will pop up in
Section~\ref{Sec:AbraStegun}:
\begin{equation}\label{Equ:InitialId}
\begin{gathered}
\sum_{k=0}^{\infty}(4k+1)\frac{(2k)!}{k!^22^{2k}}P(z,k)=1,\quad
\sum_{k=0}^{\infty}-(4k+1)k\frac{(2k+1)!}{k!^22^{2k-1}}P(z,k)=-z^2,\\
\sum_{k=0}^{\infty}(4k+1)k(2k-1)\frac{(2k+2)!}{k!^22^{2k+1}}P(z,k)=\frac{1}{4}z^4+z^2
\end{gathered}
\end{equation}
where
\begin{equation}\label{Equ:BesselSum}
P(z,k)=\sum_{i=0}^{\infty}\frac{\sqrt{\pi}}{2}\frac{(-z^2/4)^i(z/2)^{2k}}{i!(2k+i+1/2)!}.
\end{equation}
Note that $P(z,k)$ is equal to $j_{2k}(z)$ where $j_k(z)$ are the
Spherical Bessel functions of the first kind;
see~\cite{Abramowitz:65}. In order to prove these identities, we
compute differential equations for the left-hand sides
of~\eqref{Equ:InitialId} as follows. First, we derive a recurrence
of the form
\begin{equation}\label{Equ:DiffKZShiftDefinite}
P(z,k+s+1)=a_0(z,k)P(z,k)+\dots+a_s(z,k)P(z,k+s).
\end{equation}
With \SigmaP\ we get for our sum $P(z,k)$
\begin{mma}
\In sumP=\sum_{i=0}^{\infty}\frac{\sqrt{\pi}}{2}\frac{(-z^2/4)^i(z/2)^{2k}}{i!(2k+i+1/2)!};\\
\end{mma}
\noindent the recurrence relation
\begin{mma}\MLabel{MMA:sumPForAbr}
\In{recP = GenerateRecurrence[sumP, k][[1]]/.SUM\to P}\\
\Out P[k+2]==-\frac{4k+7}{4k+3}P[k]+\frac{(4k+5)(16k^2+40k-2z^2+21)}{(4k+3)z^2}P[k+1]\\
\end{mma}

\noindent Next, we look for a difference-differential equation of
the form
\begin{equation}\label{Equ:DiffKShiftDefinite}
\frac{d}{dz}P(z,k)=b_0(z,k)P(z,k)+\dots+b_s(z,k)P(z,k+s).
\end{equation}
This can be accomplished by the function call.


\begin{mma}\MLabel{MMA:MixedDEREExp}
\In{recOneDiff = GenerateRecurrence[sumP, k, OneDiffIn\to z][[1]]/.SUM\to P}\\
\Out P^{(0,1)}[z,k]==\frac{8k^2+6k-z^2}{(4k+3)z}P[k]-\frac{z}{4k+3}P[k+1]\\
\end{mma}

\noindent{\it Remark.} Given the summand $f(z,k,j)$, set up the
creative telescoping equation
\begin{equation}\label{Equ:CreaDEOneShiftMore}
g(z,k,i+1)-g(z,k,i)=c_0(z,k)f(z,k,i)+c_1(z,k)f(z,k+1,i)+c_2(z,k)\frac{d}{dz}f(z,k,i)
\end{equation}
and solve the underlying problem~\eqref{Equ:CreaProblemDF} where
$f_0$, $f_1$, and $f_2$ correspond to $f(z,k,i)$, $f(z,k+1,i)$, and
$\frac{d}{dz}f(z,k,i)$, respectively. Summing the
result~\eqref{Equ:CreaDEOneShiftMore} over $k$
gives~\myOut{\ref{MMA:MixedDEREExp}}.

\medskip

\noindent Using~\myOut{\ref{MMA:sumPForAbr}} we can compute a
differential equation for the left-hand side
of~\eqref{Equ:InitialId}:

\begin{mma}\MLabel{MMA:DEComp}
\In{GenerateDE[\sum_{k=0}^{\infty}-(4k+1)k\frac{(2k+1)!}{k!^22^{2k-1}}P[k], z, \{recP, P[k]\}, recOneDiff]}\\
\Out\{2\text{SUM}[z]-z\text{SUM}'[z]==0\}\\
\end{mma}

Internally, \SigmaP\ solves the problem as follows:
Given~\myOut{\ref{MMA:sumPForAbr}}
and~\myOut{\ref{MMA:MixedDEREExp}}, we look for a solution
$g(z,k)=g_0(z,k)P(z,k)+g_1(z,k)P(z,k+1)$ with
\begin{align*}
g(z,k+1)-g(z,k)=&c_0(z)P(z,k)+c_1(z)\frac{d}{dz}P(z,k)\\
\stackrel{\text{\sf\tiny{\tiny
Out}[\ref{MMA:MixedDEREExp}]}}{=}&c_0(z)P(z,k)+c_1(z)\Big[\frac{8k^2+6k-z^2}{(4k+3)z}P(z,k)-\frac{z}{4k+3}P(z,k+1)\Big].
\end{align*}
Together with~~\myOut{\ref{MMA:sumPForAbr}} this is nothing else
than a certain instance of problem~\eqref{Equ:ParaTeleForDeFinite}.
Therefore we continue as in Section~\ref{Sec:CreaTeleMethodDeFinite}
and can compute the solution $c_0=2$, $c_1=-z$ and
$$g(z,k)=\frac{(2k)!}{k!^22^{2k}}\frac{2(k-1)k(2k+1)}{4k+3}\big[(z^2-16k^2-16k-3)P(z,k)+z^2P(z,k+1)\big].$$
The correctness can be checked along the lines of
Section~\ref{Sec:DefVeri}. Hence, summing this equation over $k$
gives~\myOut{\ref{MMA:DEComp}}.

\medskip

\noindent Completely analogously we find differential equations for
the remaining two sums in~\eqref{Equ:InitialId}:


\begin{mma}
\In{GenerateDE[\sum_{k=0}^{\infty}(4k+1)\frac{(2k)!}{k!^22^{2k}}P[k], z, \{recP, P[k]\}, recOneDiff]}\\
\Out \{\text{SUM}'[z]==0\}\\
\end{mma}

\begin{mma}
\In{GenerateDE[\sum_{k=0}^{\infty}(4k+1)k(2k-1)\frac{(2k+2)!}{k!^22^{2k+1}}P[k], z, \{recP, P[k]\}, recOneDiff]}\\
\Out\{-4(z^2+2)\text{SUM}[z]+z(z^2+4)\text{SUM}'[z]==0\}\\
\end{mma}

\noindent By looking at the solutions of these differential
equations, the identities in~\eqref{Equ:InitialId} follow.

\smallskip

Summarizing, we propose the following strategy to find a
differential equation for~\eqref{Equ:DoubleSumDE}. First, try to
compute a difference-differential
system~\eqref{Equ:DiffKZShiftDefinite},
\eqref{Equ:DiffKShiftDefinite} for the inner sum
$P(z,k)=\sum_{j}h(z,k,j)$ of~\eqref{Equ:DoubleSumDE}. Then we have
methods in hand for the following problem.

\begin{ProblemSpec}{Creative telescoping with a difference-differential system}
\noindent{\bf Given} $\delta\in\NN$ and
$f(z,k):=h_0(z,k)P(z,k)+\dots+h_s(z,k)P(z,k+s)$
plus~\eqref{Equ:KShiftDefinite}
and~\eqref{Equ:DiffKShiftDefinite};\\
{\bf find} a solution $c_0(z),\dots,c_{\delta}(z)$, not all zero,
and $g(z,k)$ for
\begin{equation}\label{Equ:CreaDeProblem}
g(z,k+1)-g(z,k)=c_0(z)f(z,k)+c_1(z)\frac{d}{dz}f(z,k)+\dots+c_{\delta}(z)\frac{d^{\delta}}{dz^{\delta}}f(z,k)
\end{equation}
where $g(z,k)$ is of the form
$g(z,k)=g_0(z,k)P(z,k)+\dots+g_s(z,k)P(z,k+s)$.
\end{ProblemSpec}

\noindent More precisely, with~\eqref{Equ:KShiftDefinite}
and~\eqref{Equ:DiffKShiftDefinite} we can rewrite
$$f_0(k):=f(z,k),\dots,f_{\delta}(k):=\frac{d^{\delta}}{dz^{\delta}}f(z,k)$$
in the form~\eqref{Equ:ParaDFiniteF}, respectively. Summarizing, we
can reduce problem~\eqref{Equ:CreaDeProblem} to
problem~\eqref{Equ:ParaTeleForDeFinite}. A solution
of~\eqref{Equ:ParaTeleForDeFinite} by our method from
Section~\ref{Sec:CreaTeleMethodDeFinite} will provide us with a
solution for problem~\eqref{Equ:CreaDeProblem}. Then summing such a
solution~\eqref{Equ:CreaDeProblem} over $k$ gives (under the
assumption that~\eqref{Equ:CreaDeProblem} holds for all $0\leq k\leq
n$) a differential equation of the form
$$q(z)=c_0(z)S(z)+c_1(z)S'(z)+\dots+c_{\delta}(z)S^{(\delta)}(z)$$
for some function $q(z)$. We emphasize that the sketched double-sum
approach for differential equations can be carried over to general
multi-sums along the lines of~\cite[Section~4]{Schneider:05d}.

\section{Applications}

\subsection{Stembridge's TSPP Theorem}
In~\cite{Schneider:05e} we derived a computer-assisted proof of
Stembridge's Totally Symmetric Plane Partition (TSPP)
Theorem~\cite{Stembridge:95}. Consider a plane partition with
largest part $\leq n$, i.e., a matrix \small
$$\begin{matrix}
n\geq&a_{11}&\geq&a_{12}&\geq&a_{13}&\geq&\dots &a_{1r}\\
&\vleq&&\vleq&&&&&\vleq\\
&a_{21}&\geq&a_{22}&&&&\dots&a_{2r}\\
&\vleq&&&&&&&\vleq\\
%&a_{31}&&&&&&&a_{3r}\\
&\vdots&&&&&&&\vdots\\
&\vleq&&&&&&&\vleq\\
&a_{s1}&\geq&a_{s2}&\geq&a_{s3}&\geq&\dots\geq&a_{s,r}\geq 0\\
\end{matrix}$$
\normalsize where in each row and column the positive integers are
weakly decreasing. Typically, one can represent a plane partition in
3-$d$ as follows:

\vspace*{-0.3cm}

$$\begin{array}[c]{ccccc}
3&&2&&1\\
2&&1&&0\\
1&&0&&0
\end{array}\longleftrightarrow\begin{minipage}[c]{2.3cm}
\resizebox{2.2cm}{!}{\includegraphics{cube.eps}}\end{minipage}$$
Then a TSPP is such a 3-d cube which can be rotated and reflected
without changing the graphical picture. In the beginning of the
eighties G.E.~Andrews, I.G.~Macdonald and R.P.~Stanley conjectured
that for the number $T_n$ of TSPPs with largest part $\leq n$ the
following identity holds:
\begin{equation}\label{Thm:TSPPEv}
T_n=\prod_{1\leq i\leq j\leq k\leq
n}\frac{i+j+k-1}{i+j+k-2},\quad\quad n\geq1;
\end{equation}
cf.~\cite[case 4]{Stanley:86b} and~\cite{Stembridge:95}. Moreover,
in~\cite{Okada:89} a matrix $M(n)=\Mat{\mu(i,j)}_{0\leq i,j\leq
n-1}$ with explicit expressions $\mu(i,j)$ was given such that
$$T_n^2=\detB{M}.$$
Since the expressions $\mu(i,j)$ are rather complicated, there was
no chance to simplify the determinant evaluation in order to
show~\eqref{Thm:TSPPEv}. Finally, in the beginning of the nineties
G.~Andrews could guess a highly non-trivial matrix
$W=\text{\tiny$\left(\begin{matrix}
*&\dots&*\\
&\ddots&\vdots\\
\text{\large$0$}&&*
\end{matrix}\right)$}$ with $\det(W)=1$ and

\vspace*{-0.5cm}

\begin{equation}\label{Equ:DetIdentity}
M W=\left(\begin{matrix}
*&&\text{\Large$0$}\\
\vdots&\ddots\\
*&\dots&*\\
\end{matrix}\right)=:U.
\end{equation}
Since $\det(M)=\det(M)\det(W)=\det(M\,W)=\det(U)$, one only has to
take the product of the diagonal elements of $U$, which leads
exactly to~\eqref{Thm:TSPPEv}.\\
The only remaining task is to show~\eqref{Equ:DetIdentity}.
Unfortunately, the expressions in $W$ (triple sums are involved)
look even more complicated than the expressions in $M$ (only double
sums are involved). Hence verifying~\eqref{Equ:DetIdentity} leads to
identities with quadruple sums! Summarizing, at that time a proof
of~\eqref{Equ:DetIdentity} was out of scope -- even by using the
computer. Finally, J.~Stembridge found an elegant
proof~\cite{Stembridge:95} which combines the combinatorics of
Pfaffians and reduction of such to known determinant
representations.



\smallskip

Luckily, G.~Andrews did not forget his fascinating attempt and sent
his problem~\eqref{Equ:DetIdentity} to RISC in~2003. After several
weeks of hard work, Peter Paule and I won the battle. In a first
step P.~Paule managed to simplify in a non-trivial way the
underlying identities involving quadruple sums to identities with
triple sums. E.g., define
\begin{align*}
A_0(i,m)&:=\sum_{k=0}^{2m}\binom{i+k-3}{i-2}h(k,m)\quad\text{and}\quad
A_2(i,m):=\sum_{k=i}^{2m}(-1)^k h(k,m)\quad\text{where}\\
h(k,m)&:=\sum_{s=0}^{\lfloor\frac{2m-k}{2}\rfloor-1}\hspace*{-0.2cm}\frac{k}{m-s}
\binom{m-s}{2m-2s-k} \frac{(-1)^{s+k}}{2m\,4^s}\sum_{r=0}^s
\frac{(m-r)\Pochhammer{m}{r}\Pochhammer{-3m-1}{r}}{r!\Pochhammer{\frac{1}{2}-2m}{r}}.
\end{align*}
Then one among the many identities looks like follows: for all
$m\geq 1$ and all $3\leq i\leq 2m+1$,

\vspace*{-0.6cm}

\begin{multline}\label{Equ:TSPPSumId}
2h(i-2,m)-5h(i-1,m) -A_0(i,m) +6(-1)^iA_2(i,m)
-3(-1)^i\prod_{s=1}^{2m-1}\tfrac{2(m+s-1)}{2m+s-2}=0.
\end{multline}

\vspace*{-0.2cm}

\noindent Here \SigmaP\ enters the game: we compute for each of the
ingredients recurrences in~$i$. E.g., for $A_0(i,m)$ we get a
recurrence as follows:

\begin{mma}
\In
hSum=\sum_{s=0}^{\lfloor\frac{2m-k}{2}\rfloor-1}\hspace*{-0.2cm}\frac{k}{m-s}
\binom{m-s}{2m-2s-k} \frac{(-1)^{s+k}}{2m\,4^s}\sum_{r=0}^s
\frac{(m-r)\Pochhammer{m}{r}\Pochhammer{-3m-1}{r}}{r!\Pochhammer{\frac{1}{2}-2m}{r}};\\
\end{mma}

\vspace*{-0.1cm}

\begin{mma}
\In rec=GenerateRecurrence[hSum, k, FiniteSupport\to
True][[1]]/.SUM\to h\\
\Out
-(k-2m+2)(k+2m+3)h(k+3)(k+1)^2+2(k+2)^2(k-2m)(k+2m+1)h[k]+\newline
\hspace*{0.5cm}(-5k^4-29k^3+12m^2k^2+6mk^2-58k^2+40m^2k+20mk-46k+24m^2+12m-12)h[k+1]+\newline
\hspace*{1cm}(4k^4+26k^3-12m^2k^2-6mk^2+59k^2-28m^2k-14mk+55k-12m^2-6m+18)h[k+2]==0\\
\end{mma}

\vspace*{-0.2cm}

\begin{mma}
\In recA0 = GenerateRecurrence[\sum_{k=0}^{2m}\binom{i+k-3}{i-2}h[k], i, \{rec, h[k]\}, FiniteSupport\to True]\\
\Out
(i^2+i+2)(i+2m-1)(i-2(m+1))SUM[i]-(i+3)(i^3-i^2+2i+4m^2+2m-2)SUM[i+1]-\newline
\hspace*{0.5cm}(i-3)(i^3+i^2+2i-4m^2-2m+2)SUM[i+2]+(i^2-i+2)(i-2m+1)(i+2m+2)SUM[i+3]==0\\
\end{mma}

\noindent Given all the recurrences, see~\cite{Schneider:05e}, we
combine them to one recurrence by using the Mathematica package {\sf
GeneratingFunctions}~\cite{Mallinger:96}, which is based on the
ideas of~\cite{Salvy:94}. By checking initial values we show that
all the sums combined in~\eqref{Equ:TSPPSumId} evaluate to zero.

\noindent We conclude our result with Zeilberger's Opinion
65~\cite{Zeilberger:05a}:

\begin{myQuote}
Seeing all the details, (that nowadays can (and should!) be easily
relegated to the computer), even if they are extremely hairy, is a
hang-up that traditional mathematicians should learn to wean
themselves from. A case in point is the excellent but unnecessarily
long-winded recent article~\cite{Schneider:05e}. It is a new,
computer-assisted proof, of John Stembridge's celebrated TSPP
theorem. It is so long because they insisted on showing explicitly
all the hairy details, and easily-reproducible-by-the-reader "proof
certificates". It would have been much better if they would have
first applied their method to a much simpler case, that the reader
can easily follow, that would take one page, and then state that the
same method was applied to the complicated case of Stembridge's
theorem and the result was TRUE. For those poor people who are
unable or unwilling to run the program themselves, they could have
posted the computer output on their websites, but please, have mercy
on the rain forest! You don't need 30 pages, and frankly all this
EXPLICIT LANGUAGE of hairy computer output is almost pornographic.
\end{myQuote}

\smallskip

\noindent Here I would like to mention that our TSPP-proof is indeed
hairy and highly non-trivial. The challenge was to illustrate that
such non-trivial problems can be proven {\it completely rigorously
with the computer}. As a consequence, we derived proof certificates
that do not fill 30 pages, as Doron mentioned, but 80 pages :-)
Interestingly enough, there was quite some human interaction
necessary, e.g., to avoid summation over poles. Exactly this kind of
problems have been checked carefully in the extended
version~\cite{Schneider:T04c}.



\subsection{Lost proofs of the Handbook of Mathematical Functions}\label{Sec:AbraStegun}

In spring 2005 Frank Olver asked Peter Paule if the algorithms of
the RISC combinatorics group can provide proofs of about twelve
identities in the Handbook of Mathematical
Functions~\cite{Abramowitz:65}. The real challenge was that the
original proofs have been lost and no alternative proofs were known.
After a long weekend the Comb-group could find computer proofs for
each of the identities~\cite{SchneiderP:06b}. One of the identities
is~\cite[Equ.~(10.1.48)]{Abramowitz:65}
\begin{equation}\label{Equ:AbrStegOrg}
J_0(z\sin\theta)=\sum_{k=0}^\infty(4k+1)\frac{(2k)!}{2^{2k}k!^2}j_{2k}(z)P_{2k}(\cos\theta)
\end{equation}
where $P_k(z)$ are the Legendre polynomials, $J_k(z)$ are the Bessel
functions of the first kind, and $j_k(z)$ are Spherical Bessel
functions of the first kind.

When I have seen this identity for the first time, I wondered
myself, what~\SigmaP\ could have in common with all these functions.
After having a closer look, it was clear: The problem can be
transformed exactly to the input class of \SigmaP. First we apply
the substitution $t:=\cos\theta$. Hence with
$\sin(\theta)=\sqrt{1-t^2}$ our identity reads as
$$J_0(z\sqrt{1-t^2})=\sum_{k=0}^\infty(4k+1)\frac{(2k)!}{2^{2k}k!^2}j_{2k}(z)P_{2k}(t).$$
Moreover, by hypergeometric series representations
from~\cite{Abramowitz:65} we get
\begin{align*} J_0(z
\sqrt{1-t^2})&=\sum_{n=0}^{\infty}\frac{(-\frac{1}{2}z^2)^n}{n!^2}\left(\frac{1-t^2}{2}\right)^n,&
P_{2k}(t)&=\sum_{i=0}^{\infty}\frac{(-2k)_i(2k+1)_i}{i!^2}\left(\frac{1-t}{2}\right)^i,\\
\end{align*}

\vspace*{-0.5cm}

\noindent and $P(k):=P(z,k)=j_{2k}(z)$ from~\eqref{Equ:BesselSum}.
Summarizing, we have to show
\begin{equation}\label{Equ:AbrStegId}
\sum_{n=0}^{\infty}a_n\left(\frac{1-t^2}{2}\right)^n=\sum_{n=0}^{\infty}b_n\left(\frac{1-t}{2}\right)^n
\end{equation}

\vspace*{-0.5cm}

where
\begin{align*}
a_n&=\frac{(-\frac{1}{2}z^2)^n}{n!^2},&\text{and}&&
b_n&=\sum_{k=0}^{\infty}(4k+1)\frac{(2k)!}{2^{2k}k!}\frac{(-2k)_n(2k+1)_n}{n!^2}P(k).
\end{align*}
Given this representation, our RISC-packages can finish the job.
First we derive recurrences for $a_k$ and $b_k$; the recurrence $z^2
a_n+2(n+1)^3a_{n+1}=0$ is immediate. We get a recurrence for $b_k$
by the following function call; here we use the
recurrence~\myOut{\ref{MMA:sumPForAbr}} for $P(k)$.

\begin{mma}
\In recB = GenerateRecurrence[\newline
\hspace*{1cm}\sum_{k=0}^{\infty}(4k+1)\frac{(2k)!}{2^{2k}k!}\frac{(-2k)_n(2k+1)_n}{n!^2}P[k],
n, \{recP,P[k]\}][[1]]/. SUM\to b\\
\Out4(n+3)z^2b[n]-2(2n+5)z^2b[n+1]
-(n+2)(n^2+5n+6-z^2)b[n+2]+(n+2)(n+3)^2b[n+3]==0\\
\end{mma}

\noindent Next, we use closure properties of holonomic
functions~\cite{Salvy:94} in order to compute differential equations
for both sides of~\eqref{Equ:AbrStegId}. The
package~\cite{Mallinger:96} (which is inspired by~\cite{Salvy:94})
helps here.

\begin{mma}
\In << GeneratingFunctions.m \\
\Print GeneratingFunctions Package by Christian Mallinger
\copyright\ RISC-Linz\\
\end{mma}

\noindent Namely, given the recurrence for $b_k$, we get a
differential equation for $\sum_{k=0}^{\infty}b_kt^k$ by the
function call

\begin{mma}
\In deB = RE2DE[recB, b[k], B[t]]\\
\Out 12z^2 B[t]+10(2t z^2-z^2)B'[t]
+(4t^2z^2-4tz^2+z^2-6)B''[t]-3(2t-1)B^{(3)}[t]-t(t-1)B^{(4)}[t]==0\\
\end{mma}

\noindent Then by the substitution $t\to(1-t)/2$ we compute

\begin{mma}
\In{deB = ACompose[deB, B[t] == (1 - t)/2, B[t]]}\\
\Out -3z^2 B[t]-5t z^2B'[t]-(t^2z^2-6)B''(t)+6tB^{(3)}[t]+(t+1)(t-1)B^{(4)}[t]==0\\
\end{mma}


\noindent for
$B(t)=\sum_{k=0}^{\infty}b_k\left(\frac{1-t}{2}\right)^k$.
Similarly, we obtain

\begin{mma}
\In deA=-t^3z^2 A[t]+(t^2+1)A'[t]+t(t+1)(t-1)A''[t]==0;\\
\end{mma}

\noindent for
$A(t)=\sum_{k=0}^{\infty}a_k\left(\frac{1-t^2}{2}\right)^k$. With
\begin{mma}
\In DEPlus[(deA/.A\to C),(deB/.B\to C), C[t]]\\
\Out -3z^2 C[t]-5t z^2C'[t]-(t^2z^2-6)C''(t)+6tC^{(3)}[t]+(t+1)(t-1)C^{(4)}[t]==0\\
\end{mma}

\noindent we find a differential equation for $C(t):=A(t)-B(t).$ By
inspection we get the initial conditions $b_0=a_0$, $b_1=2a_1$, and
$b_2=-2a_1+4a_2$. Notice that these are the already proven
identities~\eqref{Equ:InitialId}. This completes the proof
of~\eqref{Equ:AbrStegId} and therefore of~\eqref{Equ:AbrStegOrg}.



\section{Conclusion}

I illustrated how \SigmaP\ can handle non-trivial summation
problems, most of them related to combinatorial questions. As a
conclusion I want to emphasize that the title can be reversed:
``Combinatorics assists symbolic summation''. Namely, most of the
examples in this survey article were important case studies to
improve the summation package \SigmaP. Even more, challenging
problems, like the TSPP-problem, were the source to extend \SigmaP.

I am looking forward to see how symbolic summation and combinatorics
will inspire each other in the future.

The first public release of \SigmaP\ is planned for summer 2007.

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{DPSW06b}

\bibitem[ABP95]{Abramov:95b}
S.A. Abramov, M.~Bronstein, and M.~Petkov{\v s}ek.
\newblock On polynomial solutions of linear operator equations.
\newblock In T.~Levelt, editor, {\em Proc. ISSAC'95}, pages 290--296. ACM
  Press, 1995.

\bibitem[Abr75]{Abramov:75}
S.A. Abramov.
\newblock The rational component of the solution of a first-order linear
  recurrence relation with a rational right-hand side.
\newblock {\em U.S.S.R. Comput. Maths. Math. Phys.}, 15:216--221, 1975.
\newblock Transl. from Zh. vychisl. mat. mat. fiz. 15, pp. 1035--1039, 1975.

\bibitem[Abr89a]{Abramov:89b}
S.A. Abramov.
\newblock Problems in computer algebra that are connected with a search for
  polynomial solutions of linear differential and difference equations.
\newblock {\em Moscow Univ. Comput. Math. Cybernet.}, 3:63--68, 1989.

\bibitem[Abr89b]{Abramov:89a}
S.A. Abramov.
\newblock Rational solutions of linear differential and difference equations
  with polynomial coefficients.
\newblock {\em U.S.S.R. Comput. Math. Math. Phys.}, 29(6):7--12, 1989.

\bibitem[Abr95]{Abramov:95a}
S.A. Abramov.
\newblock Rational solutions of linear difference and $q$-difference equations
  with polynomial coefficients.
\newblock In T.~Levelt, editor, {\em Proc. ISSAC'95}, pages 285--289. ACM
  Press, 1995.

\bibitem[Abr03]{Abramov:03b}
S.A. Abramov.
\newblock When does {Z}eilberger's algorithm succeed?
\newblock {\em Adv. in Appl. Math.}, 30:424--441, 2003.

\bibitem[ACGL04]{Abramov:04}
S.A. Abramov, J.J. Carette, K.O. Geddes, and H.Q. Le.
\newblock Telescoping in the context of symbolic summation in {M}aple.
\newblock {\em J.~Symbolic Comput.}, 38:1303--1326, 2004.

\bibitem[AL05]{Abramov:05}
S.A. Abramov and H.Q. Le.
\newblock On the order of the recurrence produced by the method of creative
  telescoping.
\newblock {\em Discrete Math.}, 298:2--17, 2005.

\bibitem[ALP03]{Abramov:03a}
S.A. Abramov, H.Q. Le, and M.~Petkovsek.
\newblock Rational canonical forms and efficient representations of
  hypergeometric terms.
\newblock In J.R. Sendra, editor, {\em Proc. ISSAC'03}, pages 7--14. ACM Press,
  2003.

\bibitem[AP94]{Abramov:94}
S.A. Abramov and M.~Petkov{\v s}ek.
\newblock D'{A}lembertian solutions of linear differential and difference
  equations.
\newblock In J.~von~zur Gathen, editor, {\em Proc. ISSAC'94}, pages 169--174.
  ACM Press, 1994.

\bibitem[AP99]{Andrews:99}
G.E. Andrews and P.~Paule.
\newblock Mac{M}ahon's partition analysis {I}{V}: Hypergeometric multisums.
\newblock {\em S\'em. Lothar. Combin.}, B42i:1--24, 1999.

\bibitem[AP02]{Abramov:02}
S.A. Abramov and M.~Petkov{\v s}ek.
\newblock Rational normal forms and minimal decompositions of hypergeometric
  terms.
\newblock {\em J.~Symbolic Comput.}, 33(5):521--543, 2002.

\bibitem[AP06]{Petkovsek:06}
S.A. Abramov and M.~Petkov{\v s}ek, 2006.
\newblock Private Communication.

\bibitem[APP98]{Abramov:98}
S.A. Abramov, P.~Paule, and M.~Petkov{\v s}ek.
\newblock $q$-{H}ypergeometric solutions of $q$-difference equations.
\newblock {\em Discrete Math.}, 180(1-3):3--22, 1998.

\bibitem[APS04]{Schneider:T04c}
G.E. Andrews, P.~Paule, and C.~Schneider.
\newblock Plane partitions {V}{I}: {S}tembridge's {T}{S}{P}{P} {T}heorem --- a
  detailed algorithmic proof.
\newblock Technical Report 04-08, RISC-Linz, J.~Kepler University, 2004.

\bibitem[APS05]{Schneider:05e}
G.E. Andrews, P.~Paule, and C.~Schneider.
\newblock {Plane Partitions VI: Stembridge's TSPP Theorem}.
\newblock {\em Advances in Applied Math.}, 34(4):709--739, 2005.

\bibitem[AS65]{Abramowitz:65}
M.~Abramowitz and I.A. Stegun.
\newblock {\em Handbook of Mathematical Functions}.
\newblock Dover Publications, Inc, New York, 1965.

\bibitem[AU85]{Andrews:85}
G.E. Andrews and K.~Uchimura.
\newblock Identities in combinatorics {I}{V}: Differentiation and harmonic
  numbers.
\newblock {\em Util. Math.}, 28:265--269, 1985.

\bibitem[AZ06]{Zeilberger:06}
M.~Apagodu and D.~Zeilberger.
\newblock Multi-variable {Z}eilberger and {A}lmkvist–--{Z}eilberger algorithms
  and the sharpening of {W}ilf–--{Z}eilberger theory.
\newblock {\em Advances in Applied Math.}, 37:139--152, 2006.

\bibitem[BG96]{Borwein:96}
J.M. Borwein and R.~Girgensohn.
\newblock Evaluation of triple {E}uler sums.
\newblock {\em Electron. J.~Combin.}, 3:1--27, 1996.

\bibitem[BK99]{Koepf:99}
H.~B{\"o}ing and W.~Koepf.
\newblock Algorithms for q-hypergeometric summation in computer algebra.
\newblock {\em J.~Symbolic Comput.}, 28:777--799, 1999.

\bibitem[BP99]{Bauer:99}
A.~Bauer and M.~Petkov{\v{s}}ek.
\newblock Multibasic and mixed hypergeometric {Gosper}-type algorithms.
\newblock {\em J.~Symbolic Comput.}, 28(4--5):711--736, 1999.

\bibitem[BPP{\etalchar{+}}06]{Schneider:06g}
A.~Be\'cirovi\'c, P.~Paule, V.~Pillwein, A.~Riese, C.~Schneider, and
  J.~Sch\"oberl.
\newblock Hypergeometric summation algorithms for high order finite elements.
\newblock {\em Computing}, 78(3):235--249, 2006.

\bibitem[Bro00]{Bron:00}
M.~Bronstein.
\newblock On solutions of linear ordinary difference equations in their
  coefficient field.
\newblock {\em J.~Symbolic Comput.}, 29(6):841--877, 2000.

\bibitem[Bro05]{Bron:05}
M.~Bronstein, 2005.
\newblock Private Communication.

\bibitem[Cal94]{Calkin:94}
N.J. Calkin.
\newblock A curious binomial identity.
\newblock {\em Discrete Math.}, 131(1-3):335--337, 1994.

\bibitem[CHM05]{Chen:05}
W.Y.C. Chen, Q.H. Hou, and Y.P. Mu.
\newblock Applicability of the $q$-analogue of {Z}eilberger's algorithm.
\newblock {\em J.~Symbolic Comput.}, 39:155--170, 2005.

\bibitem[CHM06]{Chen:06}
W.Y.C. Chen, Q.H. Hou, and Y.P. Mu.
\newblock A telescoping method for double summations.
\newblock {\em J. Comput. Appl. Math.}, 196(2):553--566, 2006.

\bibitem[Chu05]{Chu:05}
W.~Chu.
\newblock Harmonic number identities and {H}ermite-{P}ad\'e approximations to
  the logarithm function.
\newblock {\em Journal of Approximation Theory}, 137(1):42 -- 56, 2005.

\bibitem[Chy00]{Chyzak:00}
F.~Chyzak.
\newblock An extension of {Z}eilberger's fast algorithm to general holonomic
  functions.
\newblock {\em Discrete Math.}, 217:115--134, 2000.

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

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

\bibitem[Dix03]{Dixon:03}
A.C. Dixon.
\newblock Summation of a certain series.
\newblock {\em Proc. London Math. Soc. (1)}, 35:285--289, 1903.

\bibitem[DPSW06a]{Schneider:06a}
K.~Driver, H.~Prodinger, C.~Schneider, and J.A.C. Weideman.
\newblock Pad\'e approximations to the logarithm~{II}: Identities, recurrences,
  and symbolic computation.
\newblock {\em Ramanujan~J.}, 11(2):139--158, 2006.

\bibitem[DPSW06b]{Schneider:06b}
K.~Driver, H.~Prodinger, C.~Schneider, and J.A.C. Weideman.
\newblock Pad\'e approximations to the logarithm~{III}: Alternative methods and
  additional results.
\newblock {\em Ramanujan~J.}, 12(3):299--314, 2006.

\bibitem[Fas45]{Celine:45}
{Sister Mary Celine} Fasenmyer.
\newblock {\em Some generalized hypergeometric polynomials}.
\newblock PhD thesis, University of Michigan, 1945.

\bibitem[FK00]{Krattenthaler:00}
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 J.~Combin.}, 21(5):601--640, 2000.

\bibitem[FS98]{Flajolet:98}
P.~Flajolet and B.~Salvy.
\newblock Euler sums and contour integral representations.
\newblock {\em Experimental Math.}, 7(1):15--35, 1998.

\bibitem[Ger04]{Gerhard:04}
J.~Gerhard.
\newblock {\em Modular algorithms in symbolic summation and symbolic
  integration}.
\newblock Lecture Notes in Computer Science. Springer, 2004.

\bibitem[GKO{\etalchar{+}}06]{SchneiderP:06b}
S.~Gerhold, M.~Kauers, F.W.J. Olver, P.~Paule, C.~Schneider, and
B.~Zimmermann.
\newblock Computer proofs of some identities involving derivatives of bessel
  functions with respect to order.
\newblock {\em In preparation}, 2006.

\bibitem[GKP94]{Graham:94}
R.L. Graham, D.E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics: a foundation for computer science}.
\newblock Addison-Wesley Publishing Company, Amsterdam, 2nd edition, 1994.

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

\bibitem[Hir96]{Hirschhorn:96}
M.~Hirschhorn.
\newblock Calkin's binomial identity.
\newblock {\em Discrete Math.}, 273-278, 1996.

\bibitem[Hoe98]{vanHoeij:98}
{M.~van} Hoeij.
\newblock Rational solutions of linear difference equations.
\newblock In O.~Gloor, editor, {\em Proc. ISSAC'98}, pages 120--123. ACM Press,
  1998.

\bibitem[Hoe99]{vanHoeij:99}
{M.~van} Hoeij.
\newblock Finite singularities and hypergeometric solutions of linear
  recurrence equations.
\newblock {\em J.~Pure Appl. Algebra}, 139(1-3):109--131, 1999.

\bibitem[Hor92]{Hornegger:92}
J.~Hornegger.
\newblock Hypergeometrische {S}ummation und polynomiale {R}ekursion.
\newblock Master's thesis, University Erlangen, 1992.

\bibitem[HS99]{Singer:99}
P.A. Hendriks and M.F. Singer.
\newblock Solving difference equations in finite terms.
\newblock {\em J.~Symbolic Comput.}, 27(3):239--259, 1999.

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

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

\bibitem[Koe95]{Koepf:95}
W.~Koepf.
\newblock Algorithms for m-fold hypergeometric summation.
\newblock {\em J.~Symbolic Comput.}, 20(399-417), 1995.

\bibitem[Koo93]{Koornwinder:93}
T.H. Koornwinder.
\newblock On {Z}eilberger's algorithm and its $q$-analogue.
\newblock {\em J.~Comp. Appl. Math.}, 48:91--111, 1993.

\bibitem[Kra03]{Kratt:03}
C.~Krattenthaler, 2003.
\newblock Private Communication.

\bibitem[KS06a]{Schneider:06e}
M.~Kauers and C.~Schneider.
\newblock Application of unspecified sequences in symbolic summation.
\newblock In J.G. Dumas, editor, {\em Proc. ISSAC'06.}, pages 177--183. ACM
  Press, 2006.

\bibitem[KS06b]{Schneider:06d}
M.~Kauers and C.~Schneider.
\newblock Indefinite summation with unspecified summands.
\newblock {\em Discrete Math.}, 306(17):2021--2140, 2006.

\bibitem[M06]{Kauers:06}
Kauers M.
\newblock {{S}um {C}racker -- {A} Package for Manipulating Symbolic Sums and
  Related Objects}.
\newblock {\em J.~Symbolic Computat.}, 41(9):1039--1057, 2006.

\bibitem[Mal96]{Mallinger:96}
C.~Mallinger.
\newblock Algorithmic manipulations and transformations of univariate holonomic
  functions and sequences.
\newblock Master's thesis, RISC, J.~Kepler University, Linz, 1996.

\bibitem[MZ05]{Zeilberger:05b}
M.~Mohammed and D.~Zeilberger.
\newblock Sharp upper bounds for the orders of the recurrences outputted by the
  {Z}eilberger and q-{Z}eilberger algorithms.
\newblock {\em J.~Symbolic Comput.}, 39:201--207, 2005.

\bibitem[Oka89]{Okada:89}
S.~Okada.
\newblock On the generating functions for certain classes of plane partitions.
\newblock {\em J.~Combin. Theory Ser. A}, 51:1--23, 1989.

\bibitem[Pau95]{Paule:95}
P.~Paule.
\newblock Greatest factorial factorization and symbolic summation.
\newblock {\em J.~Symbolic Comput.}, 20(3):235--268, 1995.

\bibitem[Pau04]{Paule:06a}
P.~Paule.
\newblock Contiguous relations and creative telescoping.
\newblock {\em Preprint}, 2004.

\bibitem[Pet92]{Petkov:92}
M.~Petkov{\v s}ek.
\newblock Hypergeometric solutions of linear recurrences with polynomial
  coefficients.
\newblock {\em J.~Symbolic Comput.}, 14(2-3):243--264, 1992.

\bibitem[PP05]{Prodinger:05}
A.~Panholzer and H.~Prodinger.
\newblock Computer-free evaluation of an infinite double sum.
\newblock {\em S\'em. Lothar. Combin.}, 55:1--3, 2005.

\bibitem[PR97]{PauleRiese:97}
P.~Paule and A.~Riese.
\newblock A {M}athematica q-analogue of {Z}eil\-ber\-ger'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[PS95a]{PauleSchorn:95}
P.~Paule and M.~Schorn.
\newblock A {M}athematica version of {Z}eilberger's algorithm for proving
  binomial coefficient identities.
\newblock {\em J.~Symbolic Comput.}, 20(5-6):673--698, 1995.

\bibitem[PS95b]{PauleStrehl:95}
P.~Paule and V.~Strehl.
\newblock Symbolic summation - some recent developments.
\newblock In J.~Fleischer et~al., editor, {\em Computer Algebra in Science and
  Engineering - Algorithms, Systems, and Applications}, pages 138--162. World
  Scientific, Singapore, 1995.

\bibitem[PS95c]{Pirastu:95a}
R.~Pirastu and V.~Strehl.
\newblock Rational summation and {G}osper-{P}etkov{\v s}ek representation.
\newblock {\em J.~Symbolic Comput.}, 20:617--635, 1995.

\bibitem[PS03]{Schneider:03}
P.~Paule and C.~Schneider.
\newblock Computer proofs of a new family of harmonic number identities.
\newblock {\em Adv. in Appl. Math.}, 31(2):359--378, 2003.

\bibitem[PS04]{SchneiderP:06a}
P.~Paule and C.~Schneider.
\newblock Creative telescoping for hypergeometric double sums.
\newblock {\em Preprint}, 2004.

\bibitem[PS07]{Schneider:06c}
R.~Pemantle and C.~Schneider.
\newblock When is 0.999... equal to 1?
\newblock {\em To appear in Amer. Math. Monthly}, April 2007.

\bibitem[PWZ96]{AequalB}
M.~Petkov{\v s}ek, H.~S. Wilf, and D.~Zeilberger.
\newblock {\em $A=B$}.
\newblock A. K. Peters, Wellesley, MA, 1996.

\bibitem[Rie03]{Riese:03}
A.~Riese.
\newblock q{M}ultisum - {A} package for proving $q$-hypergeometric multiple
  summation identities.
\newblock {\em J.~Symbolic Comput.}, 35:349--377, 2003.

\bibitem[Ris69]{Risch:69}
R.~Risch.
\newblock The problem of integration in finite terms.
\newblock {\em Trans. Amer. Math. Soc.}, 139:167--189, 1969.

\bibitem[Ris70]{Risch:70}
R.~Risch.
\newblock The solution to the problem of integration in finite terms.
\newblock {\em Bull. Amer. Math. Soc.}, 76:605--608, 1970.

\bibitem[Sch00]{Schneider:00}
C.~Schneider.
\newblock An implementation of {K}arr's summation algorithm in {M}athematica.
\newblock {\em S\'em. Lothar. Combin.}, S43b:1--10, 2000.

\bibitem[Sch01]{Schneider:T01}
C.~Schneider.
\newblock Symbolic summation in difference fields.
\newblock Technical Report 01-17, RISC-Linz, J.~Kepler University, November
  2001.
\newblock PhD Thesis.

\bibitem[Sch02]{Schneider:02}
C.~Schneider.
\newblock How one can play with sums.
\newblock In H.~Kredel and W.~Seiler, editors, {\em Proceedings of the 8th
  Rhine Workshop on Computer Algebra}, pages 73--83, Mannheim, Germany, 2002.

\bibitem[Sch04a]{Schneider:04b}
C.~Schneider.
\newblock A collection of denominator bounds to solve parameterized linear
  difference equations in ${\Pi}{\Sigma}$-extensions.
\newblock In D.~Petcu et~al., editor, {\em Proc. SYNASC04}, pages 269--282.
  Mirton Publishing, 2004.

\bibitem[Sch04b]{Schneider:04c}
C.~Schneider.
\newblock The summation package {S}igma: Underlying principles and a rhombus
  tiling application.
\newblock {\em Discrete Math. Theor. Comput. Sci.}, 6(2):365--386, 2004.

\bibitem[Sch04c]{Schneider:04a}
C.~Schneider.
\newblock Symbolic summation with single-nested sum extensions.
\newblock In J.~Gutierrez, editor, {\em Proc. ISSAC'04}, pages 282--289. ACM
  Press, 2004.

\bibitem[Sch05a]{Schneider:05b}
C.~Schneider.
\newblock Degree bounds to find polynomial solutions of parameterized linear
  difference equations in ${\Pi}{\Sigma}$-fields.
\newblock {\em Appl. Algebra Engrg. Comm. Comput.}, 16(1):1--32, 2005.

\bibitem[Sch05b]{Schneider:05f}
C.~Schneider.
\newblock Finding telescopers with minimal depth for indefinite nested sum and
  product expressions.
\newblock In M.~Kauers, editor, {\em Proc. ISSAC'05}, pages 285--292. ACM,
  2005.

\bibitem[Sch05c]{Schneider:05d}
C.~Schneider.
\newblock A new {S}igma approach to multi-summation.
\newblock {\em Advances in Applied Math.}, 34(4):740--767, 2005.

\bibitem[Sch05d]{Schneider:05c}
C.~Schneider.
\newblock Product representations in ${\Pi}{\Sigma}$-fields.
\newblock {\em Annals of Combinatorics}, 9(1):75--99, 2005.

\bibitem[Sch05e]{Schneider:05a}
C.~Schneider.
\newblock Solving parameterized linear difference equations in terms of
  indefinite nested sums and products.
\newblock {\em J. Differ. Equations Appl.}, 11(9):799--821, 2005.

\bibitem[Sch06]{Schneider:05g}
C.~Schneider.
\newblock Some notes on ``{W}hen is 0.999... equal to 1?''.
\newblock In Thierry~Coquand et~al., editor, {\em Mathematics, Algorithms,
  Proofs}, number 05021 in Dagstuhl Seminar Proceedings. Internationales
  Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany, 2006.

\bibitem[Sch07]{Schneider:06f}
C.~Schneider.
\newblock Simplifying sums in ${\Pi}{\Sigma}^*$-extensions.
\newblock {\em To appear in J. Algebra Appl.}, 2007.

\bibitem[Sta86]{Stanley:86b}
R.P. Stanley.
\newblock Symmetries of plane partitions.
\newblock {\em J.~Combin. Theory Ser. A}, 43:103--113, 1986.

\bibitem[Ste95]{Stembridge:95}
J.~Stembridge.
\newblock The enumeration of totally symmetric plane partitions.
\newblock {\em Advances in Math.}, 111:227--243, 1995.

\bibitem[SZ94]{Salvy:94}
B.~Salvy and P.~Zimmermann.
\newblock Gfun: A package for the manipulation of generating and holonomic
  functions in one variable.
\newblock {\em ACM Trans. Math. Software}, 20:163--177, 1994.

\bibitem[Ver74]{Verbaeten:74}
P.~Verbaeten.
\newblock The automatic construction of pure recurrence equations.
\newblock {\em ACM-SIGSAM Bulletin}, 8:96--98, 1974.

\bibitem[Weg97]{Wegschaider:97}
K.~Wegschaider.
\newblock Computer generated proofs of binomial multi-sum identities.
\newblock Di\-plo\-ma thesis, RISC Linz, Johannes Kepler University, 1997.

\bibitem[Wei05]{Weideman:05}
J.A.C. Weideman.
\newblock Pad\'e approximations to the logarithm {I}: Derivation via
  differential equations.
\newblock {\em Quaestiones Mathematicae}, 28:375--390, 2005.

\bibitem[WZ92]{Wilf:92}
H.~Wilf and D.~Zeilberger.
\newblock An algorithmic proof theory for hypergeometric (ordinary and ``q'')
  multisum/integral identities.
\newblock {\em Invent. Math.}, 108:575--633, 1992.

\bibitem[Zei90]{Zeilberger:90a}
D.~Zeilberger.
\newblock A holonomic systems approach to special functions identities.
\newblock {\em J.~Comput. Appl. Math.}, 32:321--368, 1990.

\bibitem[Zei91]{Zeilberger:91}
D.~Zeilberger.
\newblock The method of creative telescoping.
\newblock {\em J.~Symbolic Comput.}, 11:195--204, 1991.

\bibitem[Zei05]{Zeilberger:05a}
D.~Zeilberger.
\newblock Opinion 65.
\newblock http://www.math.rutgers.edu/~zeilberg/Opinion65.html, 2005.

\bibitem[Zha99]{Zhang:99}
Z.~Zhang.
\newblock A kind of binomial identity.
\newblock {\em Discrete Math.}, 196(1-3):291--298, 1999.

\end{thebibliography}

\end{document}
