Combinatorial Sums in the Analysis of a Generalized van der Pol Equation

Helmut Prodinger ^{∗}

Introduction

In [1, 2, 3] 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 Maple.

Before we start, let me say a few words about the origin of the problem: The generalized van der Pol equation is

\frac{d^{2}u}{dt^{2}} + u = ε(1 − u^{2n})\frac{du}{dt}.  (1)

In order to obtain a perturbation solution, a first order equation (in ε)

sin T \frac{dF_{1}}{dT} + 2 cos T F_{1} = (1 − a_{0}^{2n} cos^{2n} T) sin T (2)

was studied; the solution involves the sums that will be discussed in the sequel.

For 1 ≤ k ≤ n, set

B_{k}^{(1)}(n) := −\frac{k}{\binom{2n+1}{n}} ∑_{j=k}^{n} \frac{2j + 1}{j(j + 1)}\binom{2n + 1}{n − j} . (3)

The first sum [1, (3.18)]:

SUM_{1} := B_{1}^{(1)}(n) = ?  (4)

The second sum [1, (4.11)]:

SUM_{2} := ∑_{k=1}^{n} \frac{1}{k} B_{k}^{(1)}(n) + \frac{B_{1}^{(1)}(n)}{2} = ?  (5)

The third sum [1, (5.14)]:

SUM_{3} := \frac{1}{\binom{2n+1}{n}2} ∑_{k=1}^{n} \frac{(2k + 1)^{2}}{k(k + 1)} \binom{2n + 1}{n − k}^{2} = ? (6)

The fourth sum [3]:

SUM_{4} := ∑_{k=1}^{n} \binom{2n + 2}{n + 1 − k}^{2} [k^{2}(4n + 1) − n(n + 1)] = ?

(7)

In particular, it was conjectured that

(n + 1)^{2}\binom{2n + 1}{n}^{2}SUM_{3} = (n + 1)(2n + 1)^{3}

− (4n + 1)(n + 1)^{2}\binom{2n + 1}{n}^{2}  (8)

+ (2n + 1)SUM_{4}.

Results

Let H_{n} = ∑_{k=1}^{n} \frac{1}{k} denote the nth harmonic number. I found the following.

Theorem 1

SUM_{1} = 1 − H_{n+1} .  (9)

Theorem 2

SUM_{2} = \frac{3}{2} − \frac{1}{2(n + 1)} − \frac{4^{n}}{\binom{2n}{n}} .  (10)

Theorem 3

SUM_{3} = \begin{matrix}( & {4n+1 \atop 2n} & ) \\ \binom{2n}{n} & 2 \end{matrix} − 3 + \frac{2}{n + 1} .  (11)

Theorem 4

SUM_{4} = \binom{4n + 4}{2n + 2}\frac{(n + 1)(2n + 1)}{2(4n + 3)}  (12)

+ \frac{(n + 1)n}{2}\binom{2n + 2}{n + 1}^{2} − (n + 1)(2n + 1)^{2} .

Sketch of Human Proofs

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

To deal with SUM_{1}, define

f_{n} = ∑_{k=1}^{n} \frac{2k + 1}{k(k + 1)}\binom{2n + 1}{n − k}  (13)

and note that

\binom{2n − 1}{n − 1 − k} = \binom{2n + 1}{n − k}\frac{n(n + 1) − k(k + 1)}{(2n + 1)(2n)}, (14)

from which we find

f_{n−1} = \frac{n(n + 1)}{(2n + 1)(2n)}f_{n} − \frac{1}{2(n + 1)}\binom{2n}{n}.  (15)

∗Department for Algebra and Discrete Mathematics, TU Wien, Wiedner Hauptstrasse 8–10/118, A-1040 Wien, Austria, email:

Helmut.Prodinger@tuwien.ac.at

Combinatorial Sums in the Analysis of a Generalized van der Pol Equation

Introducing summation factors, this first order recurrence is solved by summing.

To deal with SUM_{2}, we start from

\frac{1}{k} B_{k}^{(1)}(n) = 1 − H_{n+1} + \frac{1}{\binom{2n+1}{n}} ∑_{j=1}^{k−1} \frac{2j + 1}{j(j + 1)}\binom{2n + 1}{n − j}.

(16)

Summing on k and interchanging the order of summation, we get

∑_{k=1}^{n} \frac{1}{k} B_{k}^{(1)}(n) = n (1 − H_{n+1})  (17)

+ \frac{1}{\binom{2n+1}{n}} ∑_{1≤j≤n} \frac{2j + 1}{j(j + 1)}\binom{2n + 1}{n − j}(n − j).

The remaining sum is handled in the style of SUM_{1}.

For SUM_{3}, we use that

\frac{(2k + 1)^{2}}{k(k + 1)} = 4 + \frac{1}{k} − \frac{1}{k + 1}  (18)

and

\binom{2n + 1}{n − k}^{2} − \binom{2n + 1}{n + 1 − k}^{2} = −\frac{k}{n + 1}\binom{2n + 2}{n + 1 − k}^{2}

(19)

to rewrite the sum as

SUM_{3} = 2\begin{matrix}( & {4n+2 \atop 2n+1} & ) \\ \binom{2n+1}{n} & 2 \end{matrix} −\frac{1}{(n + 1)\binom{2n+1}{n}^{2}} ∑_{k=1}^{n+1} \binom{2n + 2}{n + 1 − k}^{2}−3;

(20)

the remaining evaluation is standard (Vandermonde, see [4]), as is the evaluation of SUM_{4}.

Computer Proofs

• SUM_{1}

We use the Maple program ‘ekhad’, by Doron Zeilberger. (Later versions of Maple should include similar programs in the sumtools package)

           > read `ekhad`:

Version of Oct. 17 , 1995

This is EKHAD, One of the Maple packages

accompanying the forthcoming book

”A = B”

(soon to be published by A.K . Peters, Ltd.)

by Marko Petkovsek, Herb Wilf , and Doron Zeilberger.

The most current version of EKHAD is always

available by anonymous ftp to

ftp.math.temple.edu/pub/zeilberg/programs/EKHAD

or on the www : http : //www.math.temple.edu/˜ zeilberg

For general help, and a list of the available functions,

type ”ezra(); ”

For specific help type ”ezra(procedure name)” .

                                                                  > ezra();

A Maple package for proving Hypergemetric

(Binomial Coeff .) and other kinds of identities .

For help with a specific procedure,

type ”ezra(procedure name); ”

Contains procedures :

findrec, ct, zeil, zeilpap, zeillim,

AZd, AZc, AZpapd, AZpapc, celine.

Now we define the general summand in SUM_{1} to be F = F (n, k),

                                                                  > F:=-1/binomial(2*n+1,n)
                                                                  > *(2*k+1)/k/(k+1)*binomial(2*n+1,n-k);

F := − \frac{( 2 k + 1 ) binomial( 2 n + 1, n − k)}{binomial( 2 n + 1, n) k ( k + 1 )}

and use Zeilberger’s algorithm;

                                                                  > zeil(F,k,n);

1 − N, \frac{k ( k + 1 )}{( 2 k + 1 ) ( n − k + 1 )}

The answer means the following: If we set

R(n, k) := \frac{k(k + 1)}{(2k + 1)(n − k + 1)}

and

G(n, k) := F (n, k) R(n, k),

then

F (n, k) − F (n + 1, k) = G(n, k + 1) − G(n, k). (21)

We might sum this up about k ≥ 1 and get

SUM_{1}(n) − SUM_{1}(n + 1) = −G(n, 1) = \frac{1}{n + 2}. (22)

Unwinding this recursion, we get the result of Theorem 1.

• SUM_{2}

We start from equation (17) and have to prove

F (n) := \frac{1}{\binom{2n+1}{n}} ∑_{1≤k≤n} \frac{2k + 1}{k(k + 1)}\binom{2n + 1}{n − k}(n − k)

= 1 + \frac{H_{n}}{2} − n + nH_{n+1} − \frac{4^{n}}{\binom{2n}{n}} .  (23)

This formula might be (provided, we don’t ‘know’ it already) guessed with Gfun, a Maple package written by Bruno Salvy and Paul Zimmermann, [5]:

           > read `gfun`: with(gfun):
           > l:=[-3/4,-4/3,-73/40,-79/35,-667/252,
           >  -694/231,-22901/6864,...];
           > guessgf(l,z);

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

           > 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);

and find

2 ( n + 1 ) ( 2 n + 3 ) − ( 4 n + 7 ) N ( 2 n + 1 )

+ N^{2} ( 2 n + 3 ) ( 2 n + 1 ),

− \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} + 20 n k^{3} + 8 n^{2} k^{3})( k + 1 ) /( ( n − k) ( 2 k + 1 ) ( n + 2 + k) ( n − k + 1 ) )

This means in a more common notation

2(n + 1)(2n + 3)F (n, k)
− (4n + 7)(2n + 1)F (n + 1, k)
+ (2n + 3)(2n + 1)F (n + 2, k)
= G(n, k + 1) − G(n, k)  (24)

with G(n, k) := F (n, k)R(n, k) and

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

Summing this over k ≥ 1 we find

2(n + 1)(2n + 3)F (n) − (4n + 7)(2n + 1)F (n + 1)

+ (2n + 3)(2n + 1)F (n + 2)
= \frac{(n + 1)(4n^{2} + 26n + 27)}{2(n + 2)(n + 3)} .  (25)

We only have to check whether

F test(n) := 1 + \frac{H_{n}}{2} − n + nH_{n+1} − \frac{4^{n}}{\binom{2n}{n}}  (26)

fulfills this recursion, which Maple confirms very easily:

                                                                  > 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)));

0

Two initial conditions also match, and the proof is finished.

• SUM_{3}

For SUM_{3} we do this. From experiments with Gfun, we ‘know’ the correct answer, and we only want to prove it with Zeilberger’s algorithm.

Our general term is now this:

                                                                  > 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);

−( 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 + 16 n^{3} k + 54 n^{2} k + 56 n k − 9 − 27 n^{2} − 28 n − 8 n^{3})( n + 1 )

/(( n − k + 1 )^{2} ( 2 k + 1 ))

                                                                  > recu:="[1];

recu := −( 5 + 4 n) ( 4 n + 3 ) ( n + 1 )
+ 2 ( 2 n + 3 ) ( 2 n + 1 )^{2} N

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 ≥ 1, and end up with −G(n, 1). The latter quantity gets the name ‘rside’.

                                                                  > rside:=-subs(k=1, F)*subs(k=1,""[2]);

rside := 3( 8 n^{3} + 27 n^{2} + 24 n + 4 ) ( n + 1 )

binomial( 2 n + 1, n − 1 )^{2} /

(n^{2} binomial( 2 n + 1, n)^{2} )

Now we check whether our guessed answer, which we call ‘Ftest’, fulfills the recursion.

                                                                  > Ftest:=n->binomial(4*n+1,2*n)/
                                                                  > binomial(2*n,n)^2-3+2/(n+1);

Ftest := n → \frac{binomial( 4 n + 1, 2 n)}{binomial( 2 n, n)^{2}} − 3 + 2 \frac{1}{n + 1}

           > normal(expand(-(5+4*n)*(4*n+3)*(n+1)
           > *Ftest(n)+2*(2*n+3)*(2*n+1)^2
           > *Ftest(n+1)-rside));

0

This is the case, and since initial conditions also match, we are done.

• SUM_{4}

We ask Maple to perform

A := ∑_{k=0}^{n+1} \binom{2n + 2}{n + 1 − k}^{2}k^{2}  (27)

by saying

           > simplify(sum(binomial(2*n+2,n+1-k)^2
           > *k^2,k=0..n+1));

with the result

2\frac{16^{n}(n + 1)Γ(3/2 + 2n)}{π^{1/2}Γ(2n + 2)},

which we rewrite by hand as

A = \frac{n + 1}{2}\binom{4n + 2}{2n + 1}.  (28)

The other part,

B := ∑_{k=0}^{n+1} \binom{2n + 2}{n + 1 − k}^{2}  (29)

looks simpler, but is actually harder. However, we can help Maple by noticing a symmetry. We ask for the “full” sum

           > simplify(sum(binomial(2*n+2,k)^2,
           > k=0..2*n+2));

with the result

\frac{Γ(5 + 4n)}{Γ(2n + 3)^{2}} ,

which is simply

\binom{4n + 4}{2n + 2} .  (30)

To this quantity we add the “middle” element \binom{2n+2}{n+1}^{2} and obtain our sum as half of that;

B = \frac{1}{2} (\binom{4n + 4}{2n + 2} + \binom{2n + 2}{n + 1}^{2}) .  (31)

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.

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 [1, 2].

References

[1] G.M. Moremedi and D.P. Mason: Analysis of the Limit Cycle of a Generalised van der Pol Equation by a Time Transformation Method, Quaestiones Mathematicae, 17, pp. 349–379, (1994).

[2] G.M. Moremedi, D.P. Mason, and V.M. Gorringe: On the Limit Cycle of a Generalized van der Pol Equation Int. J. Non–Linear Mechanics, 28, pp. 237–250, (1993).

[3] G.M. Moremedi: Private Communication, (1994).

[4] R. Graham, D.E. Knuth, and O. Patashnik: Concrete Mathematics, Addison Wesley, (1994) .

[5] B. Salvy and P. Zimmermann: Gfun, A Maple Package for the Manipulation of Generating and Holonomic Functions in one Variable, ACM Transactions on Mathematical Software, 20, pp. 163–167, (1994).