INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A22

TRUNCATING BINOMIAL SERIES WITH SYMBOLIC SUMMATION

Peter Paule

Research Institute for Symbolic Computation, J. Kepler University Linz, A-4040 Linz, Austria

                      Peter.Paule@risc.uni-linz.ac.at

Carsten Schneider^{1}

Research Institute for Symbolic Computation, J. Kepler University Linz, A-4040 Linz, Austria

                   Carsten.Schneider@risc.uni-linz.ac.at

Received: 1/4/07, Accepted: 4/3/07, Published: 4/24/07

Abstract

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.

1. Introduction

Consider the identity

∑_{k=m+1}^{∞} \frac{m}{k(k − 1)} ∑_{j=0}^{m} \binom{k}{j}x^{k−j}(1 − x)^{j} = x, m ≥ 1, 0 ≤ x ≤ 1,  (1)

which arose in the theory of records [Blo86, Isr88]. In an attempt to generalize this result, Tamás Lengyel [Len06] found the binomial series

a_{m,n}(x) = \binom{m}{n − 1} ∑_{k=m+1}^{∞} \binom{k}{n}^{−1} ∑_{j=0}^{m} \binom{k}{j}x^{k−j}(1 − x)^{j},

which evaluates for all integers n and m with 0 ≤ n − 1 ≤ m to

a_{m,n}(x) = \begin{cases}\frac{n}{n−1}(1 − (1 − x)^{n−1}), & if n ≥ 2 and 0 ≤ x ≤ 1 \\ − ln(1 − x), & if n = 1 and 0 ≤ x < 1. \end{cases}  (2)

1Supported by the SFB-grant F1305 and the grant P16613-N12 of the Austrian FWF.

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 (2) where Lengyel’s a_{m,n}(x) series is replaced by the truncated version

a_{m,n}^{(K)}(x) = \binom{m}{n − 1} ∑_{k=m+1}^{K} \binom{k}{n}^{−1} ∑_{j=0}^{m} \binom{k}{j}x^{k−j}(1 − x)^{j}

in which K ≥ m + 1.

In Section 2 we present an automatic evaluation of a_{m,n}(x) using Gosper’s telescoping and Zeilberger’s creative telescoping algorithms, respectively. In Section 3 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 4 we derive such identities which in the limit K → ∞ give (2); see (7) and (8). To obtain the limit for K → ∞, a generating function identity (9) is used. In Section 5 we demonstrate that (9) can be also derived with symbolic summation. In Section 6 some concluding remarks are given.

All computations are done using the package Sigma [Sch04a]; to derive (7) and (8) special Sigma features are applied.

2. Automatic Evaluation of a_{m,n}(x)

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 ∑_{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} ∑_{N=1}^{∞}(−1)^{N}x^{N} ∑_{k=m+1}^{∞}(−1)^{k}\binom{k}{n}^{−1}A_{m}(N)

where

A_{m}(N) = ∑_{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 Sigma package into the computer algebra system Mathematica

In[1]:= << Sigma.m

Sigma - A summation package by Carsten Schneider \begin{matrix}c \\ ◯ \end{matrix} RISC-Linz

we insert the hypergeometric sum S = A_{m}(N). Note that various Sigma functions support the user, like SigmaSum for sums, SigmaProduct for products, SigmaPower for powers, or

SigmaBinomial for binomials.

In[2]:= S = SigmaSum[ SigmaPower[−1, j]SigmaBinomial[k, j]SigmaBinomial[j, N − k + j], {j, 0, m}]

Out[2]= ∑_{j=0}^{m}(−1)^{j}\binom{k}{j}\binom{j}{N − k + j}

Then, by telescoping, Sigma produces the following closed form for A_{m}(x)(= S):

In[3]:= SigmaReduce[S]

Out[3]= −\frac{(−1)^{m}(m − k)}{N}\binom{k}{m}\binom{m}{N − k + m}.

This can also be achieved by any implementation of Gosper’s algorithm [Gos78], so we omit details here. Hence

a_{m,n}(x) = (−1)^{m}\binom{m}{n − 1} ∑_{N=1}^{∞} \frac{(−1)^{N}x^{N}}{N} B_{m,n}(N)  (3)

where

B_{m,n}(N) = ∑_{k=m+1}^{∞}(−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 Sigma function

In[4]:= GenerateRecurrence[ ∑_{k=m+1}^{∞}(−1)^{k}\binom{k}{n}^{−1}\binom{k}{m}\binom{m}{N − k + m}(k − m), N]

Out[4]= {(−1 + n − N)SUM[N] − NSUM[1 + N] == 0}

which is based on creative telescoping [Zei91] and which computes the recurrence Out[4] for SUM[N] = B_{m,n}(N). This can be also achieved by any implementation of Zeilberger’s algorithm, so we omit details here.

The recurrence Out[4] 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

B_{m,n}(x) = (−1)^{N+m}n\binom{m}{n − 1}^{−1}\binom{N − n}{N − 1},  (4)

i.e.,

a_{m,n}(x) = n ∑_{N=1}^{∞} \frac{x^{N}}{N} \binom{N − n}{N − 1}.

Finally, for n = 1,

a_{m,1}(x) = ∑_{N=1}^{∞} \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} ∑_{N=1}^{∞}(−x)^{N} \binom{n − 1}{N} = −\frac{n}{n − 1}(−1 + (1 − x)^{n−1}).

3. A Truncated Variant of the Original Identity (1)

With respect to our starting point, identity (1), the computer algebra approach taken in Section 2 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

B_{m,2}^{(K)}(N) = ∑_{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}

for N > 1 and arbitrary K ≥ m + 1. Obviously for N = 1,

B_{m,2}^{(K)}(1) = \frac{(−1)^{m+1}}{m} for K ≥ m + 1.

Consequently, the truncated version a_{m,2}^{(K)}(x) of a_{m,2}(x) finds the following evaluation for K ≥ m + 1:

a_{m,2}^{(K)}(x) = 2(−1)^{m}m ∑_{N=1}^{K} \frac{(−1)^{N}x^{N}}{N} B_{m,2}^{(K)}(N)

= 2x + 2m(−1)^{K+m}\binom{K − 1}{m} ∑_{N=2}^{K} \frac{(−1)^{N}x^{N}}{N(N − 1)}\binom{m − 1}{K − N}.  (5)

In the limit K → ∞, one retrieves identity (1).

One observes that B_{m,n}^{(K)}(x) also telescopes for all other specific values of n ≥ 3. This suggests that a nice truncated generalization like (5) 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 Sigma which will lead us to an answer in the form of identities (7) and (8).

4. Closed Form Evaluations of a_{m,n}^{(K)}(x)

In contrast to Sections 2 and 3, we will apply Sigma 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,

α_{m,n}^{(K)}(x) := ∑_{k=1}^{K} \frac{x^{m+k}}{\binom{m+k}{n}}D_{m,k}(x)

with

D_{m,k}(x) = ∑_{j=0}^{m} \frac{(1 − x)^{j}}{x^{j}} \binom{m + k}{j}.

Note that for K ≥ m + 1 ≥ n ≥ 1,

a_{m,n}^{(K)}(x) = \binom{m}{n − 1}α_{m,n}^{(K−m)}(x).  (6)

Also note that we restrict to x ≠ 0; the case x = 0 is trivial.

4.1. Preprocessing

A first step to simplify the sum α_{m,n}^{(K)}(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 ∑_{j=0}^{k} f(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

In[5]:= D = ∑_{j=0}^{m} \frac{(1 − x)^{j}}{x^{j}} \binom{m + k}{j};

and compute a recurrence^{2} for SUM[k] = D_{m,k}(x):

In[6]:= rec = GenerateRecurrence[D, k][[1]]

Out[6]= x^{m}SUM[k] − x^{m+1}SUM[k + 1] == (1 − x)^{m+1}\binom{k + m}{m}

Next, we solve this recurrence with the Sigma function

In[7]:= recSol = SolveRecurrence[rec, SUM[k]]

Out[7]= \{\{0, ∏_{i=1}^{k} \frac{1}{x}\}, \{1, − (∏_{i=1}^{k} \frac{1}{x}) \frac{(1 − x)^{m+1}}{x^{m+1}} ∑_{i=0}^{k} \frac{i\binom{m+i}{m}x^{i}}{m + i} \}\}

This means that \frac{1}{x^{k}} is a solution of the homogeneous version, and −\frac{(1−x)^{m+1}}{x^{m+k+1}} ∑_{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

2As in Out[4], this can be achieved by any implementation of Zeilberger’s algorithm.

D_{m,k}(x) = \frac{c}{x^{k}} − \frac{(1 − x)^{m+1}}{x^{m+k+1}} ∑_{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

∑_{j=0}^{m} \frac{(1 − x)^{j}}{x^{j}} \binom{m}{j} = c; i.e., c = \frac{1}{x^{m}} .

Summarizing, we can represent α_{m,n}^{(K)}(x) =: A in the form

In[8]:= A = ∑_{k=1}^{K} \frac{x − (1 − x)^{m+1}∑_{i=0}^{k} \frac{i\binom{m+i}{m}x^{i}}{m + i}}{x\binom{k+m}{n}} ;

4.2. The Case n > 1.

Now Sigma is ready to simplify A in one stroke (i.e., no splitting into two sums is needed):

In[9]:= result = SigmaReduce[A, SimpleSumRepresentation → True]

 Out[9]= −\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}} ∑_{i=0}^{K} \frac{ix^{i}\binom{i+m}{m}}{i + m} − \frac{(1 − x)^{n+1}}{x(n − 1)} ∑_{i=1}^{K} \frac{ix^{i}\binom{i+m}{m}}{\binom{i+m}{n}}

Remark. Sigma automatically found the additional sum ∑_{i=1}^{K} ix^{i}\binom{i+m}{m}\binom{i+m}{n}^{−1} in order to simplify A = α_{m,n}^{(K)}(x) to an expression consisting only of single sums; for details of the method see [Sch04b].

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 ≥ m + 1 ≥ n ≥ 2,

\begin{aligned}a_{m,n}^{(K)}(x) = \frac{n}{n − 1}[1 − \begin{matrix}( & {m \atop n−1} & ) \\ ( & {K \atop n−1} & ) \end{matrix} & + \begin{matrix}( & {m \atop n−1} & ) \\ ( & {K \atop n−1} & ) \end{matrix}(1 − x)^{m+1} ∑_{i=0}^{K−m−1}(−1)^{i}\binom{−m − 1}{i}x^{i} \\ & − (1 − x)^{m+1} ∑_{i=0}^{K−m−1}(−1)^{i}\binom{n − m − 2}{i}x^{i}]. \end{aligned}  (7)

In the limit K → ∞, owing to the binomial theorem, we retrieve Lengyel’s identity (2).

Concerning the case n = 2 we remark that the equivalence of (5) and (7) is based on a non-trivial transformation; e.g., for the elementary special case x = 1 it specializes to (K ≥ m + 1)

∑_{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 [GKP94, (5.41)].

4.3. The Case n = 1.

After inserting α_{m,1}^{(K)}(x) by

In[10]:= A1 = A/.n → 1

Out[10]= ∑_{k=1}^{K} \frac{x − (1 − x)^{m+1}∑_{i=0}^{k} \frac{i\binom{m+i}{m}x^{i}}{m + i}}{x(m + k)}

we get the simplification

In[11]:= SigmaReduce[A1, SimpleSumRepresentation → True]

Out[11]= (1 − (1 − x)^{m+1} ∑_{i=0}^{K}x^{i}\binom{i + m}{m}) ∑_{i=1}^{K} \frac{1}{i + m} + (1 − x)^{m+1} ∑_{i=1}^{K}x^{i}\binom{i + m}{m} ∑_{j=1}^{i} \frac{1}{j + m}

Remark. Similar as in Out[9] Sigma automatically found the sum expressions ∑_{i=1}^{K} \frac{1}{i+m} and ∑_{i=1}^{K} x^{i}\binom{i+m}{m} ∑_{j=1}^{i} \frac{1}{j+m} in order to simplify A1 = α_{m,1}^{(K)}(x) in Out[11]; for details see [Sch05].

Using ∑_{i=1}^{K} \frac{1}{i+m} = H_{K+m} − H_{m} where H_{m} = 1 + \frac{1}{2} + ⋯ + \frac{1}{m} are the harmonic numbers, we can write a_{m,1}^{(K)}(x) in the form (K ≥ m + 1 and m ≥ 0)

a_{m,1}^{(K)}(x) = H_{K+m} − H_{m} − (1 − x)^{m+1}[H_{K+m} ∑_{i=0}^{K} \binom{i + m}{m}x^{i} − ∑_{i=0}^{K} \binom{i + m}{m}H_{m+i}x^{i}]. (8)

In the limit K → ∞ we retrieve (2), owing to the binomial theorem and the fact [GKP94, (7.43)] that

∑_{i=0}^{∞} \binom{i + m}{m}H_{m+i}x^{i} = −\frac{1}{(1 − x)^{m+1}} ( ln(1 − x) − H_{m}).  (9)

5. Generating Functions with Sigma

Identity (9) can be also derived with computer algebra. A standard method would be to utilize holonomic closure properties by using the packages [SZ94] or [Mal96]. However, in the given context, we find it instructive to show that (9) can be also obtained with Sigma, namely as follows. We input the sum

In[12]:= E = ∑_{i=0}^{∞} \binom{i + m}{m}H_{m+i}x^{i};

and compute a recurrence relation satisfied by it:

In[13]:= GenerateRecurrence[E, m]

Out[13]= −(m + 2)(x − 1)^{2}SUM[m + 2] − (2m + 3)(x − 1)SUM[m + 1] + (−m − 1)SUM[m] == 0

Next, we solve the recurrence with the Sigma function

In[14]:= recSol = SolveRecurrence[rec[[1]], SUM[m]]

Out[14]= \{\{0, ∏_{i=1}^{m} \frac{1}{1 − x}\}, \{0, ∏_{i=1}^{m} \frac{1}{1 − x} ∑_{i=1}^{m} \frac{1}{i}\}, \{1, 0\}\}

Denoting the left hand side of (9) 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} = ∑_{i=0}^{∞} H_{i}x^{i}(= E_{0}(x))

and

\frac{c_{0}}{(1 − x)} + \frac{c_{1}}{(1 − x)} = ∑_{i=0}^{∞}(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

In[15]:= SigmaReduce[∑_{i=0}^{K}(i + 1)H_{i+1}x^{i}, Tower → {∑_{i=0}^{K} H_{i}x^{i}}]

Out[15]= \frac{(x − 2)x^{K+1} + (K + 1)(x − 1)H_{K}x^{K+1} + 1 + (1 − x) ∑_{i=0}^{K}H_{i}x^{i}}{(x − 1)^{2}}

Hence, with K → ∞ and the assumption that 0 ≤ x < 1, we get

E_{1}(x) = \frac{1}{(1 − x)^{2}} + \frac{1}{1 − x} ∑_{i=0}^{∞} H_{i}x^{i}.

Thus c_{1} = \frac{1}{1−x}, and therefore

E_{m}(x) = \frac{∑_{i=0}^{∞} H_{i}x^{i}}{(1 − x)^{m}} + \frac{H_{m}}{(1 − x)^{m+1}} .

Invoking the knowledge ∑_{i=0}^{∞} H_{i}x^{i} = − ln(1 − x)/(1 − x), we arrive at (9).

6. Conclusion

With identity (2) 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 Sigma package has led us to find the relations (5),

(7) and (8) 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 (1).

References

[Blo86] G. Blom. Poblem 6522. Amer. Math. Monthly, 93:485, 1986.

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

[Gos78] R. W. Gosper. Decision procedures for indefinite hypergeometric summation. Proc. Nat. Acad. Sci. U.S.A., 75:40–42, 1978.

[Isr88] R.B. Israel. Persistence of a distribution. Amer. Math. Monthly, 95:360–362, 1988.

[Len06] T. Lengyel. An invariant sum related to record statistics. Preprint, 2006.

[Mal96] C. Mallinger. Algorithmic manipulations and transformations of univariate holonomic functions and sequences. Master’s thesis, RISC, J. Kepler University, Linz, August 1996.

[Sch04a] C. Schneider. The summation package Sigma: Underlying principles and a rhombus tiling application. Discrete Math. Theor. Comput. Sci., 6(2):365–386, 2004.

[Sch04b] C. Schneider. Symbolic summation with single-nested sum extensions. In J. Gutierrez, editor, Proc. ISSAC’04, pages 282–289. ACM Press, 2004.

[Sch05] C. Schneider. Finding telescopers with minimal depth for indefinite nested sum and product expressions. In M. Kauers, editor, Proc. ISSAC’05, pages 285–292. ACM, 2005.

[SZ94] B. Salvy and P. Zimmermann. Gfun: A package for the manipulation of generating and holonomic functions in one variable. ACM Trans. Math. Software, 20:163–177, 1994.

[Zei91] Doron Zeilberger. The method of creative telescoping. Journal of Symbolic Computation, 11:195– 204, 1991.