Proof of an Identity of Don Knuth

Doron ZEILBERGER^{1}

Don Knuth, in a letter to Richard Stanley, Cc-d to several people, asked whether anybody has seen the following identity before:

∑_{0≤x_{1},...,x_{n}≤1} \frac{(z − x_{1}z^{n+1})(z^{2} − x_{2}z^{n+1}) … (z^{n} − x_{n}z^{n+1})z^{−nx_{1}−(n−1)x_{2}−···−x_{n}}}{(x_{1} + 1)(x_{1}x_{2} + x_{2} + 1) … (x_{1} … x_{n} + ⋯ + x_{n} + 1)}

= \frac{(1 − z)(1 − z^{2}) … (1 − z^{n+1})}{(n + 1)! (1 − z)^{n+1}}.

I have not. Here is a proof.

I will prove the more general identity:

A(n, r) := ∑_{0≤x_{1},...,x_{n}≤1} \frac{(z − x_{1}z^{n+1})(z^{2} − x_{2}z^{n+1}) … (z^{n} − x_{n}z^{n+1})z^{−nx_{1}−(n−1)x_{2}−···−x_{n}}}{(rx_{1} + 1)(rx_{1}x_{2} + x_{2} + 1) … (rx_{1} … x_{n} + x_{2} … x_{n} + ⋯ + x_{n} + 1)}

= \frac{(1 − z)(1 − z^{2}) … (1 − z^{n})}{(1 − z)^{n+1}} · ∑_{l=1}^{n+1} \frac{z^{n−l+1}(1 − z)^{l}r!}{(r + l − 1)!(n − l + 1)!}.

(∗)

The original identity follows by plugging r = 1 and using the Binomial Theorem: (z +(1−z))^{n+1} − z^{n+1} = 1 − z^{n+1}.

To prove the identity for A(n, r), split the sum according to whether x_{1} = 0 or x_{1} = 1 to get the recurrence:

A(n, r) = z^{n}A(n − 1, 1) + \frac{(1 − z^{n})}{r + 1}A(n − 1, r + 1) .

Since A(0, r) = 1, and the expression on the right of (∗) obviously also satisfies this recurrence, we are done.

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 .

Sept. 19, 1995.