Hankel determinants of linear combinations

of moments of orthogonal polynomials

J. Cigler and C. Krattenthaler^{†}

Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

             WWW: http://homepage.univie.ac.at/johann.cigler
                 WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We prove evaluations of Hankel determinants of linear combinations of moments of orthogonal polynomials (or, equivalently, of generating functions for Motzkin paths), thus generalising known results for Catalan numbers.

1. Introduction. Let C_{n} = \frac{1}{n+1} \binom{2n}{n} denote the n-th Catalan number, and let (F_{n})_{n≥0} be the sequence of Fibonacci numbers defined by F_{n} = F_{n−1} + F_{n−2} with initial values F_{0} = 0 and F_{1} = 1.

In [6], Cvetković, Rajković and Ivković proved the Hankel determinant evaluations

det (C_{i+j} + C_{i+j+1})_{i,j=0}^{n−1} = F_{2n+1}  (1.1)

and

det (C_{i+j+1} + C_{i+j+2})_{i,j=0}^{n−1} = F_{2n+2}.  (1.2)

In [7], Dougherty, French, Saderholm and Qian proved a result of similar flavour, namely

det (C_{i+j} + 2C_{i+j+1} + C_{i+j+2})_{i,j=0}^{n−1} = ∑_{j=0}^{n} F_{2j+1}^{2}.  (1.3)

One finds variations and generalisations of these identities at numerous places in the literature, for example in [2, 3, 5, 6, 7, 8, 9, 18, 21].

2010 Mathematics Subject Classification. Primary 05A19; Secondary 05A10 05A15 11C20 15A15 33C45 42C05.

Key words and phrases. Hankel determinants, moments of orthogonal polynomials, Catalan numbers, Motzkin numbers, Fibonacci numbers, Lucas numbers, Schröder numbers, Riordan numbers, Fine numbers, central binomial coefficients, central trinomial numbers, Chebyshev polynomials, Rogers–Szegő polynomials, Dyck paths, Motzkin paths, non-intersecting lattice paths.

†Research partially supported by the Austrian Science Foundation FWF (grant S50-N15) in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

Very recently, the first author became aware of

\frac{det (\binom{2i+2j+2}{i+j+1} + 2\binom{2i+2j+4}{i+j+2} + \binom{2i+2j+6}{i+j+3})_{i,j=0}^{n−1}}{2^{n}} = ∑_{j=0}^{n} L_{2j+1}^{2},  (1.4)

where L_{n} denotes the n-th Lucas number, defined by the Fibonacci recurrence L_{n} = L_{n−1} +L_{n−2} with initial values L_{0} = 2 and L_{1} = 1. This formula was posted without proof by a mathematical amateur, Tony Foster, in a Facebook group about Pascal’s triangle.

We decided to search for the general background of this kind of Hankel determinant evaluations. Our main result in Theorem 1 in the next section provides a formula for the evaluation of Hankel determinants of a linear combination of three generating functions for Motzkin paths. In these generating functions, the weight of a path depends on its steps. In that section, in Corollary 2, we then record separately the corresponding result for Dyck paths. Indeed, by appropriate specialisations, all the above identities as well as many more, in the literature or not, can be obtained, see Sections 3 and 4. One result that is of particular note is Corollary 3, which gives a closed form evaluation, in terms of Chebyshev polynomials, of Hankel determinants as in Theorem 1 for the special case where weights of steps do not depend on their height, except if they are at height zero.

We provide two different proofs for Theorem 1 and Corollary 2, both of which are of interest as we believe. The proofs in Section 5 are based on the decomposition of the matrices of which we want to compute the determinant into the product of “easier to handle” matrices. In particular, the proof of Corollary 2 in that section shows that it indeed follows from our main theorem, Theorem 1, although this is not completely obvious from the outset. On the other hand, in Section 6, we present combinatorial proofs that make use of the combinatorics of non-intersecting lattice paths. Once the setup is explained, the proofs themselves then consist of just one picture in each case. We point out that the basic idea has appeared before in [17, paragraph after Theorem 29 and paragraph above Theorem 30] and [2] but has not been fully exploited there.

Finally, in Section 7 we consider the Hankel determinants of linear combinations of four path generating functions. Indeed, the combinatorial model from Section 6 can be readily extended to yield a corresponding formula, see Theorem 5. We also derive the extension of Corollary 3 for the specialisation where the step weights do not depend on the height of the steps (except if they are at height zero), see Corollary 6. By a perusal of Corollaries 3 and 6, a pattern emerges. On this basis, we make a conjecture on the evaluation of the Hankel determinant of an arbitrarily long linear combination of path generating functions in the case of the aforementioned specialisation, see Conjecture 8.

2. The main theorem and a corollary. Let (s_{n})_{n≥0} and (t_{n})_{n≥0} be sequences of real numbers with t_{n} ≠ 0 for all n, and define polynomials (in α and the s_{i}’s and t_{i}’s) f_{n}(α) by the recursion

f_{n}(α) = (α + s_{n−1})f_{n−1}(α) − t_{n−2}f_{n−2}(α),  (2.1)

with f_{0}(α) = 1 and f_{−1}(α) = 0.

Consider now Motzkin paths, i.e., lattice paths on the two-dimensional integer lattice ℤ^{2} with up-steps (x, y) → (x + 1, y + 1), horizontal steps (x, y) → (x + 1, y), and down-steps (x, y) → (x + 1, y − 1), which start at (0, 0) and never run below the x-axis.^{1} The weight of such a path is the product of the weights of its steps, where the weight of an up-step is 1, the weight of a horizontal step on height h is s_{h}, and the weight of a down-step which ends on height h is t_{h}.

Let m(n, k) denote the sum of the weights of all such paths with end point (n, k). Then we have

m(n, k) = m(n − 1, k − 1) + s_{k}m(n − 1, k) + t_{k}m(n − 1, k + 1),  (2.2)

with m(0, k) = [k = 0] and m(n, k) = 0 for k < 0, where the Iverson bracket [A] is defined by [A] = 1 if A is true and [A] = 0 otherwise. In order to explain the title of the paper: it is well known (see e.g. [16, Theorems 11–13]) that the polynomials p_{n}(x) defined recursively by

p_{n}(x) = (x − s_{n−1})p_{n−1}(x) − t_{n−2}p_{n−2}(x),  (2.3)

with initial values p_{−1}(x) = 0 and p_{0}(x) = 1 are orthogonal with respect to the linear functional L defined by L(p_{n}(x)) = [n = 0], and that their moments are L(x^{n}) = m(n, 0). (In other words: the polynomials f_{n}(α) are related to the polynomials p_{n}(α) by the replacement of s_{i} by −s_{i} for all i.) So let us write m_{n} for m(n, 0). The reader should be aware that, if we set s_{i} = t_{i} = 1 for all i, then m_{n} reduces to the classical Motzkin number M_{n} given by M_{n} = ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k} \frac{1}{k+1} \binom{2k}{k}, and f_{n}(α) becomes U_{n}((α +1)/2), where U_{n}(x) is the n-th Chebyshev polynomial of the second kind

U_{n}(x) = ∑_{k≥0}(−1)^{k}\binom{n − k}{k}(2x)^{n−2k}.  (2.4)

With these notations we are ready to state our main result about Hankel determinants of linear combinations of the path generating functions m_{n} = m(n, 0).

Theorem 1. Let α and β be indeterminates. Then, for all positive integers n, we have

\begin{matrix}det & (αβm_{i+j} + (α + β)m_{i+j+1} + m_{i+j+2}) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = ∑_{j=0}^{n} f_{j}(α)f_{j}(β) ∏_{ℓ=j}^{n−1} t_{ℓ}.  (2.5)

Remark. We should point out that it is well known (see e.g. [24, Ch. IV, Cor. 6]) that

det (m_{i+j})_{i,j=0}^{n−1} = ∏_{i=0}^{n−1} t_{i}^{n−i−1}.  (2.6)

It is worthwhile to state the analogous result for Dyck paths separately.

1We should point out that we use a slightly extended version of the notion of “Motzkin path” here.

Usually, a Motzkin path is required to return to the x-axis at the end. We do not make this requirement.

Let (T_{n})_{n≥0} be a sequence of real numbers with T_{n} ≠ 0 for all n. Define polynomials (in α and the T_{i}’s) g_{n}(α) by

g_{2n}(α) = αg_{2n−1}(α) + T_{2n−2}g_{2n−2}(α),
g_{2n+1}(α) = g_{2n}(α) + T_{2n−1}g_{2n−1}(α),  (2.7)

with g_{−1}(α) = 0 and g_{0}(α) = 1.

Consider now Dyck paths, i.e., lattice paths on the two-dimensional integer lattice ℤ^{2} with up-steps (x, y) → (x + 1, y + 1) and down-steps (x, y) → (x + 1, y − 1), which start at (0, 0) and never run below the x-axis.^{2} As before, the weight of such a path is the product of the weights of its steps. Here, the weight of an up-step is 1, and the weight of a down-step which ends on height h is T_{h}.

Let c(n, k) denote the sum of the weights of all such paths with end point (n, k). Then we have

c(n, k) = c(n − 1, k − 1) + T_{k}c(n − 1, k + 1),  (2.8)

with c(0, k) = [k = 0] and c(n, −1) = 0. Finally, set c_{n} = c(2n, 0). Here, the reader should be aware that, if we set T_{i} = 1 for all i, then c_{n} reduces to the Catalan number C_{n}. Furthermore, it can be shown that g_{2n}(α) = U_{n}((α + 2)/2) − U_{n−1}((α + 2)/2) and g_{2n+1}(α) = U_{n}((α + 2)/2), where U_{n}(x) denotes as before the n-th Chebyshev polynomial (2.4).

Corollary 2. Let α and β be indeterminates. Then, for all positive integers n, we have

\begin{matrix}det & (αβc_{i+j} + (α + β)c_{i+j+1} + c_{i+j+2}) & {n−1 \atop i,j=0} \\ det & (c_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = ∑_{j=0}^{n} T_{2j}T_{2j+1} ⋯ T_{2n−1}g_{2j}(α)g_{2j}(β), (2.9)

\begin{matrix}det & (αβc_{i+j+1} + (α + β)c_{i+j+2} + c_{i+j+3}) & {n−1 \atop i,j=0} \\ det & (c_{i+j+1}) & {n−1 \atop i,j=0} \end{matrix} = ∑_{j=0}^{n} T_{2j+1}T_{2j+2} ⋯ T_{2n}g_{2j+1}(α)g_{2j+1}(β). (2.10)

Remark. Again, we must point out that it is well known (see e.g. [17, Eqs. (5.44) and (5.45)]) that

det (c_{i+j})_{i,j=0}^{n−1} = ∏_{i=0}^{n−1}(T_{2i}T_{2i+1})^{n−i−1}.  (2.11)

and

det (c_{i+j+1})_{i,j=0}^{n−1} = ∏_{i=0}^{n−1} T_{0}(T_{2i+1}T_{2i+2})^{n−i−1}.  (2.12)

2Again, we are using a slightly extended version of the notion of “Dyck path” here, by not requiring a Dyck path to return to the x-axis at the end.

3. Immediate consequences. In this section, we state some direct implications of Theorem 1 and of Corollary 2 explicitly which result by specialising β to 0 respectively to ∞.

First, if we let β = 0 in (2.5), then we obtain

\begin{matrix}det & (αm_{i+j+1} + m_{i+j+2}) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = ∑_{j=0}^{n} f_{j}(α)f_{j}(0) ∏_{ℓ=j}^{n−1} t_{ℓ}.  (3.1)

Next we read coefficients of β^{n} on both sides of (2.5). Since each element of the matrix in the numerator on the left-hand side of which the determinant is taken is linear in β and the matrix itself is an n × n matrix, reading the coefficient of β^{n} on the left-hand side amounts to reading the coefficient of β^{1} in each element of the matrix. On the other hand, due to the recurrence (2.1), the coefficient of β^{n} in f_{j}(β) is zero as long as j < n, whereas it is 1 for f_{n}(β). Hence, we obtain

\begin{matrix}det & (αm_{i+j} + m_{i+j+1}) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = f_{n}(α).  (3.2)

Remark. The identities (3.1) and (3.2) have been given earlier by Mu, Wang and Yeh in [21, Theorem 1.3] in a different but equivalent form.

In the same way, from Corollary 2 we obtain

\begin{matrix}det & (αc_{i+j+1} + c_{i+j+2}) & {n−1 \atop i,j=0} \\ det & (c_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = ∑_{j=0}^{n} g_{2j}(α)g_{2j}(0) ∏_{ℓ=2j}^{2n−1} T_{ℓ},  (3.3)

\begin{matrix}det & (αc_{i+j+2} + c_{i+j+3}) & {n−1 \atop i,j=0} \\ det & (c_{i+j+1}) & {n−1 \atop i,j=0} \end{matrix} = ∑_{j=0}^{n} g_{2j+1}(α)g_{2j+1}(0) ∏_{ℓ=2j+1}^{2n} T_{ℓ},  (3.4)

\begin{matrix}det & (αc_{i+j} + c_{i+j+1}) & {n−1 \atop i,j=0} \\ det & (c_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = g_{2n}(α),  (3.5)

\begin{matrix}det & (αc_{i+j+1} + c_{i+j+2}) & {n−1 \atop i,j=0} \\ det & (c_{i+j+1}) & {n−1 \atop i,j=0} \end{matrix} = g_{2n+1}(α).  (3.6)

4. Specialisations. By (further) specialising α, β, the s_{i}’s and t_{i}’s, we obtain numerous Hankel determinant evaluations, covering many of those that one finds in the literature. In particular, they cover all of the evaluations that we mentioned in the introduction.

In fact, Mu, Wang and Yeh [21] provide an extensive list of specialisations of the path generating functions m_{n} = m(n, 0) that give familiar combinatorial sequences. For the convenience of the reader we reproduce it here (the codes in parentheses refer to the sequence number in The On-Line Encyclopedia of Integer Sequences [22]):

(i) Motzkin numbers M_{n}: s_{i} = t_{i} = 1 for all i (A001006).

(ii) Catalan numbers C_{n}: s_{0} = 1, s_{i} = 2 for i ≥ 1, and t_{i} = 1 for all i (A000108). (iii) shifted Catalan numbers C_{n+1}: s_{i} = 2 and t_{i} = 1 for all i. (iv) central binomial coefficients \binom{2n}{n}: s_{i} = 2 for all i, t_{0} = 2, and t_{i} = 1 for i ≥ 1

(A000984).

(v) central trinomial coefficients T_{n}: s_{i} = 1 for all i, t_{0} = 2, and t_{i} = 1 for i ≥ 1

(A002426).

(vi) central Delannoy numbers D_{n}: s_{i} = 3 for all i, t_{0} = 4, and t_{i} = 2 for i ≥ 1

(A001850).

(vii) large Schröder numbers r_{n}: s_{0} = 2, s_{i} = 3 for i ≥ 1, and t_{i} = 2 for all i (A006318). (viii) little Schröder numbers S_{n}: s_{0} = 1, s_{i} = 3 for i ≥ 1, and t_{i} = 2 for all i (A001003). (ix) Fine numbers Fine_{n}: s_{0} = 0, s_{i} = 2 for i ≥ 1, and t_{i} = 1 for all i (A000957).

(x) Riordan numbers R_{n}: s_{0} = 0, s_{i} = 1 for i ≥ 1, and t_{i} = 1 for all i (A005043). (xi) numbers of restricted hexagonal polyominoes H_{n}: s_{i} = 3 and t_{i} = 1 for all i

(A002212).

(xii) Bell numbers B_{n}: s_{i} = t_{i} = i + 1 for all i (A000110). (xiii) factorials n!: s_{i} = 2i + 1 and t_{i} = (i + 1)^{2} for all i.

We refer the reader to [1, 23] for definitions and discussion of most of these numbers, and to [13] for the hexagonal polyominoes (called polyhexes in [13]).

We add a few more specialisations:

(xiv) shifted and scaled central binomial coefficients \frac{1}{2} \binom{2n+2}{n+1}: s_{0} = 3, s_{i} = 2 for i ≥ 1,

and t_{i} = 1 for all i. (xv) odd and even central binomial coefficients \binom{n}{⌊n/2⌋}: s_{0} = 1, s_{i} = 0 for i ≥ 1, and

t_{i} = 1 for all i. (xvi) Catalan numbers interleaved with zeroes [n even]C_{n/2}: s_{i} = 0 and t_{i} = 1 for all i. (xvii) central binomial coefficients interleaved with zeroes [n even]\binom{n}{n/2}: s_{i} = 0 for all i,

t_{0} = 2, and t_{i} = 1 for i ≥ 1. (xviii) Fine numbers interleaved with zeroes [n = 0] + [n even]Fine_{n/2}: s_{i} = 0 for all i,

t_{0} = 1, and t_{i} = −1 for i ≥ 1.

Mu, Wang and Yeh note that, in most of these specialisations, s_{i} and t_{i} are constant for i ≥ 1 (namely in (i)–(xi)), and the same is true for (xiv)–(xviii). They then discuss that special case separately, find generating functions for the values of m_{n} and f_{n}(α) provided that s_{i} ≡ s and t_{i} ≡ t for i ≥ 1, but — at the time — missed to notice that the specialised polynomials f_{n}(α) can be expressed in terms of Chebyshev polynomials, and consequently did not realise that, for this specialisation, the sum on the right-hand side of (3.1) can actually be evaluated. The corresponding (missed) results are the contents of the following corollary.

Corollary 3. With the setup in Section 2, let s_{i} ≡ s and t_{i} ≡ t for i ≥ 1. Then f_{0}(α) = 1 and

f_{n}(α) = t_{0}t^{(n−2)/2}U_{n} (\frac{α+s}{2\sqrt{t}}) + ((t − t_{0})(α + s) − t(s − s_{0}))t^{(n−3)/2}U_{n−1} (\frac{α+s}{2\sqrt{t}}) (4.1)

= t^{n/2}U_{n} (\frac{α+s}{2\sqrt{t}}) − t^{(n−1)/2}(s − s_{0})U_{n−1} (\frac{α+s}{2\sqrt{t}})
+ t^{(n−2)/2}(t − t_{0})U_{n−2} (\frac{α+s}{2\sqrt{t}}) , for n ≥ 1. (4.2)

Moreover, in that case we have

\begin{matrix}det & (αβm_{i+j} + (α + β)m_{i+j+1} + m_{i+j+2}) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = \frac{Num(α, β)}{α − β},  (4.3)

where

Num(α, β) = t^{n+1/2}(U_{n+1}(x)U_{n}(y) − U_{n}(x)U_{n+1}(y))

− t^{n}(s − s_{0})(U_{n+1}(x)U_{n−1}(y) − U_{n−1}(x)U_{n+1}(y))
+ t^{n−1/2}((s − s_{0})^{2} − (t − t_{0}))(U_{n}(x)U_{n−1}(y) − U_{n−1}(x)U_{n}(y))
+ t^{n−1/2}(t − t_{0})(U_{n+1}(x)U_{n−2}(y) − U_{n−2}(x)U_{n+1}(y))
− t^{n−1}(s − s_{0})(t − t_{0})(U_{n}(x)U_{n−2}(y) − U_{n−2}(x)U_{n}(y))

+ t^{n−3/2}(t − t_{0})^{2}(U_{n−1}(x)U_{n−2}(y) − U_{n−2}(x)U_{n−1}(y)),

with x = (α + s)/(2\sqrt{t}) and y = (β + s)/(2\sqrt{t}).

Proof. The Chebyshev polynomials U_{n}(x) are defined by

U_{j}(cos θ) = \frac{sin((j + 1)θ)}{sin θ} = \frac{e^{i(j+1)θ} − e^{−i(j+1)θ}}{e^{iθ} − e^{−iθ}} .  (4.4)

In particular, they satisfy the recurrence

U_{n+1}(x) = 2xU_{n}(x) − U_{n−1}(x), for n ≥ 1,  (4.5)

with initial values U_{0}(x) = 1 and U_{1}(x) = 2x. Hence, the polynomials t^{n/2}U_{n}((α + s)/(2\sqrt{t})) satisfy the recurrence (2.1) under the given specialisations of the s_{i}’s and t_{i}’s. Thus, also the right-hand side of (4.1) satisfies (2.1). It is then routine to check that it also has the same initial values as the f_{n}(α)’s. This proves (4.1). The alternative expression (4.2) (to which we shall come back in Section 7) follows from this by an application of (4.5).

For the second claim, we use the right-most expression in (4.4) to rewrite U_{j}(x) as \frac{z^{j+1}−z^{−j−1}}{z−z^{−1}} , where z = e^{iθ} and x = cos θ. Then the evaluation of the sum on the righthand side of (2.5) amounts to an exercise in computing geometric series and rearranging terms (which one obviously performs with the help of a computer algebra programme). In the end, one arrives at the right-hand side of (4.3). □

Obviously, we can now take any of the specialisations (i)–(xi) and (xiv)–(xviii), substitute the corresponding values of s_{0}, s, t_{0}, t in (4.3), and get a Hankel determinant evaluation in which the entries are linear combinations of three consecutive members of a well-known sequence. Of course, of special interest are those cases where the evaluations of the Chebyshev polynomials in (4.3) have a closed form. In this regard, we have

U_{n}(0) = [n even](−1)^{n/2},  (4.6)

U_{n}(1/2) = \{ \begin{matrix}1, & if n ≡ 0, 1 mod 6, \\ 0, & if n ≡ 2 mod 3, \\ −1, & if n ≡ 3, 4 mod 6, \end{matrix}  (4.7)

U_{n}(1) = n + 1,  (4.8)
U_{n}(3/2) = F_{2n+2},  (4.9)
U_{n}(i/2) = i^{n}F_{n+1},  (4.10)
U_{n}(i) = i^{n}P_{n+1},  (4.11)

where P_{n} is the n-th Pell number defined by P_{n} = 2P_{n−1} + P_{n−2} with initial values P_{0} = 0 and P_{1} = 1.

(I) In order to obtain (1.1), we have to apply the specialisation (ii) in (3.2) with α = 1. In that case, we have m_{n} = C_{n} and \frac{α+s}{2\sqrt{t}} = \frac{3}{2}, and therefore f_{n}(1) = F_{2n+2} − F_{2n} = F_{2n+1} by (4.1) and (4.9).

In the same vein, to obtain (1.2) we need to apply the specialisation (iii) in (3.2) with α = 1. Here we have m_{n} = C_{n+1} and \frac{α+s}{2\sqrt{t}} = \frac{3}{2}, and therefore f_{n}(α) = F_{2n+2} by (4.1) and (4.9).

Next, in view of the above, we see that application of specialisation (ii) in (2.5) with α = β = 1 leads directly to (1.3), while specialisation (iii) produces

det (C_{i+j+1} + 2C_{i+j+2} + C_{i+j+3})_{i,j=0}^{n−1} = ∑_{j=0}^{n} F_{2j+2}^{2}.  (4.12)

On the other hand, if instead we set α = β = −1 in (2.5) then, by (4.7), we obtain

det (C_{i+j} − 2C_{i+j+1} + C_{i+j+2})_{i,j=0}^{n−1} = ∑_{j=0}^{n} (U_{j}(1/2) − U_{j−1}(1/2))^{2} = ⌊\frac{2n + 3}{3}⌋ (4.13)

and

det (C_{i+j+1} − 2C_{i+j+2} + C_{i+j+3})_{i,j=0}^{n−1} = ∑_{j=0}^{n} U_{j}^{2}(1/2) = ⌊\frac{2n + 4}{3}⌋ .  (4.14)

More generally, without specialising α and β in (2.5), we get

det (αβC_{i+j} + (α + β)C_{i+j+1} + C_{i+j+2})_{i,j=0}^{n−1}

= \frac{\begin{matrix}(U_{n+1}(x)U_{n}(y) − U_{n}(x)U_{n+1}(y) + U_{n−1}(x)U_{n+1}(y) \\ −U_{n+1}(x)U_{n−1}(y) + U_{n}(x)U_{n−1}(y) − U_{n−1}(x)U_{n}(y)) \end{matrix}}{α − β} , (4.15)

with x = (α + 2)/2 and y = (β + 2)/2, and

det (αβC_{i+j+1} + (α + β)C_{i+j+2} + C_{i+j+3})_{i,j=0}^{n−1}

= \frac{U_{n+1}((α + 2)/2)U_{n}((β + 2)/2) − U_{n}((α + 2)/2)U_{n+1}((β + 2)/2)}{α − β}. (4.16)

(II) The most straightforward specialisation, s_{i} = t_{i} = 1 for all i, summarised above in Case (i), when applied in (2.5), leads to

det (αβM_{i+j} + (α + β)M_{i+j+1} + M_{i+j+2})_{i,j=0}^{n−1} = ∑_{j=0}^{n} U_{j} (\frac{α+1}{2}) U_{j} (\frac{β+1}{2}) .  (4.17)

In particular, for α = β = 1, by (4.8) this reduces to

det (M_{i+j} + 2M_{i+j+1} + M_{i+j+2})_{i,j=0}^{n−1} = ∑_{j=0}^{n}(j + 1)^{2} = \frac{(n + 1)(n + 2)(2n + 3)}{6}. (4.18)

On the other hand, if instead we set α = β = −1, then by (4.6) we get

det (M_{i+j} − 2M_{i+j+1} + M_{i+j+2})_{i,j=0}^{n−1} = ⌊\frac{n + 2}{2}⌋ .  (4.19)

Another interesting specialisation is α = β = 2. In this case, Identity (3.2) becomes

det (2M_{i+j} + M_{i+j+1})_{i,j=0}^{n−1} = F_{2n+2},  (4.20)

and (2.5) becomes

det (4M_{i+j} + 4M_{i+j+1} + M_{i+j+2})_{i,j=0}^{n−1} = ∑_{j=0}^{n} F_{2j+2}^{2}.  (4.21)

(III) We come to determinants involving central binomial coefficients. In Case (iv) above, we have m_{n} = \binom{2n}{n} and \frac{α+s}{2\sqrt{t}} = \frac{α+2}{2}, and therefore f_{0}(1) = 1 and

f_{n}(1) = 2U_{n}(3/2) − 3U_{n−1}(3/2) = 2F_{2n+2} − 3F_{2n} = L_{2n}, for n ≥ 1 by (4.1) and (4.9). Hence, from (4.3) we obtain

\frac{det (αβ\binom{2i+2j}{i+j} + (α + β)\binom{2i+2j+2}{i+j+1} + \binom{2i+2j+4}{i+j+2})_{i,j=0}^{n−1}}{2^{n−1}}

= \frac{\begin{matrix}(U_{n+1}(x)U_{n}(y) − U_{n}(x)U_{n+1}(y) + U_{n}(x)U_{n−1}(y) − U_{n−1}(x)U_{n}(y) \\ −U_{n+1}(x)U_{n−2}(y) + U_{n−2}(x)U_{n+1}(y) + U_{n−1}(x)U_{n−2}(y) − U_{n−2}(x)U_{n−1}(y)) \end{matrix}}{α − β} , (4.22)

with x = (α + 2)/2 and y = (β + 2)/2. For α = β = 1, Identity (2.5) tells us that the above reduces to

\frac{det (\binom{2i+2j}{i+j} + 2\binom{2i+2j+2}{i+j+1} + \binom{2i+2j+4}{i+j+2})_{i,j=0}^{n−1}}{2^{n−1}} = −2 + ∑_{j=0}^{n} L_{2j}^{2}.  (4.23)

(The “correction” of −2 on the right-hand side above is caused by the “discrepancy” between f_{0}(α) = 1 and L_{0} = 2.)

In the same vein, in Case (xiv) we have m_{n} = \frac{1}{2} \binom{2n+2}{n+1} and \frac{α+s}{2\sqrt{t}} = \frac{α+2}{2}, and therefore f_{n}(1) = U_{n}(3/2) + U_{n−1}(3/2) = F_{2n+2} + F_{2n} = L_{2n+1} by (4.1) and (4.9). Hence, from (4.3) we obtain

\frac{det (αβ\binom{2i+2j+2}{i+j+1} + (α + β)\binom{2i+2j+4}{i+j+2} + \binom{2i+2j+6}{i+j+3})_{i,j=0}^{n−1}}{2^{n}}

= \frac{\begin{matrix}(U_{n+1}(x)U_{n}(y) − U_{n}(x)U_{n+1}(y) + U_{n+1}(x)U_{n−1}(y) \\ −U_{n−1}(x)U_{n+1}(y) + U_{n}(x)U_{n−1}(y) − U_{n−1}(x)U_{n}(y)) \end{matrix}}{α − β} , (4.24)

with x = (α + 2)/2 and y = (β + 2)/2. For α = β = 1, Identity (2.5) tells us that the above reduces to (1.4).

(IV) We continue with central binomial coefficients, but with even and odd central binomial coefficients, which are obtained by the choice described in Case (xv). In this case, we have m_{n} = \binom{n}{⌊n/2⌋} and \frac{α+s}{2\sqrt{t}} = \frac{α}{2}, and therefore

f_{n}(1) = U_{n}(1/2) + U_{n−1}(1/2) = \{ \begin{matrix}1, & if n ≡ 0, 2 (mod 6), \\ −1, & if n ≡ 3, 5 (mod 6), \\ 2, & if n ≡ 1 (mod 6), \\ −2, & if n ≡ 4 (mod 6), \end{matrix}

and

f_{n}(−1) = U_{n}(−1/2) + U_{n−1}(−1/2) = \{ \begin{matrix}1, & if n ≡ 0 (mod 3), \\ −1, & if n ≡ 2 (mod 3), \\ 0, & if n ≡ 1 (mod 3), \end{matrix}

by (4.1) and (4.7). Further special evaluations are f_{n}(2) = (n + 1) + n = 2n + 1 and f_{n}(3/2) = F_{2n+2} + F_{2n} = L_{2n+1}. Hence, from (4.3) we obtain

det (αβ\binom{i + j}{⌊(i + j)/2⌋} + (α + β)\binom{i + j + 1}{⌊(i + j + 1)/2⌋} + \binom{i + j + 2}{⌊(i + j + 2)/2⌋})_{i,j=0}^{n−1}

= \frac{\begin{matrix}(U_{n+1}(x)U_{n}(y) − U_{n}(x)U_{n+1}(y) + U_{n+1}(x)U_{n−1}(y) \\ −U_{n−1}(x)U_{n+1}(y) + U_{n}(x)U_{n−1}(y) − U_{n−1}(x)U_{n}(y)) \end{matrix}}{α − β} , (4.25)

with x = α/2 and y = β/2. In particular, for α = β = 1, this reduces to

det (\binom{i + j}{⌊(i + j)/2⌋} + 2\binom{i + j + 1}{⌊(i + j + 1)/2⌋} + \binom{i + j + 2}{⌊(i + j + 2)/2⌋})_{i,j=0}^{n−1}

= \{ \begin{matrix}2n + 1, & if n ≡ 0 (mod 3), \\ 2n + 3, & if n ≡ 1 (mod 3), \\ 2n + 4, & if n ≡ 2 (mod 3). \end{matrix} (4.26)

On the other hand, for α = β = −1 we get

det (\binom{i + j}{⌊(i + j)/2⌋} − 2\binom{i + j + 1}{⌊(i + j + 1)/2⌋} + \binom{i + j + 2}{⌊(i + j + 2)/2⌋})_{i,j=0}^{n−1} = ⌊\frac{2n + 3}{3}⌋ .

(4.27)

For α = 2 and α = 3, curious evaluations can be obtained from (3.2), namely

det (2\binom{i + j}{⌊(i + j)/2⌋} + \binom{i + j + 1}{⌊(i + j + 1)/2⌋})_{i,j=0}^{n−1} = 2n + 1  (4.28)

and

det (3\binom{i + j}{⌊(i + j)/2⌋} + \binom{i + j + 1}{⌊(i + j + 1)/2⌋})_{i,j=0}^{n−1} = L_{2n+1}.  (4.29)

(V) Another curious special case arises if we choose s_{i} = 0 and t_{i} = −1 for all i. Then m_{n} = [n even](−1)^{n/2}C_{n/2} and f_{n}(1) = (−i)^{n}U_{n}(i/2) = F_{n+1}. (The important point here is to choose \sqrt{t} = \sqrt{−1} consistently; our choice here is \sqrt{−1} = −i.) From (3.2) we therefore get

det ((−1)^{⌊(i+j+1)/2⌋}C_{⌊(i+j+1)/2⌋})_{i,j=0}^{n−1} = det (m_{i+j} + m_{i+j+1})_{i,j=0}^{n−1}

= det (m_{i+j})_{i,j=0}^{n−1} · F_{n+1} = (−1)^{\binom{n}{2}}F_{n+1}. (4.30)

For example, for n = 5, we get

det ( \begin{matrix}1 & −1 & −1 & 2 & 2 \\ −1 & −1 & 2 & 2 & −5 \\ −1 & 2 & 2 & −5 & −5 \\ 2 & 2 & −5 & −5 & 14 \\ 2 & −5 & −5 & 14 & 14 \end{matrix} ) = 8 = F_{6}.

Formula (2.5) with the same choices of the s_{i}’s and t_{i}’s gives

det (m_{i+j} + 2m_{i+j+1} + m_{i+j+2})_{i,j=0}^{n−1} = (−1)^{\binom{n+1}{2}} ∑_{j=0}^{n}(−1)^{j}F_{j+1}^{2}.  (4.31)

(VI) We point out that our formula (4.3) allows us to vastly generalise the second main result in [7, Theorem 3]. Namely, there Dougherty, French, Saderholm and Qian establish a linear recurrence of order 4 for the Hankel determinant

det (λC_{i+j} + μC_{i+j+1} + C_{i+j+2})_{i,j=0}^{n−1},

where λ and μ are some constants. Our formula in (4.3) provides even a closed form expression for a determinant that has much more general matrix entries (and the reparameterisation λ = αβ and μ = α + β). Using this, we may deduce the following corollary.

Corollary 4. With the setup in Section 2, let s_{i} ≡ s and t_{i} ≡ t for i ≥ 1. Then the scaled Hankel determinants

t_{0}^{−(n−1)}t^{−\binom{n−1}{2}} det (αβm_{i+j} + (α + β)m_{i+j+1} + m_{i+j+2})_{i,j=0}^{n−1}  (4.32)

satisfy a linear recurrence of order 4 with constant coefficients.

Remark. The reader should note that the scaling in (4.32) is exactly the value of the determinant in the denominator on the left-hand side of (4.3).

Proof of Corollary 4. The reader should note that the expression on the righthand side of (4.3) is a linear combination of products of the form t^{n}U_{n+δ}(x)U_{n+ε}(y) with constant coefficients, where δ, ε ∈ {1, 0, −1, −2}. (We recall that the arguments of the Chebyshev polynomials are x = (α + s)/(2\sqrt{t}) and y = (β + s)/(2\sqrt{t}).) Now, by (4.5), for each fixed δ the sequence (t^{n/2}U_{n+δ}(x))_{n≥0} satisfies the recurrence relation

p_{n+1} = (α + s)p_{n} − tp_{n−1}.  (4.33)

Similarly, for each fixed ε the sequence (t^{n/2}U_{n+ε}(y))_{n≥0} satisfies the same recurrence relation with α replaced by β. Hence, each product sequence (t^{n}U_{n+δ}(x)U_{n+ε}(y))_{n≥0} satisfies the same recurrence relation, namely the one resulting from the “product” of (4.33) with (4.33) where α has been replaced by β. It follows from the proof of [23, Theorem 6.4.9] (which is actually a much more general theorem) that the order of this “product” recurrence is 2 · 2 = 4. □

(VII) We turn to q-analogues. We use the familiar notations (a; q)_{0} := 1, (a; q)_{n} := (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}), n ≥ 1, for the q-shifted factorials, and

[ \begin{matrix}n \\ k \end{matrix} ]_{q} := \frac{(q; q)_{n}}{(q; q)_{k} (q; q)_{n−k}}

for the q-binomial coefficients. The Rogers–Szegő polynomials r_{n}(t), defined by

r_{n}(t) := ∑_{k=0}^{n} [ \begin{matrix}n \\ k \end{matrix} ]_{q} t^{k},

are the moments for the orthogonal polynomials (2.3) with s_{i} = q^{i}(t + 1) and t_{i} = q^{i}t(q^{i+1} − 1). The corresponding polynomials f_{n}(α) are given by

f_{n}(α) = ∑_{k=0}^{n} [ \begin{matrix}n \\ k \end{matrix} ]_{q} ∑_{j=0}^{k} q^{\binom{j}{2}+\binom{k−j}{2}} [ \begin{matrix}k \\ j \end{matrix} ]_{q} t^{j}α^{n−k}.

Thus, from (3.2) we obtain

\frac{det (αr_{i+j}(t) + r_{i+j+1}(t))_{i,j=0}^{n−1}}{(−t)^{\binom{n}{2}}q^{\binom{n}{3}} ∏_{i=1}^{n−1}(q, q)_{i}} = ∑_{k=0}^{n} [ \begin{matrix}n \\ k \end{matrix} ]_{q} ∑_{j=0}^{k} q^{\binom{j}{2}+\binom{k−j}{2}} [ \begin{matrix}k \\ j \end{matrix} ]_{q} t^{j}α^{n−k},  (4.34)

and from (2.5) we get

\frac{det (αβr_{i+j}(t) + (α + β)t_{i+j+1}(t) + r_{i+j+2}(t))_{i,j=0}^{n−1}}{(−t)^{\binom{n}{2}}q^{\binom{n}{3}} ∏_{i=1}^{n−1}(q, q)_{i}}

= ∑_{j=0}^{n} f_{j}(α)f_{j}(β)(−t)^{n−j}q^{\binom{n}{2}−\binom{j}{2}}(q^{j+1}; q)_{n−j}, (4.35)

with f_{j}(α) as above. We point out that the right-hand sides in (4.34) and (4.35) simplify for t = −1 since, in basic hypergeometric notation (cf. [10]), we have

∑_{j=0}^{k} q^{\binom{j}{2}+\binom{k−j}{2}} [ \begin{matrix}k \\ j \end{matrix} ]_{q} t^{j} = q^{\binom{k}{2}}_{1}ϕ_{1}[ \begin{matrix}q^{−k} \\ 0 \end{matrix} ; q, qt] ,

and this _{1}ϕ_{1}-series can be evaluated by means of [10, (1.8.1); Appendix (II.9); b → ∞]. To be precise, for t = −1 we have

∑_{j=0}^{k} q^{\binom{j}{2}+\binom{k−j}{2}} [ \begin{matrix}k \\ j \end{matrix} ]_{q} (−1)^{j} = \{ \begin{matrix}(−1)^{k/2}q^{\frac{1}{4} (k^{2}−2k)}(q; q^{2})_{k/2}, & if k is even, \\ 0, & if k is odd, \end{matrix}

and thus for example

\frac{det (αr_{i+j}(−1) + r_{i+j+1}(−1))_{i,j=0}^{n−1}}{q^{\binom{n}{3}} ∏_{i=1}^{n−1}(q, q)_{i}} = ∑_{k=0}^{n} [ \begin{matrix}n \\ 2k \end{matrix} ]_{q} (−1)^{k}q^{k^{2}−k}(q; q^{2})_{k}α^{n−2k},  (4.36)

by (4.34). For α = 1, this reduces even further, namely to

\frac{det (r_{i+j}(−1) + r_{i+j+1}(−1))_{i,j=0}^{n−1}}{q^{\binom{n}{3}} ∏_{i=1}^{n−1}(q, q)_{i}} = q^{\binom{n}{2}},  (4.37)

which is most easily seen by looking at the recursion (2.1) for α = 1, s_{i} = 0, and t_{i} = t^{i}(t^{i+1} − 1) for all i.

(VIII) The powers q^{\binom{n}{2}} are the moments for the orthogonal polynomials (2.3) with s_{i} = q^{i−1}(q^{i+1} + q^{i} − 1) and t_{i} = q^{3i}(q^{i+1} − 1). The corresponding polynomials f_{n}(α) are given by

f_{n}(α) = ∑_{k=0}^{n} [ \begin{matrix}n \\ k \end{matrix} ]_{q} q^{(n−1)k}α^{n−k}.

Thus, from (2.5) we obtain

\frac{det (αβq^{\binom{i+j}{2}} + (α + β)q^{\binom{i+j+1}{2}} + q^{\binom{i+j+2}{2}})_{i,j=0}^{n−1}}{(−1)^{\binom{n}{2}}q^{3\binom{n}{3}} ∏_{i=1}^{n−1}(q; q)_{i}}

= ∑_{j=0}^{n}(−1)^{n−j}q^{3\binom{n}{2}−3\binom{j}{2}}(q^{j+1}; q)_{n−j} ∑_{k_{1}=0}^{j} [ \begin{matrix}j \\ k_{1} \end{matrix} ]_{q} q^{(j−1)k_{1}}α^{j−k_{1}} ∑_{k_{2}=0}^{j} [ \begin{matrix}j \\ k_{2} \end{matrix} ]_{q} q^{(j−1)k_{2}}β^{j−k_{2}}. (4.38)

(IX) For another example, we choose T_{i} = q^{⌊(i+1)/2⌋} (1 − q^{⌊(i+2)/2⌋}) in the Dyck path setting in Section 2. Then we get c_{n} = (q; q)_{n/2} for even n and c_{n} = 0 for odd n. The corresponding polynomials are

g_{2n}(α) = ∑_{k=0}^{n} q^{\binom{k}{2}}(q; q)_{k} [ \begin{matrix}n \\ k \end{matrix} ]_{q}^{2} α^{n−k}

and

g_{2n+1}(α) = ∑_{k=0}^{n} q^{\binom{k}{2}}(q; q)_{k}[ \begin{matrix}n + 1 \\ k \end{matrix} ]_{q}[ \begin{matrix}n \\ k \end{matrix} ]_{q}α^{n−k}.

Hence, from (3.5) with α = 1 we obtain

\frac{det ((q; q)_{⌊(i+j+1)/2⌋})_{i,j=0}^{n−1}}{q^{\frac{1}{6} n(2n^{2}−3n+1)} ∏_{i=1}^{n−1}(q; q)_{i}^{2}} = ∑_{k=0}^{n} q^{\binom{k}{2}}(q; q)_{k} [ \begin{matrix}n \\ k \end{matrix} ]_{q}^{2} ,  (4.39)

and similarly, from (3.6),

\frac{det ((q; q)_{⌊(i+j+2)/2⌋})_{i,j=0}^{n−1}}{q^{2\binom{n+1}{3}}(q; q)_{n} ∏_{i=1}^{n−1}(q; q)_{i}^{2}} = ∑_{k=0}^{n} q^{\binom{k}{2}}(q; q)_{k} [ \begin{matrix}n + 1 \\ k \end{matrix} ]_{q} [ \begin{matrix}n \\ k \end{matrix} ]_{q} .  (4.40)

(X) Obviously, our identities in Sections 2 and 3 lead to many more Hankel determinant evaluations involving well-known functions when applied to the “orthogonal polynomials as moments” from [14, 15].

5. Computational proofs using matrix algebra.

Proof of Theorem 1. Define the matrices G_{n}(α) by

G_{n}(α) := ( \begin{matrix}α + s_{0} & & & 1 \\ t_{0} & & & α + s_{1} & & 1 \\ & & & t_{1} & & α + s_{2} & & & 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ & & & & & t_{n−3} & & & α + s_{n−2} & & & 1 \\ & & & & & & & & t_{n−2} & & & α + s_{n−1} \end{matrix} )

(we show only non-zero entries in the matrix). By expanding the determinant along the last row of the matrix, we obtain

det G_{n}(α) = (α + s_{n−1}) det G_{n−1}(α) − t_{n−2} det G_{n−2}(α).

Since we have in addition

det G_{1}(α) = α + s_{0} = f_{1}(α) and det G_{2}(α) = (α + s_{0})(α + s_{1}) − t_{0} = f_{2}(α),

we see that

f_{n}(α) = det G_{n}(α).  (5.1)

Let A_{n} be the matrix of path generating functions (m(i, j))_{i,j=0}^{n−1}, and let D_{n} be the

diagonal matrix with entries d(i, i) = ∏_{ℓ=0}^{i−1} t_{ℓ}. By (2.2) we get

(m(i + 1, j))_{i,j=0}^{n−1} = A_{n}R_{n},  (5.2)

where

R_{n} := ( \begin{matrix}s_{0} & & & 1 \\ t_{0} & & & s_{1} & & & 1 \\ & & & t_{1} & & & s_{2} & & 1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ & & & & & & t_{n−3} & & s_{n−2} & & & 1 \\ & & & & & & & & t_{n−2} & & & s_{n−1} \end{matrix} ) .

It is well known (cf. e.g. [4]) and easy to see by cutting a Motzkin path from (0, 0) to (i + j, 0) after i steps that

∑_{k} m(i, k)m(j, k) ∏_{ℓ=0}^{k−1} t_{ℓ} = m(i + j, 0).  (5.3)

This means that

(m_{i+j})_{i,j=0}^{n−1} = A_{n}D_{n}A_{n}^{t},

and it implies that

(αm_{i+j} + m_{i+j+1})_{i,j=0}^{n−1} = αA_{n}D_{n}A_{n}^{t} + A_{n}R_{n}D_{n}A_{n}^{t} = A_{n}G_{n}(α)D_{n}A_{n}^{t}.

Since A_{n} is a lower diagonal matrix and m(i, i) = 1 for all i, we get

det (A_{n}G_{n}(α)D_{n}A_{n}^{t}) = det D_{n} · det G_{n}(α),

which, recalling (2.6) and (5.1), implies (3.2).

In the same way as before (5.2), we get

(m(i + 2, j))_{i,j=0}^{n−1} = A_{n}(R_{n}^{2} + t_{n−1}E_{n}),  (5.4)

where E_{n} = (u_{n}(i, j))_{i,j=0}^{n−1} with u_{n}(n − 1, n − 1) = 1 and u_{n}(i, j) = 0 otherwise. The term t_{n−1}E_{n} arises to account for the Motzkin paths that are included in the weighted enumeration m(n + 1, n − 1) which end with an up-step followed by a down-step. Then, using (5.3) with i replaced by i + 2, we infer

(αβm(i + j, 0) + (α + β)m(i + j + 1, 0) + m(i + j + 2, 0))_{i,j=0}^{n−1}
= A_{n}(αβI_{n} + (α + β)R_{n} + R_{n}^{2} + t_{n−1}E_{n})D_{n}A_{n}^{t}
= A_{n}(G_{n}(α)G_{n}(β) + t_{n−1}E_{n})D_{n}A_{n}^{t},  (5.5)

where I_{n} denotes the n × n identity matrix.

If [A]_{k} denotes the restriction of the matrix A to the first k rows and columns, then it is a simple exercise to verify that

[G_{n}(α)G_{n}(β)]_{n−1} = G_{n−1}(α)G_{n−1}(β) + t_{n−2}E_{n−1}.

If we write H_{n} for the matrix G_{n}(α)G_{n}(β) + t_{n−1}E_{n}, then the above relation entails a recursion for the determinant of this matrix, namely

det H_{n} = det (G_{n}(α)G_{n}(β)) + t_{n−1} det[G_{n}(α)G_{n}(β)]_{n−1} = f_{n}(α)f_{n}(β) + t_{n−1} det H_{n−1}.

Consequently, by induction, we get det H_{n} = ∑_{j=0}^{n} f_{j}(α)f_{j}(β) ∏_{ℓ=j}^{n−1} t_{ℓ}. If this is substituted in (5.5) and the determinant is taken on both sides of that identity, then we obtain (2.5) if we again recall (2.6). □

Proof of Corollary 2. There is a well-known correspondence between Dyck paths and Motzkin paths which arises by arranging the steps of a Dyck path in groups of two, and then interpreting a group of two up-steps as an up-step in the corresponding Motzkin path, a group of two down-steps as a down-step in the corresponding Motzkin path, and a group consisting of an up-step and a down-step as a level step in the corresponding Motzkin path. This idea stands behind all the computations below.

With the c(n, k)’s defined by (2.8), we let a(n, k) = c(2n, 2k) and b(n, k) = c(2n+1, 2k+ 1). Then, by iterating (2.8), we get

a(n, k) = a(n − 1, k − 1) + s_{k}a(n − 1, k) + t_{k}a(n − 1, k + 1)  (5.6)

with s_{k} = T_{2k−1} + T_{2k} and t_{k} = T_{2k}T_{2k+1}, where, by convention, T_{−1} = 0, and

b(n, k) = b(n − 1, k − 1) + s_{k}b(n − 1, k) + t_{k}b(n − 1, k + 1)  (5.7)

with s_{k} = T_{2k} + T_{2k+1} and t_{k} = T_{2k+1}T_{2k+2}.

Then, with the g_{n}(α)’s as defined by (2.7), we get

g_{2n}(α) = αg_{2n−1}(α) + T_{2n−2}g_{2n−2}(α)
= αg_{2n−2}(α) + T_{2n−2}g_{2n−2}(α) + αT_{2n−3}g_{2n−3}(α)
= αg_{2n−2}(α) + T_{2n−2}g_{2n−2}(α) + T_{2n−3}(g_{2n−2}(α) − T_{2n−4}g_{2n−4}(α))
= (α + T_{2n−2} + T_{2n−3})g_{2n−2}(α) − T_{2n−3}T_{2n−4}g_{2n−4}(α).

This implies that for a(n, k) the associated polynomials f_{n}(α) (in the sense of the setup in Section 2, where the s_{k}’s and t_{k}’s are as given below (5.6)) are given by f_{n}(α) = g_{2n}(α).

Similarly, we have

g_{2n+1}(α) = g_{2n}(α) + T_{2n−1}g_{2n−1}(α)
= αg_{2n−1}(α) + T_{2n−1}g_{2n−1}(α) + T_{2n−2}g_{2n−2}(α)
= αg_{2n−1}(α) + T_{2n−1}g_{2n−1}(α) + T_{2n−2}(g_{2n−1}(α) − T_{2n−3}g_{2n−3}(α))
= (α + T_{2n−1} + T_{2n−2})g_{2n−1}(α) − T_{2n−2}T_{2n−3}g_{2n−3}(α).

This implies that for b(n, k) the associated polynomials f_{n}(α) (defined by the s_{k}’s and t_{k}’s as given below (5.7)) are given by f_{n}(α) = g_{2n+1}(α).

Therefore, Identity (2.5) with s_{k} = T_{2k−1} + T_{2k} and t_{k} = T_{2k}T_{2k+1} directly gives (2.9) since in that case we have m_{n} = a(n, 0) = c(2n, 0) = c_{2n}. Similarly, by observing that c(2n + 2, 0) = T_{0}c(2n + 1, 1) for n ≥ 0, we see that Identity (2.5) with s_{k} = T_{2k} + T_{2k+1} and t_{k} = T_{2k+1}T_{2k+2} gives (2.10) since in that case we have m_{n} = b(n, 0) = c(2n + 1, 1) = T_{0}^{−1}c(2n + 2, 0) = T_{0}^{−1}c_{2n+2}. □

6. Combinatorial proofs using non-intersecting lattice paths.

Proof of Theorem 1. In order to give a combinatorial proof of (2.5), we need a combinatorial model for the polynomials f_{n}(α), and we need (another) combinatorial model for the Hankel determinant

det (αβm_{i+j} + (α + β)m_{i+j+1} + m_{i+j+2})_{i,j=0}^{n−1} .  (6.1)

Our model for f_{n}(α) consists of n × 1 “pillars” which are decomposed into “squares” (1×1 bricks) — which come in two kinds — and “dominoes” (2×1 bricks). An example for n = 8 can be found in Figure 1. There, squares of the second kind are indicated by thick framing, whereas squares of the first kind are shown “normally”. (The labelling should be ignored at this point.) This pillar consists — from bottom to top — of a square of the

α −t_{1} −t_{3} s_{5} α s_{7} Figure 1

second kind, followed by two dominoes, followed by a square of the first kind, a square of the second kind, and a square of the first kind.

We define the weight of a square of the first kind whose bottom is at height h to be s_{h}, we define the weight of a square of the second kind to be α, and we define the weight of a domino whose bottom is at height h to be −t_{h}. The weight of a pillar p is by definition the product of the weights of its squares and dominoes and is denoted by w(p). Thus, the weight of the pillar in Figure 1 is

α(−t_{1})(−t_{3})s_{5}αs_{7}

(which now also explains the labels in Figure 1).

Let P_{n} denote the set of all n × 1 pillars. We claim that

∑_{p∈P_{n}} w(p) = f_{n}(α).  (6.2)

This is indeed easy to see. For, on top of such a pillar we may either have a square of either kind, where the sum of the weights of these two possible squares is α + s_{n−1}, or a domino, which has weight −t_{n−2}. If we remove the top brick, then there remains an (n − 1) × 1, respectively an (n − 2) × 1 pillar. Consequently, the generating function for n × 1 pillars, ∑_{p∈P_{n}} w(p), satisfies as well the recurrence (2.1), and the initial conditions are obvious. This establishes the claim.

We turn to our model for the Hankel determinant (6.1). Not very surprisingly, it is a model of non-intersecting lattice paths and is based on the corresponding enumeration theorem due to Lindström [20, Lemma 1] and Gessel and Viennot [11; 12, Theorem 1]. We recall that a family of paths in a (directed) graph is called non-intersecting if no two paths of the family have a graph vertex in common.

The underlying directed graph is the following: vertices are the points (x, y) in the two-dimensional integer lattice ℤ × ℤ with non-negative ordinate (i.e., with y ≥ 0). The edges are up-steps (x, y) → (x + 1, y + 1) with weight 1, down-steps (x, y) → (x + 1, y − 1) with weight t_{y−1} if y ≥ 1, and horizontal steps (x, y) → (x + 1, y) with weight s_{y}; in a strip of width 2 centred at the y-axis, we introduce further horizontal steps of a “second kind”: in our directed graph we have additional horizontal steps (−1, y) → (0, y) with weight α, and additional horizontal steps (0, y) → (1, y) with weight β. As before, the weight w(P) of a path P is the product of the weights of all its edges.

Let e(A_{i}, E_{j}) := ∑_{P:A_{i}→E_{j}} w(P), where the sum is over all paths from A_{i} = (−i − 1, 0) to E_{j} = (j + 1, 0), for i, j ≥ 0. Then we have

e(A_{i}, E_{j}) = αβm_{i+j} + (α + β)m_{i+j+1} + m_{i+j+2}.

For, the set of those paths which do not contain any of the additional horizontal steps contributes m_{i+j+2} to the total weight, the set of those paths which use one of the additional horizontal steps of the type (−1, y) → (0, y) contributes αm_{i+j+1}, the set of those paths which use one of the additional horizontal steps of the type (0, y) → (1, y) contributes βm_{i+j+1}, and the set of those paths which which use both types of additional horizontal steps contributes αβm_{i+j}.

The Lindström–Gessel–Viennot theorem then gives

det (αβm_{i+j} + (α + β)m_{i+j+1} + m_{i+j+2})_{i,j=0}^{n−1}

= det (e(A_{i}, E_{j}))_{i,j=0}^{n−1} = ∑_{P} sgn(σ(P)) ∏_{i=0}^{n−1} w(P_{i}). (6.3)

Here, P = (P_{0}, P_{1}, …, P_{n−1}) runs over all families of non-intersecting paths, where P_{i} runs from A_{i} to E_{σ(i)}, i = 0, 1, …, n − 1, for some permutation σ of {0, 1, …, n − 1}. An example of such a family of non-intersecting lattice paths for n = 9 is shown in Figure 2. There, the additional horizontal steps between the abscissa −1 and +1 are indicated by thick segments. For example, path P_{0} consists of two of these additional steps (hence its weight is αβ), while path P_{6} contains an additional horizontal step with weight α, and path P_{7} contains an additional horizontal step with weight β. The permutation σ associated with the path family in Figure 2 is 031426578 (meaning that P_{0} ends in E_{0}, P_{1} ends in E_{3}, etc.).

A reader who is experienced in the combinatorics of non-intersecting lattice paths does not have to go through the following explanations in detail; it will suffice to look at Figures 2 and 3, since they contain the essence of the argument. Everything else is — so-to-speak — just “book-keeping”.

However, in order to properly explain, we start with the question of how such an above family of non-intersecting paths looks like?

In the figure, we have marked the vertical lines x = −1 and x = +1 by dotted lines. To the left of x = −1, the paths are uniquely determined by the condition of being nonintersecting, and the same is true to the right of x = +1; see the figure. Thus, it is only in the strip between the vertical lines x = −1 and x = +1 where something “interesting” may happen.

In that strip, there may be some paths on the top, say P_{n−1}, …, P_{j}, which, in that strip, have an up-step followed by a down-step. (In the figure, this is only the case for the

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; A_{4}; A_{5}; A_{6}; A_{7}; A_{8}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}; E_{5}; E_{6}; E_{7}; E_{8}] Figure 2

top-most path P_{8}.) All other paths do not exceed height j − 1, and they form patterns in that strip that can be described as follows. We first look into the left substrip between the vertical lines x = −1 and x = 0. There, a path P_{i} may do three different things (see Figure 2):

(1) a horizontal step, which may be of two different kinds — “ordinary” or one of the “additional” steps;

(2) a down-step, but then there must be another path doing an up-step in the substrip crossing P_{i};

(3) an up-step, but then there must be another path doing a down-step in the substrip crossing P_{i}.

The same is true in the substrip between the vertical lines x = 0 and x = +1, and what happens there is independent from what is happening in the other substrip.

In order to determine the contribution of all this to the overall generating function (6.3), we observe that the weight contribution of the path parts to the left of the vertical line x = −1 and to the right of the vertical line x = +1 is in total the right-hand side of (2.6), or, in other words,

det (m_{i+j})_{i,j=0}^{n−1},

the denominator in (2.5). Hence, the contribution of the various configurations between the vertical lines x = −1 and x = +1 must give the right-hand side of (2.5).

This contribution of the “free” part in the strip between the vertical lines x = −1 and x = +1 is composed of the following constituents:

(1) The top-most paths P_{n−1}, …, P_{j}, each of which have an up-step followed by a down-step in this strip, contribute a multiplicative factor of

t_{j}t_{j+1} ⋯ t_{n−1}  (6.4)

to the total weight.

(2) According to the above considerations, the contribution of the paths P_{0}, P_{1}, …, P_{j−1} below equals the product of the their contributions in the left substrip between the vertical lines x = −1 and x = 0 and their contributions in the right substrip between the vertical lines x = 0 and x = +1. Combinatorially, we find the same configurations in the left substrip and the right substrip. The only difference is that the “additional” horizontal steps have weight α in the left substrip, whereas they have weight β in the right substrip. Hence, if we denote the generating function of the configurations in the left substrip by GF_{j}(α), then the total contribution coming from the strip between the vertical lines x = −1 and x = +1 equals

GF_{j}(α) GF_{j}(β).  (6.5)

Let us concentrate on the contributions of P_{0}, P_{1}, …, P_{j−1} in the left substrip, that is on GF_{j}(α). In order to see that GF_{j}(α) = f_{j}(α), we set up a weight-preserving bijection between these contributions and the pillars that we introduced at the beginning of this section. In this bijection, we map an “ordinary” horizontal step on height h to a square of the first kind on height h, we map an “additional” horizontal step on height h to a square of the second kind on height h, and we map a “cross”, that is a pair consisting of a down-step and an up-step that cross each other, with the down-step ending on height h, to a domino on height h. The left part of Figure 3 shows this correspondence for the configuration in the left substrip of Figure 2. (For the sake of completeness, the right part of Figure 3 shows the correspondence for the configuration in the right substrip of Figure 2. The reader is alerted that the weights of the squares of the second kind must be defined here to equal β in order to set up a weight-preserving correspondence.)

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; ⟷; α; −t_{1}; −t_{3}; s_{5}; α; s_{7}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; ⟷; β; s_{1}; −t_{2}; s_{4}; −t_{5}; β] Figure 3

This is indeed a weight-preserving bijection. For the correspondence between horizontal steps and squares this is obvious, but it also works for the correspondence between crosses and dominoes: in a cross two paths change sides^{3}; in the corresponding permutation σ(P) this corresponds to a transposition, which has negative sign. Indeed, we have defined the weight of a domino on height h by −t_{h}, that is, with a negative sign in front. If we now remember (6.2), then we see that the proof of (2.5) is complete. □

Sketch of proof of Corollary 2. The two Hankel determinant evaluations in Corollary 2 can also be directly established by a non-intersecting lattice path model. Since the corresponding arguments are very similar to the previous proof, we content ourselves with giving just a rough sketch that essentially only consists in presenting the figures analogous to the ones in Figures 2 and 3.

Here, the underlying graph is again the upper two-dimensional integer lattice. However, in difference to the previous proof, there are no “ordinary” horizontal steps at all, while the “additional” horizontal steps are horizontal steps of length 2 from (−2, y) to (0, y) and from (0, y) to (2, y), for y ≥ 0. The former horizontal steps have weight α, while the latter have weight β. As for the “ordinary” steps, up-steps have weight 1, and down-steps (x, y + 1) → (x + 1, y) have weight T_{y}.

The non-intersecting lattice path model for the Hankel determinant in the numerator of (2.9) consists of families P = (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths where P_{i} runs from A_{i} = (−2i − 2) to E_{σ(i)}, with E_{i} = (2i + 2, 0) and σ being some permutation of {0, 1, …, n − 1}. See Figure 4 for an example.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; A_{4}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}] Figure 4

3It is important to notice that a cross is not a violation of the property of being non-intersecting: the “intersection” happens in a non-lattice point, that is, the corresponding paths do not have a vertex of the underlying graph in common.

Here, the only freedom for the paths is in the strip between the vertical lines x = −2 and x = +2. Again, except for some top paths that have two up-steps followed by two down-steps in that strip, what happens in the substrips to the left and to the right of the y-axis is independent. We then map the configurations in these substrips to pillars, as is illustrated in Figure 5 for the example in Figure 4. The weight contribution of the uniquely determined parts to the left of x = −2 and to the right of x = +2 is exactly the right-hand side in (2.11) and thus equal to the denominator in (2.9).

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; ⟷; T_{1}; T_{3}; α; α; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; ⟷; β; T_{2}; T_{5}; β] Figure 5

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; A_{4}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}] Figure 6

The combinatorial model for the Hankel determinant in the numerator of (2.10) is completely analogous to the previous one. Essentially, what one has to do is to raise all paths in the previous model by one unit, prepend an up-step and append a down-step to each path. We present a corresponding illustration in Figure 6 and leave the details to the reader. □

7. Afterthoughts. A reader, after having seen [21] (presented here in (3.1) and (3.2)) and Theorem 1, will ask: what about the “next” Hankel determinant,

det (αβγm_{i+j} + (αβ + βγ + γα)m_{i+j+1} + (α + β + γ)m_{i+j+2} + m_{i+j+3})_{i,j=0}^{n−1} ?

Nothing prevents us from attacking it in just the same way. As a matter of fact, the obvious extension of our combinatorial model from Section 6 in terms of non-intersecting lattice paths leads rather directly to the following result.

Theorem 5. Let α, β, and γ be indeterminates. Then, for the setup of Section 2, for all positive integers n we have

\begin{matrix}det & (αβγm_{i+j} + (αβ + βγ + γα)m_{i+j+1} + (α + β + γ)m_{i+j+2} + m_{i+j+3}) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix}

= ∑_{0≤k≤j≤n} f_{j}(α)f_{k}(β)f_{k}(γ) (f_{n−j}(β)|_{\begin{matrix}s_{l}→s_{l+j+1} \\ t_{l}→t_{l+j+1} \end{matrix}} ) ∏_{ℓ=k}^{n−1} t_{ℓ}

+ ∑_{0≤j<k≤n} f_{j}(α)f_{j}(β)f_{k}(γ) (f_{n−k}(β)|_{\begin{matrix}s_{l}→s_{l+k+1} \\ t_{l}→t_{l+k+1} \end{matrix}} ) ∏_{ℓ=j}^{n−1} t_{ℓ}. (7.1)

Sketch of proof. We consider the same underlying graph as in the proof of Theorem 1 in Section 6, except that we do not only introduce additional horizontal steps between the vertical lines x = −1 and x = 0 (weighted by α) and between the vertical lines x = 0 and x = +1 (weighted by β) but also between the vertical lines x = +1 and x = +2, weighted by γ. The combinatorial model for the determinant in the numerator in the left-hand side of (7.1) consists of families P = (P_{0}, P_{1}, …, P_{n−1}) of non-intersecting lattice paths, where P_{i} runs from A_{i} = (−i − 1, 0) to E_{i} = (σ(i) + 2, 0), i = 0, 1, …, n − 1, for some permutation σ that depends on P. Figure 7 shows an example for n = 9. Again, we have indicated the additional horizontal edges by thick segments.

The combinatorial analysis of such families of non-intersecting lattice paths leads to the following conclusions:

(1) Being non-intersecting, the paths are uniquely determined to the left of the vertical line x = −1 and to the right of the vertical line x = +2. Only in the strip between these two vertical lines there is (some) freedom.

(2) In that strip, there may be some paths on top, P_{n−1}, …, P_{m}, which have there an up-step followed by a horizontal step (ordinary or additional) followed by a down-step. (In Figure 7, these are the two paths P_{8} and P_{7}.)

(3) Below P_{m}, exactly one of the vertices of our graph (= lattice points with nonnegative ordinate) on the vertical line x = 0 and exactly one of the vertices of our graph on the vertical line x = +1 is not taken by any of the paths. Let these vertices be (0, j) and (1, k), respectively. (In the example of Figure 7, these are the points (0, 6) and (1, 7).) We must have m = max{j, k} + 1.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; A_{4}; A_{5}; A_{6}; A_{7}; A_{8}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}; E_{5}; E_{6}; E_{7}; E_{8}] Figure 7

Now let first j < k (as in our example in Figure 7). Then, necessarily, we must have a down-step from any lattice point (0, y) with j < y ≤ k to (1, y − 1). In the substrip between the vertical lines x = −1 and x = 0 but below y = j, we find a configuration that is enumerated by f_{j}(α). Likewise in the substrip between x = 0 and x = +1 but below y = j, we find a configuration that is enumerated by f_{j}(β), while in the substrip between x = +1 and x = +2 but below y = k, we find a configuration that is enumerated by f_{k}(γ). Moreover, in the substrip between x = 0 and x = +1 but above y = k, we find a configuration that is enumerated by f_{n−k}(β), where each s_{l} has to be replaced by s_{l+k+1} and each t_{l} by t_{l+k+1}. This explains the second sum on the right-hand side of (7.1).

The case where j ≥ k is disposed of similarly and it leads to the first sum on the right-hand side of (7.1). □

In the case where the s_{i}’s and the t_{i}’s are constant for i ≥ 1, the right-hand side of (7.1) can again be evaluated in closed form in terms of Chebyshev polynomials. In order to have a succinct notation for the result, we introduce the umbral notation

U_{α}^{n} ≡ U_{n} (\frac{α+s}{2\sqrt{t}}) , for n ≥ 0.

Corollary 6. Let α, β, and γ be indeterminates, and in the setup of Section 2 set s_{i} ≡ s and t_{i} ≡ t for i ≥ 1. Then, for all positive integers n, we have

\begin{matrix}det & (αβγm_{i+j} + (αβ + βγ + γα)m_{i+j+1} + (α + β + γ)m_{i+j+2} + m_{i+j+3}) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix}

= \frac{Num(α, β, γ)}{(α − β)(β − γ)(γ − α)}, (7.2)

where

Num(α, β, γ) = t^{(3n+3)/2}(U_{α} − U_{β})(U_{β} − U_{γ})(U_{γ} − U_{α})

× (1 − t^{−1/2}(s − s_{0})U_{α}^{−1} + t^{−1}(t − t_{0})U_{α}^{−2})
× (1 − t^{−1/2}(s − s_{0})U_{β}^{−1} + t^{−1}(t − t_{0})U_{β}^{−2})

× (1 − t^{−1/2}(s − s_{0})U_{γ}^{−1} + t^{−1}(t − t_{0})U_{γ}^{−2})U_{α}^{n}U_{β}^{n}U_{γ}^{n}.

Obviously, we could now again derive many Hankel determinant evaluations for the special cases that were discussed in Section 4. We refrain from doing so here in the interest of not going overboard at this point, and instead content ourselves with presenting a small list of examples:

det (M_{i+j} + 3M_{i+j+1} + 3M_{i+j+2} + M_{i+j+3})_{i,j=0}^{n−1}
= \frac{(n + 1)(n + 2)^{2}(n + 3)(2n + 3)(2n + 5)}{180},  (7.3)
det (−M_{i+j} + 3M_{i+j+1} − 3M_{i+j+2} + M_{i+j+3})_{i,j=0}^{n−1}
= [n even](−1)^{n/2} (\frac{n}{2} + 1)^{2} ,  (7.4)
det (−M_{i+j} − M_{i+j+1} + M_{i+j+2} + M_{i+j+3})_{i,j=0}^{n−1}
= \{ \begin{matrix}(−1)^{n_{0}}(n_{0} + 1)^{2}, & if n = 2n_{0}, \\ (−1)^{n_{0}−1}\binom{2n_{0}+2}{3}, & if n = 2n_{0} − 1, \end{matrix}  (7.5)
det (−C_{i+j} + 3C_{i+j+1} − 3C_{i+j+2} + C_{i+j+3})_{i,j=0}^{n−1}

= \{ \begin{matrix}(−1)^{n_{0}}n_{0}(2n_{0} + 1), & if n = 3n_{0} − 1, \\ (−1)^{n_{0}}(2n_{0} + 1)^{2}, & if n = 3n_{0}, \\ (−1)^{n_{0}}(n_{0} + 1)(2n_{0} + 1), & if n = 3n_{0} + 1, \end{matrix} (7.6)

det (−C_{i+j+1} + 3C_{i+j+2} − 3C_{i+j+3} + C_{i+j+4})_{i,j=0}^{n−1}

= \{ \begin{matrix}(−1)^{n_{0}−1}n_{0}(2n_{0} + 1), & if n = 3n_{0} − 1, \\ (−1)^{n_{0}}(n_{0} + 1)(2n_{0} + 1), & if n = 3n_{0}, \\ (−1)^{n_{0}}(2n_{0} + 2)^{2}, & if n = 3n_{0} + 1. \end{matrix} (7.7)

Interestingly, by chance (?) the evaluation in (7.3) turns out to be exactly the same as the evaluation of the Hankel determinant det(C_{i+j+4})_{i,j=0}^{n−1}.

In the same way as we got Corollary 4 from Corollary 3, the above corollary entails that the expressions in (7.2) satisfy a linear recurrence of order 8. This generalises [7, Theorem 4].

Corollary 7. With the setup in Section 2, let s_{i} ≡ s and t_{i} ≡ t for i ≥ 1. Then the scaled Hankel determinants

t_{0}^{−(n−1)}t^{−\binom{n−1}{2}}

× det (αβγm_{i+j} + (αβ + βγ + γα)m_{i+j+1} + (α + β + γ)m_{i+j+2} + m_{i+j+3})_{i,j=0}^{n−1} (7.8) satisfy a linear recurrence of order 8 with constant coefficients.

Clearly, one could continue in this manner. However, the combinatorial analysis would become more and more intricate. On the other hand, it should be noted that Corollaries 3 and 6 (as well as (3.2) with (4.2)) follow a pattern. On this basis, we make the following conjecture on the evaluation of the Hankel determinant of an arbitrary linear combination of path generating functions in the case where the s_{i}’s and the t_{i}’s are constant for i ≥ 1. In order to state the result, we also employ umbral notation for the path generating functions, namely m^{n} ≡ m_{n} for all n.

Conjecture 8. Let α_{1}, α_{2}, …, α_{d} be indeterminates, and in the setup of Section 2 set s_{i} ≡ s and t_{i} ≡ t for i ≥ 1. Then, for all positive integers d and n, we have

\begin{matrix}det & (m^{i+j} ∏_{ℓ=1}^{d}(α_{ℓ} + m)) & {n−1 \atop i,j=0} \\ det & (m_{i+j}) & {n−1 \atop i,j=0} \end{matrix} = \frac{Num(α_{1}, …, α_{d})}{∏_{1≤i<j≤d}(α_{i} − α_{j})},  (7.9)

where

Num(α_{1}, …, α_{d}) = t^{^{\frac{1}{2}}(dn+\binom{d}{2})} ∏_{1≤i<j≤d}(U_{α_{i}} − U_{α_{j}})

× ∏_{i=1}^{d} (1 − t^{−1/2}(s − s_{0})U_{α_{i}}^{−1} + t^{−1}(t − t_{0})U_{α_{i}}^{−2})U_{α_{i}}^{n}.

Obviously (compare with the proof of Corollary 4), if true, then this formula implies that the scaled determinants on the left-hand side of (7.9) satisfy a linear recurrence of order 2^{d} with constant coefficients. This would be a vast generalisation of [7, Conj. 5].

Note. After the first version of this article was written, the second author discovered a general identity for Hankel determinants of linear combinations of moments of orthogonal polynomials of which Conjecture 8 is a special case, and that this identity somehow exists in the folklore of the theory of orthogonal polynomials but does not seem to be well-known. These findings will be reported in the forthcoming article [19].

Acknowledgement. This article was written while the second author was visiting the Institut Mittag–Leffler during the “Algebraic and Enumerative Combinatorics” programme (grant no. 2016-06596 of the Swedish Research Council) in Spring 2020, organised by Sara Billey, Petter Brändén, Sylvie Corteel and Svante Linusson.

References

1. Martin Aigner, Catalan and other numbers: a recurrent theme, Algebraic Combinatorics and Computer Science (H. Crapo, D. Senato, eds.), Springer–Verlag, Berlin, 2001, pp. 347–390.

2. Naiomi T. Cameron and Andrew C.M. Yip, Hankel determinants of sums of consecutive Motzkin numbers, Linear Algebra Appl. 434 (2011), 712–722.

3. Johann Cigler, Some relations between generalized Fibonacci and Catalan numbers, Sitz.ber. d. Österr. Akad. Wiss. Math.-Naturwiss. Klasse 211 (2002), 143–154.

4. Johann Cigler, A simple approach to some Hankel determinants, manuscript, arχiv:0902.1650.

5. Johann Cigler, Hankel determinants of some polynomial sequences, manuscript, arχiv:1211.0816.

6. Aleksandar Cvetković, Predrag Rajković and Miloš Ivković, Catalan numbers, and Hankel transform, and Fibonacci numbers, J. Integer Seq. 5 (2002), Article 02.1.3, 8 pp.

7. Michael Dougherty, Christopher French, Benjamin Saderholm and Wenyang Qian, Hankel transforms of linear combinations of Catalan numbers, J. Integer Seq. 14 (2011), Article 11.5.1, 20 pp.

8. Mohamed Elouafi, A unified approach for the Hankel determinants of classical combinatorial numbers, J. Math. Anal. Appl. 431 (2015), 1253–1274.

9. Sen-Peng Eu, Tsai-Lien Wong and Pei-Lan Yen, Hankel determinants of sums of consecutive weighted Schröder numbers, Linear Algebra Appl. 437 (2012), 2285–2299.

10. George Gasper and Mizan Rahman, Basic Hypergeometric Series, second edition, Encyclopedia of Math. And Its Applications 96, Cambridge University Press, Cambridge, 2004.

11. Ira Martin Gessel and Xavier Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

12. Ira Martin Gessel and Xavier Viennot, Determinants, paths, and plane partitions, preprint, 1989,

available at http://www.cs.brandeis.edu/~ira.

13. Frank Harary and Ronald C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1–13.

14. Mourad E.H. Ismail and Dennis Stanton, Classical orthogonal polynomials as moments, Can. J. Math. 49 (1997), 520–542.

15. Mourad E.H. Ismail and Dennis Stanton, More orthogonal polynomials as moments, 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. 377–396.

16. Christian Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (“The Andrews Festschrift”) (1999), Article B42q, 67 pp.

17. Christian Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166.

18. Christian Krattenthaler, Determinants of (generalised) Catalan numbers, J. Statist. Plann. Inference 140 (2010), 2260–2270.

19. Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, II, preprint, arχiv:2101.04225.

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

21. Lili Mu, Yi Wang and Yeong-Nan Yeh, Hankel determinants of linear combinations of consecutive Catalan-like numbers, Discrete Math. 340 (2017), 3097–3103.

22. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

23. Richard Peter Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.

24. Xavier Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, UQAM, Montréal,

Québec, 1983, available at http://www.xavierviennot.org/xavier/polynomes orthogonaux.html.

Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

WWW: http://homepage.univie.ac.at/johann.cigler, http://www.mat.univie.ac.at/~kratt