A DETERMINANT EVALUATION CONJECTURED BY ROLAND BACHER

C. KRATTENTHALER^{†}

Abstract. We evaluate the determinant of a matrix the entries of which are certain binomial sums. This proves a conjecture of Roland Bacher.

Roland Bacher [private communication] made the following conjecture. Conjecture. For all non-negative integers n, we have

det_{0≤i,j≤n−1} (∑_{k≥0} \binom{2i}{k}\binom{2j}{k}2^{k}) = 2^{n^{2}−n} ∏_{i=0}^{n−1} \frac{i!^{2} (4i)!}{(2i)!^{3}}.

We shall in fact prove the following theorem. Theorem. For all non-negative integers n and s with s ≤ n, we have

det_{0≤i,j≤n−1} (∑_{k≥0} \binom{2(i + χ(i ≥ s))}{k}\binom{2j}{k}2^{k})

= 2^{n^{2}−n} \frac{(4s + 1)}{(2n + 2s + 1)}\binom{n}{s}\frac{(n + s + \frac{1}{2})_{n−s}}{(s + \frac{1}{2})_{n−s}} ∏_{i=0}^{n−1} \frac{i!^{2} (4i)!}{(2i)!^{3}}, (1)

where χ(S) = 1 if S is true and χ(S) = 0 otherwise.

Clearly, the above conjecture is the special case s = n of this theorem.

Proof of the theorem. The proof follows the basic set-up in [2], except that we do not make use of recurrences.

The determinants on the left-hand side of (1) are — up to sign — co-factors of the matrix

M_{n} = (∑_{k≥0} \binom{2i}{k}\binom{2j}{k}2^{k})_{0≤i,j≤n} .

More precisely, they are — again, up to sign — the co-factors where the last column and some row of M_{n} is omitted. Let C_{s} denote the determinant of the matrix which arises from M_{n} by deleting the last column and the s-th row, s = 0, 1, …, n. According to basic principles of linear algebra, the C_{s}’s satisfy the obvious equations

∑_{s=0}^{n}(−1)^{s}(M_{n})_{s,j} · X_{s} = 0,  j = 0, 1, …, n − 1,  (2)

2000 Mathematics Subject Classification. Primary 15A15; Secondary 05A10 33C05.

Key words and phrases. Binomial determinant, hypergeometric series.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

with X_{s} = C_{s}. The above equations determine the X_{s}’s up to some common multiplicative constant (provided that the matrix M_{n} is non-singular, which will turn out to be true as a by-product of this proof.). They will be uniquely determined if we fix one of the X_{s}’s to a particular value, say, if we fix X_{n} to be the determinant of the matrix arising from M_{n} by deleting the last column and the last row, or, in other words, we fix X_{n} = det M_{n−1}. In that case, the above system of linear equations forces X_{s} to be equal to C_{s}, s = 0, 1, …, n − 1.

In summary, we can turn the above observations into an inductive proof of the Theorem by establishing (2) with X_{s} = C_{s}, s = 0, 1, …, n, and

∑_{s=0}^{n}(−1)^{s+n}(M_{n})_{s,n} · C_{s} = 2^{n^{2}+n} ∏_{i=0}^{n} \frac{i!^{2} (4i)!}{(2i)!^{3}}.  (3)

(The reader should observe that the right-hand side of (3) is the claimed value of det M_{n}.)

We now calculate the sum on the left-hand sides of (2) and (3), for j = 0, 1, …, n. We have

∑_{s=0}^{n}(−1)^{s+j}(M_{n})_{s,j} · C_{s}

= 2^{n^{2}−n} ∏_{i=0}^{n−1} \frac{i!^{2} (4i)!}{(2i)!^{3}} ∑_{s=0}^{n}(−1)^{s+j} ∑_{k=0}^{2s} \binom{2s}{k}\binom{2j}{k}2^{k} \frac{(4s + 1)}{(2n + 2s + 1)}\binom{n}{s}\frac{(n + s + \frac{1}{2})_{n−s}}{(s + \frac{1}{2})_{n−s}} .

Substitution of the right-hand side in (2) and (3) shows that, what we have to prove is

∑_{s=0}^{n}(−1)^{s+j} ∑_{k=0}^{2s} \binom{2s}{k}\binom{2j}{k}2^{k} \frac{(4s + 1)}{(2n + 2s + 1)}\binom{n}{s}\frac{(n + s + \frac{1}{2})_{n−s}}{(s + \frac{1}{2})_{n−s}}

= δ_{j,n}2^{2n} \frac{n!^{2} (4n)!}{(2n)!^{3}}. (4)

where δ_{j,n} is the usual Kronecker delta.

In order to proceed, we rewrite the sum over k has a contour integral,

∑_{k=0}^{2s} \binom{2s}{k}\binom{2j}{k}2^{k} = \frac{1}{2πi} ∫_{C}(1 + z)^{2s}(z + 2)^{2j} \frac{dz}{z^{2j+1}} ,

where C is a small contour encircling the origin once in positive direction. We substitute this on the left-hand side of (4), and we write the sum over s in hypergeometric notation. Thus, we obtain

(−1)^{j} \frac{(n + \frac{1}{2})_{n}}{(2n + 1) (\frac{1}{2})_{n}} \frac{1}{2πi} ∫_{C}(z + 2)^{2j}_{3}F_{2}[\begin{matrix}\frac{5}{4}, \frac{1}{2}, −n \\ \frac{1}{4}, n + \frac{3}{2} \end{matrix}; (z + 1)^{2}] \frac{dz}{z^{2j+1}}  (5)

for the left-hand side of (4). We now apply the contiguous relation

3F_{2}[\begin{matrix}a, b, c \\ d, e \end{matrix}; x] = _{3}F_{2}[\begin{matrix}a − 1, b, c \\ d, e \end{matrix}; x] + \frac{xbc}{de}_{3}F_{2}[\begin{matrix}a, b + 1, c + 1 \\ d + 1, e + 1 \end{matrix}; x]

with a = 5/4, b = 1/2, c = −n, d = 1/4, e = n + \frac{3}{2}, x = (z + 1)^{2}. This leads to the expression

(−1)^{j} \frac{(n + \frac{1}{2})_{n}}{(2n + 1) (\frac{1}{2})_{n}} \frac{1}{2πi} ∫_{C}(z + 2)^{2j}(_{2}F_{1}[\begin{matrix}\frac{1}{2}, −n \\ n + \frac{3}{2} \end{matrix}; (z + 1)^{2}]

− \frac{4n(z + 1)^{2}}{2n + 3}_{2}F_{1}[\begin{matrix}\frac{3}{2}, −n + 1 \\ n + \frac{5}{2} \end{matrix}; (z + 1)^{2}])\frac{dz}{z^{2j+1}}

Next, we apply the transformation formula (see [1, (1.8.10), terminating form])

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

where N is a nonnegative integer, to both _{2}F_{1}-series. This yields the expression

(−1)^{j} \frac{(n + 1)_{n}}{(4n + 1) (\frac{1}{2})_{n}} \frac{1}{2πi} ∫_{C}(z + 2)^{2j}(_{2}F_{1}[\begin{matrix}\frac{1}{2}, −n \\ −2n \end{matrix}; −z(z + 2)]

− (1 + z(z + 2))_{2}F_{1}[\begin{matrix}\frac{3}{2}, −n + 1 \\ −2n + 1 \end{matrix}; −z(z + 2)])\frac{dz}{z^{2j+1}} ,

or, if we expand the hypergeometric series and evaluate the contour integrals,

(−1)^{j} \frac{4^{n}}{(4n + 1)}(∑_{ℓ=0}^{n}(−1)^{ℓ} \frac{(\frac{1}{2})_{ℓ} (−n)_{ℓ}}{(−2n)_{ℓ} ℓ!} \binom{2j + ℓ}{2j − ℓ}2^{2ℓ}

− ∑_{ℓ=0}^{n−1}(−1)^{ℓ} \frac{(\frac{3}{2})_{ℓ} (−n + 1)_{ℓ}}{(−2n + 1)_{ℓ} ℓ!} \binom{2j + ℓ}{2j − ℓ}2^{2ℓ} − ∑_{ℓ=0}^{n−1}(−1)^{ℓ} \frac{(\frac{3}{2})_{ℓ} (−n + 1)_{ℓ}}{(−2n + 1)_{ℓ} ℓ!} \binom{2j + ℓ + 1}{2j − ℓ − 1}2^{2ℓ+2}).

We replace ℓ by ℓ − 1 in the last sum, and then we put everything together into one sum over ℓ. After some simplification, we arrive at

(−1)^{j+1}4^{n} ∑_{ℓ=1}^{n}(−1)^{ℓ} \frac{(\frac{3}{2})_{ℓ−1} (−n + 1)_{ℓ−1}}{(1 − 2n)_{ℓ} (ℓ − 1)!} \binom{2j + ℓ}{2j − ℓ}2^{2ℓ−2}.

We write the sum in hypergeometric notation and obtain

(−1)^{j+1}4^{n} \frac{2j(2j + 1)}{2(2n − 1)}_{3}F_{2}[\begin{matrix}−2j + 1, 2j + 2, −n + 1 \\ 2, −2n + 2 \end{matrix}; 1] .  (6)

This _{3}F_{2}-series can be evaluated by means of Watson’s _{3}F_{2}-summation formula (see [1, (2.3.3.13); Appendix (III.23)])

3F_{2}[\begin{matrix}a, b, c \\ \frac{a}{2} + \frac{b}{2} + \frac{1}{2}, 2c \end{matrix}; 1] = \frac{Γ(\frac{1}{2}) Γ(c + \frac{1}{2}) Γ(\frac{a}{2} + \frac{b}{2} + \frac{1}{2}) Γ(c − \frac{a}{2} − \frac{b}{2} + \frac{1}{2})}{Γ(\frac{a}{2} + \frac{1}{2}) Γ(\frac{b}{2} + \frac{1}{2}) Γ(c − \frac{a}{2} + \frac{1}{2}) Γ(c − \frac{b}{2} + \frac{1}{2})}.  (7)

Care must however be taken when applying this formula to our series since direct application of the formula leads to singularities. Instead of (6), let us consider

(−1)^{j+1}4^{n} \frac{2j(2j + 1)}{2(2n − 1)} lim_{ε→0}_{3}F_{2}[\begin{matrix}−2j − 2ε + 1, 2j + 2ε + 2, −n + ε + 1 \\ 2, −2n + ε + 2 \end{matrix}; 1] .

Now we may apply (7), which transforms the above expression into

(−1)^{j+1}4^{n} \frac{2j(2j + 1)}{2(2n − 1)}

× lim_{ε→0} \frac{Γ(\frac{1}{2}) Γ(−n + ε + \frac{3}{2}) Γ(−n + ε)}{Γ(−j − ε + 1) Γ(j + ε + \frac{3}{2}) Γ(−n + j + 2ε + 1) Γ(−n − j + \frac{1}{2})}. (8)

Here, the critical terms are Γ(−n + ε), Γ(−j − ε + 1), Γ(−n + j + 2ε + 1), which tend to infinity for ε → 0, the last one only if j < n. Consequently, if j < n, the limit in (8) obviously vanishes, whence (4) is indeed true in this case.

It remains to consider the case j = n. Since we have

lim_{ε→0} \frac{Γ(−n + ε)}{Γ(−n − ε + 1)} = \frac{1}{n},

the expression (8) reduces to

(−1)^{n+1}4^{n} \frac{(2n + 1)}{(2n − 1)} \frac{Γ(\frac{1}{2}) Γ(−n + \frac{3}{2})}{Γ(n + \frac{3}{2}) Γ(−2n + \frac{1}{2})}.

Further rewriting converts this into

4^{n} \frac{n!^{2} (4n)!}{(2n)!^{3}},

which is again in accordance with (4). This completes the proof of the theorem. □

Remark. Roland Bacher has a similar conjecture for the determinant

det_{0≤i,j≤n−1} (∑_{k≥0} \binom{2i}{k}\binom{2j}{k}4^{k}) .

To find a proof appears to be harder than in the case of the conjecture proved here.

References

[1] L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

[2] D. Zeilberger, The holonomic Ansatz II. Automatic discovery(!) and proof(!!) of holonomic determinant evaluations, Ann. Combin. 11 (2007), 241–247.

Fakultät für Mathematik, Universität Wien, Nordbergstrasze 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.