Hankel Transforms of Linear Combinations of Catalan Numbers

Michael Dougherty, Christopher French, Benjamin Saderholm, and

Wenyang Qian Department of Mathematics and Statistics Grinnell College Grinnell, IA 50112 USA

                 doughert@grinnell.edu
                 frenchc@grinnell.edu
                 saderhol@grinnell.edu
                 qianweny@grinnell.edu

Abstract

Cvetković, Rajković, and Ivković proved that the Hankel transform of the sequence of sums of adjacent Catalan numbers is the bisection of the sequence of Fibonacci numbers. Here, we find recurrence relations for the Hankel transform of more general linear combinations of Catalan numbers, involving up to four adjacent Catalan numbers, with arbitrary coefficients. Using these, we make certain conjectures about the recurrence relations satisfied by the Hankel transform of more extended linear combinations.

1 Introduction

Given a sequence of integers {a_{n}}_{n=0}^{∞}, the Hankel matrix of the sequence is the infinite matrix H whose (i, j) entry is a_{i+j}. Here, we allow i and j to be 0, so our rows and columns are numbered beginning with 0. That is,

H = (\begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ \\ a_{1} & a_{2} & a_{3} & ⋯ \\ a_{2} & a_{3} & a_{4} & ⋯ \\ a_{3} & a_{4} & a_{5} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

In general, if A is an infinite matrix, with row and column indices beginning at 0, and n ≥ 0 is an integer, we let A(n) denote the upper-left (n + 1) × (n + 1) submatrix of A. Thus, H(0) is the 1 × 1 matrix (a_{0}), H(1) is the 2 × 2-matrix

H(1) = (\begin{matrix}a_{0} & a_{1} \\ a_{1} & a_{2} \end{matrix}) ,

and

H(2) = (\begin{matrix}a_{0} & a_{1} & a_{2} \\ a_{1} & a_{2} & a_{3} \\ a_{2} & a_{3} & a_{4} \end{matrix}) .

We let h_{n} = det(H(n)). Then the sequence {h_{n}}_{n=0}^{∞} is called the Hankel transform of the sequence {a_{n}}_{n=0}^{∞}.

The Hankel transform is particularly interesting when applied to the Catalan numbers. Recall that the Catalan numbers c_{n} are defined by the recurrence relation

c_{n+1} = c_{n}c_{0} + c_{n−1}c_{1} + c_{n−2}c_{2} + ⋯ + c_{0}c_{n}

where c_{0} = 1. It is well-known that the Hankel transform of the sequence of Catalan numbers is the sequence of all 1’s. Mays and Wojciechowski [6] found the Hankel transform of the sequences obtained by removing 1, 2, or 3 terms from the beginning of the Catalan number sequence. If we remove 1 term, then the Hankel transform is a sequence of 1’s; if we remove 2 terms, the Hankel transform is the sequence {n + 2}_{n=0}^{∞}; if we remove 3 terms, the Hankel transform is the sequence \{\frac{(n+2)(n+3)(2n+5)}{6}\}_{n=0}^{∞}. (Note that our n is k − 1 in [6].) Cvetković, Rajković, and Ivković [5] proved that the Hankel transform of the sequence {c_{n} +c_{n+1}} is the sequence 2, 5, 13, 34, 89, ⋯ consisting of every other Fibonacci number. Benjamin, Cameron, Quinn, and Yerger [2] also reproved this result using a more combinatorial approach. Notice that, in particular, the Hankel transform of the sequence {c_{n}+c_{n+1}} satisfies the homogeneous linear recurrence relation

h_{n+2} − 3h_{n+1} + h_{n} = 0.  (1)

In this paper, we take up the question of finding recurrence relations satisfied by more general linear combinations of Catalan numbers. In particular, we ask

Question 1. Suppose given k + 1 integers α_{0}, α_{1}, α_{2}, ⋯, α_{k}. Let {h_{n}} denote the Hankel transform of the sequence whose n^{th} term is ∑_{i=0}^{k} α_{i}c_{n+i}. What homogeneous linear recurrence relation, if any, is satisfied by the sequence h_{n}?

For example, in the case where k = 1 and α_{0} = α_{1} = 1, we know that h_{n} satisfies the recurrence relation of Equation 1. Of course, if k = 0 and α_{0} = 1, then {h_{n}} is just the Hankel transform of the sequence of Catalan numbers, so h_{n} = 1 for all n. From this, it is easy to see that when k = 0 and α_{0} is arbitrary, we have h_{n} = α_{0}^{n+1}. Thus, the sequence {h_{n}} satisfies the first-order homogeneous linear recurrence relation

h_{n+1} − α_{0}h_{n} = 0.

Our next three theorems, which we will prove in this paper, answer Question 1 when k = 1, k = 2, and k = 3. For ease of reading, we adjust our notation, replacing α_{0}, α_{1}, α_{2}, and α_{3} by α, β, γ, δ.

Theorem 2. The Hankel transform of the sequence {αc_{n} + βc_{n+1}} satisfies the second-order homogeneous linear recurrence relation

h_{n+2} − (α + 2β)h_{n+1} + β^{2}h_{n} = 0.

Theorem 3. The Hankel transform of the sequence {αc_{n} + βc_{n+1} + γc_{n+2}} satisfies the fourth-order homogeneous linear recurrence relation

h_{n+4} + (−α − 2β − 4γ)h_{n+3} + (β^{2} − 2αγ + 4βγ + 6γ^{2})h_{n+2}
+(−α − 2β − 4γ)γ^{2}h_{n+1} + γ^{4}h_{n} = 0.

Theorem 4. The Hankel transform of the sequence {αc_{n} + βc_{n+1} + γc_{n+2} + δc_{n+3}} satisfies the eighth-order homogeneous linear recurrence relation

h_{n+8}
+(−α − 2β − 4γ − 8δ)h_{n+7}
+(β^{2} − 2αγ + 4βγ + 6γ^{2} − 12αδ + 4βδ + 24γδ + 28δ^{2})h_{n+6}
+(−αγ^{2} − 2βγ^{2} − 4γ^{3} + 2αβδ + 4β^{2}δ − 4αγδ − 24γ^{2}δ − 7αδ^{2} + 2βδ^{2} − 60γδ^{2} − 56δ^{3})h_{n+5}

+(γ^{4} − 4βγ^{2}δ + 8γ^{3}δ + α^{2}δ^{2} + 4αβδ^{2} + 6β^{2}δ^{2} + 12αγδ^{2} − 8βγδ^{2} + 36γ^{2}δ^{2} + 40αδ^{3} − 8βδ^{3} + 80γδ^{3} + 70δ^{4})h_{n+4}

+(−αγ^{2} − 2βγ^{2} − 4γ^{3} + 2αβδ + 4β^{2}δ − 4αγδ − 24γ^{2}δ − 7αδ^{2} + 2βδ^{2} − 60γδ^{2} − 56δ^{3})δ^{2}h_{n+3}
+(β^{2} − 2αγ + 4βγ + 6γ^{2} − 12αδ + 4βδ + 24γδ + 28δ^{2})δ^{4}h_{n+2}
+(−α − 2β − 4γ − 8δ)δ^{6}h_{n+1}
+δ^{8}h_{n} = 0.

Of course, Theorem 3 follows from Theorem 4 by setting δ equal to 0, and Theorem 2 follows from Theorem 3 by setting γ = 0. Notice also that the result of Cvetković, Rajković, and Ivković [5] follows from Theorem 2 by setting α = β = 1. In this case, it is trivial to check that the initial two terms of the Hankel transform are 2 and 5, and then the recurrence relation implies the rest.

While the recurrence relations given above quickly grow in complexity as k increases, there are several features of these recurrence relations that seem interesting. On the basis of these features, we make the following conjectures. First, we note that the order of the recurrence relations doubles each time we increase k by 1.

Conjecture 5. The Hankel transform of the sequence whose n^{th} term is

∑_{i=0}^{k} α_{i}c_{n+i}

satisfies a homogeneous linear recurrence relation of order 2^{k}.

We also notice that the coefficient of h_{n+2^{k}−1} is of a particularly simple form.

Conjecture 6. The coefficient of h_{n+2^{k}−1} in the recurrence relation of Conjecture 5 is

−(α_{0} + 2α_{1} + 4α_{2} + ⋯ + 2^{k}α_{k}).

Finally, we note that the coefficients of h_{n+2^{k}−r} and h_{n+r} seem to be related. For example, in Theorem 3, the coefficient of h_{n+1} is the product of γ^{2} and the coefficient of h_{n+3}. Likewise, the coefficient of h_{n} is the product of γ^{4} and the coefficient of h_{n+4}.

Conjecture 7. When r < 2^{k−1}, the coefficient of h_{n+r} in the recurrence relation of Conjecture 5 is equal to the product of α_{k}^{2^{k}−2r} and the coefficient of h_{n+2^{k}−r}.

Using Theorem 3, we can show that certain sequences in the OEIS [7] are Hankel transforms of linear combinations of Catalan numbers. For example, if we set α = 1, β = 1, γ = 1, we get the sequence

4, 20, 111, 624, 3505, 19676, 110444, 619935, 3479776, 19532449, …

which is sequence \underline{A014523} in the OEIS, the number of Hamiltonian paths in a 4 × (2n + 1) grid (see also [4]). To see this, we simply observe from the OEIS that sequence \underline{A014523} satisfies the recurrence relation

a_{n+4} − 7a_{n+3} + 9a_{n+2} − 7a_{n+1} + a_{n} = 0.

By Theorem 3, this is the same as the recurrence relation satisfied by the Hankel transform of c_{n} + c_{n+1} + c_{n+2}. One now simply observes that the first four terms of the two sequences coincide!

Likewise, if we set α = 1, β = 2, γ = 1, we get the sequence

5, 30, 199, 1355, 9276, 63565, 435665, 2986074, 20466835, 140281751, …

which is sequence \underline{A103433} in the OEIS, namely the sequence ∑_{i=0}^{n} F_{2i−1}^{2} where F_{k} denotes the k^{th} Fibonacci number. To see this, we note from the OEIS that sequence \underline{A103433} has generating function

G(x) = \frac{x(1 − 4x + x^{2})}{(1 − 7x + x^{2})(1 − x)^{2}} = \frac{x − 4x^{2} + x^{3}}{x^{4} − 9x^{3} + 16x^{2} − 9x + 1}.

From here, it is easy to check that the sequence satisfies the recurrence relation

h_{n+4} − 9h_{n+3} + 16h_{n+2} − 9h_{n+1} + h_{n} = 0.

By Theorem 3, this is the same as the recurrence relation satisfied by the Hankel transform of c_{n} +2c_{n+1} +c_{n+2}. Again, one simply observes that the first four terms of the two sequences coincide.

Our paper is organized as follows. In Section 2, we state some basic results concerning Hankel matrices and shifts of Catalan numbers. These results are proved in Section 3. Using only these basic results, we prove Theorem 2 in Section 2. For Theorems 3 and 4 we need somewhat more sophisticated arguments. To prepare for these, we state and prove two easy lemmas about recurrence relations in Section 4. The work of Section 2 shows that we can simplify our study of the Hankel matrices of linear combinations of Catalan numbers by investigating a class of matrices which we call hyperdiagonal. We carry out this investigation in Section 5, and use the results from there to finish off the proofs of Theorems 3 and 4 in Section 6.

2 Catalan Numbers and Hankel Matrices

In this section, we state some results about the Hankel matrices of shifts of the sequence of Catalan numbers; we will prove these results in the next section. Using these results, we give an easy proof of Theorem 2. To begin, we need some definitions.

Definition 8. Let C be the Hankel matrix of the sequence of Catalan numbers, so C_{i,j} = c_{i+j}, where i, j are non-negative integers. Let C{k} denote the Hankel matrix of the sequence of Catalan numbers with the first k terms removed, so C{k}_{i,j} = c_{i+j+k}. In particular, C = C{0}.

Definition 9. Let L be the infinite matrix defined by L_{i,j} = (−1)^{i+j}\binom{i+j}{i−j}. (When i < j, L_{i,j} = 0.) Let U = L^{T}, so U_{i,j} = (−1)^{i+j}\binom{i+j}{j−i}.

Notation 10. For an infinite matrix A and an integer n ≥ 0, let A(n) denote the upper-left (n + 1) × (n + 1) submatrix of A.

In the next section, we will prove

Proposition 11. The matrix product LCU is the identity matrix. The matrix LC{1}U is tridiagonal with

(LC\{1\}U)_{i,j} = \begin{cases}1, & if |i − j| = 1 or i = j = 0; \\ 2, & if i = j ≥ 1; \\ 0, & otherwise. \end{cases}

That is, LC{1}U takes the form

(\begin{matrix}1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & ⋯ \\ 0 & 1 & 2 & 1 & 0 & ⋯ \\ 0 & 0 & 1 & 2 & 1 & ⋯ \\ 0 & 0 & 0 & 1 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Assuming this result, we now obtain an elementary proof of Theorem 2.

Proof. Let {h_{n}} be the Hankel transform of the sequence αc_{n} + βc_{n+1}. The Hankel matrix of this sequence is αC + βC{1}. Recall that for an infinite matrix A, A(n) denotes the upper-left (n + 1) × (n + 1) submatrix of A. Then, we have

h_{n} = det((αC + βC{1})(n))

Since L(n) and U(n) are triangular (n + 1) × (n + 1) matrices with 1’s on the diagonal, they both have determinant 1, so we now have

h_{n} = det(L(n)(αC + βC{1})(n)U(n))

= det((L(αC + βC{1})U)(n)) = det((αLCU + βLC{1}U)(n)).

By Proposition 11, αLCU + βLC{1}U is equal to

(\begin{matrix}β + α & β & 0 & 0 & 0 & ⋯ \\ β & 2β + α & β & 0 & 0 & ⋯ \\ 0 & β & 2β + α & β & 0 & ⋯ \\ 0 & 0 & β & 2β + α & β & ⋯ \\ 0 & 0 & 0 & β & 2β + α & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Thus,

h_{n+2} = |\begin{matrix}β + α & β & ⋯ & 0 & 0 & 0 \\ β & 2β + α & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 2β + α & β & 0 \\ 0 & 0 & ⋯ & β & 2β + α & β \\ 0 & 0 & ⋯ & 0 & β & 2β + α \end{matrix}|

where the given matrix has n + 3 rows and n + 3 columns. Expanding along the last column gives

(2β + α) |\begin{matrix}β + α & β & ⋯ & 0 & 0 \\ β & 2β + α & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 2β + α & β \\ 0 & 0 & ⋯ & β & 2β + α \end{matrix}| − β |\begin{matrix}β + α & β & ⋯ & 0 & 0 \\ β & 2β + α & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 2β + α & β \\ 0 & 0 & ⋯ & 0 & β \end{matrix}| .

Expanding the right-hand matrix along the bottom row now yields

(2β + α) |\begin{matrix}β + α & β & ⋯ & 0 & 0 \\ β & 2β + α & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 2β + α & β \\ 0 & 0 & ⋯ & β & 2β + α \end{matrix}| − β^{2} |\begin{matrix}β + α & β & ⋯ & 0 \\ β & 2β + α & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 2β + α \end{matrix}|

= (2β + α)h_{n+1} − β^{2}h_{n}.

Thus, h_{n+2} − (2β + α)h_{n+1} + β^{2}h_{n} = 0 for all n ≥ 0.

In the next section, we will also prove the following Proposition: Proposition 12. When i + j ≥ k ≥ 0, (LC\{k\}U)_{i,j} = \binom{2k}{k+i−j}.

Again, \binom{n}{m} is defined to be 0 when m < 0 or m > n. We will later use this proposition in the proofs of Theorems 3 and 4. As an example, LC{2}U takes the form

(\begin{matrix}2 & 3 & 1 & 0 & 0 & 0 & ⋯ \\ 3 & 6 & 4 & 1 & 0 & 0 & ⋯ \\ 1 & 4 & 6 & 4 & 1 & 0 & ⋯ \\ 0 & 1 & 4 & 6 & 4 & 1 & ⋯ \\ 0 & 0 & 1 & 4 & 6 & 4 & ⋯ \\ 0 & 0 & 0 & 1 & 4 & 6 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

The 3 entries in the top left (the 2 and the two 3’s) are not given by Proposition 12, but can easily be computed directly. Likewise, LC{3}U takes the form

(\begin{matrix}5 & 9 & 5 & 1 & 0 & 0 & 0 & ⋯ \\ 9 & 19 & 15 & 6 & 1 & 0 & 0 & ⋯ \\ 5 & 15 & 20 & 15 & 6 & 1 & 0 & ⋯ \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & ⋯ \\ 0 & 1 & 6 & 15 & 20 & 15 & 6 & ⋯ \\ 0 & 0 & 1 & 6 & 15 & 20 & 15 & ⋯ \\ 0 & 0 & 0 & 1 & 6 & 15 & 20 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Again, the six entries in the top left (the three 5’s, the two 9’s, and the 19) are not given by Proposition 12, but can easily be computed directly.

3 Proofs of Propositions 11 and 12

In this section, as the title suggests, we prove Propositions 11 and 12. The main technical tool in these proofs is the following Lemma. The second author used this idea previously [3] having found it originally in a paper by Bajunaid, Cohen, Colonna, and Signman [1].

Lemma 13. Let g(z) be the power series ∑_{n=0}^{∞} c_{k}z^{k}. Then, g(z(1 − z)) = ∑_{k=0}^{∞} z^{k}.

Proof. By definition of the Catalan numbers,

g(z)^{2} = ∑_{k=0}^{∞} (∑_{l=0}^{k} c_{l}c_{k−l}) z^{k} = ∑_{k=0}^{∞} c_{k+1}z^{k}.

Thus,

zg(z)^{2} = ∑_{k=0}^{∞} c_{k+1}z^{k+1} = ∑_{k=1}^{∞} c_{k}z^{k} = g(z) − 1.

We may substitute z(1 − z) into this equation to obtain

z(1 − z)g(z(1 − z))^{2} = g(z(1 − z)) − 1.

Multiplying by z(1 − z) yields

(z(1 − z)g(z(1 − z)))^{2} = (z(1 − z)g(z(1 − z))) − z(1 − z).

If we let h(z) = z(1−z)g(z(1−z)), then the above equation implies h(z)^{2}−h(z)+z(1−z) = 0, so that (h(z) − z)(h(z) − (1 − z)) = 0. Since the ring of power series is an integral domain, this implies h(z) = z or h(z) = 1 − z. But we know h(0) = 0, so h(z) = z, whence z(1 − z)g(z(1 − z)) = z. This implies g(z(1 − z)) = \frac{1}{1−z} = ∑_{k=0}^{∞} z^{k}.

Corollary 14. Suppose i ≥ t ≥ 1. Then, we have

∑_{k=i−t}^{2i−t}(−1)^{k+t}\binom{k + t}{2i − t − k}c_{k} = 0.

For any i ≥ 0, we have

∑_{k=i}^{2i}(−1)^{k}\binom{k}{2i − k}c_{k} = 1,

and

∑_{k=i+1}^{2i+1}(−1)^{k−1}\binom{k − 1}{2i + 1 − k}c_{k} = 2i + 1.

Proof. First, we have

(1 − z)^{t}g(z(1 − z)) = ∑_{k=0}^{∞} c_{k}z^{k}(1 − z)^{k+t} = ∑_{k=0}^{∞} ∑_{m=0}^{k+t}(−1)^{m}\binom{k + t}{m}c_{k}z^{k+m}.

For an integer i ≥ 0, the coefficient of z^{2i−t} is

∑_{k=i−t}^{2i−t}(−1)^{k+t}\binom{k + t}{2i − t − k}c_{k}.

On the other hand, by Lemma 13, (1−z)^{t}g(z(1−z)) = (1−z)^{t−1}, so if i ≥ t, then 2i−t ≥ t, so the coefficient of i − t is 0.

For the second formula, we have

g(z(1 − z)) = ∑_{k=0}^{∞} c_{k}z^{k}(1 − z)^{k} = ∑_{k=0}^{∞} ∑_{m=0}^{k}(−1)^{m}\binom{k}{m}c_{k}z^{k+m}.

For an integer i ≥ 0, the coefficient of z^{2i} is

∑_{k=i}^{2i}(−1)^{k}\binom{k}{2i − k}c_{k}.

By Lemma 13, this coefficient is equal to 1.

Finally, we have

\frac{g(z(1 − z)) − 1}{1 − z} = ∑_{k=1}^{∞} c_{k}z^{k}(1 − z)^{k−1} = ∑_{k=1}^{∞} ∑_{m=0}^{k−1}(−1)^{m}\binom{k − 1}{m}c_{k}z^{k+m}.

For an integer i ≥ 0, the coefficient of z^{2i+1} is

∑_{k=i+1}^{2i+1}(−1)^{k−1}\binom{k − 1}{2i + 1 − k}c_{k}.

But by Lemma 13 again,

\frac{g(z(1 − z)) − 1}{1 − z} = \frac{1/(1 − z) − 1}{1 − z} = \frac{z}{(1 − z)^{2}} = ∑ kz^{k},

so the coefficient of z^{2i+1} is 2i + 1.

Lemma 15. The product LC is an upper triangular matrix, with LC_{i,i} = 1 for all i ≥ 0, and LC_{i,i+1} = 2i + 1.

Proof. First, we observe that since L is lower triangular,

(LC)_{i,j} = ∑_{k=0}^{∞} L_{i,k}C_{k,j} = ∑_{k=0}^{i} L_{i,k}C_{k,j},

so that the matrix product LC is well-defined. Now, by definition of L and C,

(LC)_{i,j} = ∑_{k=0}^{i}(−1)^{i+k}\binom{i + k}{i − k}c_{k+j} = ∑_{k=j}^{i+j}(−1)^{i−j+k}\binom{i − j + k}{i + j − k}c_{k}.

When j < i, let t = i − j. Then i ≥ t ≥ 1, and the sum becomes

∑_{k=i−t}^{2i−t}(−1)^{k+t}\binom{k + t}{2i − t − k}c_{k},

which is 0 by Corollary 14. The other two statements similarly follow from Corollary 14.

We are now ready to prove Proposition 11.

Proof. (of Proposition 11). First, LC and U are both upper triangular with 1’s on the diagonal, so LCU is upper triangular with 1’s on the diagonal. Also, (LCU)^{t} = U^{t}C^{t}L^{t} = LC^{t}U. Since C is symmetric, this is LCU. Thus, LCU is also symmetric, so LCU is the identity.

Now, (LC{1})_{i,j} = 0 if i > j + 1. Since U_{i,j} = 0 for i > j, it follows easily that (LC{1}U)_{i,j} = 0 whenever i > j + 1. Moreover, when i ≥ 1, we have

(LC{1}U)_{i,i−1} = ∑_{k=0}^{∞}(LC{1})_{i,k}U_{k,i−1}

= ∑_{k=i−1}^{i−1}(LC{1})_{i,k}U_{k,i−1} = (LC{1})_{i,i−1}U_{i−1,i−1} = LC_{i,i}U_{i−1,i−1}.

By Lemma 15, this is 1. When i ≥ 1, we have

(LC{1}U)_{i,i} = ∑_{k=0}^{∞}(LC{1})_{i,k}U_{k,i}

= ∑_{k=i−1}^{i}(LC{1})_{i,k}U_{k,i} = (LC{1})_{i,i−1}U_{i−1,i} + (LC{1})_{i,i}U_{i,i}

= (LC)_{i,i}U_{i−1,i} + LC_{i,i+1}U_{i,i}.

By Lemma 15 and the definition of U, this is −(2i−1)+2i+1 = 2. Likewise, (LC{1}U)_{0,0} = (LC{1})_{0,0}U_{0,0} = (LC)_{0,1}U_{0,0} = 1. The rest of the claim follows since LC{1}U is symmetric.

We now turn to considering LC{k}U. The following definition will be useful.

Definition 16. Let S be the infinite matrix defined by S_{i,j} = δ_{i,j+1}, where δ is the Kronecker delta symbol.

We note that if A is an infinite matrix, then AS is the matrix obtained by removing the first column of A. In particular, if A is the Hankel matrix of a sequence {a_{i}}_{i=0}^{∞}, then AS is the Hankel matrix of the sequence {a_{i}}_{i=1}^{∞}. Thus, CS^{k} = C{k}.

Proposition 17. For any k ≥ 0, we have (LC{1}U)^{k} = LC{k}U.

Proof. We have seen already in Proposition 11 that LCU = I, so LC{0}U = (LC{1}U)^{0}. It is easy to check that if A and B are both upper triangular, then (AB)(n) = A(n)B(n). Thus, (LC)(n)U(n) is the n + 1 × n + 1 identity matrix. Thus, LC(n) = U(n)^{−1}, so (ULC)(n) = U(n)(LC)(n) is the n + 1 × n + 1 identity matrix for each n. Therefore, ULC is the infinite identity matrix. Thus,

(LC{1}U) = (LCSU)^{k} = LCS(ULCS)^{k−1}U
= LCS(S^{k−1})U = LCS^{k}U = LC{k}U.

We now can prove Proposition 12.

Proof. (of Proposition 12) We prove this by induction on k. The cases when k = 0 or k = 1 follow easily from Proposition 11. Now, suppose the claim holds when k = t ≥ 1. Then by Proposition 17 we have

LC{t + 1}U = (LC{1}U)^{t}(LC{1}U) = (LC{t}U)(LC{1}U).

Thus, we have

(LC{t + 1}U)_{i,j} = ∑_{l}(LC{t}U)_{i,l}(LC{1}U)_{l,j}.

If j ≥ 1, then by Proposition 11, we get

(LC{t + 1}U)_{i,j} = (LC{t}U)_{i,j−1} + 2(LC{t}U)_{i,j} + (LC{t}U)_{i,j+1}.

Now, assuming i + j ≥ t + 1, we have i + (j − 1) ≥ t, so by the inductive hypothesis, the above sum is

\binom{2t}{t + i − j + 1} + 2\binom{2t}{t + i − j} + \binom{2t}{t + i − j − 1}

= (\binom{2t}{t + i − j + 1} + \binom{2t}{t + i − j}) + (\binom{2t}{t + i − j} + \binom{2t}{t + i − j − 1})

= \binom{2t + 1}{t + i − j + 1} + \binom{2t + 1}{t + i − j} = \binom{2(t + 1)}{(t + 1) + i − j},

as needed.

On the other hand, if j = 0, then by Proposition 11, we get

(LC{t + 1}U)_{i,j} = ∑_{l}(LC{t}U)_{i,l}(LC{1}U)_{l,j} = (LC{t}U)_{i,0} + (LC{t}U)_{i,1}.

Now, since we may assume i + j ≥ t + 1, we have i ≥ t + 1, so by the inductive hypothesis, the above term is \binom{2t}{t+i} + \binom{2t}{t+i−1} = \binom{2t+1}{t+i}. If i = t + 1, then

\binom{2t + 1}{t + i} = 1 = \binom{2(t + 1)}{(t + 1) + i},

while if i > t + 1, then

\binom{2t + 1}{t + i} = 0 = \binom{2(t + 1)}{(t + 1) + i},

as needed.

4 Recurrence Relations

In this section, we make two observations about solutions to recurrence relations. The second observation, Lemma 20, is an easy application of the Cayley-Hamilton theorem to recurrence relations. The first observation, Lemma 19, describes a technique for showing that a given solution of a recurrence relation in fact satisfies a recurrence relation of lower order. An example will help to illustrate this idea.

Example 18. Suppose a sequence {x_{n}} satisfies the recurrence relation

a_{n+3} − 2a_{n+2} + a_{n} = 0,

and suppose that x_{2} = x_{1} + x_{0}. Then the sequence {x_{n}} satisfies the recurrence relation

a_{n+2} − a_{n+1} − a_{n} = 0.

To see this, define a new sequence {y_{n}} by y_{n} = x_{n+2} − x_{n+1} − x_{n}. Then

y_{n+1} − y_{n} = (x_{n+3} − x_{n+2} − x_{n+1}) − (x_{n+2} − x_{n+1} − x_{n})
= x_{n+3} − 2x_{n+2} + x_{n} = 0,

so y_{n+1} = y_{n} for all n. At the same time, y_{0} = x_{2} − x_{1} − x_{0} = 0. Thus, y_{n} = 0 for all n, so that x_{n+2} − x_{n+1} − x_{n} = 0 for all n.

To generalize the example above, recall that a recurrence relation

c_{k}a_{n+k} + c_{k−1}a_{n+k−1} + ⋯ + c_{1}a_{n+1} + c_{0}a_{n} = 0

has an associated characteristic polynomial

p(x) = c_{k}x^{k} + c_{k−1}x^{k−1} + ⋯ + c_{1}x + c_{0}.

In the following lemma, we suppose given two polynomials of degree k_{1} and k_{2} respectively:

p_{1}(x) = ∑_{j} c_{j,1}x^{j}, p_{2}(x) = ∑_{j} c_{j,2}x^{j}.

Here, the summations are over all integers, but c_{j,1} = 0 for all j > k_{1} and all j < 0, while c_{j,2} = 0 for all j > k_{2} and all j < 0. We let

q(x) = p_{1}(x) · p_{2}(x) = ∑_{j} (∑_{l} c_{l,1}c_{j−l,2}) x^{j}.

Lemma 19. Suppose given a sequence {x_{n}} such that for some positive integer m, we have

1. {x_{n}} satisfies the recurrence relation with characteristic polynomial q(x) for n ≥ m, and

2. For 0 ≤ n ≤ m + k_{1} − 1, we have ∑_{j} c_{j,2}x_{n+j} = 0. That is, for 0 ≤ n ≤ m + k_{1} − 1, {x_{n}} satisfies the recurrence relation with characteristic polynomial p_{2}(x).

Then {x_{n}} satisfies the recurrence relation with characteristic polynomial p_{2}(x) for all n ≥ 0.

Proof. Let y_{n} = ∑_{j} c_{j,2}x_{n+j}. Then

∑_{l} c_{l,1}y_{n+l} = ∑_{l} ∑_{j} c_{l,1}c_{j,2}x_{n+l+j} = ∑_{j} (∑_{l} c_{l,1}c_{j−l,2}) x_{n+j}.

By our first hypothesis, this last term is 0 whenever n ≥ m, so {y_{n}} satisfies the k_{1}^{th}-order homogeneous linear recurrence relation with characteristic polynomial p_{1}(x) for n ≥ m. By our second hypothesis, y_{n} = 0 for 0 ≤ n ≤ m + k_{1} − 1, which includes the k_{1} consecutive values of n beginning at m. It follows by induction that y_{n} = 0 for all n ≥ 0. Thus, {x_{n}} satisfies the recurrence relation with characteristic polynomial p_{2}(x).

Now, we turn to our application of the Cayley-Hamilton theorem. Consider a sequence {v⃗_{n}} of vectors in ℝ^{m}; we let v_{n}^{i} denote the i^{th} component of v⃗_{n}.

Lemma 20. Suppose {v⃗_{n}} satisfies the recurrence relation v⃗_{n+1} = Av⃗_{n}, where A is an m×m matrix. Then for each i ∈ {1, 2, …, m}, the sequence v_{n}^{i} satisfies a recurrence relation whose characteristic polynomial is equal to the characteristic polynomial of the matrix A, det(λI − A).

Proof. Let p(λ) = det(λI − A) = c_{m}λ^{m} + c_{m−1}λ^{m−1} + ⋯ + c_{0}. Then by the Cayley-Hamilton theorem, p(A) = 0, so for any n,

c_{m}A^{m}v⃗_{n} + c_{m−1}A^{m−1}v⃗_{n} + ⋯ + c_{0}v⃗_{n} = 0.

Since v⃗_{n+1} = Av⃗_{n} for all n, this yields

c_{m}v⃗_{n+m} + c_{m−1}v⃗_{n+m−1} + ⋯ + c_{0}v⃗_{n} = 0.

Now, taking the i^{th} component of the above equation yields the result.

5 Hyperdiagonal matrices

Just as Proposition 11 allowed us to study the Hankel transform of the sequence αc_{n} +βc_{n+1} in the proof of Theorem 2, so Proposition 12 allows us to investigate the Hankel transforms of more complicated linear combinations of Catalan numbers. Proposition 12 motivates studying a class of matrices which we now describe.

Definition 21. An infinite matrix M is k-hyperdiagonal if M_{i,j} = 0 whenever |j − i| > k, and for j + i ≥ k, M_{i,j} only depends on |j − i|. We let m_{t} and m_{−t} denote the value of M_{i,j} when |j − i| = t and j + i ≥ k (so m_{t} = 0 when t > k or t < −k.)

Example 22. By Proposition 12, the matrix LC\{k\}U is k-hyperdiagonal, with m_{t} = \binom{2k}{k−t} = \binom{2k}{k+t}.

In this section, we will investigate the determinants of the sequence of upper left (n + 1) × (n + 1) submatrices of a k-hyperdiagonal matrix M.

Notation 23. Suppose M is a k-hyperdiagonal infinite matrix, and let r⃗ denote the integervalued vector ⟨r_{1}, r_{2}, ⋯, r_{k}⟩, where −k < r_{1} < r_{2} < ⋯ < r_{k} ≤ k. Let M(n)r⃗ denote the (n + 1) × (n + 1) matrix whose (i, j) entry is given by

\begin{cases}M_{i,j}, & 0 ≤ i ≤ n and 0 ≤ j < max\{0, n − k + 1\}; \\ M_{i,n+r_{j−(n−k)}}, & 0 ≤ i ≤ n and max\{0, n − k + 1\} ≤ j ≤ n. \end{cases}

Thus, when n ≥ k, M(n)r⃗ is obtained by removing all rows of M past the n^{th} row, retaining the 0^{th} through (n − k)^{th} columns, removing all columns past the (n + k)^{th} column, and retaining the (n + r_{i})^{th} columns for 1 ≤ i ≤ k.

Remark 24. If r⃗ = ⟨1 − k, 2 − k, 3 − k, …, 0⟩, then M(n)r⃗ = M(n), where we recall from Notation 10 that M(n) denotes is the upper left (n + 1) × (n + 1)-submatrix of M. Indeed, in this case, r_{i} = i − k, so n + r_{j−(n−k)} = j, whence M_{i,n+r_{j−(n−k)}} = M_{i,j}.

Example 25. Suppose k = 2 and

M = (\begin{matrix}∗ & ∗ & x & 0 & 0 & 0 & 0 & ⋯ \\ ∗ & z & y & x & 0 & 0 & 0 & ⋯ \\ x & y & z & y & x & 0 & 0 & ⋯ \\ 0 & x & y & z & y & x & 0 & ⋯ \\ 0 & 0 & x & y & z & y & x & ⋯ \\ 0 & 0 & 0 & x & y & z & y & ⋯ \\ 0 & 0 & 0 & 0 & x & y & z & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Then

M(6)_{⟨0,2⟩} = (\begin{matrix}∗ & ∗ & x & 0 & 0 & 0 & 0 \\ ∗ & z & y & x & 0 & 0 & 0 \\ x & y & z & y & x & 0 & 0 \\ 0 & x & y & z & y & 0 & 0 \\ 0 & 0 & x & y & z & x & 0 \\ 0 & 0 & 0 & x & y & y & 0 \\ 0 & 0 & 0 & 0 & x & z & x \end{matrix}) .

Here, we have retained columns numbered 0 through 4, together with columns numbered 6 = 6 + 0 and 8 = 6 + 2. As another example, if we retain columns numbered 5 = 6 + (−1) and 7 = 6 + 1, we get

M(6)_{⟨−1,1⟩} = (\begin{matrix}∗ & ∗ & x & 0 & 0 & 0 & 0 \\ ∗ & z & y & x & 0 & 0 & 0 \\ x & y & z & y & x & 0 & 0 \\ 0 & x & y & z & y & x & 0 \\ 0 & 0 & x & y & z & y & 0 \\ 0 & 0 & 0 & x & y & z & x \\ 0 & 0 & 0 & 0 & x & y & y \end{matrix}) .

Observe that the determinant of M(6)_{⟨0,2⟩} is equal to the product of x and the determinant of M(5)_{⟨−1,1⟩}. Likewise, the determinant of M(6)_{⟨−1,1⟩} is

x (det(M(5)_{⟨0,2⟩})) − y (det(M(5)_{⟨−1,2⟩})) + y (det(M(5)_{⟨−1,0⟩})) .

As we will shortly show, the determinant of M(n)r⃗ can be expressed as a linear combination of determinants of the form M(n−1)s⃗ for various vectors s⃗. We now describe how the needed vectors s⃗ can be obtained from r⃗.

Notation 26. Suppose 0 ≤ l ≤ k, and suppose given a vector r⃗ with

−k < r_{1} < r_{2} < ⋯ < r_{k} ≤ k.

If r_{k} < k or l = k, let δ_{l}r⃗ be the vector obtained by inserting −k as a 0^{th} term, removing the l^{th} term, and then adding one to all the components of r⃗. If r_{k} = k and l < k, then δ_{l}r⃗ is undefined.

Thus, if l = k, then

δ_{l}r⃗ = ⟨−k + 1, r_{1} + 1, r_{2} + 1, ⋯, r_{k−1} + 1⟩.

When 1 ≤ l ≤ k − 1, and r_{k} < k, we have

δ_{l}r⃗ = ⟨−k + 1, r_{1} + 1, r_{2} + 1, ⋯, r_{l−1} + 1, r_{l+1} + 1, ⋯, r_{k} + 1⟩.

If l = 0 and r_{k} < k, then

δ_{0}r⃗ = ⟨r_{1} + 1, r_{2} + 1, ⋯, r_{k} + 1⟩.

Lemma 27. Suppose 0 ≤ l ≤ k, n ≥ k − l, and r⃗ is a vector with

−k < r_{1} < r_{2} < ⋯ < r_{k} ≤ k.

If r_{k} = k and l < k, then removing the n^{th} row and the (n − k + l)^{th} column of M(n)r⃗ yields a matrix with a column of all zeros. If r_{k} < k or l = k, then removing the n^{th} row and the (n − k + l)^{th} column of M(n)r⃗ yields M(n − 1)_{δ_{l}r⃗}.

Proof. First, if r_{k} = k and l < k, then for 0 ≤ i ≤ n − 1, the (i, n)-entry of M(n)r⃗ is M_{i,n+k}, which is 0 since n + k − i > k and M is k-hyperdiagonal. Thus, since n − k + l < n, it follows that removing the n^{th} row and (n − k + l)^{th} of M(n)r⃗ yields a matrix whose last column is all 0’s.

Now, suppose r_{k} < k or l = k. Let M′ denote the n × n matrix obtained by removing the n^{th} row and the (n − k + l)^{th} column from M(n)r⃗. Then M′_{i,j} is equal to the (i, j) entry of M(n)r⃗ when 0 ≤ j < n − k + l and is equal to the (i, j + 1) entry of M(n)r⃗ when n − k + l ≤ j ≤ n − 1. Thus,

M′_{i,j} = \begin{cases}M_{i,j}, & if 0 ≤ i ≤ n − 1 and 0 ≤ j < max\{0, n − k + 1\}; \\ M_{i,n+r_{j−(n−k)}}, & if 0 ≤ i ≤ n − 1 and max\{0, n − k + 1\} ≤ j < n − k + l; \\ M_{i,n+r_{j+1−(n−k)}}, & if 0 ≤ i ≤ n − 1 and n − k + l ≤ j ≤ n − 1. \end{cases}

Now, for a sequence −k < s_{1} < s_{2} < ⋯ < s_{k} ≤ k, the (i, j) entry of the n × n matrix M(n − 1)s⃗ is

\begin{cases}M_{i,j}, & if 0 ≤ i ≤ n − 1 and 0 ≤ j < max\{0, n − k\}; \\ M_{i,(n−1)+s_{j−(n−1−k)}}, & if 0 ≤ i ≤ n − 1 and max\{0, n − k\} ≤ j ≤ n − 1. \end{cases}

When s_{1} = −k + 1 and j = n − k, M_{i,(n−1)+s_{j−(n−1−k)}} = M_{i,j}, so the above can be rewritten as

\begin{cases}M_{i,j}, & if 0 ≤ i ≤ n − 1 and 0 ≤ j < max\{0, n − k + 1\}; \\ M_{i,(n−1)+s_{j−(n−1−k)}}, & if 0 ≤ i ≤ n − 1 and max\{0, n − k + 1\} < j ≤ n − 1. \end{cases}

If we set s⃗ = δ_{l}r⃗, then we see that M(n − 1)s⃗ = M′, as needed.

Notation 28. Let d(M, r⃗)_{n} = det(M(n)r⃗). In general, there are \binom{2k}{k} vectors r⃗ with −k < r_{1} < r_{2} < ⋯ < r_{k} ≤ k, and we will order these lexicographically, starting from ⟨−k+1, −k+ 2, ⋯, 0⟩ and ending at ⟨1, 2, 3, ⋯, k⟩. For a fixed value of n, the set of numbers d(M, r⃗)_{n} thus forms a column vector of length \binom{2k}{k}, which we will denote d(M)_{n}.

Corollary 29. Suppose n ≥ k, and suppose r⃗ = ⟨r_{1}, r_{2}, ⋯, r_{k}⟩ where

−k < r_{1} < r_{2} < ⋯ < r_{k} < k.

Let r_{0} = −k. Then

d(M, r⃗)_{n} = ∑_{l=0}^{k}(−1)^{k−l}m_{r_{l}}d(M, δ_{l}r⃗)_{n−1}.

If r_{k} = k, then d(M, r⃗)_{n} = m_{r_{k}}d(M, δ_{k}r⃗)_{n−1}.

Proof. This follows immediately from Lemma 27 using cofactor expansion along the bottom row.

Using Corollary 29, we may find a recurrence relation for the sequence d(M)_{n} in ℝ^{\binom{2k}{k}}.

Example 30. Suppose k = 1. Then there are 2 permissible vectors r⃗ of length k = 1, namely ⟨0⟩ and ⟨1⟩. By Corollary 29, we have for n ≥ 1

d(M, ⟨0⟩)_{n} = −m_{1}d(M, ⟨1⟩)_{n−1} + m_{0}d(M, ⟨0⟩)_{n−1},

and

d(M, ⟨1⟩)_{n} = m_{1}d(M, ⟨0⟩)_{n−1}.

We will write z, y for m_{0}, m_{1} respectively. Then, the system of equations above can be written in matrix form as

d(M)_{n} = (\begin{matrix}z & −y \\ y & 0 \end{matrix}) d(M)_{n−1}

for all n ≥ 1. Shifting indices, we have for all n ≥ 0:

d(M)_{n+1} = (\begin{matrix}z & −y \\ y & 0 \end{matrix}) d(M)_{n}.

By Lemma 20, for each permissible vector r⃗, the sequence d(M, r⃗)_{n} satisfies a recurrence relation with characteristic polynomial equal to the characteristic polynomial of the matrix

(\begin{matrix}z & −y \\ y & 0 \end{matrix}), which is λ^{2} − zλ + y^{2}. By Remark 24, the sequence of determinants det(M(n))

coincides with the sequence d(M, ⟨0⟩)_{n}. Thus, the sequence of determinants det(M(n)) satisfies the recurrence relation with characteristic polynomial equal to λ^{2} − zλ + y^{2}.

Example 31. Now suppose k = 2. Then there are 6 permissible vectors r⃗ of length k = 2, namely ⟨−1, 0⟩, ⟨−1, 1⟩, ⟨−1, 2⟩, ⟨0, 1⟩, ⟨0, 2⟩, ⟨1, 2⟩. Now we will write z, y, x for m_{0}, m_{1}, m_{2} respectively. Using Corollary 29 again (and again shifting indices), we can compute that for n ≥ 1

d(M)_{n+1} = (\begin{matrix}z & −y & 0 & x & 0 & 0 \\ y & 0 & −y & 0 & x & 0 \\ x & 0 & 0 & 0 & 0 & 0 \\ 0 & y & −z & 0 & 0 & x \\ 0 & x & 0 & 0 & 0 & 0 \\ 0 & 0 & x & 0 & 0 & 0 \end{matrix}) d(M)_{n}.

Here, the characteristic polynomial of the matrix in the above equation is

λ^{6} − zλ^{5} + (y^{2} − x^{2})λ^{4} + (2x^{2}z − 2xy^{2})λ^{3} + (x^{2}y^{2} − x^{4})λ^{2} − x^{4}zλ + x^{6},

which factors as

(λ − x)^{2}(λ^{4} + (2x − z)λ^{3} + (2x^{2} + y^{2} − 2xz)λ^{2} + (2x^{3} − x^{2}z)λ + x^{4}).

Again, it follows from Lemma 20 and Remark 24 that the sequence of determinants det(M(n)) satisfies a recurrence relation with the above characteristic polynomial for n ≥ 1.

Example 32. Now suppose k = 3. In this case, there are \binom{6}{3} = 20 permissible vectors r⃗ of length 3. We then use Corollary 29 as in Example 31 above, and we get a 20 × 20 matrix A such that

d(M)_{n+1} = A · d(M)_{n}

for all n ≥ 2. The matrix A can be expressed as follows, where we write z, y, x, w for m_{0}, m_{1}, m_{2}, m_{3} respectively.

( \begin{matrix}z & −y & 0 & 0 & x & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ y & 0 & −y & 0 & 0 & x & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x & 0 & 0 & −y & 0 & 0 & x & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & y & −z & 0 & 0 & 0 & 0 & x & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & x & 0 & −z & 0 & 0 & 0 & 0 & x & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 & 0 & 0 \\ 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & x & −y & 0 & 0 & 0 & 0 & 0 & x & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 & 0 \\ 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & y & −z & 0 & y & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & x & 0 & −z & 0 & y & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −w & 0 & 0 \\ 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & x & −y & 0 & 0 & y & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −w & 0 \\ 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & x & −y & z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −w \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & w & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} )

The characteristic polynomial of the above matrix factors as the product

(λ^{6} − xλ^{5} + wyλ^{4} − w^{2}zλ^{3} + w^{3}yλ^{2} − w^{4}xλ + w^{6})^{2}·
(λ^{8} + (2x − z)λ^{7} + (w^{2} + 2x^{2} − 2wy + y^{2} − 2xz)λ^{6}
+(2w^{2}x + 2x^{3} − 4wxy − w^{2}z − x^{2}z + 2wyz)λ^{5}
+(4w^{2}x^{2} + x^{4} − 4w^{3}y − 4wx^{2}y + 2w^{2}y^{2} + w^{2}z^{2})λ^{4}
+(2w^{4}x + 2w^{2}x^{3} − 4w^{3}xy − w^{4}z − w^{2}x^{2}z + 2w^{3}yz)λ^{3}
+(w^{6} + 2w^{4}x^{2} − 2w^{5}y + w^{4}y^{2} − 2w^{4}xz)λ^{2} + (2w^{6}x − w^{6}z)λ + w^{8}

Again, it follows from Lemma 20 and Remark 24 that the sequence of determinants det(M(n)) satisfies a recurrence relation with the above characteristic polynomial for n ≥ 2.

6 Proofs of Theorems 3 and 4

Before turning to the proofs of Theorems 3 and 4, we give another proof of Theorem 2. As in our previous proof, we let {h_{n}} denote the Hankel transform of the sequence αc_{n} + βc_{n+1}, and we recall that

h_{n} = det((αLCU + βLC{1}U)(n)).

Thus, if we let M = αLCU + βLC{1}U, then h_{n} = det(M(n)). Now, by Proposition 12, the matrix M is a 1-hyperdiagonal matrix, with m_{1} = β and m_{0} = 2β + α. By Example 30, substituting y = β and z = 2β + α, the sequence det(M(n)) satisfies a recurrence relation with characteristic polynomial λ^{2} − zλ + y^{2} for all n ≥ 0. That is, for all n ≥ 0, we have

h_{n+2} − (2β + α)h_{n+1} + β^{2}h_{n} = 0.

Our proofs of Theorems 3 and 4 follow a similar pattern.

Proof. (Theorem 3). We let {h_{n}} denote the Hankel transform of the sequence αc_{n} +βc_{n+1} + γc_{n+2}. We then have

h_{n} = det((αLCU + βLC{1}U + γLC{2}U)(n)).

Thus, if we let

M = αLCU + βLC{1}U + γLC{2}U,

then h_{n} = det(M(n)). Now, by Proposition 12, the matrix M is a 2-hyperdiagonal matrix, with

m_{2} = γ, m_{1} = 4γ + β, m_{0} = 6γ + 2β + α.

By Example 31, substituting x = γ, y = 4γ + β and z = 6γ + 2β + α, we find that for n ≥ 1, the sequence h_{n} = det(M(n)) satisfies the recurrence relation whose characteristic polynomial is the product of (λ − γ)^{2} and

λ^{4} + (−α − 2β − 4γ)λ^{3} + (β^{2} − 2αγ + 4βγ + 6γ^{2})λ^{2} + (−α − 2β − 4γ)γ^{2}λ + γ^{4}.

We compute directly that for 0 ≤ n ≤ 2, h_{n} satisfies the recurrence relation with characteristic polynomial

λ^{4} + (−α − 2β − 4γ)λ^{3} + (β^{2} − 2αγ + 4βγ + 6γ^{2})λ^{2} + (−α − 2β − 4γ)γ^{2}λ + γ^{4}.

Our result now follows from Lemma 19 with m = 1, k_{1} = 2, and k_{2} = 4.

Proof. (Theorem 4). We let {h_{n}} denote the Hankel transform of the sequence

αc_{n} + βc_{n+1} + γc_{n+2} + δc_{n+3}.

We then have

h_{n} = det((αLCU + βLC{1}U + γLC{2}U + δLC{3}U)(n)).

Thus, if we let

M = αLCU + βLC{1}U + γLC{2}U + δLC{3}U,

then h_{n} = det(M(n)). Now, by Proposition 12, the matrix M is a 3-hyperdiagonal matrix, with

m_{3} = δ, m_{2} = 6δ + γ, m_{1} = 15δ + 4γ + β, m_{0} = 20δ + 6γ + 2β + α.

By Example 32, substituting w = δ, x = 6δ+γ, y = 15δ+4γ+β and z = 20δ+6γ+2β+α, we find that the sequence h_{n} = det(M(n)) satisfies the recurrence relation whose characteristic polynomial factors as the product of the square of

(λ^{6} + (−γ − 6δ)λ^{5} + (β + 4γ + 15δ)δλ^{4} + (−α − 2β − 6γ − 20δ)δ^{2}λ^{3} + (β + 4γ + 15δ)δ^{3}λ^{2} + (−γ − 6δ)δ^{4} + δ^{6})

and

λ^{8}
+(−α − 2β − 4γ − 8δ)λ^{7}
+(β^{2} − 2αγ + 4βγ + 6γ^{2} − 12αδ + 4βδ + 24γδ + 28δ^{2})λ^{6}
+(−αγ^{2} − 2βγ^{2} − 4γ^{3} + 2αβδ + 4β^{2}δ − 4αγδ − 24γ^{2}δ − 7αδ^{2} + 2βδ^{2} − 60γδ^{2} − 56δ^{3})λ^{5}

+(γ^{4} − 4βγ^{2}δ + 8γ^{3}δ + α^{2}δ^{2} + 4αβδ^{2} + 6β^{2}δ^{2} + 12αγδ^{2} − 8βγδ^{2} + 36γ^{2}δ^{2} + 40αδ^{3} − 8βδ^{3} + 80γδ^{3} + 70δ^{4})λ^{4}

+(−αγ^{2} − 2βγ^{2} − 4γ^{3} + 2αβδ + 4β^{2}δ − 4αγδ − 24γ^{2}δ − 7αδ^{2} + 2βδ^{2} − 60γδ^{2} − 56δ^{3})δ^{2}λ^{3}
+(β^{2} − 2αγ + 4βγ + 6γ^{2} − 12αδ + 4βδ + 24γδ + 28δ^{2})δ^{4}λ^{2}
+(−α − 2β − 4γ − 8δ)δ^{6}λ^{1}
+δ^{8}λ^{0}

We compute directly that for 0 ≤ n ≤ 13, h_{n} satisfies the recurrence relation with characteristic polynomial equal to the second polynomial above. Our result now follows from Lemma 19 with m = 2, k_{1} = 12, and k_{2} = 8.

References

[1] I. Bajunaid, J. M. Cohen, F. Colonna, and D. Signman, Function series, Catalan numbers, and Random walks on trees, Amer. Math. Monthly 112 (2005), 765–785.

[2] A. T. Benjamin, N. T. Cameron, J. J. Quinn, and C. R. Yerger, Catalan determinants — a combinatorial approach, Congr. Numer. 200 (2010), 27–34.

[3] M. Chamberland and C. French, Generalized Catalan numbers and generalized Hankel transformations, J. Integer Seq. 10 (2007), Article 07.1.1.

[4] K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29–38.

[5] A. Cvetković, P. Rajković, and M. Ivković, Catalan numbers, and Hankel transform, and Fibonacci numbers, J. Integer Seq. 5 (2002), Article 02.1.3.

[6] M. E. Mays and J. Wojciechowski, A determinant property of Catalan numbers. Discrete Math. 211 (2000), 125–133.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

   cally at http://oeis.org.

2010 Mathematics Subject Classification: Primary: 11C20; Secondary 11B37, 11B75, 15A15. Keywords: Hankel transform, Catalan Numbers, recurrence relations, integer sequences.

(Concerned with sequences \underline{A000159}, \underline{A014523}, and \underline{A103433}.)

Received January 28 2011; revised version received April 5 2011. Published in Journal of Integer Sequences, April 20 2011.

Return to Journal of Integer Sequences home page.