the electronic journal of combinatorics 3 (2) (1996), #R16 1

A SHORT WZ-STYLE PROOF OF ABEL’S IDENTITY

Shalosh B. Ekhad and John E. Majewicz

Submitted: February 17, 1995; Accepted: July 25, 1995

Dedicated to Dominique Foata on the occasion of his sixtieth birthday.

Abstract. Using a certification procedure for Abel-type sums, we present a computerized proof of Abel’s identity.

Abel’s identity [1],[2] can be proved in many ways, including the elegant combinatorial methods of [3]. Here we present the first computer-generated proof using the methods introduced in [4].

Theorem([1]; [2], p.128). For n ≥ 0:

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

Proof. Let F_{n,k}(r, s) and a_{n}(r, s) denote, respectively, the summand and sum on the LHS of (1), 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.

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}, (1) follows. □

We thank Herb Wilf for a great shrinking comment on an earlier (much longer) version.

References

1. N. Abel, Beweis eines Ausdruckes, von welchem die Binomial-Formel ein einzelner Fall ist, Crelle’s J. Mathematik (1826), 159-60.

2. Louis Comtet, Advanced Combinatorics, D. Reidel Publ. Co., Dordrecht/Boston, 1974, p. 128.

3. D. Foata, Enumerating k-Trees, Disc. Math. (1971), 181-186.

4. J. Majewicz, WZ-type certification procedures and Sister Celine’s technique for Abel-type sums,, to appear (also available via anonymous ftp to ftp.math.temple.edu in directory pub/jmaj ).

Department of Mathematics, Temple University, Philadelphia, PA 19122

E-mail address: ekhad@math.temple.edu, jmaj@euclid.math.temple.edu

Typeset by AMS-TEX