%\documentclass[11pt,reqno]{amsart}
\documentclass[12pt]{article}
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 

\newcommand{\SigmaP}{{\sf Sigma}}


\textheight=23.0cm

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



\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 ##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}}




\makeatletter %% this should really go into a style file!

\renewcommand\section{\@startsection {section}{1}{\z@}%
                                 % {-3.5ex \@plus -1ex \@minus -.2ex}%
        % here is your vskip of 30pt:
                                   {-30pt  \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
        % add a point after section numbers:

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad}

\makeatother

\begin{document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A22}
\vskip 40pt
\begin{center}
\uppercase{\bf Truncating Binomial Series with Symbolic Summation}
\vskip 20pt
{\bf Peter Paule}\\
{\smallit Research Institute for Symbolic Computation,
J. Kepler University Linz,
A-4040 Linz, Austria}\\
{\tt Peter.Paule@risc.uni-linz.ac.at}\\ 
\vskip 10pt
{\bf Carsten Schneider\footnote{Supported by the SFB-grant F1305 and the grant
P16613-N12 of the Austrian FWF.
}}\\
{\smallit Research Institute for Symbolic Computation,
J. Kepler University Linz,
A-4040 Linz, Austria}\\
{\tt Carsten.Schneider@risc.uni-linz.ac.at}\\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: 1/4/07, Accepted: 4/3/07,
 Published: 4/24/07}
\vskip 30pt 

\centerline{\bf Abstract}

\noindent
Taking an example from statistics, we show how symbolic summation
can be used to find generalizations of binomial identities that
involve infinite series. In such generalizations, the infinite series
are replaced by truncated versions.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
 JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A22\hfill}

\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt


\section{Introduction}

Consider the identity
\begin{equation}\label{Equ:OriginalSum}
\sum_{k=m+1}^{\infty}\frac{m}{k(k-1)}\sum_{j=0}^m\binom{k}{j}x^{k-j}(1-x)^j=x,\quad
m\geq1,\;0\leq x\leq1,
\end{equation}
which arose in the theory of records~\cite{Blom:86,Israel:88}. In an
attempt to generalize this result, Tam{\'a}s
Lengyel~\cite{Lengyel:06} found the binomial series
$$a_{m,n}(x)=\binom{m}{n-1}\sum_{k=m+1}^{\infty}\binom{k}{n}^{-1}\sum_{j=0}^m\binom{k}{j}x^{k-j}(1-x)^j,$$
which evaluates for all integers $n$ and $m$ with $0\leq n-1\leq m$
to
\begin{equation}\label{LengyelId}
a_{m,n}(x)=\begin{cases} \frac{n}{n-1}\big(1-(1-x)^{n-1}\big),&\text{if }n\geq2\text{ and }0\leq x\leq1\\
-\ln(1-x),&\text{if }n=1\text{ and }0\leq x<1.
\end{cases}
\end{equation}
For $n=2$ one obtains the original identity.

In this note we illustrate how algorithms from symbolic summation
can be used to obtain generalizations of~\eqref{LengyelId} where
Lengyel's $a_{m,n}(x)$ series is replaced by the truncated version
$$a_{m,n}^{(K)}(x)=\binom{m}{n-1}\sum_{k=m+1}^{K}\binom{k}{n}^{-1}\sum_{j=0}^m\binom{k}{j}x^{k-j}(1-x)^j$$
in which $K\geq m+1$.

In Section~\ref{Sec:EvLengyel} we present an automatic evaluation of
$a_{m,n}(x)$ using Gosper's telescoping and Zeilberger's creative
telescoping algorithms, respectively. In Section~\ref{Sec:TruncOrg}
we observe that for specific values of $n$ creative telescoping can
be replaced by plain telescoping. This gives rise to conjecture that
identities for the truncated version $a_{m,n}^{(K)}(x)$ exist. In
Section~\ref{Sec:TruncLeng} we derive such identities which in the
limit $K\to\infty$ give~\eqref{LengyelId}; see~\eqref{Equ:MainId1}
and~\eqref{Equ:MainId2}. To obtain the limit for $K\to\infty$, a
generating function identity~\eqref{Equ:HarId} is used. In
Section~\ref{Sec:GenSigma} we demonstrate that~\eqref{Equ:HarId} can
be also derived with symbolic summation. In
Section~\ref{Sec:Conclusion} some concluding remarks are given.

All computations are done using the
package~\SigmaP~\cite{Schneider:04c}; to derive~\eqref{Equ:MainId1}
and~\eqref{Equ:MainId2} special \SigmaP\ features are applied.


\section{Automatic Evaluation of $a_{m,n}(x)$}\label{Sec:EvLengyel}

Before applying computer algebra it is convenient to rewrite
$a_{m,n}(x)$ as a series expanded in powers of $x$. To this end, in
$a_{m,n}(x)$ we replace $(1-x)^j$ with
$\sum_l(-1)^l\binom{j}{l}x^l$. Then collecting coefficients of $x^N$
($N=k-j+l$) turns Lengyel's series into
$$
a_{m,n}(x)=\binom{m}{n-1}\sum _{N=1}^{\infty }
   (-1)^N x^N \sum_{k=m+1}^{\infty }
   (-1)^k\binom{k}{n}^{-1}A_{m}(N)$$ where
$$A_{m}(N)=\sum_{j=0}^m(-1)^j\binom{k}{j}\binom{j}{N-k+j}.$$
Now the rest can be done with computer algebra. After loading the
\SigmaP\ package 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 the hypergeometric sum ${\tt S}=A_{m}(N)$. Note
that various \SigmaP\ functions support the user, like {\tt
SigmaSum} for sums, {\tt SigmaProduct} for products, {\tt
SigmaPower} for powers, or {\tt SigmaBinomial} for binomials.

\begin{mma}
\In S=SigmaSum[\newline
\hspace*{1cm}SigmaPower[-1,j]SigmaBinomial[k,j]SigmaBinomial[{j},{N-k+j}],\{j,0,m\}]\\
\Out\sum_{j=0}^m(-1)^j\binom{k}{j}\binom{j}{N-k+j}\\
\end{mma}

\noindent Then, by telescoping, \SigmaP\ produces the following closed
form for $A_{m}(x)(={\tt S})$:

\begin{mma}\MLabel{MMA:Sigma}
\In SigmaReduce[S]\\
\Out -\frac{(-1)^m (m-k)}{N}\binom{k}{m}\binom{m}{N-k+m}.\\
\end{mma}

\noindent This can  also be achieved by any implementation of
Gosper's algorithm~\cite{Gosper:78}, so we omit details here. Hence
\begin{equation}\label{Equ:Rewriteamn}
a_{m,n}(x)=(-1)^m\binom{m}{n-1}\sum_{N=1}^{\infty}\frac{(-1)^Nx^N}{N}B_{m,n}(N)
\end{equation}
where
$$B_{m,n}(N)=\sum_{k=m+1}^{\infty}(-1)^k\binom{k}{n}^{-1}\binom{k}{m}\binom{m}{N-k+m} (k-m).$$

Since telescoping fails to simplify $B_{m,n}(N)$, we continue
differently. Namely, for definite sums one can execute the \SigmaP\
function

\begin{mma}\MLabel{MMA:CreaTele}
\In GenerateRecurrence[
\sum_{k=m+1}^{\infty}(-1)^k \binom{k}{n}^{-1}\binom{k}{m}\binom{m}{N-k+m}(k-m),N]\\
\Out\{(-1+n-N)SUM[N]-N\,SUM[1+N]==0\}\\
\end{mma}
\noindent which is based on creative
telescoping~\cite{Zeilberger:91} and which computes the
recurrence~\myOut{\ref{MMA:CreaTele}} for
$\text{SUM}[N]=B_{m,n}(N)$. This can be also achieved by any
implementation of Zeilberger's algorithm, so we omit details here.

\medskip

The recurrence~\myOut{\ref{MMA:CreaTele}} gives
$B_{m,n}(N)=(-1)^{N+1}\binom{N-n}{N-1}B_{m,n}(1)$. With the initial
value $B_{m,n}(1)=-n(-1)^m\binom{m}{n-1}^{-1}$ we find
\begin{equation}\label{Exp:HypId}
B_{m,n}(x)=(-1)^{N+m}n\binom{m}{n-1}^{-1}\binom{N-n}{N-1},
\end{equation}
i.e.,
$$a_{m,n}(x)=n\sum_{N=1}^{\infty}\frac{x^N}{N}\binom{N-n}{N-1}.$$
Finally, for $n=1$,
$$a_{m,1}(x)=\sum_{N=1}^{\infty}\frac{x^N}{N}=-\ln(1-x);$$
for $n>1$, because of $\binom{N-n}{N-1}=(-1)^{N-1}\binom{n-2}{N-1}$,
$$a_{m,n}(x)=-\frac{n}{n-1}\sum_{N=1}^{\infty}(-x)^N\binom{n-1}{N}=
-\frac{n}{n-1}(-1+(1-x)^{n-1}).$$


\section{A Truncated Variant of the Original
Identity~\eqref{Equ:OriginalSum}}\label{Sec:TruncOrg}

With respect to our starting point,
identity~\eqref{Equ:OriginalSum}, the computer algebra approach
taken in Section~\ref{Sec:EvLengyel} brings along an additional
feature. Namely, if $n=2$, one observes that the $B_{m,2}^{(K)}(N)$
sum telescopes for $N>1$. Thus one has
\begin{align*}
B^{(K)}_{m,2}(N)&=\sum_{k=m+1}^{K}\frac{(-1)^k}{k(k-1)}\binom{k}{m}\binom{m}{N-k+m}(k-m)\\
&=(-1)^K\frac{(K-m)(K-m-N)}{Km(1-N)}\binom{K}{m}\binom{m}{K-N}
\end{align*}
for $N>1$ and arbitrary $K\geq m+1$. Obviously for $N=1$,
$$B^{(K)}_{m,2}(1)=\frac{(-1)^{m+1}}{m}\quad\text{for }K\geq m+1.$$
Consequently, the truncated version $a_{m,2}^{(K)}(x)$ of
$a_{m,2}(x)$ finds the following evaluation for $K\geq m+1$:
\begin{align}
a_{m,2}^{(K)}(x)&=2(-1)^mm\sum_{N=1}^K\frac{(-1)^Nx^N}{N}B_{m,2}^{(K)}(N)\nonumber\\
&=2x+2m(-1)^{K+m}\binom{K-1}{m}\sum_{N=2}^K\frac{(-1)^Nx^N}{N(N-1)}\binom{m-1}{K-N}.\label{Equa2mDef}
\end{align}
In the limit $K\to\infty$, one retrieves
identity~\eqref{Equ:OriginalSum}.

One observes that $B_{m,n}^{(K)}(x)$ also telescopes for all other
specific values of $n\geq3$. This suggests that a nice truncated
generalization like~\eqref{Equa2mDef} might exist for generic $n$.
To obtain such a formula, one could try to guess a pattern from the
evaluations at $n=2,3$, etc. However, we prefer to utilize specific
features of \SigmaP\ which will lead us to an answer in the form of
identities~\eqref{Equ:MainId1} and~\eqref{Equ:MainId2}.




\section{Closed Form Evaluations of $a^{(K)}_{m,n}(x)$}\label{Sec:TruncLeng}

In contrast to Sections~\ref{Sec:EvLengyel} and~\ref{Sec:TruncOrg},
we will apply \SigmaP\ to $a_{m,n}^{(K)}(x)$ in its original form.
To this end, it will be convenient to proceed with a slight
variation of the truncated generalization of $a_{m,n}^{(K)}(x)$,
namely,
\begin{equation*}
\alpha_{m,n}^{(K)}(x):=\sum_{k=1}^{K}\frac{x^{m+k}}{\binom{m+k}{n}}D_{m,k}(x)
\end{equation*}
with
$$D_{m,k}(x)=\sum_{j=0}^m\frac{(1-x)^j}{x^{j}}\binom{m+k}{j}.$$
Note that for $K\geq m+1\geq n\geq1$,
\begin{equation}\label{Equ:TransAlphaA}
a_{m,n}^{(K)}(x)=\binom{m}{n-1}\alpha_{m,n}^{(K-m)}(x).
\end{equation}
Also note that we restrict to $x\neq0$; the case $x=0$ is trivial.

\subsection{Preprocessing} A first step to simplify the sum
$\alpha^{(K)}_{m,n}(x)$ is to represent the inner sum $D_{m,k}(x)$
as an indefinite sum in $k$. This means, we try to express
$D_{m,k}(x)$ in form of a sum $\sum_{j=0}^kf(m,j)$ where the summand
$f(m,j)$ is free of $k$. In order to accomplish this goal, we insert
$D_{m,k}(x)$ with
\begin{mma}
\In D=\sum_{j=0}^m\frac{(1-x)^j}{x^{j}}\binom{m+k}{j};\\
\end{mma}
\noindent and compute a recurrence\footnote{As
in~\myOut{\ref{MMA:CreaTele}}, this can be achieved by any
implementation of Zeilberger's algorithm.} for
$\text{SUM}[k]=D_{m,k}(x)$:

\begin{mma}
\In rec= GenerateRecurrence[D, k][[1]]\\
\Out x^m \text{SUM}[k]-x^{m+1}\text{SUM}[k+1]==(1-x)^{m+1} \binom{k+m}{m}\\
\end{mma}
\noindent Next, we solve this recurrence with the \SigmaP\ function
\begin{mma}
\In recSol = SolveRecurrence[rec, SUM[k]]\\
\Out\{\{0,\prod_{i=1}^k\frac{1}{x}\},\{1,-\left(\prod_{i=1}^k\frac{1}{x}\right)\frac{(1-x)^{m+1}}{x^{m+1}}\sum_{i=0}^k\frac{i\binom{m+i}{m}x^i}{m+i}\}\}\\
\end{mma}
\noindent This means that $\frac{1}{x^k}$ is a solution of the
homogeneous version, and
$-\frac{(1-x)^{m+1}}{x^{m+k+1}}\sum_{i=0}^k\frac{i\binom{m+i}{m}x^i}{m+i}$
is a particular solution of the recurrence itself. As a consequence
we can write
$$D_{m,k}(x)=\frac{c}{x^k}-\frac{(1-x)^{m+1}}{x^{m+k+1}}\sum_{i=0}^k\frac{i\binom{m+i}{m}x^i}{m+i}$$
for a constant $c$ which is free of $k$. Looking at the case $k=0$
gives
$$\sum_{j=0}^m\frac{(1-x)^j}{x^{j}}\binom{m}{j}=c;\quad\text{i.e., }c=\frac{1}{x^m}.$$

Summarizing, we can represent $\alpha_{m,n}^{(K)}(x)=:{\tt A}$ in
the form

\begin{mma}
\In A=\sum_{k=1}^{K}\frac{x-(1-x)^{m+1}{\displaystyle\sum_{i=0}^k\frac{i\binom{m+i}{m}x^i}{m+i}}}{x\binom{k+m}{n}};\\
\end{mma}

\medskip

\subsection{The Case $n>1$.} Now \SigmaP\ is ready to simplify $A$
in one stroke (i.e., no splitting into two sums is needed):

\begin{mma}\MLabel{MMA:Sigma04Reduce}
\In result=SigmaReduce[A,
SimpleSumRepresentation\to True]\\
\Out
-\frac{K+m-n+1}{(n-1)\binom{K+m}{n}}+\frac{1+m-n}{(n-1)\binom{m}{n}}+
\frac{(K+m-n+1)(1-x)^{m+1}}{(n-1)x\binom{K+m}{n}}\sum_{i=0}^K\frac{ix^i\binom{i+m}{m}}{i+m}
-\frac{(1-x)^{n+1}}{x(n-1)}\sum_{i=1}^K\frac{ix^i\binom{i+m}{m}}{\binom{i+m}{n}}\\
\end{mma}

\smallskip

\noindent{\it Remark.} \SigmaP\ automatically found the additional
sum $\sum_{i=1}^Kix^i\binom{i+m}{m}\binom{i+m}{n}^{-1}$ in order to
simplify $A=\alpha_{m,n}^{(K)}(x)$ to an expression consisting only
of single sums; for details of the method see~\cite{Schneider:04a}.

\medskip

\noindent Summarizing, using relations like
$\binom{i+m-1}{m}=\frac{i}{i+m}\binom{i+m}{m}$ or
$i\binom{i+m}{m}\binom{i+m}{n}^{-1}=\binom{m+1}{n}^{-1}\binom{m+i-n}{i-1}$,
one obtains that, for $K\geq m+1\geq n\geq2$,
\begin{equation}\label{Equ:MainId1}
\begin{split}
a_{m,n}^{(K)}(x)=\frac{n}{n-1}\Big[1-\frac{\binom{m}{n-1}}{\binom{K}{n-1}}
&+\frac{\binom{m}{n-1}}{\binom{K}{n-1}}(1-x)^{m+1}
\sum_{i=0}^{K-m-1}(-1)^i\binom{-m-1}{i}x^i\\
&-(1-x)^{m+1}\sum_{i=0}^{K-m-1}(-1)^i\binom{n-m-2}{i}x^i\Big].
\end{split}
\end{equation}
In the limit $K\to\infty$, owing to the binomial theorem, we
retrieve Lengyel's identity~\eqref{LengyelId}.

Concerning the case $n=2$ we remark that the equivalence
of~\eqref{Equa2mDef} and~\eqref{Equ:MainId1} is based on a
non-trivial transformation; e.g., for the elementary special case
$x=1$ it specializes to ($K\geq m+1$)
$$\sum_{N=2}^K\frac{(-1)^N}{N(N-1)}\binom{m-1}{K-N}=\frac{(-1)^{K+m+1}}{K}\binom{K-1}{m}^{-1}.$$
Of course, such identities could be proved easily with computer
algebra; however, it is instructive to consult background
information like the discussion related to~\cite[(5.41)]{Graham:94}.


\subsection{The Case $n=1$.} After inserting
$\alpha_{m,1}^{(K)}(x)$ by

\begin{mma}
\In A1=A/.n\to1\\
\Out
\sum_{k=1}^{K}\frac{x-(1-x)^{m+1}{\displaystyle\sum_{i=0}^k\frac{i\binom{m+i}{m}x^i}{m+i}}}{x(m+k)}\\
\end{mma}

\noindent we get the simplification

\begin{mma}\MLabel{MMA:A1Com}
\In SigmaReduce[A1,
SimpleSumRepresentation\to True]\\
\Out\Big(1-(1-x)^{m+1}\sum_{i=0}^Kx^i\binom{i+m}{m}\Big)\sum_{i=1}^K\frac{1}{i+m}
+(1-x)^{m+1}\sum_{i=1}^Kx^i\binom{i+m}{m}\sum_{j=1}^i\frac{1}{j+m}\\
\end{mma}

\smallskip

\noindent{\it Remark.} Similar as in~\myOut{\ref{MMA:Sigma04Reduce}}
\SigmaP\ automatically found the sum expressions
$\sum_{i=1}^K\frac{1}{i+m}$ and
$\sum_{i=1}^Kx^i\binom{i+m}{m}\sum_{j=1}^i\frac{1}{j+m}$ in order to
simplify $A1=\alpha_{m,1}^{(K)}(x)$ in~\myOut{\ref{MMA:A1Com}}; for
details see~\cite{Schneider:05f}.

\medskip

Using $\sum_{i=1}^K\frac{1}{i+m}=H_{K+m}-H_m$ where
$H_m=1+\frac{1}{2}+\dots+\frac{1}{m}$ are the harmonic numbers, we
can write $a_{m,1}^{(K)}(x)$ in the form $(K\geq m+1$ and $m\geq0$)
\begin{equation}\label{Equ:MainId2}
a_{m,1}^{(K)}(x)=H_{K+m}-H_m-(1-x)^{m+1}\Big[H_{K+m}\sum_{i=0}^K\binom{i+m}{m}x^i
-\sum_{i=0}^K\binom{i+m}{m}H_{m+i}x^i\Big].
\end{equation}
In the limit $K\to\infty$ we retrieve~\eqref{LengyelId}, owing to
the binomial theorem and the fact~\cite[(7.43)]{Graham:94} that
\begin{equation}\label{Equ:HarId}
\sum_{i=0}^{\infty}
\binom{i+m}{m}H_{m+i}x^i=-\frac{1}{(1-x)^{m+1}}\big(\ln(1-x)-H_m\big).
\end{equation}


\section{Generating Functions with Sigma}\label{Sec:GenSigma}

Identity~\eqref{Equ:HarId} can be also derived with computer
algebra. A standard method would be to utilize holonomic closure
properties by using the packages~\cite{Salvy:94}
or~\cite{Mallinger:96}. However, in the given context, we find it
instructive to show that~\eqref{Equ:HarId} can be also obtained with
\SigmaP, namely as follows. We input the sum
\begin{mma}
\In E=\sum_{i=0}^{\infty} \binom{i+m}{m}H_{m+i}x^i;\\
\end{mma}
\noindent and compute a recurrence relation satisfied by it:
\begin{mma}
\In GenerateRecurrence[E,m]\\
\Out-(m+2)(x-1)^2\text{SUM}[m+2]-(2m+3)(x-1)\text{SUM}[m+1]+(-m-1)\text{SUM}[m]==0\\
\end{mma}
\noindent Next, we solve the recurrence with the \SigmaP\ function
\begin{mma}
\In recSol=SolveRecurrence[rec[[1]], SUM[m]]\\
\Out\{\{0,\prod_{i=1}^m\frac{1}{1-x}\},\{0,\prod_{i=1}^m\frac{1}{1-x}\sum_{i=1}^m\frac{1}{i}\},\{1,0\}\}\\
\end{mma}
\noindent Denoting the left hand side of~\eqref{Equ:HarId} by
$E_m(x)$ this means
$$E_{m}(x)=\frac{c_0}{(1-x)^m}+c_1\frac{H_m}{(1-x)^m}$$
for constants $c_1$ and $c_2$ which are free of $m$. Finally, we
determine the constants $c_1$ and $c_2$. The two initial conditions
at $m=0$ and $m=1$ lead to
$$c_0=\sum_{i=0}^{\infty}H_{i}x^i(=E_0(x))$$
and
$$\frac{c_0}{(1-x)}+\frac{c_1}{(1-x)}=\sum_{i=0}^{\infty}(i+1)H_{i+1}x^i(=E_1(x)).$$
Finally, we succeed in expressing a truncated version of $E_1(x)$ by
a truncated version of $E_0(x)$; namely by

\begin{mma}
\In SigmaReduce[\sum_{i=0}^{K}(i+1)H_{i+1}x^i,Tower\to\{\sum_{i=0}^{K}H_{i}x^i\}]\\
\Out \frac{(x-2) x^{K+1}+(K+1) (x-1) H_Kx^{K+1}+1+(1-x)\sum_{i=0}^{K}H_{i}x^i}{(x-1)^2}\\
\end{mma}
\noindent Hence, with $K\to\infty$ and the assumption that $0\leq
x<1$, we get
$$E_1(x)=\frac{1}{(1-x)^2}+\frac{1}{1-x}\sum_{i=0}^{\infty}H_{i}x^i.$$
Thus $c_1=\frac{1}{1-x}$, and therefore
$$E_m(x)=\frac{\sum_{i=0}^{\infty}H_ix^i}{(1-x)^m}+\frac{H_m}{(1-x)^{m+1}}.$$
Invoking the knowledge $\sum_{i=0}^{\infty}H_ix^i=-\ln(1-x)/(1-x)$,
we arrive at~\eqref{Equ:HarId}.

\section{Conclusion}\label{Sec:Conclusion}

With identity~\eqref{LengyelId} as an illustrative example, we
showed how symbolic summation methods can be used to find
generalizations of binomial identities where infinite series are
replaced by truncated versions. In the given context the \SigmaP\
package has led us to find the relations~\eqref{Equa2mDef},
\eqref{Equ:MainId1} and~\eqref{Equ:MainId2} for terminating variants
of Lengyel's infinite series $a_{m,n}(x)$.

From a combinatorial point of view it might be interesting to
explore whether such truncated variants do also have statistical
interpretations, e.g., within the theory of records like
identity~\eqref{Equ:OriginalSum}.

\begin{thebibliography}{GKP94} \footnotesize

\bibitem[Blo86]{Blom:86}
G.~Blom.
\newblock Poblem 6522.
\newblock {\em Amer. Math. Monthly}, 93:485, 1986.

\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[Isr88]{Israel:88}
R.B. Israel.
\newblock Persistence of a distribution.
\newblock {\em Amer. Math. Monthly}, 95:360--362, 1988.

\bibitem[Len06]{Lengyel:06}
T.~Lengyel.
\newblock An invariant sum related to record statistics.
\newblock {\em Preprint}, 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, August 1996.
\bibitem[Sch04a]{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[Sch04b]{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[Sch05]{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[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[Zei91]{Zeilberger:91}
Doron Zeilberger.
\newblock The method of creative telescoping.
\newblock {\em Journal of Symbolic Computation}, 11:195--204, 1991.

\end{thebibliography}


\end{document}