Generalized Catalan Numbers and Generalized Hankel Transformations

Marc Chamberland and Christopher French Department of Mathematics and Statistics Grinnell College Grinnell, IA 50112 USA

                  chamberl@math.grinnell.edu
                   frenchc@math.grinnell.edu

Abstract

Cvetković, Rajković and Ivković proved that the Hankel transformation of the sequence of sums of adjacent Catalan numbers is a sequence of every other Fibonacci number. In this paper, an elementary proof is given and a generalization to sequences of generalized Catalan numbers.

1 Introduction

Given a sequence of numbers S = {s_{0}, s_{1}, s_{2}, …}, the Hankel matrix of order n generated by the sequence S is the n×n-matrix whose (i, j)-entry is given by s_{i+j} for 0 ≤ i, j ≤ n−1. The Hankel transform of the sequence S is the sequence of determinants of the Hankel matrices generated by S.

Suppose that

a_{n} = \frac{1}{n + 1}\binom{2n}{n} + \frac{1}{n + 2}\binom{2n + 2}{n + 1},

so that a_{n} is the sum of the n^{th} and n + 1^{st} Catalan numbers. Then the Hankel transform of {a_{0}, a_{1}, a_{2}, …} begins 2, 5, 13, 34, . . .. Layman first conjectured in the On-Line Encyclopedia of Integer Sequences ([4], see sequence A001906) that this sequence consists of every other Fibonacci number, and subsequently Cvetković, Rajković and Ivković [2] proved this conjecture. The current paper arose out of an attempt to understand and generalize this result.

The Catalan numbers c_{n} = \frac{1}{n+1} \binom{2n}{n} uniquely satisfy the nonlinear recurrence relation

c_{n+1} = ∑_{r=0}^{n} c_{n−r}c_{r}, c_{0} = 1.

This sequence has been generalized to the recurrence relation

c_{n+1,k} = ∑_{r=0}^{⌊ \frac{n}{k−1} ⌋}(c_{n−r(k−1),k}) ∗ (c_{r(k−1),k}), c_{0,k} = 1.

When k = 2, c_{n,k} is simply the n^{th} Catalan number. It can be shown ([3]) that

c_{(k−1)n+l−1,k} = \frac{l}{kn + l}\binom{kn + l}{n}, 1 ≤ l ≤ k − 1.

Some notation is necessary to state our more general result. Let a′_{n,k} = c_{n,k} + c_{n+1,k} and a′′_{n,k} = c_{n,k} + c_{n+k−1,k}. Note that a′_{n,2} and a′′_{n,2} both coincide with the sequence a_{n} described above. Let A′_{n,k} and A′′_{n,k} be the n × n-matrices whose (i, j)-entries are given respectively by a′_{(k−1)i+j,k} and a′′_{(k−1)i+j,k} for 0 ≤ i, j ≤ n − 1. Let F′_{n,k} be the sequence determined by the recurrence relation

F′_{n+1,k} = F′_{n−(k−2),k} + F′_{n−(k−1),k}

with initial conditions

F′_{1,k} = F′_{2,k} = ⋯ = F′_{k,k} = 1,

and let F′′_{n,k} be the sequence determined by

F′′_{n+1,k} = F′′_{n,k} + F′′_{n−(k−1),k}

with the same initial conditions. Note that F′_{n,2} = F′′_{n,2} = F_{n} (the n^{th} Fibonacci number). We can now state our main theorem:

Theorem 1.1.

det(A′_{n,k}) = F′_{kn+1,k}, and det(A′′_{n,k}) = F′′_{kn+1,k}.

Note that when k = 2, our theorem reduces to the result of Cvetković, Rajković and Ivković [2].

In Section 2, we find LU decompositions of the inverses of a sequence of matrices C_{n,k} obtained from the generalized Catalan numbers. It turns out that these take surprisingly simple forms, and can be used to prove our main result, as seen in Section 3.

2 Generalized Catalan numbers

Definition 2.1. Let C_{n,k} be the n × n matrix whose (i, j) entry is given by c_{(k−1)i+j,k} for 0 ≤ i, j ≤ n − 1. Let L_{n,k} be the n × n matrix whose (i, j) entry is given by (−1)^{i−j}\binom{i+(k−1)j}{i−j}

for 0 ≤ i, j ≤ n−1. Let U_{n,k} be the n×n matrix whose (i, j) entry is given by (−1)^{j−i}\binom{j+⌊ \frac{i}{k−1} ⌋}{j−i} for 0 ≤ i, j ≤ n − 1.

It is easy to see that L_{n,k} is lower triangular with 1’s on the diagonal and U_{n,k} is upper triangular with 1’s on the diagonal. Our goal in this section is to prove that the product L_{n,k}C_{n,k}U_{n,k} is equal to the identity matrix.

Our first step is to show that the product L_{n,k}C_{n,k} is upper triangular with 1’s on the diagonal. We will then show that C_{n,k}U_{n,k} is lower triangular with 1’s on the diagonal. From these two facts, the result will follow formally.

The proof makes use of certain generating functions.

Definition 2.2. For 1 ≤ l ≤ k − 1, let g_{l}(z) = ∑_{n=0}^{∞} c_{(k−1)n+l−1}z^{n}, and let g(z) = g_{1}(z).

It follows from the recurrence relation defining c_{n,k} that g_{l}(z)g(z) = g_{l+1}(z) for 1 ≤ l ≤ k − 2, and also that g_{k−1}(z)g(z) = \frac{g(z)−1}{z}. Thus,

g(z)^{l} = g_{l}(z), 1 ≤ l ≤ k − 1  (1)

and

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

Bajunaid, Cohen, Colonna, and Signman [1] prove that the function

f(z) := (1 − z)g(z(1 − z)^{k−1})  (3)

converges to the constant function at 1 for z close to 0. This is then used to show that

∑_{n=⌈m/k⌉}^{m}(−1)^{n}c_{(k−1)n,k}\binom{kn − n}{kn − m} = (−1)^{m}.

(Note that the cited reference refers to c_{(k−1)n,k} as a_{n,k}.) We use exactly the same technique to prove the following slightly stronger result.

Lemma 2.1. Suppose i and j are nonnegative integers. Then

∑_{m=0}^{i}(−1)^{i−m}\binom{i + (k − 1)m}{i − m}c_{(k−1)m+j,k} = \begin{cases}0, & j < i; \\ 1, & j = i. \end{cases}

Proof. It follows from Equation 1 that,

f_{l}(z) := (1 − z)^{l}g_{l}(z(1 − z)^{k−1})  (4)

is equal to f(z)^{l}, and therefore (by 3) converges to 1 for z close to 0. From this, we find that for any s ≥ 0, the series

∑_{m=0}^{∞} c_{(k−1)m+(l−1),k}[z(1 − z)^{k−1}]^{m}(1 − z)^{s} = (1 − z)^{s−l}f_{l}(z)

converges to (1 − z)^{s−l} for z close to 0. Expanding (1 − z)^{m(k−1)+s}, we can rewrite this sum as

∑_{m=0}^{∞} c_{(k−1)m+(l−1),k} ( ∑_{t=0}^{mk−m+s}(−1)^{t}\binom{(k − 1)m + s}{t}z^{t+m})

= ∑_{n=0}^{∞} ( ∑_{m=⌈ \frac{n−s}{k} ⌉}^{n}(−1)^{n−m}\binom{(k − 1)m + s}{n − m}c_{(k−1)m+(l−1),k}) z^{n}.

Therefore, if n > s − l

∑_{m=⌈ \frac{n−s}{k} ⌉}^{n}(−1)^{n−m}\binom{(k − 1)m + s}{n − m}c_{(k−1)m+(l−1),k} = \begin{cases}0, & s > l − 1; \\ 1, & s = l − 1. \end{cases}

Now, by the division algorithm, we may write j as (k −1)r +(l−1), for some nonnegative integer r and some l with 1 ≤ l ≤ k − 1. Letting s = i − (k − 1)r and n = i + r, gives

∑_{m=r}^{i+r}(−1)^{i−(m−r)}\binom{(k − 1)(m − r) + i}{n − m}c_{(k−1)(m−r)+j,k} = \begin{cases}0, & j < i; \\ 1, & j = i. \end{cases}

The result now follows by an index shift. Corollary 2.1. The product L_{n,k}C_{n,k} is upper triangular with 1’s on the diagonal. Proof. The (i, j) entry of L_{n,k}C_{n,k} is

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

We now turn to consider the product C_{n,k}U_{n,k}. Lemma 2.2.

∑_{m=0}^{j} c_{(k−1)i+m,k}(−1)^{j−m}\binom{j + ⌊\frac{m}{k−1}⌋}{j − m} = \begin{cases}0, & i < j; \\ 1, & i = j. \end{cases}

Proof. By Equation 2

∑_{l=0}^{k−1} (zg(z^{k−1}(1 − z)))^{l} = \frac{(zg(z^{k−1}(1 − z)))^{k} − 1}{zg(z^{k−1}(1 − z)) − 1} = \frac{z^{k} \frac{g(z^{k−1}(1−z))−1}{z^{k−1}(1−z)} − 1}{zg(z^{k−1}(1 − z)) − 1} = \frac{1}{1 − z}

for z close to 0. It follows by Equation 1 that

∑_{l=0}^{k−1} z^{l}g_{l}(z^{k−1}(1 − z)) = \frac{1}{1 − z} ,

so subtracting 1, dividing by z, and multiplying by (1 − z)^{s} gives

∑_{l=1}^{k−1}(1 − z)^{s}z^{l−1}g_{l}(z^{k−1}(1 − z)) = (1 − z)^{s−1}.

Now,

(1 − z)^{s}z^{l−1}g_{l}(z^{k−1}(1 − z)) = ∑_{p=0}^{∞} c_{(k−1)p+l−1,k}(1 − z)^{p+s}z^{p(k−1)+l−1}

= ∑_{p=0}^{∞} c_{(k−1)p+l−1,k} ∑_{t=0}^{p+s}(−1)^{t}\binom{p + s}{t}z^{p(k−1)+l−1+t}

= ∑_{n=0}^{∞} (∑_{p}(−1)^{n−p(k−1)−(l−1)}\binom{p + s}{n − p(k − 1) − (l − 1)}c_{(k−1)p+l−1,k}) z^{n}.

Therefore,

∑_{l=1}^{k−1}(1 − z)^{s}z^{l−1}g_{l}(z^{k−1}(1 − z)) = ∑_{n=0}^{∞} (∑_{m}(−1)^{n−m}\binom{s + ⌊\frac{m}{k−1}⌋}{n − m}c_{m,k}) z^{n}.

Here, we have used the division algorithm to substitute m = p(k − 1) + l − 1, where 1 ≤ l ≤ k − 1. So,

∑_{m}(−1)^{n−m}\binom{s + ⌊\frac{m}{k−1}⌋}{n − m}c_{m,k} = \begin{cases}0, & n ≥ s > 0; \\ 1, & s = 0. \end{cases}

Letting s = j − i, n = j + (k − 1)i and shifting index yields the result.

Corollary 2.2. The product C_{n,k}U_{n,k} is lower triangular with 1’s on the diagonal.

Theorem 2.1. The product L_{n,k}C_{n,k}U_{n,k} is equal to the identity matrix.

Proof. By Corollaries 2.1 and 2.2, the products L_{n,k}^{−1}(L_{n,k}C_{n,k}) and (C_{n,k}U_{n,k})U_{n,k}^{−1} are both LU decompositions of C_{n,k}. By uniqueness of LU decompositions, L_{n,k}^{−1} = C_{n,k}U_{n,k}.

3 Proof of the Main Theorem

In this section, we prove our main result, which will follow from two additional lemmas.

Lemma 3.1. The determinant of the (n − 1) × (n − 1) minor of C_{n,k} obtained by removing the final column and the jth row is \binom{n−1+(k−1)j}{n−1−j}. The determinant of the (n − 1) × (n − 1)

minor of C_{n,k} obtained by removing the final row and the ith column is \binom{n−1+⌊ \frac{i}{k−1} ⌋}{n−1−i}.

Proof. Since the determinant of L_{n,k} and U_{n,k} are both 1, the determinant of C_{n,k} is 1, so C_{n,k}^{−1} is equal to the adjoint of C_{n,k}. Since C_{n,k}^{−1} = U_{n,k}L_{n,k}, the final row of the adjoing of C_{n,k} is equal to the final row of L_{n,k} and the final column of the adjoing of C_{n,k} is equal to the final column of U_{n,k}. Now the (i, j) entry in the adjoint of C_{n,k} is the product of (−1)^{i+j} and the determinant of the (n − 1) × (n − 1) minor of C_{n,k} obtained by removing the ith column and the jth row. The claim follows.

Lemma 3.2. The determinants of A′_{n,k} and A′′_{n,k} are respectively given by

∑_{i=0}^{n} \binom{n + ⌊\frac{i}{k−1}⌋}{n − i}

and

∑_{j=0}^{n} \binom{n + (k − 1)j}{n − j}.

Proof. We consider only the determinant of A′_{n,k}, the other argument being similar. For each j between 1 and n + 1, let c_{j} be the column vector consisting of the first n terms in the jth row of C_{n+1,k}. Then the jth column vector of A′_{n,k} is c_{j} + c_{j+1}. Therefore, the determinant of A′_{n,k} could be written as the sum of the determinants of 2^{n} matrices, where the jth column vector of each matrix is either c_{j} or c_{j+1}. Most of these determinants are zero, since the determinant of any matrix with two identical column vectors is zero. The nonzero determinants belong to those matrices whose column vectors are n distinct vectors from the set {c_{1}, c_{2}, …, c_{n+1}}, in order. But these are just the determinants of the minors of C_{n+1,k} obtained by removing the final row and one of the columns. The result follows by Lemma 3.1.

We now prove Theorem 1.1.

Proof. For n ≥ 0 and 1 ≤ l ≤ k, let G′_{kn+l,k} = ∑_{i=0}^{n} \binom{n+⌊ \frac{i+l−1}{k−1} ⌋}{n−i}. We now show that G′_{kn+l,k} = F′_{kn+l} for all n ≥ 0, 1 ≤ l ≤ k. This follows from the following three observations.

1. For 1 ≤ l ≤ k, G′_{l,k} = 1.

2. For 1 ≤ l ≤ k − 1,

G′_{kn+l,k} + G′_{kn+l+1,k} = ∑_{i=0}^{n} \binom{n + ⌊\frac{i+l−1}{k−1}⌋}{n − i} + ∑_{i=0}^{n} \binom{n + ⌊\frac{i+l}{k−1}⌋}{n − i}

= ∑_{i=0}^{n} \binom{n + ⌊\frac{i+l−1}{k−1}⌋}{n − i} + ∑_{i=1}^{n+1} \binom{n + ⌊\frac{i−1+l}{k−1}⌋}{n − (i − 1)} = ∑_{i=0}^{n+1} \binom{n + 1 + ⌊\frac{i+l−1}{k−1}⌋}{n − i} = G′_{k(n+1)+l,k}.

3.

G′_{kn+k,k} + G′_{k(n+1)+1,k} = ∑_{i=0}^{n} \binom{n + ⌊\frac{i+k−1}{k−1}⌋}{n − i} + ∑_{i=0}^{n+1} \binom{n + 1 + ⌊\frac{i}{k−1}⌋}{n + 1 − i}

= ∑_{i=0}^{n+1} (\binom{n + 1 + ⌊\frac{i}{k−1}⌋}{n − i} + \binom{n + 1 + ⌊\frac{i}{k−1}⌋}{n + 1 − i})

= ∑_{i=0}^{n+1} \binom{n + 2 + ⌊\frac{i}{k−1}⌋}{n + 1 − i} = ∑_{i=0}^{n+1} \binom{n + 1 + ⌊\frac{i+k−1}{k−1}⌋}{n + 1 − i} = G′_{k(n+1)+k,k}.

Now for n ≥ 0 and 1 ≤ l ≤ k, let G′′_{kn+l,k} = ∑_{j=0}^{n} \binom{n+(k−1)j+l−1}{n−j}. We now show that G′′_{kn+l,k} = F′′_{kn+l} for all n ≥ 0, 1 ≤ l ≤ k. This follows from the following three observations.

1. For 1 ≤ l ≤ k, G′′_{l,k} = 1.

2. For 1 ≤ l ≤ k − 1,

G′′_{kn+l,k} + G′′_{k(n−1)+(l+1),k} = ∑_{j=0}^{n} (\binom{n + (k − 1)j + l − 1}{n − j} + \binom{n − 1 + (k − 1)j + l}{n − 1 − j})

= ∑_{j=0}^{n} \binom{n + (k − 1)j + l}{n − j} = G′′_{kn+l+1,k}.

3.

G′′_{kn+k,k} + G′′_{kn+1,k} = ∑_{j=0}^{n} (\binom{n + (k − 1)j + k − 1}{n − j} + \binom{n + (k − 1)j}{n − j})

= ∑_{j=1}^{n+1}(\binom{n + (k − 1)j}{n − (j − 1)})+∑_{j=0}^{n} \binom{n + (k − 1)j}{n − j} = ∑_{j=0}^{n+1}(\binom{n + 1 + (k − 1)j}{n + 1 − j} = G′′_{k(n+1)+1,k}.

The statement of the theorem now follows from Lemma 3.2.

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. Cvetković, P. Rajković and M. Ivković, Catalan numbers, and Hankel transform, and Fibonacci numbers, J. Integer Seq. 5 (2002), no. 1, Article 02.1.3, 8 pp. (electronic).

[3] P. Hilton and J. Pederson, Catalan numbers, their generalization, and their uses, Math. Int. 13 (1991), 64–75.

[4] Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2005, published electronically at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11B75.

Keywords: Generalized Catalan numbers, Hankel transform.

(Concerned with sequence \underline{A001906}.)

Received August 28 2006; revised version received December 6 2006. Published in Journal of Integer Sequences, December 8 2006.

Return to Journal of Integer Sequences home page.