KNUTH’S OLD SUM — A SURVEY

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Abstract. We take an old combinatorial sum of Knuth as an example to show several methods of finding a closed form. Particularly, we want to emphasize the algorithmic approach of Zeilberger. It is interesting to note that the sum in question appears already in Riordan’s book, where it is labelled ‘Reed Dawson’.

1.Introduction

The sum in question is

f(n) = ∑_{k≥0} \binom{n}{k}\binom{2k}{k}( − \frac{1}{2})^{k}.

I want to give several methods of evaluation from the literature, featuring especially the algorithmic aspect of combinatorial sums.

I am not a real specialist, but I like the subject, and I hope, other people will (learn to) like it as well.

2. The original approach of Jonassen and Knuth

This one is long and elementary, [4]. We give only the key steps.

Using the recursion for the binomial coefficients (“Pascal’s triangle”) they find

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

Pulling out parts of the sum they halt at

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

This one will be multiplied by n; then the corresponding equation where n is replaced by n − 1 is written down. The difference of the 2 equations allows finally to evaluate the extra sum;

n(f(n) + f(n − 1)) − (n − 1)(f(n − 1) + f(n − 2)) = f(n − 1),

Knuth’s old sum 2 or finally

nf(n) = (n − 1)f(n − 2).

Since f(0) = 1 and f(1) = 0, the f(2m + 1)’s are all equal to zero, and

f(2m) = \frac{2m − 1}{2m}f(2m − 2) = \frac{2m − 1}{2m} \frac{2m − 3}{2m − 2} … \frac{1}{2}

= \frac{1}{2^{m}m!} \frac{(2m)!}{2^{m}m!} = \frac{1}{4^{m}} \binom{2m}{m}.

Therefore the answer is

f(n) = \{ \begin{matrix}\frac{1}{2^{n}} \binom{n}{n/2} & n even \\ 0 & n odd. \end{matrix}

3. The proof of Ira Gessel

This proof is reported in [3] and is as follows.

First, interchange the order of summation,

f(n) = ∑_{k≥0} \binom{n}{k}\binom{2n − 2k}{n − k}( − \frac{1}{2})^{n−k}.

Now, express the binomial coefficients as coefficients in appropriate generating functions,

\binom{n}{k}( − \frac{1}{2})^{−k} = [x^{k}](1 − 2x)^{n}

and

\binom{2n − 2k}{n − k} = [y^{n−k}](1 + y)^{2n−2k} = [y^{n}]y^{k}(1 + y)^{2n−2k}.

Hence

f(n) = ( − \frac{1}{2})^{n}[y^{n}](1 + y)^{2n} ∑_{k}[x^{k}](1 − 2x)^{n}(\frac{y}{(1 + y)^{2}} )^{k}.

But

∑_{k} u^{k}[v^{k}]g(v) = g(u),

and thus

f(n) = ( − \frac{1}{2})^{n}[y^{n}](1 + y)^{2n} (1 − 2\frac{y}{(1 + y)^{2}} )^{n}
= ( − 2)^{−n}[y^{n}] (1 + y^{2})^{n}

The answer is now obvious.

Knuth’s old sum 3

3. The approach of C.C. Rousseau

This one is also reported in [3].

First,

\binom{2k}{k} = [x^{0}] (x + \frac{1}{x})^{2k} .

Now

(1 − \frac{(x + \frac{1}{x})}{2}^{2})^{n} = ∑_{k=0}^{n} \binom{n}{k}( − \frac{1}{2})^{k} (x + \frac{1}{x})^{2k} ,

and

f(n) = [x^{0}] (1 − \frac{(x + \frac{1}{x})}{2}^{2})^{n} = [x^{0}] (x^{2} + x^{−2})^{n} ,

from which the answer is now immediate.

4. My solution

In [7] I gave a simple solution based on the so-called Euler transformation.

First, in general, if

A(z) = ∑_{k} a_{k}z^{k},

then

\frac{1}{1 − z} A(\frac{z}{1 − z} ) = ∑_{n} z^{n} ∑_{k} \binom{n}{k}a_{k}.

This is not hard to see:

\frac{1}{1 − z} A(\frac{z}{1 − z} ) = ∑_{m} \frac{1}{(1 − z)^{m+1}} a_{m}z^{m}

= ∑_{m} ∑_{j} \binom{m + j}{j}z^{j}a_{m}z^{m}

= ∑_{n} z^{n} ∑_{k} \binom{n}{k}a_{k}.

If we apply this principle to Knuth’s sum, then

∑_{n} f(n)z^{n} = \frac{1}{1 − z} A(\frac{z}{1 − z} ),

with

A(z) = ∑_{n} \binom{2n}{n}( − \frac{1}{2})^{n}z^{n} = \frac{1}{\sqrt{1 − 4\frac{−z}{2}}} = \frac{1}{\sqrt{1 + 2z}} .

Hence

∑_{n} f(n)z^{n} = \frac{1}{1 − z} \sqrt{\frac{1 − z}{1 + z}} = \frac{1}{\sqrt{1 − z^{2}}} ,

and

f(n) = [z^{n}]\frac{1}{\sqrt{1 − z^{2}}} .

From this the answer is immediate.

Let’s see whether we can say something more general. Since \binom{2k}{k} = \binom{− \frac{1}{2}}{k}(−4)^{k}, we write more generally

∑_{k=0}^{n} \binom{n}{k}\binom{a}{k}q^{k},

where a = −\frac{1}{2} and q = 2 means Knuth’s sum. The generating function is now

\frac{1}{1 − z} (1 + \frac{qz}{1 − z} )^{a} = \frac{(1 + (q − 1)z)^{a}}{(1 − z)^{a+1}} .

When do we get a closed form? If a is a natural number, which is obvious, since the sum itself is of closed form (only a + 1 terms), or if a + 1 = −m is a negative integer, since it is then

∑_{j=0}^{m} \binom{m}{j}(−1)^{j}(q − 1)^{n−j}\binom{−m − 1}{n − j}.

If a = −\frac{1}{2}, we get for the generating function

\frac{1}{\sqrt{1 + (q − 2)z + (q − 1)z^{2}}} ,

and we see that q = 2 gives Knuth’s sum, while q = 1 corresponds to the Vandermonde formula, which is of course also of closed form.

5. Riordan’s approach

Recently, I found out that the famous book of Riordan [8, page 71] contains a solution as well. However, the identies are credited to Reed Dawson.

Riordan writes a_{n} = 2^{−n}\binom{2n}{n}, b_{n} = f(n) and notes the recursion

a_{n} = 2a_{n−1} − \frac{1}{n}a_{n−1}.

The formula

b_{n} = ∑_{k} \binom{n}{k}(−1)^{k}a_{k}

means umbrally

b_{n} = (1 − a)^{n}, a^{k} ≡ a_{k}.

Like Jonassen and Knuth he writes

b_{n} = −b_{n−1} + \frac{1}{n} ∑_{k} \binom{n}{k + 1},

which leads to

c_{n} := n(b_{n} + b_{n−1}) = c_{n−1} + b_{n−1}.

The c_{n−1} may now be eliminated, leading to nb_{n} = (n − 1)b_{n−1}, The rest is as before.

This proof and the one of Jonassen and Knuth are very similar.

Riordan also gives some additional formulæ and generalizations.

6. Hypergeometric series

We refer to [2] for this.

We start from the reversed summation,

f(n) = ∑_{k≥0} \binom{n}{k}\binom{2n − 2k}{n − k}( − \frac{1}{2})^{n−k}.

and compute the ratio t_{k+1}/t_{k} of 2 consecutive terms:

\frac{t_{k+1}}{t_{k}} = \frac{n − k}{k + 1} \frac{n − k}{2n − 2k} \frac{n − k}{2n − 2k − 1}(−2) = \frac{(k − n)^{2}}{k − n + \frac{1}{2}} \frac{1}{2}.

Since t_{0} = \binom{2n}{n}(−\frac{1}{2})^{n}, we have the following representation of f(n) as a hypergeometric series,

f(n) = \binom{2n}{n}( − \frac{1}{2})^{n}F ({−n, −n \atop −n + \frac{1}{2}} |\frac{1}{2}) .

But there is an identity of Gauss,

F ({2a, 2b \atop a + b + \frac{1}{2}} |\frac{1}{2}) = F ({a, b \atop a + b + \frac{1}{2}} |1) ,

and we therefore find

f(n) = \binom{2n}{n}( − \frac{1}{2})^{n}F ({−\frac{n}{2}, −\frac{n}{2} \atop −n + \frac{1}{2}} |1).

But such a series can be evaluated by another formula of Gauss;

F ({a, b \atop c}|1) = \frac{Γ(c − a − b)Γ(c)}{Γ(c − a)Γ(c − b)}.

Hence we can conclude that

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

This formula gives already that f(n) = 0 for odd n, since we have “infinity” in the denominator. Let’s now concentrate on even n = 2m.

Knuth’s old sum 6

The functional equation for the Γ–function gives

Γ(\frac{1}{2}) = ( − \frac{1}{2})( − \frac{3}{2}) … ( − m + \frac{1}{2})Γ( − m + \frac{1}{2})

and

Γ( − m + \frac{1}{2}) = ( − m − \frac{1}{2})( − m − \frac{3}{2}) … ( − 2m + \frac{1}{2})Γ( − 2m + \frac{1}{2}).

Hence

\frac{Γ(\frac{1}{2})Γ(−n + \frac{1}{2})}{Γ^{2}(−\frac{n}{2} + \frac{1}{2})} = \frac{( − \frac{1}{2})( − \frac{3}{2}) … ( − m + \frac{1}{2})}{( − m − \frac{1}{2})( − m − \frac{3}{2}) … ( − 2m + \frac{1}{2})}

= \frac{1 · 3 … (2m − 1)}{(2m + 1)(2m + 3) … (4m − 1)}

= \frac{[1 · 3 … (2m − 1)]^{2}}{1 · 3 … (4m − 1)}

But

1 · 3 … (2m − 1) = \frac{(2m)!}{2^{m}m!},

and so

f(2m) = \binom{4m}{2m}\frac{1}{4^{m}} [\frac{(2m)!}{2^{m}m!}]^{2} · \frac{4^{m}(2m)!}{(4m)!} = \frac{1}{4^{m}} \binom{2m}{m},

as desired.

7. Sister Celine’s technique

I follow the description as to be found in [9].

We write

f(n) = ∑_{k≥0} F (n, k)

with

F (n, k) = \binom{n}{k}\binom{2k}{k}( − \frac{1}{2})^{k}.

We are looking for a non-trivial solution of

∑_{i=0}^{2} ∑_{j=0}^{2} a_{ij}(n)F (n − j, k − i) = 0.

For that, we divide by F (n, k) and cancel out common factors:

1 − a_{10}(n)\frac{k^{2}}{(2k − 1)(n − k + 1)} + a_{20}(n)\frac{k^{2}(k − 1)^{2}}{(2k − 1)(2k − 3)(n − k + 1)(n − k + 2)}

+ a_{01}(n)\frac{n − k}{n} − a_{11}(n)\frac{k^{2}}{(2k − 1)n} + a_{21}(n)\frac{k^{2}(k − 1)^{2}}{(2k − 1)(2k − 3)(n − k + 1)n}

+ a_{02}(n)\frac{(n − k + 1)(n − k)}{(n − 1)n} − a_{12}(n)\frac{k^{2}(n − k)}{(2k − 1)(n − 1)n}

+ a_{22}(n)\frac{k^{2}(k − 1)^{2}}{(2k − 1)(2k − 3)(n − 1)n} = 0

We multiply this by the common denominator

(2k − 1)(2k − 3)(n − k + 1)(n − k + 2)(n − 1)n,

sort with respect to powers of k and set all those coefficients = 0. We don’t want to write down these 7 equations, but Maple finds the general solution for us:

Cn^{2}F (n, k) + Bn(n − 1)F (n, k − 1)
− Cn(2n − 1)F (n − 1, k) + (2n − 1)(Cn − Bn + B)F (n − 1, k − 1)
+ B(2n − 1)(n − 1)F (n − 1, k − 2) + Cn(n − 1)F (n − 2, k)
+ (n − 1)(Bn − 2Cn − B)F (n − 2, k − 1) − 2B(n − 1)^{2}F (n − 2, k − 2) = 0

We have the freedom to set B = 0 and C = 1 to get an easy recursion. There is then a common factor n which will be divided out:

nF (n, k) − (2n − 1)F (n − 1, k) + (2n − 1)F (n − 1, k − 1)
+ (n − 1)F (n − 2, k) − 2(n − 1)F (n − 2, k − 1) = 0

But now we can sum up these equations for all k and get a recursion for f(n), the sum in question!

nf(n)−(2n−1)f(n−1)+(2n−1)f(n−1)+(n−1)f(n−2)−2(n−1)f(n−2) = 0,

or simply

f(n) = \frac{n − 1}{n}f(n − 2),

from which the initial values f(0) = 1 and f(1) = 0 give us the result as before.

7. Zeilberger’s algorithm

We cannot give the theoretical background of the algorithm. However, it is available via anonymous ftp from math.temple.edu in the directory pub/Zeilberger- /programs. I used a modified version which I obtained from Christian Krattenthaler.

It produces an answer like: “There is a first-order recurrence

(n + 1 − (n + 2)N^{2})f(n),

where N is the shift operator defined by N f(n) = f(n + 1).”

So, in conventional terms the recursion is

(n + 1)f(n) − (n + 2)f(n + 2).

This recursion can be solved as before, which the program does automatically. And you get a hint, how the solution is obtained (citation is not verbally correct):

“Choose (cleverly)

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

then

(n + 1 − (n + 2)N^{2})F (n, k) = G(n, k) − G(n, k − 1),

and the recursion follows upon summing on k.”

This is easy to check but a little bit mysterious if you don’t know the theory behind it.

The second edition of “Concrete Mathematics” (just appeared) contains a new section, emphasizing Zeilberger’s algorithm.

8. Koornwinder’s implementation of Zeilberger’s method

This Maple program gives you about this answer:

∑_{k=0}^{m} (F (n, k) − \frac{n − 1}{n}F (n − 2, k)) = −\frac{(m + 1)^{2}}{n^{2}} F (n, m + 1),

which might be rephrased as

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

with

G(n, k) = −\frac{k^{2}}{n^{2}} F (n, k).

Then it does, as the other one, the summation over k, causing the right hand side to vanish (“telescoping”), and solves the resulting recursion

f(n) − \frac{n − 1}{n}f(n − 2) = 0

by iteration.

9. Implementation of Paule and Schorn

There is also a Mathematica package doing Zeilberger’s algorithm [6], but I did not work with it.

10. WZ–Pairs

Now that we know that f(n) vanishes for odd n, let’s concentrate on the even ones.

f(2n) = ∑_{k≥0} \binom{2n}{k}\binom{2k}{k}( − \frac{1}{2})^{k} = \frac{1}{4^{n}} \binom{2n}{n}.

Write it as

∑_{k} F (n, k) = 1,

with

F (n, k) = \frac{\binom{2n}{k}\binom{2k}{k}(−\frac{1}{2})^{k}}{\frac{1}{4^{n}} \binom{2n}{n}} = 4^{n}( − \frac{1}{2})^{k} \frac{(2k)!n!^{2}}{k!^{3}(2n − k)!}.

Now define

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

and

\begin{aligned}G(n, k) & = R(n, k) · F (n, k) \\ & = −4^{n}( − \frac{1}{2})^{k} \frac{(2k)!n!^{2}}{k!(k − 1)^{2}(2n − k + 2)!}. \end{aligned}

Then it is easy to check (but not as easy to find this ‘certificate’ R(n, k)) that

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

Two discrete functions F and G which are related in this way are termed “WZ–pair” ([9]).

By summing on k, we obtain the recursion

f(n) := ∑_{k} F (n, k) = f(n − 1),

which, together with f(0) = 1 proves the identity again. But the WZ–pair contains even more information!

There is a dual WZ–pair, obtained in this way:

Substitute all factorials (an+bk +c)! by (−1)^{an+bk}/(−an−bk −c−1)!, except in the case a + b = 0, then do nothing. This gives you the pair F̄, Ḡ. Finally, change variables by

\begin{aligned}F′(n, k) & := Ḡ(−k − 1, −n) \\ G′(n, k) & := F̄(−k, −n − 1). \end{aligned}

Doing that we obtain in our instance

F′(n, k) = (−1)^{n+1} \frac{2^{n}}{4^{k+1}} \frac{(n − 1)!n!^{2}(2k − 1 − n)!}{(2n − 1)!k!^{2}}

G′(n, k) = (−1)^{n+1} \frac{2^{n+1}}{4^{k}} \frac{n!^{3}(2k − 2 − n)!}{(2n + 1)!(k − 1)!^{2}}

Now we want – in the usual way – to define

f′(n) := ∑_{k} F′(n, k).

However, because of the (2k − 1 − n)! term we have to be a little bit careful. So define (only for n ≥ 1)

f′(n) := ∑_{k≥⌈ \frac{n+1}{2} ⌉} F′(n, k).

Because of this dependency, summing up over k in

F′(n + 1, k) − F′(n, k) = G′(n, k + 1) − G′(n, k)

does not simply let the right hand side disappear. We can only sum up for k ≥ ⌈\frac{n}{2}⌉ + 1, but this gives us an extra term. It is now wise to distinguish the cases n even and n odd. So we have

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

Now let’s assume that n is even, n = 2m. Then we can sum up for k ≥ m + 2, and obtain

f′(2m + 2) − [f′(2m) − F′(2m, m + 1)] = −G′(2m + 1, m + 2) − G′(2m, m + 2),

or

f′(2m + 2) − f′(2m) = (3m + 2)\frac{(2m + 1)!(2m)!^{2}}{(4m + 3)!m!(m + 1)!^{2}} .

Iterating this we find

f′(2m + 2) = f′(2) + ∑_{j=1}^{m}(3j + 2)\frac{(2j + 1)!(2j)!^{2}}{(4j + 3)!j!(j + 1)!^{2}} .

Therefore we are going to compute

f′(2) = −\frac{2}{3} ∑_{k≥2} \frac{1}{4^{k}} \frac{(2k − 3)!}{k!^{2}}

An extremely boring computation produces the value

f′(2) = −\frac{1}{2} log 2 + \frac{1}{3}.

It was done by Maple, starting from

∑_{k≥0} \frac{(2k)!}{k!(k + 1)!}z^{k} = \frac{1 − \sqrt{1 − 4z}}{2z} ,

by some subtractions, substitutions and integrations.

Finally we obtain the following identity

\begin{matrix}− 4^{m} \frac{(2m − 1)!(2m)!^{2}}{(4m − 1)!} ∑_{k≥m+1} \frac{(2k − 1 − 2m)!}{k!^{2}} \frac{1}{4^{k+1}} \\ = −\frac{1}{2} log 2 + \frac{1}{3} + ∑_{j=1}^{m−1}(3j + 2)\frac{(2j + 1)!(2j)!^{2}}{(4j + 3)!j!(j + 1)!^{2}} . \end{matrix}

One can even go one step further down, to m = 0, since

lim_{m→0} \frac{(2m − 1)!}{(4m − 1)!} = 2.

A similar computation as before (or an adaption of the previous formula) evaluates

f′(0) = −\frac{log 2}{2},

and we have for m ≥ 0 (the index was shifted)

\begin{matrix}\frac{(2m − 1)!(2m)!^{2}}{(4m − 1)!} & ∑_{k≥1} & \frac{(2k − 1)!}{(k + m)!^{2}} & \frac{1}{4^{k+1}} \\ = \frac{1}{2} log 2 − ∑_{j=0}^{m−1}(3j + 2)\frac{(2j + 1)!(2j)!^{2}}{(4j + 3)!j!(j + 1)!^{2}} . \end{matrix}

This formula evaluates a certain infinite series, and it contains about as many terms as the parameter.

For odd n a similar formula could be produced. We leave it as an exercise.

11. Elimination

I follow Zeilberger’s description in [10].

Let us again concentrate on the even values of n, that means, we consider

f(n) := ∑_{k} F (n, k) = ∑_{k} \binom{2n}{k}\binom{2k}{k}( − \frac{1}{2})^{k}.

We use the shift operators N, defined by NF (n, k) = F (n + 1, k) and K, defined by KF (n, k) = F (n, k + 1). We compute

\begin{aligned}\frac{F (n + 1, k)}{F (n, k)} & = \frac{(2n + 2)(2n + 1)}{(2n + 2 − k)(2n + 1 − k)} \\ \frac{F (n, k + 1)}{F (n, k)} & = −\frac{(2n − k)(2k + 1)}{(k + 1)^{2}}. \end{aligned}

Cross multiplication leads to

\begin{matrix}(2n + 2 − k)(2n + 1 − k)F (n + 1, k) − (2n + 2)(2n + 1)F (n, k) = 0 \\ (k + 1)^{2}F (n, k + 1) − (k − 2n)(2k + 1)F (n, k) = 0. \end{matrix}

Or, in operator notation:

\begin{aligned}[(2n + 2)(2n + 1)(N − 1) − k(4n + 3)N + k^{2}N]F (n, k) & ≡ 0 \\ [(K − 2)k^{2} + k(4n − 1) + 2n]F (n, k) & ≡ 0 \end{aligned}

Observe that (4n+3)N in the first equivation can be replaced by N(4n−1). Define the operators P, Q by

\begin{aligned}P & = (2n + 2)(2n + 1)(N − 1) − kN(4n − 1) + k^{2}N \\ Q & = (K − 2)k^{2} + k(4n − 1) + 2n. \end{aligned}

Now compute

\begin{aligned}NQ + P & = N(K − 1)k^{2} + 2Nn + (2n + 2)(2n + 1)(N − 1) \\ & = N(K − 1)k^{2} + 4(n + 1)^{2}N − (2n + 2)(2n + 1) \end{aligned}

Now it has a nice form; K − 1 times something + something independent of K and k.

Apply it to F (n, k):

4(n + 1)^{2}F (n + 1, k) − (2n + 2)(2n + 1)F (n, k) = G(n + 1, k) − G(n, k),

with

G(n, k) := −Nk^{2}F (n, k) = \binom{2n + 2}{k}\binom{2k}{k}k^{2}( − \frac{1}{2})^{k+1}.

Now the right hand side telescopes upon summing on k, and we find

4(n + 1)^{2}f(n + 1) − (2n + 2)(2n + 1)f(n) = 0,

which we simplify to

2(n + 1)f(n + 1) − (2n + 1)f(n) = 0,

or

f(n) = \frac{2n − 1}{2n}f(n − 1).

Now, f(0) = 1, and we obtain our usual answer

f(n) = \frac{1}{4^{n}} \binom{2n}{n}

again by iteration.

Now, if we apply the whole procedure to the original thing,

f(n) := ∑_{k} F (n, k) = ∑_{k} \binom{n}{k}\binom{2k}{k}( − \frac{1}{2})^{k},

we find

\begin{aligned}\frac{F (n + 1, k)}{F (n, k)} & = \frac{n + 1}{n + 1 − k} \\ \frac{F (n, k + 1)}{F (n, k)} & = −\frac{(n − k)(2k + 1)}{(k + 1)^{2}}. \end{aligned}

The operators are this time

\begin{aligned}P & = −Nk + (n + 1)(N − 1) \\ Q & = (k + 1)^{2}K + 2kn − 2k^{2} + n − k. \end{aligned}

Since Q = (K − 1)k^{2} − k^{2} + 2kn + n − k, we can continue with P and Q_{1} := −k^{2} + 2kn + n − k. First, we have to get rid of the k^{2}–term, whence we compute

Q_{2} := NQ_{1} − kP = k(nN + n + 1) + Nn.

We now want to use P and Q_{2} in order to get rid of the k–term. However, when trying to get the coefficient at k in both operators equal, we have to be a little bit careful, since only multiplication from the left is allowed! Thus we compute

(Nn + n + 2)P + NQ_{2} = (n + 2)^{2}N^{2} − (n + 2)(n + 1).

We can divide by one factor n + 2 and get the recursion

(n + 2)f(n + 2) − (n + 1)f(n),

which is of course the usual one.

12. A contour integral for f(n)

We might write

f(n) = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}φ(k),

with

φ(k) = \binom{2k}{k}(\frac{1}{2})^{k}.

Since there is a “continuation” of φ(k) to the complex plane via

φ(z) = \frac{Γ(2z + 1)}{Γ^{2}(z + 1)}2^{−z},

we have

f(n) = −\frac{1}{2πi} ∫_{C} \frac{Γ(n + 1)Γ(−z)}{Γ(n + 1 − z)}f(z) dz,

where C is positively oriented and encircles (exactly) the poles 0, 1, …, n of the integrand.

Such an integral is sometimes called a Rice–integral, see the recent survey [1]. Here, this representation is probably not too useful.

13. Addendum (June 28, 1994)

Herbert Wilf’s book “generatingfunctionology” also discusses the sum, in a manner that closely resembles the one discussed in section 4.

Christian Krattenthaler has written a Mathematika package “HYP” that is very convenient for dealing with hypergeometric series. It does the derivation in section 6 in a half–automatic way.

Knuth’s old sum 14

References

1. P.Flajolet, R.Sedgewick, Mellin transforms and asymptotics: Finite differences and Rice’s integrals, Theoret. Comput. Sci. (1994) (to appear).

2. R.Graham, D.E.Knuth, and O.Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

3. D.Greene and D.E.Knuth, Mathematics for the Analysis of Algorithms, Birkhäuser, 1981.

4. A.Jonassen and D.E.Knuth, A trivial algorithm whose analysis isn’t, Journal of Computer and System Sciences 16 (1978), 301–322.

5. T.Koornwinder, On Zeilberger’s algorithm and its q-analogue: a rigorous description, J. of Comput. and Appl. Math. 48 (1993), 91–111.

6. P.Paule and M.Schorn, A Mathematica Version of Zeilberger’s Algorithm for Proving Binomial Coefficient Identities, J. Symb. Comput. (to appear).

7. H.Prodinger, Some information about the binomial transform, The Fibonacci Quarterly (1994) (to appear).

8. J.Riordan, Combinatorial Identities, John Wiley, 1968.

9. H.Wilf, Identities (and their computer proofs), available by ftp ftp.cis.upenn.edu as file

   pub/wilf/lecnotes.ps, 1993.

10. D.Zeilberger, 3 Recitations on Holonomic Systems and Hypergeometric Series, available by

   ftp nath.temple.edu in the directory pub/zeilberger/papers (1993).

Helmut Prodinger Department of Algebra and Discrete Mathematics TU Vienna Wiedner Hauptstrasse 8-10 A-1040 Vienna Austria