INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A03

TWO q–IDENTITIES FROM THE THEORY OF FOUNTAINS AND HISTOGRAMS PROVED WITH A TRI–DIAGONAL DETERMINANT

Helmut Prodinger^{1}

The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics,

University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

                          helmut@maths.wits.ac.za

Received: 8/27/04, Accepted: 2/3/05, Published: 2/8/05

Abstract

Two identities required in the theory of fountains and histograms are easily proved by expanding a tri–diagonal determinant (reminiscent of Schur’s) in two different ways.

We consider the following infinite tri-diagonal determinant (elements not displayed are zero)

Schur(x) := |\begin{matrix}1 & & \overbrace{0 … 0}^{p−2} & & xq^{1} & & & & … \\ −1 & 1 & & 0 … 0 & & xq^{2} & & & … \\ & −1 & 1 & & 0 … 0 & & xq^{3} & & … \\ & & −1 & 1 & & 0 … 0 & & xq^{4} & … \\ & & & ... & ... & ... \end{matrix}| .

Schur, when providing his proof of the Rogers–Ramanujan identities in 1917 [3] used a similar determinant; since I am advocating that Schur’s work deserves to be better known, I use the name Schur(x). This short note shows that two identities that were required in the study of fountains and histograms [1] are most easily proved by expanding the determinant in two different ways.

Expanding the determinant with respect to the first column (“top–recursion”) we get

Schur(x) = Schur(xq) + (−1)^{p}xq Schur(xq^{p}).

1Dedicated to Kathy Driver for six years of loyal support.

Thanks are due to a friendly referee who pointed out some trouble with signs.

Setting

Schur(x) = ∑_{n≥0} a_{n}x^{n},

we get, upon comparing coefficients,

a_{n} = q^{n}a_{n} + (−1)^{p}q^{1+p(n−1)}a_{n−1} = \frac{(−1)^{p}q^{1+p(n−1)}}{1 − q^{n}} .

Since a_{0} = 1, iteration leads to

a_{n} = \frac{q^{n+p\binom{n}{2}}(−1)^{pn}}{(1 − q)(1 − q^{2}) … (1 − q^{n})}.

Therefore

Schur((−q)^{p−1}) = ∑_{n≥0} \frac{(−1)^{n}q^{n+p\binom{n}{2}}}{(1 − q)(1 − q^{2}) … (1 − q^{n})}q^{(p−1)n}

= ∑_{n≥0} \frac{(−1)^{n}q^{p\binom{n+1}{2}}}{(1 − q)(1 − q^{2}) … (1 − q^{n})}.

Now consider the finite determinants Schur_{n}(x), obtained from Schur(x) by taking the first n rows and columns. Expanding this determinant with respect to the last row (“bottom– recursion”) we get

Schur_{n}(x) = Schur_{n−1}(x) + (−1)^{p}xq^{n−p+1} Schur_{n−p}(x).

In particular,

Schur_{n}((−q)^{p−1}) = Schur_{n−1}((−q)^{p−1}) − q^{n} Schur_{n−p}((−q)^{p−1}),

and Schur_{j}((−q)^{p−1}) = 1 for j = 0, …, p − 1. The quantities Schur_{n}((−q)^{p−1}) were called E_{n} in [1] (with matching initial conditions E_{j} = 1 for j = 0, …, p − 1). Whence we proved

lim_{m→∞} E_{m} = ∑_{n≥0} \frac{(−1)^{n}q^{p\binom{n+1}{2}}}{(1 − q)(1 − q^{2}) … (1 − q^{n})}.

Merlini and Sprugnoli had asked for a direct proof, which was given in [2], by showing an explicit form for E_{m}. The present proof avoids this and is thus simpler.

A second (similar) formula was also requested, namely

lim_{m→∞} D_{m} = ∑_{n≥0} \frac{(−1)^{n}q^{n+p\binom{n}{2}}}{(1 − q)(1 − q^{2}) … (1 − q^{n})}.

for D_{n} = D_{n−1} − q^{n}D_{n−p} and (different) initial values D_{j} = 1 − ∑_{i=1}^{j} q^{i} for j = 0, …, p − 1. This follows immediately by setting D_{n} = Schur_{n+p−1}((−1)^{p−1}).

References

[1] D. Merlini and R. Sprugnoli, Fountains and histograms, J. Algorithms 44 (2002), no. 1, 159–176.

[2] P. Paule and H. Prodinger, Fountains, histograms, and q–identities, Discrete Mathematics and Theoretical Computer Science 6 (2003), 101–106.

[3] I. Schur. Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche. S.-B. Preuss. Akad. Wiss. Phys.-Math. Kl., 1917, 302–321, reprinted in I. Schur, Gesammelte Abhandlungen, vol. 2, pp. 117–136, Springer, 1973.