A NON-AUTOMATIC (!) APPLICATION OF GOSPER’S ALGORITHM

EVALUATES A DETERMINANT FROM TILING ENUMERATION

M. Ciucu and C. Krattenthaler^{†}

Department of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA

                        e-mail: ciucu@math.gatech.edu
                  WWW: http://www.math.gatech.edu/~ciucu

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Ap.Univie.Ac.At

              WWW: http://www.mat.univie.ac.at/People/kratt

Abstract. We evaluate the determinant det_{1≤i,j≤n} (\binom{x+y+j}{x−i+2j} − \binom{x+y+j}{x+i+2j}), which gives the number of lozenge tilings of a hexagon with cut off corners. A particularly interesting feature of this evaluation is that it requires the proof of a certain hypergeometric identity which we accomplish by using Gosper’s algorithm in a non-automatic fashion.

The purpose of this paper is to provide a direct evaluation of the determinant

det_{1≤i,j≤n} (\binom{x + y + j}{x − i + 2j} − \binom{x + y + j}{x + i + 2j}) .  (1)

This determinant arises in our study [4] on the enumeration of lozenge tilings of hexagons with cut off corners. For example, consider a hexagon with side lengths x + n, n, y, x + n, n, y (in cyclic order) and angles of 120^{∘} of which two adjacent corners are cut off as in Figure 1(a).^{1} Figure 1(b) shows a lozenge tiling of this region, by which we mean a tiling

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A16 05A17 05A19 05B45 33C20 52C20.

Key words and phrases. rhombus tilings, lozenge tilings, plane partitions, nonintersecting lattice paths, determinant evaluations, hypergeometric series, Gosper’s algorithm.

†Partially supported by the Austrian Science Foundation FWF, grant P13190-MAT.

1To be precise, from the top-left corner we cut off a (reversed) staircase of the form (y − 1, y − 2, …, 1), meaning that the cut-off staircase consists of y − 1 rhombi in the first row, y − 2 rhombi in the second row, etc., and from the top-right corner we cut off a staircase of the form (n − 1, n − 2, …, 1).

Typeset by AMS-TEX

by unit rhombi with angles of 60^{∘} and 120^{∘}, referred to as lozenges. The number of these lozenge tilings is given by the determinant (1). This is seen by converting the lozenge tilings into families (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths consisting of positive unit steps, where the path P_{i} runs from (i, −i) to (x + 2i, y − i), i = 1, 2, …, n and does not cross the diagonal y = x − 1 (see Figure 2), and then applying the main theorem of nonintersecting lattice paths [18, Lemma 1], [8], [23, Theorem 1.2] (see [4] for details and background; there is also another case in [4] in which the determinant (1) provides the solution).

x + n x + n y  y n n {  } } { {  }

(a) A hexagon with cut off corners.

(b) A lozenge tiling of the hexagon with cut off corners.

Figure 1

By Theorem 1 below, the number of the lozenge tilings of the preceding paragraph is

(a) The path family corresponding to a lozenge tiling.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

(b) The paths made orthogonal.

Figure 2

given by a closed form expression. The proof of Theorem 1 that we present in this paper^{2} is primarily based on hypergeometric series identities. A remarkable aspect is that it contains an instance of a non-automatic application of Gosper’s algorithm [9] (see also [10, §5.7], [20, §II.5]), see Step 3 of the proof of Theorem 1. This is noteworthy, because Gosper invented his algorithm to automate summation, so that a non-automatic application must be almost considered as a misuse. But clearly (and more seriously), the fact that Gosper’s algorithm is also useful in “computer-free territory” only adds to its value. (The only other instance of a non-automatic application of Gosper’s algorithm that we are aware of appears in [19]. However, the purpose of use there is different. Roughly speaking, we use it to prove a positive result, namely to verify the truth of an identity between certain hypergeometric series, see (14). In contrast, Petkovšek and Wilf use it to prove a negative result, namely that a certain binomial sum cannot be expressed in terms of closed form expressions.)

2An alternative proof is presented in [4], in which a combinatorial argument is used to convert the determinant (1) into a different determinant that was already known from [12, Theorem 10].

Theorem 1. Let n be a positive integer, and let x and y be nonnegative integers. Then the following determinant evaluation holds:

det_{1≤i,j≤n} (\binom{x + y + j}{x − i + 2j} − \binom{x + y + j}{x + i + 2j})

= ∏_{j=1}^{n} \frac{(j − 1)! (x + y + 2j)! (x − y + 2j + 1)_{j} (x + 2y + 3j + 1)_{n−j}}{(x + n + 2j)! (y + n − j)!} , (2)

where the shifted factorial (a)_{k} is defined by (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, and (a)_{0} := 1.

Remark. We formulate Theorem 1 only for integral x and y. But in fact, with a generalized definition of factorials and binomials (cf. [10, §5.5, (5.96), (5.100)], Theorem 1 would also make sense and be true for complex x and y.

Proof. We prove the determinant evaluation by “identification of factors,” a method that is also applied successfully in [2], [3], [5], [6], [7], [11], [12], [13], [14], [16], [17] and [21] (see in particular the tutorial description in [15, §2.4] or [13, §2]).

First of all, we take appropriate factors out of the determinant. To be precise, we take (x + y + j)!/((x + n + 2j)! (y + n − j)!) out of the j-th column of the determinant in (2), j = 1, 2, …, n. Thus we obtain

∏_{i=1}^{n} \frac{(x + y + j)!}{(x + n + 2j)! (y + n − j)!}

× det_{1≤i,j≤n} ((x + 2j − i + 1)_{n+i} (y + i − j + 1)_{n−i} − (x + 2j + i + 1)_{n−i} (y − i − j + 1)_{n+i}) (3)

for the determinant in (2). Let us denote the determinant in (3) by D_{n}(x, y). Comparison of (2) and (3) yields that (2) will be proved once we are able to establish the determinant evaluation

D_{n}(x, y)

= det_{1≤i,j≤n} ((x + 2j − i + 1)_{n+i} (y + i − j + 1)_{n−i} − (x + 2j + i + 1)_{n−i} (y − i − j + 1)_{n+i})

= ∏_{j=1}^{n} (j − 1)! (x + y + j + 1)_{j} (x − y + 2j + 1)_{j} (x + 2y + 3j + 1)_{n−j}. (4)

For the proof of (4) we proceed in several steps. An outline is as follows. In the first step we show that ∏_{j=1}^{n}(x − y + 2j + 1)_{j} is a factor of D_{n}(x, y) as a polynomial in x and y. In the second step we show that ∏_{j=1}^{n}(x + y + j + 1)_{j} is a factor of D_{n}(x, y), and in the third step we show that ∏_{j=1}^{n}(x + 2y + 3j + 1)_{n−j} is a factor of D_{n}(x, y). Then, in the fourth step we determine the maximal degree of D_{n}(x, y) as a polynomial in x, and the maximal degree as a polynomial in y, which turns out to be n(3n + 1)/2 in both cases. On the other hand, the degree in x, and also in y, of the product on the right hand side of (4), which by the first three steps divides D_{n}(x, y), is exactly n(3n + 1)/2. Therefore we are forced to conclude that

D_{n}(x, y) = C(n) ∏_{j=1}^{n} (x − y + 2j + 1)_{j} (x + y + j + 1)_{j} (x + 2y + 3j + 1)_{n−j},  (5)

where C(n) is a constant independent of x and y. Finally, in the fifth step, we determine the constant C(n), which turns out to equal ∏_{j=1}^{n}(j − 1)!. Clearly, this would finish the proof of (4), and thus of (2), as we already noted.

Step 1. ∏_{j=1}^{n}(x − y + 2j + 1)_{j} is a factor of D_{n}(x, y). Let us concentrate on a typical factor (x − y + 2j + l), 1 ≤ j ≤ n, 1 ≤ l ≤ j. We claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 1 ≤ j ≤ n, 1 ≤ l ≤ j there holds

\begin{matrix}⌊ & \frac{j+l}{2} & ⌋ \\ ∑ \\ s=l \end{matrix} \frac{(j − l)}{(j − s)} \frac{(j + l − 2s + 1)_{s−l}}{(s − l)!} \frac{(x + 2j + l + n − s + 1)_{s−l} (x + n + 2s + 1)_{j+l−2s}}{(2x + 2j + l + s + 1)_{j−s}}
· (column s of D_{n}(x, x + 2j + l))

+ (column j of D_{n}(x, x + 2j + l)) = 0. (6)

To avoid confusion, for j = l it is understood by convention that the sum in (6) vanishes. In order to verify (6), we have to check

\begin{matrix}⌊ & \frac{j+l}{2} & ⌋ \\ ∑ \\ s=l \end{matrix} \frac{(j − l)}{(j − s)} \frac{(j + l − 2s + 1)_{s−l}}{(s − l)!} \frac{(x + 2j + l + n − s + 1)_{s−l} (x + n + 2s + 1)_{j+l−2s}}{(2x + 2j + l + s + 1)_{j−s}}

· ((x + i + 2j + l − s + 1)_{n−i} (x − i + 2s + 1)_{n+i}

− (x − i + 2j + l − s + 1)_{n+i} (x + i + 2s + 1)_{n−i})
+ (x − i + 2j + 1)_{n+i} (x + i + j + l + 1)_{n−i}

− (x + i + 2j + 1)_{n−i} (x − i + j + l + 1)_{n+i} = 0, (7)

which is (6) restricted to the i-th row. The exceptional case j = l can be treated immediately. By assumption, the sum in (7) vanishes for j = l, and, by inspection, also the other two expressions in (7) vanish for j = l. So it remains to establish (7) for j > l. In terms of the standard hypergeometric notation

rF_{s}[ \begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix}; z] = ∑_{k=0}^{∞} \frac{(a_{1})_{k} ⋯ (a_{r})_{k}}{k! (b_{1})_{k} ⋯ (b_{s})_{k}} z^{k} ,

this means to check

\frac{(x + i + 2j + 1)_{n−i} (x − i + 2l + 1)_{n+i+j−l}}{(2x + 2j + 2l + 1)_{j−l}}

×_{4}F_{3}[ \begin{matrix}\frac{−j}{2} + \frac{l}{2}, \frac{1}{2} − \frac{j}{2} + \frac{l}{2}, −i − 2j − x, 1 + 2j + 2l + 2x \\ 1 − j + l, \frac{1}{2} − \frac{i}{2} + l + \frac{x}{2}, 1 − \frac{i}{2} + l + \frac{x}{2} \end{matrix} ; 1]

− \frac{(x − i + 2j + 1)_{n+i} (x + i + 2l + 1)_{−i+j−l+n}}{(2x + 2j + 2l + 1)_{j−l}}

×_{4}F_{3}[ \begin{matrix}\frac{−j}{2} + \frac{l}{2}, \frac{1}{2} − \frac{j}{2} + \frac{l}{2}, i − 2j − x, 1 + 2j + 2l + 2x \\ 1 − j + l, \frac{1}{2} + \frac{i}{2} + l + \frac{x}{2}, 1 + \frac{i}{2} + l + \frac{x}{2} \end{matrix} ; 1]

+ (x − i + 2j + 1)_{n+i} (x + i + j + l + 1)_{n−i}

− (x + i + 2j + 1)_{n−i} (x − i + j + l + 1)_{n+i} = 0. (8)

Both _{4}F_{3}-series can be summed by means of a _{4}F_{3}-summation which appears in a paper by Andrews and Burge [1, Lemma 1] (see [12, Lemma A3] for a simpler proof),

4F_{3}[ \begin{matrix}−\frac{N}{2} , \frac{1}{2} − \frac{N}{2} , −a, a + b \\ 1 − N, \frac{b}{2}, \frac{1}{2} + \frac{b}{2} \end{matrix} ; 1] = \frac{(a + b)_{N}}{(b)_{N}} + \frac{(−a)_{N}}{(b)_{N}} ,

where N is a positive integer. We have to apply the case where N = j − l. This is indeed a positive integer because of our assumption j > l. Some simplification then leads to (8).

This shows that ∏_{j=1}^{n}(x − y + 2j + 1)_{j} divides D_{n}(x, y).

Step 2. ∏_{j=1}^{n}(x + y + j + 1)_{j} is a factor of D_{n}(x, y). Let us concentrate on a typical factor (x + y + j + l), 1 ≤ j ≤ n, 1 ≤ l ≤ j. We claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 1 ≤ j ≤ n, 1 ≤ l ≤ j there holds

∑_{s=1+j−l}^{j} (−\frac{1}{4})^{j−s} \binom{l − 1}{s + l − j − 1}

· \frac{(x + n + 2s + 1)_{2j−2s} (2x + 3j + l + s + 1)_{j−s}}{(x + j + s + \frac{1}{2})_{j−s} (x + j + l + s)_{j−s} (x + j + l − n + s)_{j−s}}

· (column s of D_{n}(x, −x − j − l)) = 0. (9)

In order to verify (9), we have to check

∑_{s=1+j−l}^{j} (−\frac{1}{4})^{j−s} \binom{l − 1}{s + l − j − 1}

· \frac{(x + n + 2s + 1)_{2j−2s} (2x + 3j + l + s + 1)_{j−s}}{(x + j + s + \frac{1}{2})_{j−s} (x + j + l + s)_{j−s} (x + j + l − n + s)_{j−s}}

· ((−x + i − j − l − s + 1)_{n−i} (x − i + 2s + 1)_{n+i}

− (−x − i − j − l − s + 1)_{n+i} (x + i + 2s + 1)_{n−i}) = 0, which is (9) restricted to the i-th row. Equivalently, using hypergeometric notation, this means to check

(−1)^{l} \frac{(−i − 2j − x)_{n+i} (3 + i + 2j − 2l + x)_{−2−i+2l+n} (2 + 4j + 2x)_{l−1}}{4^{l−1}(1 + 2j + x)_{l−1} (\frac{3}{2} + 2j − l + x)_{l−1} (1 + 2j − n + x)_{l−1}}

×_{4}F_{3}[ \begin{matrix}1 − l, \frac{3}{2} + 2j − l + x, 1 + 2j + x, 1 + i + 2j + x \\ 2 + 4j + 2x, 2 + \frac{i}{2} + j − l + \frac{x}{2}, \frac{3}{2} + \frac{i}{2} + j − l + \frac{x}{2} \end{matrix} ; 1]

− (−1)^{l} \frac{(i − 2j − x)_{n−i} (3 − i + 2j − 2l + x)_{−2+i+2l+n} (2 + 4j + 2x)_{l−1}}{4^{l−1}(1 + 2j + x)_{l−1} (\frac{3}{2} + 2j − l + x)_{l−1} (1 + 2j − n + x)_{l−1}}

×_{4}F_{3}[ \begin{matrix}\frac{3}{2} + 2j − l + x, 1 + 2j + x, 1 − i + 2j + x, 1 − l \\ \frac{3}{2} − \frac{i}{2} + j − l + \frac{x}{2}, 2 − \frac{i}{2} + j − l + \frac{x}{2}, 2 + 4j + 2x \end{matrix}; 1] = 0. (10)

In order to establish (10) we apply Bailey’s transformation for balanced _{4}F_{3}-series (see [22, (4.3.5.1)]),

4F_{3}[ \begin{matrix}a, b, c, −N \\ e, f, 1 + a + b + c − e − f − N \end{matrix} ; 1]

= \frac{(e − a)_{N} (f − a)_{N}}{(e)_{N} (f)_{N}} _{4}F_{3}[ \begin{matrix}−N, a, 1 + a + c − e − f − N, 1 + a + b − e − f − N \\ 1 + a + b + c − e − f − N, 1 + a − e − N, 1 + a − f − N \end{matrix} ; 1] ,

where N is a nonnegative integer, to the second _{4}F_{3}-series in (10). Thus it is converted into the first _{4}F_{3}-series, and it is routine to check that also the remaining terms that go with the _{4}F_{3}-series agree. So, the two terms on the left hand side of (10) cancel each other, as desired.

This establishes that ∏_{j=1}^{n}(x + y + j + 1)_{j} divides D_{n}(x, y).

Step 3. ∏_{i=1}^{n}(x + 2y + 3i + 1)_{n−i} is a factor of D_{n}(x, y). This is the most difficult part of the proof of (4). Trials of finding linear combinations of columns that vanish resulted in extremely messy expressions. So, we decided to work with linear combinations of rows this time. Still, the coefficients are not as “nice” as in Steps 1 and 2.

Let us concentrate on a typical factor (x + 2y + 3i + l), 1 ≤ i ≤ n, 1 ≤ l ≤ n − i. We claim that for each such factor there is a linear combination of the rows that vanishes if the factor vanishes. More precisely, we claim that for any i, l with 1 ≤ i ≤ n, 1 ≤ l ≤ n − i there holds

∑_{k=1}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) · (row k of D_{n}(−2y − 3i − l, y)) = 0,  (11)

where P_{l}(e, f) is the polynomial

P_{l}(e, f) = ∑_{r=0}^{2l+1} a_{r} (e)_{r} (−f)_{2l+1−r},  (12)

with the expansion coefficients a_{r} given by

a_{r} = ⟨x^{r}⟩ ((x^{2} + x + 1)^{l−1}(2x + 1)(x + 2)(x − 1)).  (13)

Here, ⟨x^{r}⟩g(x) denotes the coefficient of x^{r} in g(x).

By specializing (11) to the j-th column, splitting the resulting sum into two parts in the obvious way, and then moving one sum to the right hand side, we see that in order to verify (11), we have to check

∑_{k=1}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j − k + 1)_{n+k} (y + k − j + 1)_{n−k}

= ∑_{k=1}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j + k + 1)_{n−k} (y − k − j + 1)_{n+k},

or, after adding one more term as first summand on both sides, equivalently,

∑_{k=0}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j − k + 1)_{n+k} (y + k − j + 1)_{n−k}

= ∑_{k=0}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j + k + 1)_{n−k} (y − k − j + 1)_{n+k}. (14)

Empirically, we discovered that apparently both sums in (14) are indefinitely summable (“Gosper-summable”; see [10, §5.7], [20, §II.5]). It is exactly this fact which makes (14) tractable.

In the following we will show that the sums in (14) are equal, however, without exhibiting an explicit expression for the sums. Instead, what we will do is to read through Gosper’s algorithm [9] (see also [10, §5.7], [20, §II.5]), which is an algorithm that solves the problem of indefinite summation for hypergeometric sums. (For any fixed l, our sums in (14) belong to the category of hypergeometric sums.) In the course of reading through Gosper’s algorithm it will emerge that the sums on both sides of (14) must be equal.

Let us recall what Gosper’s algorithm does and how it works. Let t(k) be a “hypergeometric term”, i.e., be a term such that the ratio t(k + 1)/t(k) is a rational function in k. Then the Gosper algorithm will find a hypergeometric term T (k) (if it exists) satisfying

t(k) = T (k + 1) − T (k).  (15)

The upshot of this is that then the indefinite summation of the term t(k) can be easily carried out,

∑_{k=A}^{B} t(k) = T (B + 1) − T (A).  (16)

The term T (k) is found in the following way. First, one finds polynomials p(k), q(k), and r(k) such that

\frac{t(k + 1)}{t(k)} = \frac{p(k + 1)}{p(k)} \frac{q(k)}{r(k + 1)},  (17)

where q(k) and r(k) have the property that whenever (k + α) | q(k) and (k + β) | r(k) then the difference α − β must not be a positive integer. Next, one finds a polynomial s(k) satisfying the recurrence relation

p(k) = q(k)s(k + 1) − r(k)s(k)  (18)

for all k. The term T (k) is then given by

T (k) = \frac{r(k) s(k)}{p(k)}t(k).  (19)

Now let us carry out this program with the summands in (14). First, let t(k) = t_{1}(k), where t_{1}(k) is the summand of the sum on the left hand side of (14),

t_{1}(k) = \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j − k + 1)_{n+k} (y + k − j + 1)_{n−k}.

Then (17) holds with p(k) = p_{1}(k), q(k) = q_{1}(k), r(k) = r_{1}(k), where p_{1}(k) = P_{l}(2i, i+l−k), q_{1}(k) = (i + l − k)(−2y − 3i − l + 2j − k), and r_{1}(k) = (i + l + k)(y − j + k). So, next we have to find a polynomial s_{1}(k) satisfying the recurrence

P_{l}(2i, i + l − k) = (i + l − k)(−2y − 3i − l + 2j − k)s_{1}(k + 1) − (i + l + k)(y − j + k)s_{1}(k). (20)

For each specific instance of i and l this is just routine. However, we were not able to find an explicit formula for s_{1}(k) in general. Fortunately, we do not need such an explicit expression. Assuming that we have found a polynomial s_{1}(k) satisfying (20), by (16) and (19) we have

∑_{k=0}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j − k + 1)_{n+k} (y + k − j + 1)_{n−k}

= \frac{r_{1}(i + l + 1) s_{1}(i + l + 1)}{p_{1}(i + l + 1)}t_{1}(i + l + 1) − \frac{r_{1}(0) s_{1}(0)}{p_{1}(0)}t_{1}(0)

= −\frac{(i + l)_{i+l+1}}{(i + l)!} (−2y − 3i − l + 2j + 1)_{n} (y − j)_{n+1} s_{1}(0),  (21)

the last line being due to the fact that t_{1}(i + l + 1) = 0.

On the other hand, for t(k) = t_{2}(k), where t_{2}(k) is the summand of the sum on the right hand side of (14),

t_{2}(k) = \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j + k + 1)_{n−k} (y − k − j + 1)_{n+k},

we may choose p(k) = p_{2}(k), q(k) = q_{2}(k), r(k) = r_{2}(k), where p_{2}(k) = P_{l}(2i, i + l − k), q_{2}(k) = (i + l − k)(y − j − k), and r_{2}(k) = (i + l + k)(−2y − 3i − l + 2j + k). So, here we have to find a polynomial s_{2}(k) satisfying the recurrence

P_{l}(2i, i + l − k) = (i + l − k)(y − j − k)s_{2}(k + 1) − (i + l + k)(−2y − 3i − l + 2j + k)s_{2}(k). (22)

Again, this is just routine for each specific instance of i and l, but we do not know an explicit formula for s_{2}(k) in general. Assuming that we have found a polynomial s_{2}(k) satisfying (22), by (16) and (19) we have

∑_{k=0}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j + k + 1)_{n−k} (y − k − j + 1)_{n+k}

= \frac{r_{2}(i + l + 1) s_{2}(i + l + 1)}{p_{2}(i + l + 1)}t_{2}(i + l + 1) − \frac{r_{2}(0) s_{2}(0)}{p_{2}(0)}t_{2}(0)

= −\frac{(i + l)_{i+l+1}}{(i + l)!} (−2y − 3i − l + 2j)_{n+1} (y − j + 1)_{n} s_{2}(0),  (23)

the last line being due to the fact that also t_{2}(i + l + 1) = 0.

In order to relate s_{2}(k) to s_{1}(k), we make the following observation: We set s_{2}(k) = s̃_{2}(−k + 1), substitute this in the recurrence (22), then replace k by −k and change the sign on both sides of (22). Thus we obtain for s̃_{2}(k) the recurrence

−P_{l}(2i, i+l+k) = (i+l−k)(−2y −3i−l+2j −k)s̃_{2}(k +1)−(i+l+k)(y −j +k)s̃_{2}(k). (24)

This is almost the same recurrence as the recurrence (20) for s_{1}(k)! It is only the term on the left hand side which is different! But, in fact, there is no difference: We claim that:

Claim 1: We have P_{l}(e, e + 2l − f) = −P_{l}(e, f).

Claim 2: There exists a unique solution for the recurrence (20). Let us for the moment assume that these claims have been already established. Then, because of Claim 1, the recurrences (20) and (24) are indeed the same. Furthermore, thanks to Claim 2, there does exist a unique solution for the recurrence (20), and so also for (24). Hence, the solutions must be the same, i.e., s_{1}(k) = s̃_{2}(k), which means s_{1}(k) = s_{2}(1 − k). In particular, we have s_{1}(1) = s_{2}(0). A further fact, which follows immediately from Claim 1 on replacing e by 2e and setting f = e + l, is that P_{l}(2e, e + l) = 0. Therefore, by setting k = 0 in (20), we obtain

0 = (i + l)(−2y − 3i − l + 2j)s_{1}(1) − (i + l)(y − j)s_{1}(0).

From this equation, and the previous observation that s_{1}(1) = s_{2}(0), we infer

s_{1}(0) = \frac{(−2y − 3i − l + 2j)}{(y − j)}s_{1}(1) = \frac{(−2y − 3i − l + 2j)}{(y − j)}s_{2}(0).

Substitution of this relation in (21) gives

∑_{k=0}^{i+l} \frac{(k + i + l + 1)_{i+l−k}}{(i + l − k)!} P_{l}(2i, i + l − k) (−2y − 3i − l + 2j − k + 1)_{n+k} (y + k − j + 1)_{n−k}

= −\frac{(i + l)_{i+l+1}}{(i + l)!} (−2y − 3i − l + 2j)_{n+1} (y − j + 1)_{n} s_{2}(0).

Comparison of this identity with (23) shows that indeed the sums on both sides of (14) are identical. This would prove (14).

So it remains to settle Claims 1 and 2.

We begin with Claim 1. By the definition (12) of P_{l}(e, f), we have

P_{l}(e, e + 2l − f) = ∑_{r=0}^{2l+1} a_{r} (e)_{r} (−e − 2l + f)_{2l+1−r}

= ∑_{r=0}^{2l+1} a_{r} (e)_{r} (−1)^{r+1} (e + r − f)_{2l+1−r},

where the coefficients a_{r} are given by (13). Next we use the Chu–Vandermonde summation (see e.g. [10, §5.1, (5.27)]) in the form

∑_{s=0}^{N} \binom{N}{s}(x)_{s} (y)_{N−s} = (x + y)_{N},

with N = 2l + 1 − r, x = e + r, and y = −f. Thus,

P_{l}(e, e + 2l − f) = ∑_{r=0}^{2l+1} a_{r} (e)_{r} (−1)^{r+1} ∑_{s=0}^{2l+1−r} \binom{2l + 1 − r}{s}(e + r)_{s} (−f)_{2l+1−r−s}

= − ∑_{m=0}^{2l+1}(e)_{m} (−f)_{2l+1−m} ∑_{r=0}^{m} \binom{2l + 1 − r}{m − r}(−1)^{r}a_{r}.

Therefore, Claim 1 will follow immediately, if we are able to show that

∑_{r=0}^{m} \binom{2l + 1 − r}{m − r}(−1)^{r}a_{r} = a_{m}.  (25)

This can be readily done by using generating functions. The definition (13) of the coefficients a_{r} is equivalent to

∑_{r=0}^{∞} a_{r}x^{r} = (x^{2} + x + 1)^{l−1}(2x + 1)(x + 2)(x − 1).  (26)

Let us denote the right hand side of this equation by A(x). Now we multiply both sides of (25) by x^{m}, and we sum over all m = 0, 1, … We obtain

∑_{m=0}^{∞} ∑_{r=0}^{m} \binom{2l + 1 − r}{m − r}(−1)^{r}a_{r} = A(x),

and after interchanging summations on the left hand side and summing the (now) inner sum over m by means of the binomial theorem,

(1 + x)^{2l+1}A (−\frac{x}{1 + x}) = A(x).

It is trivial to verify this equation. Thus also the equivalent equation (25) must be true. Due to the preceding considerations, this completes the proof of Claim 1.

Next we turn to Claim 2. We show that there is a unique polynomial s_{1}(k) of degree 2l that satisfies the recurrence (20). (We leave it as an exercise that the “degree calculus” of the Gosper algorithm shows that if there is a solution to the recurrence (20) then it has to be a polynomial of degree at most 2l.) So, let s_{1}(k) = ∑_{m=0}^{2l} c(m)(k −i−l)_{m}. We substitute this into (20), then expand everything with respect to the basis (k − i − l)_{m}, m = 0, 1, … (for the space of polynomials in k), and finally compare coefficients of (k − i − l)_{m} on both sides of (20). This leads to the following system of equations for the coefficients c(m):

a_{2l+1−m}(2i)_{2l+1−m} = (y + i − l − j + m − 1) c(m − 1) − (2i + 2l − m)(y + i + l − j − m) c(m), m = 0, 1, …, 2l + 1, (27)

where, by convention, we put c(−1) = c(2l + 1) = 0. For convenience, we set

c(m) = (2i)_{2l−m} (y + i − l − j)_{2l−m} (y + i − l − j)_{m} c̃(m).

By substituting this in (27), we obtain the simpler system of equations

\frac{a_{m}}{(y + i − l − j)_{2l−m+1} (y + i − l − j)_{m}} = c̃(m − 1) − c̃(m),  m = 0, 1, …, 2l + 1. (28)

This is a system of 2l + 2 equations for 2l + 1 variables. (Recall the convention c(−1) = c(2l + 1) = 0, which of course implies c̃(−1) = c̃(2l + 1) = 0.) So, it is overdetermined. It is easy to see that this inhomogeneous system of linear equations has a (unique) solution if and only if the sum of the left hand sides of (28) over all m equals 0, i.e., if and only if

∑_{m=0}^{2l+1} \frac{a_{m}}{(y + i − l − j)_{2l−m+1} (y + i − l − j)_{m}} = 0.  (29)

This would follow immediately from the antisymmetry property a_{m} = −a_{2l+1−m}, because then the m-th and (2l + 1 − m)-th summand in the sum in (29) would cancel each other. Indeed, the substitution x → 1/x in (26) yields a_{m} = −a_{2l+1−m}. Therefore, the system of equations (27) has indeed a unique solution, which implies that there is a unique polynomial s_{1}(k) satisfying the recurrence (20), which is exactly the assertion of Claim 2.

The proof that ∏_{i=1}^{n}(x + 2y + 3i + 1)_{n−i} divides D_{n}(x, y) is now complete.

Step 4. D_{n}(x, y) is a polynomial in x of maximal degree n(3n+1)/2, and the same is true for the maximal degree of D_{n}(x, y) in y. This is because each term in the defining expansion of the determinant D_{n}(x, y) has degree n(3n + 1)/2 in x, and the same in y. Since the right hand side of (4), which by Steps 1–3 divides D_{n}(x, y) as a polynomial in x and y, also has degree n(3n + 1)/2 in x, respectively y, D_{n}(x, y) and the right hand side of (4) differ only by a multiplicative constant.

Step 5. The evaluation of the multiplicative constant. By the preceding steps we know that (5) holds. In particular, if we set y = 0, we have

det_{1≤i,j≤n} ((x + 2j − i + 1)_{n+i} (i − j + 1)_{n−i}) = C(n) ∏_{j=1}^{n} (x + j + 1)_{n+j}.  (30)

(The reader should be aware that the second term in the determinant D_{n}(x, y), as given by (4), vanishes for y = 0 because of the presence of the factor (y − i − j + 1)_{n+i}.) The determinant on the left hand side of (30) is a lower triangular matrix, hence it equals the product of its diagonal entries, which is ∏_{j=1}^{n}(x+j +1)_{n+j} (n−j)!. Therefore C(n) is equal to ∏_{j=1}^{n}(n − j)! = ∏_{j=1}^{n}(j − 1)!.

This finishes the proof of (4) and thus of the Theorem. □

Acknowledgement. We are grateful to the referee for a simplification of our original proof of (25).

References

1. G. E. Andrews and W. H. Burge, Determinant identities, Pacific J. Math. 158 (1993), 1–14.

2. M. Ciucu, T. Eisenkölbl, C. Krattenthaler and D. Zare, Enumeration of lozenge tilings of hexagons with a central triangular hole, J. Combin. Theory Ser. A 95 (2001), 251–334.

3. M. Ciucu and C. Krattenthaler, The number of centered lozenge tilings of a symmetric hexagon, J. Combin. Theory Ser. A 86 (1999), 103–126.

4. M. Ciucu and C. Krattenthaler, Enumeration of lozenge tilings of hexagons with cut off corners, J. Combin. Theory Ser. A (to appear).

5. T. Eisenkölbl, Rhombus tilings of a hexagon with two triangles missing on the symmetry axis, Electron. J. Combin. 6 (1) (1999), #R30, 19 pp.

6. M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, I, Ann. Combin. 2 (1998), 19–40.

7. M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, II, Europ. J. Combin. 21 (2000), 601–640.

8. I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300—321.

9. R. W. Gosper, Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75 (1978), 40–42.

10. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

11. C. Krattenthaler, Some q-analogues of determinant identities which arose in plane partition enumeration, Séminaire Lotharingien Combin. 36 (1996), paper B36e, 23 pp.

12. C. Krattenthaler, Determinant identities and a generalization of the number of totally symmetric selfcomplementary plane partitions, Elect. J. Combin. 4(1) (1997), #R27, 62 pp.

13. C. Krattenthaler, An alternative evaluation of the Andrews–Burge determinant, Mathematical Essays in Honor of Gian-Carlo Rota (B. E. Sagan, R. P. Stanley, eds.), Progress in Math., vol. 161, Birkhäuser, Boston, 1998, pp. 263–270.

14. C. Krattenthaler, A new proof of the M–R–R conjecture — including a generalization, J. Difference Equ. Appl. 5 (1999), 335–351.

15. C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (“The Andrews Festschrift”) (1999), paper B42q, 66 pp.

16. C. Krattenthaler and D. Zeilberger, Proof of a determinant evaluation conjectured by Bombieri, Hunt and van der Poorten, New York J. Math. 3 (1997), 54–102.

17. G. Kuperberg, Another proof of the alternating sign matrix conjecture, Int. Math. Res. Notices 3 (1996), 139–150.

18. B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

19. M. Petkovšek and H. S. Wilf, When can the sum of (1/p)th of the binomial coefficients have closed form?, Electron. J. Combin. 4 (no. 2, “The Wilf Festschrift”) (1997), #R21, 7 pp.

20. M. Petkovšek, H. Wilf and D. Zeilberger, A=B, A.K. Peters, Wellesley, 1996.

21. A. J. van der Poorten, A powerful determinant, Experimental Math. 10 (2001), 307–320.

22. L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

23. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96— 131.

Department of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.