Five surprisingly simple complexities

Volker Strehl and Herbert S. Wilf*

We describe five fairly formidable looking expressions that turn out to be rather simple. They are furthermore connected by a chain of implications.

I. A determinant that is easier than it seems to be

This identity is attributed by Muir [3] to Mena [4]. See also Fel’dman [2], and van der Poorten [3], whose title we heartily second. The identity states that

(I)  det {(D^{i−1}f(x)^{j−1})_{i,j=1}^{n}} = c_{n}f′(x)^{n(n−1)/2},

where D = d/dx and c_{n} = 1!2! ⋯ (n − 1)!. Note that although all derivatives of f up to the (n−1)^{st} appear on the left, only the first derivative survives on the right. For example,

det ( \begin{matrix}1 & f & f^{2} & f^{3} \\ 0 & f′ & 2ff′ & 3f^{2}f′ \\ 0 & f′′ & 2ff′′ + 2(f′)^{2} & 6f(f′)^{2} + 3f^{2}f′′ \\ 0 & f^{(3)} & 6f′f′′ + 2ff^{(3)} & 6(f′)^{3} + 18ff′f′′ + 3f^{2}f^{(3)} \end{matrix} ) = 12(f′)^{6}.

II. A generalization

In the course of trying to prove (1) we tried to work out an inductive proof, by expansion across the last row. To do this, some numerical experiments with Mathematica suggested that it might be true that

(II)  det \{(D^{i−1}f(x)^{a_{j}})_{i,j=1}^{n}\} = \{ ∏_{1≤i<j≤n}(a_{j} − a_{i})\}(\frac{f′(x)}{f(x)})^{\binom{n}{2}}f(x)^{a_{1}+···+a_{n}},

where the a_{j}’s are any numbers. This more general identity does indeed support an inductive proof across the last row of the matrix. It shares with (I) the property of seeming to involve many derivatives of f, but in fact involving just f and f′.

III. One that doesn’t have any determinants in it

In the course of proving (II) yet another pretty identity surfaced, one which seems not to have any relation to determinants, namely

(III)  (\frac{f′(x)}{f(x)})^{n−1} = ∑_{j=1}^{n} \frac{(D^{n−1}f(x)^{a_{j}})}{f(x)^{a_{j}}} ∏_{{1≤i≤n \atop i≠j}}(a_{j} − a_{i})^{−1}.

* Supported in part by the U. S. Office of Naval Research Again notice that all sorts of derivatives of f appear on the right, but only f, f′ are on the left.

IV. A simple polynomial disguised as a complicated rational function

Finally, the proof of (III) is easy once one has the result that what seems to be a rational function on the left side of the equation that follows is, for each fixed k, actually a polynomial:

(IV)  ∑_{j=1}^{n} \frac{a_{j}^{k}}{∏′_{i}(a_{j} − a_{i})} = \{ \begin{matrix}0, & if k = 0, 1, …, n − 2; \\ 1, & if k = n − 1; \\ h_{k−n+1}(a_{1}, …, a_{n}), & if k ≥ n, \end{matrix}

where the product extends over 1 ≤ i ≤ n, i ≠ j, and h_{r}(a) is the symmetric polynomial

h_{r}(a_{1}, …, a_{n}) = ∑_{{i_{1}+···+in=r \atop i_{1},...,in≥0}} a_{1}^{i_{1}} ⋯ a_{n}^{i_{n}}.  (1)

We are now going to prove that (IV) ⇒ (III) ⇒ (II) ⇒ (I), and then state some of their further consequences.

Proof of (IV)

Define c_{k} to be the quantity on the left side of (IV). The generating function of the {c_{k}} is clearly

∑_{k≥0} \frac{c_{k}}{t^{k}} = ∑_{j=1}^{n} \frac{t}{(t − a_{j}) ∏′_{i}(a_{j} − a_{i})}.

On the other hand, the generating function of the sequence {h_{r−n+1}(a)}_{r≥0} of (1) is, equally clearly,

∑_{r≥0} \frac{h_{r−n+1}(a)}{t^{r}} = \frac{t}{(t − a_{1})(t − a_{2}) ⋯ (t − a_{n})}.

If we equate these, we see that what we have to prove is that the Lagrange interpolating polynomial exactly represents the polynomial which is everywhere equal to 1, which it does.

Proof of (III)

First write e^{f(x)} in place of f(x) throughout. Then we have to show that

f′(x)^{n−1} = ∑_{j=1}^{n} δ_{j}e^{−a_{j}f}D^{n−1}e^{a_{j}f},  (2)

where δ_{j} is the product in (III). But

e^{−af}D^{n−1}e^{af} = ∑_{p} a^{k(p)} ∏_{r}(f^{(r)})^{m_{r}(p)},  (3)

in which the sum runs over all partitions p of the set {1, …, n − 1}, m_{r}(p) is the number of blocks of size r in the partition p, and k(p) is the total number of blocks in p.

The coefficient of a fixed monomial (f′)^{m_{1}}(f′′)^{m_{2}} ⋯ on the right side of (2), after using (3), is

ψ(n − 1, m) ∑_{j=1}^{n} a_{j}^{k}δ_{j}  (4)

where ψ is the number of partitions whose class size multiplicity vector is m, and k = ∑ m_{i}. By (IV) this coefficient vanishes for k < n − 1 and is 1 when k = n − 1.

Proof of (II)

If we expand the determinant on the left side of (II) along its bottom (nth) row, we obtain a sum of n determinants, each being again of the form on the left side of (II) in which one of the a_{j}’s is missing. Precisely, the left side of (II) is equal to

∑_{j=1}^{n}(D^{n−1}f(x)^{a_{j}})(−1)^{n−j} ∏_{{1≤r<s≤n \atop r,s≠j}}(a_{s} − a_{r})(\frac{f′}{f} )^{\binom{n−1}{2}}f^{a_{1}+···+a_{n}−a_{j}}.

To show that this is equal to the right side of (II), divide it by the right side of (II), and notice that what remains to prove, after the obvious cancellation, is the identity (III), which is already proved.

Of course, (I) is the special case of (II) in which a_{j} = j for all j = 1, …, n.

We mention some consequences of these general identities.

The special case of (III) in which a_{j} = q^{j} and f(x) = x^{t} yields the following interesting q-identity, which is valid for integer n ≥ 0, and complex q, t:

∑_{j}(−1)^{j}q^{(j+1)(j−2n)/2}\binom{tq^{j+1}}{n}\binom{n}{j}_{q} = \frac{t^{n}}{n!} ∏_{j=1}^{n}(1 − q^{j}),  (5)

in which, as usual, \binom{n}{j}_{q} = (n!)_{q}/(j!_{q}(n − j)!_{q}) and (m!)_{q} = ∏_{j=1}^{m}(1 − q^{j})/(1 − q).

The case a_{j} = 1/j, f(x) = x^{t} of (III) gives

∑_{j=1}^{n+1}(−1)^{j−1}j^{n}\binom{n + 1}{j}\binom{t/j}{n} = \frac{t^{n}}{n!} .

Finally, with a_{j} = j^{2} and f(x) = x^{t} in (III) we obtain an identity of unusual form, viz.

∑_{j=1}^{n}(−1)^{n−j}j^{2}\binom{2n}{n + j}\binom{tj^{2}}{n − 1} = \frac{(2n)!}{2(n − 1)!}t^{n−1}.

The fifth one: An identity of Milne

We now look back at (III) and (IV) from a more general point of view. For that purpose, it is convenient to introduce a bit of notation. Let us define, for any vector a = (a_{1}, …, a_{n}) of variables and any polynomial p = p(x), the determinant

V (a | p) := det ( \begin{matrix}1 & … & 1 \\ a_{1} & … & a_{n} \\ a_{1}^{2} & … & a_{n}^{2} \\ ⋮ & & ⋮ \\ a_{1}^{n−2} & … & a_{n}^{n−2} \\ p(a_{1}) & … & p(a_{n}) \end{matrix} ) ,

so that V (a | x^{n−1}) is the familiar Vandermonde determinant

V (a | x^{n−1}) = ∏_{1≤i<j≤n}(a_{j} − a_{i}) .

V (a | p) is an antisymmetric polynomial in the a_{1}, …, a_{n}, hence divisible by V (a | x^{n−1}). The quotient of the two “alternants” (in classical terminology)

\frac{V (a | p)}{V (a | x^{n−1})} = ∑_{j=1}^{n} \frac{p(a_{j})}{∏′_{i} (a_{j} − a_{i})}  (6)

is a symmetric polynomial in a_{1}, …, a_{n}, and we see from (IV) that V (a|x^{k}) is the complete symmetric function h_{k−n+1}(a_{1}, …, a_{n}) for k ≥ 0, where h_{n} ≡ 0 for n < 0 and h_{0} ≡ 1. This is, in fact, a particular case of Jacobi’s way of expressing Schur functions as determinants involving the complete symmetric functions (see e.g. Eq. 3.4 on p. 25 of [5]). The cases 0 ≤ k ≤ n in (IV) are, of course, immediate from the determinantal expression in (6).

From (6) we get (III) as follows: for any differentiable function F (z), define

p_{m}(x) := e^{−x F (z)}D_{z}^{m}e^{x F (z)} ,

which is a polynomial of degree m in x with leading coefficient c_{m} = F′(z)^{m}. Now

∑_{1≤j≤n} \frac{p_{n−1}(a_{j})}{∏′_{i}(a_{j} − a_{i})} = \frac{V (a | p_{n−1})}{V (a | x^{n−1})} = \frac{V (a | c_{n−1}x^{n−1})}{V (a | x^{n−1})} = c_{n−1} = F′(z)^{n−1} ,

which is (III) if we put f(z) = e^{F (z)}.

A remarkable property of (III) is the fact that its left hand side does not at all depend on the a_{i}. This phenomenon can be observed in similar situations which can be treated by using (IV). As a particularly interesting example we mention an identity due to and extensively studied by S. Milne in [6]. Let x_{1}, x_{2}, …, x_{n} be another set of variables. Then

1 − x_{1}x_{2} ⋯ x_{n} = ∑_{j=1}^{n}(1 − x_{j})∏_{i}′ (\frac{a_{j} − x_{i}a_{i}}{a_{j} − a_{i}} ) .  (7)

Various proofs by various people have been reproduced in Sec. 8 of [6]. Here is another, very short proof of this identity.

We observe that the right hand side of (7) can be written as

∑_{j=1}^{n} \frac{g(a_{j})}{∏′_{i} (a_{j} − a_{i})} ,

with

g(z) := \frac{∏_{i=1}^{n}(z − x_{i}a_{i})}{z} = g_{0}(z) + (−1)^{n} \frac{∏_{i=1}^{n} x_{i}a_{i}}{z} ,

where g_{0}(z) is a monic polynomial in z of degree n − 1. Note that, by slightly extending the notation introduced above,

V (a | x^{−1}) = \frac{(−1)^{n−1}}{a_{1}a_{2} ⋯ a_{n}} V (a | x^{n−1}) ,

and hence

∑_{j=1}^{n} \frac{g(a_{j})}{∏′_{i} (a_{j} − a_{i})} = \frac{V (a | g(z))}{V (a | z^{n−1})}

= \frac{V (a | g_{0}(z))}{V (a | z^{n−1})} + (−1)^{n} ∏_{i=1}^{n} x_{i}a_{i} · \frac{V (a | z^{−1})}{V (a | z^{n−1})}

= 1 − x_{1}x_{2} ⋯ x_{n} .

An unsolved problem

The passage from the identity (I) to the generalization (II) replaces the special sequence {0, 1, 2, …, n − 1} of powers of f(x) by the general sequence {a_{1}, a_{2}, …, a_{n}}. Can anything useful be said if we also replace the special sequence {0, 1, 2, …, n − 1} of powers of the differential operator D, in (II), by a general sequence {b_{1}, b_{2}, …, b_{n}}?

References

1. N. I. Fel’dman, Approximation of certain transcendental numbers, II: The approximation of certain numbers associated with the Weierstrass function, Izv. Akad. Nauk. SSSR Ser. Mat. 15, 153-176; Amer. Math. Soc. Translations Ser. 2 1959, 246-270.

2. T. Muir, Contributions to the history of determinants 1900-1920, Blackie, London 1930, p. 279.

3. A. J. van der Poorten, Some determinants that should be better known, J. Austral. Math. Soc. 21 (Series A) (1976), 278-288.

4. L. Mina, Formole generali delle derivate successive d’una funzione espresse mediante quelle della sua inverse, Giornale di Mat. xliii (1904), 196-212.

5. I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford, 1979.

6. S. C. Milne, A q-analog of the Gauss summation theorem for hypergeometric series in U(n), Adv. in Math. 72, no.1 (1988), 59-131.

University of Erlangen-Nürnberg, D-91058 Erlangen. Germany University of Pennsylvania, Philadephia, PA 19104-6395