A WORDY PROOF OF A COMBINATORIAL LEMMA THAT AROSE IN OPERATOR THEORY

Doron ZEILBERGER^{1}

Albert Einstein used to be amazed how effective mathematics is in science. Myself, I am amazed how effective combinatorics is in mathematics. Especially fruitful is the ‘formal language approach’ of notre bon Maître, Marco Schützenberger, pursued so vigorously and successfully by the École Bordelaise (see [B] and references thereof).

Recently, Baillon and Bruck[BB] proved a long-standing conjecture in operator theory, by reducing it to a hypergeometric identity that they proved using the package EKHAD^{2} (accompanying the forthcoming book [PWZ],) They asked for a ‘computer-free’ proof. Such a proof was later given by Peter Paule[P]. However, the reduction of their result to the identity proved by EKHAD and Paule required considerable human effort on their part. In this note I will give a much shorter (and purely human!) proof by playing with (Motzkin^{3}) words, dear to Viennot and his disciples.

Proposition([BB]): Let c(m, n) be defined by c(m + 1, m) = 0, (m ≥ 0), c(0, n) = 1, (n ≥ 0), and for 1 ≤ m ≤ n, by the recurrence

c(m, n) = μc(m − 1, n) + μc(m, n − 1) + (1 − 2μ)c(m − 1, n − 1) ,

then the generating function of the ‘diagonal’,

ψ(t) := ∑_{m=0}^{∞} c(m, m)t^{m} ,

is given by

ψ(t) = 1 + \frac{\sqrt{1 + \frac{4(1−μ)μt}{1−t}} − 1}{2μ} .

Proof: Consider all words w in the alphabet {N, E, D}. For any word w let y(w) be the number of Ns plus the number of Ds and let x(w) be the number of Es plus the number of Ds. Let M be the set of words w = l_{1}l_{2} … l_{r} such for any prefix w_{i} := l_{1}l_{2} … l_{i} (1 ≤ i ≤ r) one has y(w_{i}) ≥ x(w_{i}). Let M(m, n) be the subset of M for which x(w) = m and y(w) = n.

Let the weight of the letters N and E be μ, and the weight of the letter D be 1 − 2μ. Introduce two weights on the words of M. The normal weight, weight(w) is simply the product of the weights of all the letters. For example weight(NNDE) = μμ(1 − 2μ)μ = μ^{3}(1 − 2μ). The modified weight, weight′ is as before, except that the initial string of Ns is given weight 1. For example weight′(NNNDEDE) = 1^{3} · (1 − 2μ)μ(1 − 2μ)μ = (1 − 2μ)^{2}μ^{2}. Let

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg   ftp://ftp.math.temple.edu/pub/zeilberg .

Supported in part by the NSF. Aug. 2, 1995. This paper is exclusively published in the above http and ftp sites.

2 Available from the http and ftp sites given in footnote 1. Once you downloaded it into your directory, get into Maple,

and type: read EKHAD;, and follow the instructions given there 3 It is interesting that often political leaders begat combinatorialists. Theodore Motzkin is the son of the Zionist leader

Leo Motzkin (that has a town in Israel named after him, where, incidentally, I grew up). Other examples (of the sons) are Michel Mendès-France, Robin Wilson and Eri Jabotinsky.

C(m, n) := ∑_{w∈M(m, n)} weight′(w) .

Since, for n ≥ m > 0, we have M(m, n)=M(m − 1, n)E ∪ M(m, n − 1)N ∪ M(m − 1, n − 1)D, and M(m + 1, m) is the empty set, while M(0, n) consists of the single word N^{n}, taking weight′, we see that c(m, n) = C(m, n).

Let \overline{M} be the set of all words w in M such that x(w) = y(w), in other words (sic!), the set of all words in M with as many Ns as Es. Let W EIGHT (w) := t^{x(w)}weight(w), and W EIGHT′(w) := t^{x(w)}weight′(w). Since the ‘syntax’ of \overline{M} is given by:

\overline{M} = \{empty word\} ∪ D \overline{M} ∪ N \overline{M} E \overline{M} ,

taking W EIGHT and W EIGHT′ respectively yields that ϕ(t) := ∑_{w∈\overline{M}} W EIGHT (w) and ψ(t) := ∑_{w∈\overline{M}} W EIGHT′(w) satisfy the equations

ϕ(t) = 1 + t(1 − 2μ)ϕ(t) + μ^{2}tϕ(t)^{2} ,
ψ(t) = 1 + t(1 − 2μ)ϕ(t) + μtψ(t)ϕ(t) .

Now use the second equation to express ϕ(t) in terms of ψ(t), plug into the first equation, clear denominators, and solve the resulting quadratic equation in ψ(t), getting the expression for ψ(t) claimed in the proposition.

Remark: For their application, Baillon and Bruck were only interested in the asymptotics of c(m, m), which is just as easily derived from the expression in the proposition above (which is Th. 5.5 in [BB]) as from their integral representation (Th. 6.1 there). However, one can easily prove (albeit using EKHAD’s services) that these are equivalent, by typing (in EKHAD):

AZpapd(sqrt(1+4*mu*(1-mu)*t/(1-t))/t**(m+2),t,m);
and AZpapd(sqrt(t/(1-t))*(1-4*mu*(1-mu)*t)**m,t,m);

References

[BB] J.-B. Baillon and R.E. Bruck, The rate of Asymptotic Regularity is O(1/\sqrt{n}), preprint. Avail-

able from bruck@mtha.usc.edu.

[B] M. Bousquet-Mélou, “q-Énumération de polyominos convexes”, Publications de LACIM, UQAM, Montréal, 1991.

[P] P. Paule, available from peter.paule@risc.uni-linz.ac.at.

[PWZ] M. Petkovsek, H.S. Wilf, and D.Zeilberger, “A=B”, A.K.Peters, to appear.