Bijective and Automated Approaches to Abel Sums

Gil KALAI and Doron ZEILBERGER

Dedicated to Dominique Foata (b. Oct. 12, 1934), on his forthcoming 90th birthday

Abstract: In this tribute to our guru, Dominique Foata, we return to one of our (and Foata’s) first loves, and revisit Abel sums and their identities, from two different viewpoints.

Preface

In the very first issue of Crelle’s journal (the first mathematical periodical solely dedicated to mathematics), Niels Henrik Abel published a two-page paper [A], stating and proving his eponymous identity. This lead to an intensive study of general Abel Sums by many people, (see [R] [C] and their numerous references), and to beautiful bijective approaches pioneered by Dominique Foata and Aimé Fuchs [Fo][FoFu] that led to Francon’s elegant proof [Fr] (see [C], p. 129). This tribute consists of two independent parts. The first part is bijective, while the second part is automated, elaborating and extending John Majewicz’s 1997 PhD thesis [M1][M2], and more important, fully implementing it (and its extension) in a Maple package

https://sites.math.rutgers.edu/~zeilberg/tokhniot/AbelCeline.txt .

Part I: Bijective Proofs (à la Foata) of an Abel-Type identity and a generalization

In [K] (see also [K’]), the first author proved (as a special case of more general results) the following Abel-type identity. Let n, p by nonnegative integers, then

∑_{k=0}^{n} \binom{n}{k}k^{k}(n − k)^{n−k+p} = ∑_{k=0}^{n} \binom{n}{k}n^{k}(n − k)!S(p + n − k, n − k) .  (1)

Here, S(n, k) are the Stirling numbers of the second kind, and k!S(n, k) is the number of maps from a set of size k onto a set of size n. (This property can serve as the definition of these numbers.)

A special case of this formula is attributed to Cauchy (Equation (24) in Chapter 1 of [R]):

∑_{k=0}^{n} \binom{n}{k}k^{k}(n − k)^{n−k} = ∑_{k=0}^{n} \binom{n}{k}n^{k}(n − k)! .  (2)

Here we present a combinatorial proof, in the style of Foata [Fo][FoFu] for Formulas (2) and (1). We use the notation [n] = {1, 2, …, n}, and to make the argument clearer we will present both proofs.

The Proofs

Proof of Equation (2): The left hand side counts triples f, A, B where f is a function from [n] to [n] and the following conditions hold:

A ∪ B = [n], A ∩ B = ∅, f(A) ⊂ A and f(B) ⊂ B.  (3)

Indeed, if |A| = k, there are \binom{n}{k} ways to choose A (B is now determined, B = [n]\A), k^{k} ways to choose the restriction of f to A subject to the condition f(A) ⊂ A and (n − k)^{n−k} ways to choose the restriction of f to B subject to the condition f(B) ⊂ B.

The right hand side counts triples f, C, D where f is a function from [n] to [n] and following conditions hold:

C ∪ D = [n], C ∩ D = ∅, f(D) = D.  (4)

(Here, f(D) = D means that f is a bijection from D to D; Note that we relaxed the condition for C compared to A and strengthened the condition for D compared to B.) Indeed, if |C| = k, there are \binom{n}{k} ways to choose C, n^{k} ways to choose the restriction of f to C (no conditions here) and (n − k)! ways to choose the restriction of f to D subject to the condition f(D) = D.

The crucial observation is:

• For every function f from [n] to [n] the number of pairs (A, B) that satisfies Equation (3) equals the number of pairs (C, D) that satisfies equation (4).

Indeed if (A, B) is a pair that satisfies Equation (3), we can take

D = f(f(⋯ (f(B)) ⋯) and C = f^{−1}(f^{−1}(⋯ (f^{−1}(A))·).  (5)

In other words D = {d ∈ [n] : d = f^{k}(a) for some a ∈ B, and k ≥ 0} and C = {c ∈ [n] : f^{k}(c) ∈ B for some k ≥ 0}. Taking the inverse operation brings you from a pair (C, D) to a pair (A, B)

Proof of Equation (1):

Let X = [n] = {1, 2, ….n}, and Y = [n + p] Consider all triples (f, A, B) where, this time, f maps [n + p] to [n], and A, B satisfy

A ∪ B = [n], A ∩ B = ∅, f(A) ⊂ A and f(B ∪ [n + 1, n + p]) ⊂ B.

We also consider triples (f, C, D) where, f maps [n + p] to [n], and C, D satisfy

C ∪ D = [n], C ∩ D = ∅, f(D ∪ [n + 1, n + p]) = D.  (7)

Also in this case a stronger statement holds: For every function f : [n + p] → [n] there is a bijection between between pairs (A, B) satisfying equation (6) and pairs (C, D) satisfying equation (7) and the bijection is given again by (5).

This bijection is implemented in the Maple package AbelBijection.txt, available from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/AbelBijection.txt .

See the front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/abelKZ.html for a sam-

ple input file and its corresponding output file.

Remark: If we give each element k ∈ [n] a weight w_{k} and a function f from [n + p] → [n] the weight w(f) = ∏{w(f(k)) : k ∈ [n]} then our bijective proof gives a Hurwitz-type generalization of Abel’s formula, see Hurwitz [H] and Excercise 30 in Section 2.3.4.4. of Knuth [Kn]. (For Formula (1) we obtain a Hurwitz-type generalization of the Stirling numbers of the second kind.)

Part II: Automating Abel Sums

Abel’s original identity had many proofs, but the one by Shalosh B. Ekhad and John Majewicz [EM] (written 30 years ago, and dedicated to Dominique Foata on his 60^{th} birthday) has the distinction that it was computer-generated, yet with a bit of patience, humanly readable and verifiable. In order to motivate the sequel, let’s reproduce it in its entirety.

Abel’s identity: For any non-negative integer, n

∑_{k=0}^{n} \binom{n}{k} (r + k)^{k−1}(s − k)^{n−k} = \frac{(r + s)^{n}}{r} .  (8)

Proof Let F_{n,k}(r, s) and a_{n}(r, s) denote, respectively, the summand and sum on the LHS of (8), and let G_{n,k} := (s − n)\binom{n−1}{k−1} (k + r)^{k−1}(s − k)^{n−k−1}. Since

F_{n,k}(r, s)−sF_{n−1,k}(r, s)−(n+r)F_{n−1,k}(r+1, s−1)+(n−1)(r+s)F_{n−2,k}(r+1, s−1) = G_{n,k}−G_{n,k+1} ,

(check!), we have by summing from k = 0 to k = n, thanks to the telescoping on the right:

a_{n}(r, s) − sa_{n−1}(r, s) − (n + r)a_{n−1}(r + 1, s − 1) + (n − 1)(r + s)a_{n−2}(r + 1, s − 1) = 0. (9)

Since (r + s)^{n} · r^{−1} also satisfies this recurrence (check!) with the same initial conditions a_{0}(r, s) = r^{−1} and a_{1}(r, s) = (r + s) · r^{−1}, (8) follows.

This proof was derived using John Majewicz’s brilliant adaptation of Sister Celine’s technique [Fa1][Fa2][Z] (see also [PWZ], chapter 4). Recall that Sister Celine was interested in finding pure recurrence relations of the form

c_{0}(n)a_{n} + c_{1}(n)a_{n+1} + … + c_{L}(n)a_{n+L} = 0 ,  (10)

where c_{0}(n), …, c_{L}(n) are polynomials in n for sequences a_{n}, that are defined by expressions of the form

a_{n} := ∑_{k=−∞}^{∞} F_{n,k} ,

where F_{n,k} is proper hypergeometric (see [PWZ] for the definition, in particular, F_{n+1,k}/F_{n,k} and F_{n,k+1}/F_{n,k} are both rational functions of n and k) . The way she did it was to (in her case by hand, but nowadays it has all been fully automated) to search for a recurrence of the form:

∑_{i=0}^{L} ∑_{j=0}^{M} b_{ij}(n)F_{n+i,k+j} = 0 ,  (11)

for some positive integers L and M.

Dividing by F_{n,k}, and clearing denominators, looking at the numerator, and then setting all the coefficients of powers of k to 0, yields a system of linear equations (with coefficients that are polynomials in n) for the undetermined b_{ij}(n).

Having found the b_{ij}(n), summing Eq. (11) from k = −∞ to k = ∞, yields Eq. (10) with

c_{i}(n) = ∑_{j=0}^{M} b_{ij}(n) , 0 ≤ i ≤ L .

In his PhD thesis [M1][M2] (written under the direction of the second author), John Majewicz adapted Sister Celine’s method to Abel Type sums, of the form

a_{n}(r, s) = ∑_{k=0}^{n} F_{n,k} (r + k)^{k−1+p}(s − k)^{n−k+q}x^{k} ,  (12)

where F_{n,k} is hypergeometric in n and k. Here p and q are arbitrary integers, and x is any number (or symbol). It is no longer the case that a_{n}(r, s) satisfies a pure recurrence in n, with r and s fixed, but it does satisfy a functional recurrence, similar (but often much more complicated) to Eq. (10). Denoting the summand of (12) by \overline{F}_{n,k}(r, s)

\overline{F}_{n,k}(r, s) := F_{n,k}(r + k)^{k−1+p}(s − k)^{n−k+q}x^{k} ,

one looks for polynomials b_{ij}(n) (that also depend on r, s, p, q and x, but are free of k), such that

∑_{i=0}^{L} ∑_{j=0}^{M} b_{ij}(n)\overline{F}_{n+i,k+j}(r − j, s + j) = 0 .  (13)

Dividing by \overline{F}_{n,k}(r, s) (since \overline{F}_{n+i,k+j}(r − j, s + j)/\overline{F}_{n,k}(r, s) is still a rational function of n and k), clearing denominators, looking at the numerator, and setting all the coefficients of powers of k to 0, we get again a system of linear equations for the undetermined quantities b_{ij}(n). We then ask Maple to kindly solve them, and if in luck we get a non-zero solution. It can be shown ([M1][M2]) that one can always find orders L and M for which such a system is solvable (for sufficiently large L and M, there are more unknowns than equations). Having found such a recurrence for \overline{F}_{n,k}, summing over k yields a functional recurrence for a_{n}(r, s).

∑_{i=0}^{L} ∑_{j=0}^{M} b_{ij}(n)a_{n+i}(r − j, s + j) = 0 .  (14)

Implementation We fully implemented the Celine-Majewicz algorithm in a Maple packge AbelCeline.txt available from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/AbelCeline.txt . The function call

is

FindOpe(F,n,k,r,s,R,S,N,K,MaxOrd); ,

where MaxOrd is the maximal order of the recurrence you are willing to tolerate. It inputs the hypergeometric terms F_{n,k} and outputs the recurrence in the form of the corresponding operator, where N, R, and S are the forward shift operators in n, r, and s, respectively. To get a computer-generated paper, in humanese, the function call is:

Paper(F,n,k,r,s,R,S,N,K,MaxOrd):  .

Sample Output Typing

Paper(binomial(n,k)*x**k,n,k,r,s,2):,

yields in 0.12 seconds the following deep fact. Let, for any integers p and q and number (or symbol) x

a_{n}(r, s) := ∑_{k=0}^{n} \binom{n}{k}(r + k)^{k−1+p}(s − k)^{n−k+q} x^{k} ,

then a_{n}(r, s) = (nx + rx) a_{n−1}(r + 1, s − 1)+sa_{n−1}(r, s)+(−nrx − nsx + rx + sx) a_{n−2}(r + 1, s − 1) .

Typing

Paper(1/(k!**2*(n-k)!)*x**k,n,k,r,s,3):

yields that the sequence of polynomials in (r, s) defined by

a_{n}(r, s) := ∑_{k=0}^{n} \frac{1}{k!^{2}(n − k)!} (r + k)^{k−1+p}(s − k)^{n−k+q} x^{k} ,

satisfies the functional recurrence

a_{n}(r, s) = \frac{x (n + r) a_{n−1}(r + 1, s − 1)}{n^{2}} + \frac{(2n^{2} − 2ns − 2n + s) sa_{n−1}(r, s)}{(n − 1 − s) n^{2}}

−\frac{(n^{2} + 2nr − 2rs − s^{2} − n − r) xa_{n−2}(r + 1, s − 1)}{(n − 1 − s) n^{2}}

−\frac{(n − s) s^{2}a_{n−2}(r, s)}{(n − 1 − s) n^{2}} + \frac{(nr + ns − rs − s^{2}) xa_{n−3}(r + 1, s − 1)}{(n − 1 − s) n^{2}} .

To see numerous other examples, read the output files in the front of this article:

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/abelKZ.html .

In particular, to see the functional recurrence satisfied by the ‘innocent’ sum:

a_{n}(r, s) := ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}(r + k)^{k−1+p}(s − k)^{n−k+q} x^{k} ,

see the output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oAbelCeline4.txt .

Notice how complicated things get! Getting differential recurrences Since r and s, as opposed to n and k, are ‘continuous variables’, and since the functional recurrences gotten by Majewicz’ Abel-Celine technique get so complicated even with very simple summands, it occurred to us to look for differential recurrences. For any bi-variate (proper) hypergeometric term F_{n,k}, defining (as above)

a_{n}(r, s) := ∑_{k=0}^{n} F_{n,k}(r + k)^{k−1+p}(s − k)^{n−k+q} x^{k} ,

where p and q are integers (but may be left symbolic) and x is a number (again, it can be left symbolic), one looks for differential-recurrence equations of the form

∑_{i=0}^{L} ∑_{j=0}^{M} b_{i,j}(n, r, s)\frac{d^{i}}{dr^{i}} a_{n+j}(r, s) = 0 ,

and

∑_{i=0}^{L} ∑_{j=0}^{M} c_{i,j}(n, r, s)\frac{d^{i}}{ds^{i}} a_{n+j}(r, s) = 0 ,

Together these pairs of differential recurrence equations, combined with initial conditions, uniquely determine a_{n}(r, s). In fact, one can consider far more general ‘kernels’. We can find a pair of differential recurrence equations for sums of the from

a_{n}(r, s) := ∑_{k=0}^{n} F_{n,k}K(r, s, n, k) ,

for any kernel K(r, s, n, k) such that (\frac{∂K}{∂r})/K, and (\frac{∂K}{∂s})/K are rational functions of (r, s) (and k). We proceed analogously. One applies the generic operator to the summand \overline{F} (n, k), expands, clears denominators, looks at the numerator, then equates all the powers of k to 0, getting a system of linear equations that Maple can solve for you. To get these pair of equations, in verbose, human-readable from, type:

PaperD(F,n,k,r,s,MaxOrd,KER):

where MaxOrd is the maximum order you are willing to tolerate, and KER is the kernel. For example, typing

PaperD(binomial(n,k),n,k,r,s,2,(r+k)**(k-1+p)*(s-k)**(n-k+q)*x**k): ,

yields in a fraction of a second the facts that the sequence of polynomials in r and s, a_{n}(r, s) (for any p and q and x)

a_{n}(r, s) := ∑_{k=0}^{n} \binom{n}{k}(r + k)^{k−1+p}(s − k)^{n−k+q} x^{k} ,

satisfy the pair of recurrence-differential equations (the first in r, the second in s)

− (pn + ns − n + p + s − 1) a_{n}(r, s) + (nr + ns + r + s) (\frac{∂}{∂r} a_{n}(r, s))

+(n + p)a_{n+1}(r, s) − (n + r + 1) (\frac{∂}{∂r} a_{n+1}(r, s)) = 0 ,

and

− (n + 1) (q + n − s + 1) a_{n}(r, s) + qa_{n+1}(r, s) + (n − s + 1) (\frac{∂}{∂s}a_{n+1}(r, s)) = 0 .

Remark: The proof technique of this part can prove (2) and can be adapted (with some preprocessing) to prove (1).

Note that setting x = 1 and p = 0, q = 0 yields yet-another (automatic) proof of the original identity (8). In fact it is closer in spirit to Niels Abel’s original proof, that also used differentiation (or rather integration). To see many other examples, look at the output files

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oAbelCeline5.txt ,

and

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oAbelCeline6.txt .

To see examples with more complicated kernels, see

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oAbelCeline7.txt .

Readers can easily find many other such deep facts by playing with AbelCeline.txt. Enjoy! References

[A] Niels H. Abel, Beweis eines Ausdruckes, von welchem die Binomial-Formel ein einzelner Fall ist, Crelle’s J. Mathematik 1 (1826), 159-160.

https://sites.math.rutgers.edu/~zeilberg/akherim/Abel1826.pdf .

[C] Louis Comtet, “Advanced Combinatorics”, D. Reidel Publ. Co., Dordrecht/Boston, 1974 .

[EM] Shalosh B. Ekhad and John Majewicz, A short WZ-style proof of Abel’s identity, Electronic Journal of Combinatorics 3(2) (the Foata Festschrift) #R16.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/abel.pdf .

[Fa1] Sister Mary Celine Fasenmyer, Some generalized hypergeometric polynomials, Bull. Amer. Moth. Soc. 53 (1947), 806-812.

[Fa2] Sister Mary Celine Fasenmyer, A note on pure recurrence relations, Amer. Math. Monthly 56 (1949), 14-17.

[Fo] Dominique Foata, Enumerating k-Trees, Discrete Mathematics 2 (1971), 181-186.

https://irma.math.unistra.fr/~foata/paper/pub16.pdf .

[FoFu] Dominique Foata and Aimé Fuchs, Réarrangements de fonctions et dénombrement, Discrete Mathematics 2 (1971), 181-186.

https://irma.math.unistra.fr/~foata/paper/pub12.pdf .

[Fr] Jean Francon, Preuves combinatoires des identités d’Abel, Discrete Mathematics 8 (1974), 331-343.

[H] Adolf Hurwitz, Über Abels Verallgemeinerung der binomischen Formel, Acta Math. 26 (1902), 199-203. [K] Gil Kalai, A note on an evaluation of Abel sums, J. Combin, Theory (Ser. A), 27 (1979), 213-217.

https://sites.math.rutgers.edu/~zeilberg/akherim/kalai1979.pdf .

[K’] Gil Kalai, Nostalgia corner: John Riordans referee report of my first paper, blog post on Combinatorics and More, 2021. https://gilkalai.wordpress.com/2021/02/19/nostalgia-corner-john-riordans-referee-report-of-my-first-paper/

[Kn] Donald E. Knuth, The Art of Computer Programming, Vol. I: Fundamental Algorithms (AddisonΘWesley, Reading, MA, 1969).

[M1] John Majewicz, WZ-type certification procedures and Sister Celine’s technique for Abel-type sums, J. of Difference Equations and Applications 2 (1996), 55-65.

[M2] John Majewicz, WZ certification of Abel-type identities and Askey’s positivity conjecture, Ph.D. thesis, Temple University 1997.

https://sites.math.rutgers.edu/~zeilberg/Theses/JohnMajewiczThesis.pdf .

[PWZ] Marko Petkovsek, Herbert S. Wilf, and Doron Zeilberger, “A=B”, A.K. Peters, 1996.

https://sites.math.rutgers.edu/~zeilberg/AeqB.pdf .

[R] John Riordan, “Combinatorial identities”, Wiley, New York, 1968.

[Z] Doron Zeilberger, Sister Celine’s technique and its generalizations, J. Math. Anal. Appl. 85 (1982), 114-145.

https://sites.math.rutgers.edu/~zeilberg/mamarimY/celine1982.pdf .

Gil Kalai, Hebrew University of Jerusalem, Einstein Institute of Mathematics, and Reichman University, Efi Arazi School of Computer Science.

Email: gil.kalai at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

April 18, 2024 .