
\documentclass[10pt]{mtn}
\usepackage{mapleenv}


\begin{document}


\title{Combinatorial Sums in the Analysis of a 
Generalized van der Pol Equation}
\author{Helmut Prodinger
\thanks{Department for Algebra and Discrete Mathematics,
TU Wien,
Wiedner Hauptstrasse 8--10/118, 
A-1040 Wien,  Austria, 
 email: Helmut.Prodinger@tuwien.ac.at}}
\date{November 23, 1995}
\maketitle



\section{Introduction}

\def\SUM{\hbox{\rm SUM}}
\def\binom#1#2{{#1\choose#2}}
\newtheorem{theo}{Theorem}

In \cite{marcia1, marcia2, marcia3}
 I found the following sums, all of them 
unevaluated. In this little note I will demonstrate how they can be 
computed with the help of {\sc Maple}.

Before we start, let me say a few words about the origin of the problem:
The generalized van der Pol equation is
\begin{equation}   
\frac{d^2u}{dt^2}+u=\varepsilon(1-u^{2n})\frac{du}{dt}.
\end{equation}
In order to obtain a {\it perturbation solution}, a first order 
equation (in $\varepsilon$)
\begin{equation}   
\sin T\frac{dF_1}{dT}+2\cos T F_1=(1-a_0^{2n}\cos^{2n}T)\sin T
\end{equation} 
was studied; the solution involves the sums that will be discussed in the sequel.


For $1\le k\le   n$, set

\begin{equation}
B_k^{(1)}(n):=-\frac{k}{\binom{2n+1}{n}}\sum_{j=k}^{n}
\frac{2j+1}{j(j+1)}\binom{2n+1}{n-j}~.
\end{equation}

\noindent
The first sum \cite[(3.18)]{marcia1}:
\begin{equation}
\SUM_1:=B_1^{(1)}(n)=\ ?
\end{equation}

\noindent
The second sum \cite[(4.11)]{marcia1}:

\begin{equation}
\SUM_2:=\sum_{k=1}^n\frac1kB_k^{(1)}(n)+\frac{B_1^{(1)}(n)}{2}
=\ ?
\end{equation}

\noindent
The third sum \cite[(5.14)]{marcia1}:
\begin{equation}
\SUM_3:=\frac{1}{\binom{2n+1}{n}^2}\sum_{k=1}^n
\frac{(2k+1)^2}{k(k+1)}\binom{2n+1}{n-k}^2=\ ?
\end{equation}

\noindent
The fourth sum \cite{marcia3}:
\begin{equation}
\SUM_4:=
\sum_{k=1}^n\binom{2n+2}{n+1-k}^2\left[k^2(4n+1)-n(n+1)\right]
=\ ?
\end{equation}







\noindent
In particular, it was conjectured that 

\begin{eqnarray}
&&(n+1)^2\binom{2n+1}{n}^2\SUM_3={(n+1)(2n+1)^3} \nonumber\\
&&{}-(4n+1)(n+1)^2
\binom{2n+1}{n}^2\\
&&{}+(2n+1)\SUM_4.\nonumber
\end{eqnarray}

\section{Results}

Let $H_n=\sum_{k=1}^n\frac1k$ denote the $n$th harmonic number.

I found the following.

\begin{theo}
\begin{equation}
\SUM_1=1-H_{n+1}~.
\end{equation}
\end{theo}


\begin{theo}
\begin{equation}
\SUM_2=\frac32-\frac{1}{2(n+1)}-\frac{4^n}{\binom{2n}{n}}~.
\end{equation}
\end{theo}

\begin{theo}
\begin{equation}
\SUM_3=\frac{\binom{4n+1}{2n}}{\binom{2n}{n}^2}-3+\frac{2}{n+1}~.
\end{equation}
\end{theo}

\begin{theo}
\begin{eqnarray}
&&\SUM_4=
\binom{4n+4}{2n+2}\frac{(n+1)(2n+1)}{2(4n+3)} \\
&&{}+\frac{(n+1)n}{2}
\binom{2n+2}{n+1}^2
-(n+1)(2n+1)^2~.\nonumber
\end{eqnarray}
\end{theo}

\section{Sketch of Human Proofs}

Here I will indicate how one would evaluate the sums without a
computer.

To deal with $\SUM_1$, define


\begin{equation}
f_n=\sum_{k=1}^n\frac{2k+1}{k(k+1)}\binom{2n+1}{n-k}
\end{equation}
and note that
\begin{equation}
\binom{2n-1}{n-1-k}=\binom{2n+1}{n-k}\frac{n(n+1)-k(k+1)}{(2n+1)(2n)},
\end{equation}
from which we find
\begin{equation}
f_{n-1}=\frac{n(n+1)}{(2n+1)(2n)}f_n-\frac{1}{2(n+1)}\binom{2n}{n}.
\end{equation}
Introducing {\sl summation factors}, this first order recurrence is
solved by summing.

To deal with $\SUM_2$, we start from
\begin{equation}
\frac1kB_k^{(1)}(n)=1-H_{n+1}+\frac{1}{\binom{2n+1}{n}}\sum_{j=1}^{k-1}
\frac{2j+1}{j(j+1)}\binom{2n+1}{n-j}.
\end{equation}
Summing on $k$ and interchanging the order of summation, we get
\begin{eqnarray}\label{sum2:rewritten}
&&\sum_{k=1}^n\frac1kB_k^{(1)}(n)
=n\left(1-H_{n+1}\right)\\
&&{}+\frac{1}{\binom{2n+1}{n}}\sum_{1\le j\le n}
\frac{2j+1}{j(j+1)}\binom{2n+1}{n-j}(n-j).\nonumber
\end{eqnarray}
The remaining sum is handled in the style of  $\SUM_1$.

For $\SUM_3$, we use that

\begin{equation}
\frac{(2k+1)^2}{k(k+1)}=4+\frac{1}{k}-\frac{1}{k+1}
\end{equation}
and
\begin{equation}
\binom{2n+1}{n-k}^2-
\binom{2n+1}{n+1-k}^2=-\frac{k}{n+1}\binom{2n+2}{n+1-k}^2
\end{equation}
to rewrite the sum as
\begin{equation}
\SUM_3=
2\frac{\binom{4n+2}{2n+1}}{\binom{2n+1}{n}^2}-
\frac{1}{(n+1)\binom{2n+1}{n}^2}\sum_{k=1}^{n+1}
\binom{2n+2}{n+1-k}^2
-3;
\end{equation}
the remaining evaluation is standard (Vandermonde, see \cite{GKP}),
 as is the  evaluation of
$\SUM_4$.

\section{Computer Proofs}

\subsection{$\bullet \ \SUM_1$}
We use the {\sc Maple} program `ekhad', by Doron Zeilberger.
(Later versions of {\sc Maple} should include similar programs 
in the {\sl sumtools\/} package)
\begin{mapleinput}
read `ekhad`:
\end{mapleinput}
\begin{maplelatex}
\[
{\it \:Version\:of\:Oct.\:17,\:1995}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it This\:is\:EKHAD,\:One\:of\:the\:Maple\:packages}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it accompanying\:the\:forthcoming\:book\:}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it \:"A=B"\:}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it \:(soon\:to\:be\:published\:by\:A.K.\:Peters,\:Ltd.)\:}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it \:by\:Marko\:Petkovsek,\:Herb\:Wilf,\:and\:Doron\:
Zeilberger.}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{{\it The\:most\:current\:version\:of\:EKHAD\:is\:always}} 
 \]
\end{maplelatex}
\begin{maplelatex}
\[
{\it available\:by\:anonymous\:ftp\:to}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it \:ftp.math.temple.edu/pub/zeilberg/programs/EKHAD}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it or\:on\:the\:www:\:http://www.math.temple.edu/\char'176
zeilberg}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it For\:general\:help,\:and\:a\:list\:of\:the\:available\:
functions,}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it \:type\:"ezra();"}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it For\:specific\:help\:type\:
"ezra(procedure\_name)"\: .}
\]
\end{maplelatex}

\begin{mapleinput}
ezra();
\end{mapleinput}
\begin{maplelatex}
\[
{\it A\:Maple\:package\:for\:proving\:Hypergemetric\:}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it (Binomial\:
Coeff.)\:and\:other\:kinds\:of\:identities\: .}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it For\:help\:with\:a\:specific\:procedure,}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it type\:
"ezra(procedure\_name);"}
\]
\end{maplelatex}


\begin{maplelatex}
\[
{\it Contains\:procedures:\:}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it findrec,ct,zeil,zeilpap,zeillim,}
\]
\end{maplelatex}
\begin{maplelatex}
\[
{\it AZd,AZc,AZpapd,AZpapc,celine.
}
\]
\end{maplelatex}


Now we define the general summand in $\SUM_1$ to be $F=F(n,k)$,
\begin{mapleinput}
F:=-1/binomial(2*n+1,n)
*(2*k+1)/k/(k+1)*binomial(2*n+1,n-k);
\end{mapleinput}
\begin{maplelatex}
\[
{F} :=   - \,{\displaystyle \frac {(\,2
\,{k} + 1\,)\,{\rm binomial}(\,2\,{n} + 1, {n} - {k}\,)}{{\rm 
binomial}(\,2\,{n} + 1, {n}\,)\,{k}\,(\,{k} + 1\,)}}
\]
\end{maplelatex}
and use Zeilberger's algorithm;
\begin{mapleinput}
zeil(F,k,n);
\end{mapleinput}
\begin{maplelatex}
\[
1 - {N}, {\displaystyle \frac {{k}\,(\,{k} + 1\,)}{(\,2\,{k} + 1
\,)\,(\,{n} - {k} + 1\,)}}
\]
\end{maplelatex}
The answer means the following: If we set
$$
R(n,k):= \frac {k(k + 1)}{(2{k} + 1
)({n} - {k} + 1)}
$$
and
$$
G(n,k):=F(n,k)\, R(n,k),
$$
then
\begin{equation}
F(n,k)-F(n+1,k)=G(n,k+1)-G(n,k).
\end{equation}
We might sum this up about $k\ge1$ and get
\begin{equation}
\SUM_1(n)-\SUM_1(n+1)=-G(n,1)=\frac{1}{n+2}.
\end{equation}
Unwinding this recursion, we get the result of Theorem~1.




\subsection{$\bullet \ \SUM_2$}
We start from equation (\ref{sum2:rewritten})
and have to prove
\begin{eqnarray}
&&F(n):=\frac{1}{\binom{2n+1}{n}}\sum_{1\le k\le n}
\frac{2k+1}{k(k+1)}\binom{2n+1}{n-k}(n-k)\nonumber\\
&&{}=
1+\frac{H_n}{2}-n+nH_{n+1}-\frac{4^n}{\binom{2n}{n}}~.
\end{eqnarray}
This formula might be (provided, we don't `know' it already)
{\sl guessed\/} with {\sc Gfun},
a {\sc Maple} package written by Bruno Salvy and Paul Zimmermann, \cite{SZ}:
\begin{mapleinput}
read `gfun`: with(gfun):
l:=[-3/4,-4/3,-73/40,-79/35,-667/252,
    -694/231,-22901/6864,...];
guessgf(l,z);
\end{mapleinput}

I did not really run this particular example, since it would require a larger
computer than I currently have at my disposal.





We apply  Zeilberger's algorithm as before with
\begin{mapleinput}
F:=1/binomial(2*n+1,n)*(2*k+1)
*(k*(k+1)*binomial(2*n+1,n-k)*(n-k):
zeil(F,k,n);
\end{mapleinput}
\noindent and find
\begin{maplelatex}
\begin{eqnarray*}
\lefteqn{2\,(\,{n} + 1\,)\,(\,2\,{n} + 3\,) - (\,4\,{n} + 7\,)\,{
N}\,(\,2\,{n} + 1\,) } \\
&&{}+ {N}^{2}\,(\,2\,{n} + 3\,)\,(\,2\,{n} + 1\,
),  \\
 & & - \,{\displaystyle \frac {1}{2}}( - 4 - 6\,{n} + {k} - 2\,{n}^{2} + 18\,{k}^{2} + 12\,{k}^{3
} + 30\,{k}^{2}\,{n} \\
&&{}+ 9\,{k}\,{n} + 4\,{n}^{3}\,{k}
+ 12\,{n}^{2}\,{k} + 12\,{k}^{2}\,{n}^{2} \\
 & & \mbox{}  + 20\,{n}
\,{k}^{3} + 8\,{n}^{2}\,{k}^{3})(\,{k} + 1\,) \left/ {\vrule 
height0.37em width0em depth0.37em} \right. \! \! (\,(\,{n} - {k}
\,) \\
 & & (\,2\,{k} + 1\,)\,(\,{n} + 2 + {k}\,)\,(\,{n} - {k} + 1\,)\,
)\mbox{\hspace{154pt}}
\end{eqnarray*}
\end{maplelatex}
\noindent
This means in a more common notation
\begin{eqnarray}
&&2(n+1)(2n+3)F(n,k)\nonumber \\ 
&&{}-(4n+7)(2n+1)F(n+1,k)\nonumber \\ 
&&{}+(2n+3)(2n+1)F(n+2,k)
\nonumber \\ &&
{}=G(n,k+1)-G(n,k)
\end{eqnarray}
with $G(n,k):=F(n,k)R(n,k)$
and
\begin{mapleinput}
R:=-1/2*(-4-6*n+k-2*n^2+12*n^2*k^2
+12*n^2*k+30*k^2*n+9*k*n+12*k^3
+18*k^2+8*n^2*k^3)*(k+1)/
((n-k)*((2*k+1)*(n+2-k)*(n-k+1)):
\end{mapleinput}
\noindent
Summing this over $k\ge1$
we find
\begin{eqnarray}
&&2(n+1)(2n+3)F(n)-(4n+7)(2n+1)F(n+1)\nonumber\\
&&{}+(2n+3)(2n+1)F(n+2)\nonumber\\
&&{}=\frac{(n+1)(4n^2+26n+27)}{2(n+2)(n+3)}~.
\end{eqnarray}
We only have to check whether 
\begin{equation}
Ftest(n):=
1+\frac{H_n}{2}-n+nH_{n+1}-\frac{4^n}{\binom{2n}{n}}
\end{equation}
fulfills this recursion, which {\sc Maple} confirms very easily:
\begin{mapleinput}
H:=n->sum(1/k,k=1..n):
Ftest:=n->1+H(n)/2-n+n*H(n+1)
-4^n/binomial(2*n,n):
normal(expand(2*(2*n+3)*(n+1)*Ftest(n)
-(4*n+7)*(2*n+1)*Ftest(n+1)
+(2*n+3)*(2*n+1)*Ftest(n+2)-
(n+1)*(4*n^2*26*n+27)/2/(n+2)/(n+3)));
\end{mapleinput}
\begin{maplelatex}
\[
0
\]
\end{maplelatex}
Two initial conditions also match, 
and the proof is finished.


\subsection{$\bullet \ \SUM_3$}
For $\SUM_3$ we do this. From experiments with {\sc Gfun}, we `know' the
correct answer, and we only want to 
{\sl prove\/} it  with Zeilberger's algorithm.

Our general term is now this:
\begin{mapleinput}
F:=1/binomial(2*n+1,n)^2*(2*k+1)^2/
k/(k+1)*binomial(2*n+1,n-k)^2:
zeil(F,k,n);
\end{mapleinput}
\begin{maplelatex}
\begin{eqnarray*}
\lefteqn{ - (\,5 + 4\,{n}\,)\,(\,4\,{n} + 3\,)\,(\,{n} + 1\,) + 2
\,(\,2\,{n} + 3\,)\,(\,2\,{n} + 1\,)^{2}\,{N}, } \\
&&{} - (\,{k} + 1\,)(
 - 10\,{k}^{3}- 8\,{n}\,{k}^{3} + 5\,{k}^{2} + 4\,{k}^{2}\,{n} + 
18\,{k} \\
 & & \mbox{} + 16\,{n}^{3}\,{k} + 54\,{n}^{2}\,{k} + 56\,{n}\,{k} - 9
 \\
 & & \mbox{} - 27\,{n}^{2} - 28\,{n} - 8\,{n}^{3})(\,{n} + 1\,)\\
&&
 \left/ {\vrule height0.37em width0em depth0.37em} \right. \! \! 
 \left( \! \,(\,{n} - {k} + 1\,)^{2}\,(\,2\,{k} + 1\,)\, \! 
 \right) \mbox{\hspace{59pt}}
\end{eqnarray*}
\end{maplelatex}
\begin{mapleinput}
recu:="[1];
\end{mapleinput}
\begin{maplelatex}
\begin{eqnarray*}
&&{\it recu} :=  - (\,5 + 4\,{n}\,)\,(\,4\,{n} + 3\,)\,(\,{n} + 1\,
) \\&&{}+ 2\,(\,2\,{n} + 3\,)\,(\,2\,{n} + 1\,)^{2}\,{N}
\end{eqnarray*}
\end{maplelatex}
This is the recursion of the $F(n,k)$; as above, it equals 
$G(n,k+1)-G(n,k)$. We sum it up on $k\ge1$, and end up with $-G(n,1)$.
The latter quantity gets the name `rside'.
\begin{mapleinput}
rside:=-subs(k=1, F)*subs(k=1,""[2]);
\end{mapleinput}
\begin{maplelatex}
\begin{eqnarray*}
\lefteqn{{\it rside} := 3(\,8\,{n}^{3} + 27\,{n}^{2} + 24\,{n} + 
4\,)\,(\,{n} + 1\,)
} \\
&&{\rm binomial}(\,2\,{n} + 1, {n} - 1\,)^{2}
 \left/ {\vrule height0.44em width0em depth0.44em} \right. \! \! 
  \! \! \\
 & & \left( {n}^{2}\,{\rm binomial}(\,2\,{n} + 1, {n}\,)^{2}\, \right) 
\mbox{\hspace{191pt}}
\end{eqnarray*}
\end{maplelatex}
Now we check whether our guessed answer, which we call `Ftest', fulfills
the recursion.
\begin{mapleinput}
Ftest:=n->binomial(4*n+1,2*n)/
binomial(2*n,n)^2-3+2/(n+1);
\end{mapleinput}
\begin{maplelatex}
\[
{\it Ftest} := {n} \rightarrow {\displaystyle \frac {{\rm 
binomial}(\,4\,{n} + 1, 2\,{n}\,)}{{\rm binomial}(\,2\,{n}, {n}\,
)^{2}}} - 3 + 2\,{\displaystyle \frac {1}{{n} + 1}}
\]
\end{maplelatex}
\begin{mapleinput}
normal(expand(-(5+4*n)*(4*n+3)*(n+1)
*Ftest(n)+2*(2*n+3)*(2*n+1)^2
*Ftest(n+1)-rside));
\end{mapleinput}
\begin{maplelatex}
\[
0
\]
\end{maplelatex}
This is the case, and since initial conditions also match, we are done.


\subsection{$\bullet \ \SUM_4$}

We ask {\sc Maple} to perform
\begin{equation}
A:=\sum_{k=0}^{n+1}\binom{2n+2}{n+1-k}^2k^2
\end{equation}
by saying
\begin{mapleinput}
simplify(sum(binomial(2*n+2,n+1-k)^2
*k^2,k=0..n+1));
\end{mapleinput}
\noindent
with the result
\begin{maplelatex}
$$
2\frac{16^n(n+1)\Gamma(3/2+2n)}{\pi^{1/2}\Gamma(2n+2)},
$$
\end{maplelatex}
\noindent
which we rewrite by hand as
\begin{equation}
A=\frac{n+1}{2}\binom{4n+2}{2n+1}.
\end{equation}
The other part, 
\begin{equation}
B:=\sum_{k=0}^{n+1}\binom{2n+2}{n+1-k}^2
\end{equation}
looks simpler, but is actually harder. However, we can help {\sc Maple} by 
noticing a symmetry. We ask for the ``full'' sum
\begin{mapleinput}
simplify(sum(binomial(2*n+2,k)^2,
k=0..2*n+2));
\end{mapleinput}
\noindent
with the result
\begin{maplelatex}
$$
\frac{\Gamma(5+4n)}{\Gamma(2n+3)^2},
$$
\end{maplelatex}
\noindent
which is simply
\begin{equation}
\binom{4n+4}{2n+2}~.
\end{equation}
To this quantity we add the ``middle'' element $\binom{2n+2}{n+1}^2$
and obtain our sum as half of that;
\begin{equation}
B=\frac12\left(\binom{4n+4}{2n+2}+\binom{2n+2}{n+1}^2\right).
\end{equation}
Computing $(4n+1)A-n(n+1)B$ and
subtracting the missing summands (for $k=0$ and $k=n+1$), we get 
the result from Theorem~4.


\medskip
{\bf Acknowledgment.} I had interesting discussions with
Jacques Carette, Christian Krattenthaler, Bruno Salvy and Doron Zeilberger.

Also, I thank Arnold Knopfmacher for inviting me to South Africa, where I
learnt about the papers \cite{marcia1, marcia2}.




\begin{thebibliography}{9}

\bibitem{marcia1}
G.M.~Moremedi and D.P.~Mason: Analysis of the Limit Cycle of a Generalised 
van der Pol Equation by a Time Transformation Method, 
{\it Quaestiones Mathematicae}, {\bf 17}, pp. 349--379, (1994).

\bibitem{marcia2}
G.M.~Moremedi, D.P.~Mason, and V.M.~Gorringe:
On the Limit Cycle of a Generalized van der Pol Equation
{\it Int. J. Non--Linear Mechanics}, {\bf 28}, pp. 237--250, (1993).




\bibitem{marcia3}
G.M.~Moremedi:
Private Communication, (1994).

\bibitem{GKP} R.~Graham, D.E.~Knuth, and O.~Patashnik:
Concrete Mathematics,  {\it Addison Wesley}, (1994)
.

\bibitem{SZ}B.~Salvy and P.~Zimmermann: {\sc Gfun}, A {\sc Maple}
 Package for the Manipulation of
Generating and Holonomic Functions in one Variable, {\it ACM Transactions
on Mathematical Software}, {\bf 20}, pp. 163--167, (1994).


\end{thebibliography}


\end{document}


