Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Aoife Hennessy Department of Computing, Mathematics and Physics Waterford Institute of Technology Ireland

                   aoife.hennessy@gmail.com

Abstract We examine a set of special Riordan arrays, their inverses and associated Hankel

transforms.

1 Introduction

In this note we explore the properties of a simply defined family of Riordan arrays [9]. The inverses of these arrays are closely related to well-known Catalan-defined matrices. This motivates us to study the Hankel transforms [6] of the images of some well-known families of sequences under the inverse matrices. This follows a general principle which states that the Hankel transform of the images of “simple” sequences under certain Catalan-defined matrices can themselves be “simple” in structure. We give several examples of this phenomenon in this note.

Special sequences will be referred to by their A-number in the On-Line Encyclopedia of Integer Sequences, [10].

2 The matrix M

Throughout this note, we let the matrix M be the Riordan array \underline{A158454}

M = (\frac{1}{1 − x^{2}} , \frac{x}{(1 + x)^{2}} ) .

We shall also consider the related matrices

M̃ = (\frac{1}{1 − x^{2}} , \frac{−x}{(1 − x)^{2}} ) and M^{+} = (\frac{1}{1 − x^{2}} , \frac{x}{(1 − x)^{2}} ) .

The matrix M begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & −2 & 1 & 0 & 0 & 0 & … \\ 0 & 4 & −4 & 1 & 0 & 0 & … \\ 1 & −6 & 11 & −6 & 1 & 0 & … \\ 0 & 9 & −24 & 22 & −8 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

while M̃ begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & −1 & 0 & 0 & 0 & 0 & … \\ 1 & −2 & 1 & 0 & 0 & 0 & … \\ 0 & −4 & 4 & −1 & 0 & 0 & … \\ 1 & −6 & 11 & −6 & 1 & 0 & … \\ 0 & −9 & 24 & −22 & 8 & −1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The entries of M^{+} are the absolute value of entries of both these matrices. We can calculate the general term M_{n,k} of M as follows.

M_{n,k} = [x^{n}]\frac{1}{1 − x^{2}} \frac{x^{k}}{(1 + x^{2})^{k}}
= [x^{n−k}](1 − x)^{−1}(1 + x)^{−(2k+1)}
= [x^{n−k}] ∑_{j=0}^{∞} x^{j} ∑_{i=0}^{∞} \binom{−(2k + 1)}{i}x^{i}
= [x^{n−k}] ∑_{j=0}^{∞} ∑_{i=0}^{∞} \binom{2k + i}{i}(−1)^{i}x^{i+j}
= ∑_{j=0}^{n−k} \binom{n + k − j}{n − k − j}(−1)^{n−k−j}
= ∑_{j=0}^{n−k} \binom{n + k − j}{2k}(−1)^{n−k−j}.

An alternative expression for M_{n,k} can be obtained by noticing that

M = (\frac{1}{1 − x^{2}} , \frac{x}{(1 + x)^{2}} ) = (\frac{1}{1 − x}, x) · (\frac{1}{1 + x}, \frac{x}{(1 + x)^{2}} ) .

The general term of (\frac{1}{1−x}, x) is [k ≤ n] · 1, while that of (\frac{1}{1+x}, \frac{x}{(1+x)^{2}} ) is (−1)^{n−k}\binom{n+k}{2k}. Thus we obtain the alternative expression

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

This translates the combinatorial identity

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

Yet another expression for M_{n,k} can be obtained by observing that we have the factorization

M = (\frac{1}{1 − x^{2}} , x) · (1, \frac{x}{(1 + x)^{2}} ) .

This leads to the expression

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

The row sums of M are the periodic sequence

1, 1, 0, 1, 1, 0, 1, 1, 0, …

with generating function \frac{1+x}{1−x^{3}} , while the diagonal sums are the alternating sign version of \underline{A078008} given by

1, 0, 2, −2, 6, −10, 22, …

with generating function \frac{1+x}{(1−x)(1+2x)}. Of particular note are the images of the Catalan numbers C_{n} \underline{A000108} and the central binomial numbers \binom{2n}{n} \underline{A000984} under this matrix. Letting

c(x) = \frac{1 − \sqrt{1 − 4x}}{2x}

be the generating function of the Catalan numbers C_{n}, we have

(\frac{1}{1 − x^{2}} , \frac{x}{(1 + x)^{2}} ) · c(x) = \frac{1}{1 − x^{2}} \frac{1 − \sqrt{1 − 4\frac{x}{(1+x)^{2}}}}{2\frac{x}{(1+x)^{2}}} = \frac{1}{1 − x}.

Thus the image of C_{n} under the matrix M is the all 1’s sequence

1, 1, 1, …

The image of C_{n+1} is also interesting. We get the sequence 1, 2, 2, 2, … with generating function \frac{1+x}{1−x}. This can be generalized to the following result: The image of C_{n+k} under the

matrix M has generating function ^{\frac{∑_{j=0}^{k} a_{k,j}x^{j}}{1−x}}, where a_{n,k} is the general term of the matrix (c(x), xc(x)^{2}). We have a_{n,k} = \binom{2n}{n−k} \frac{2k+1}{n+k+1}. A consequence of this is the fact that the image by M of the Hankel matrix with general term C_{n+k} is a matrix whose rows tend to \binom{2n}{n}, where the first row is C_{n}:

( \begin{matrix}1 & 1 & 2 & 5 & 14 & 42 & … \\ 1 & 2 & 5 & 14 & 42 & 132 & … \\ 1 & 2 & 6 & 19 & 62 & 207 & … \\ 1 & 2 & 6 & 20 & 69 & 242 & … \\ 1 & 2 & 6 & 20 & 70 & 251 & … \\ 1 & 2 & 6 & 20 & 70 & 252 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This matrix is in fact equal to

M · (c(x), xc(x)^{2}) · (c(x), xc(x)^{2})^{T} = (\frac{1}{1 − x}, x) · (c(x), xc(x)^{2})^{T}

since (C_{n+k}) = LDL^{T} [7] where L = (c(x), xc(x)^{2}) and D = I in the case of the Catalan numbers. Now taking \binom{2n}{n} with generating function \frac{1}{\sqrt{1−4x}}, we obtain

(\frac{1}{1 − x^{2}} , \frac{x}{(1 + x)^{2}} ) · \frac{1}{\sqrt{1 − 4x}} = \frac{1}{1 − x^{2}} \frac{1}{\sqrt{1 − 4\frac{x}{(1+x)^{2}}}} = \frac{1}{(1 − x)^{2}} .

Thus the image of \binom{2n}{n} under M is n + 1 or the counting numbers \underline{A000027}

1, 2, 3, 4, 5, …

3 The inverse matrix M^{−1}

Since

M = (\frac{1}{1 − x}, x) · (\frac{1}{1 + x}, \frac{x}{(1 + x)^{2}} )

we see that

M^{−1} = (\frac{1}{1 + x}, \frac{x}{(1 + x)^{2}} )^{−1} (1 − x, x) = (c(x), xc(x)^{2})(1 − x, x).

Thus

M^{−1} = (c(x)(1 − xc(x)^{2}), xc(x)^{2}) = (1 − x^{2}c(x)^{4}, xc(x)^{2}).

The general term of M^{−1} is given by

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

We observe that

M^{−1} = (c(x)(1 − xc(x)^{2}), xc(x)^{2}) = (c(x), xc(x)^{2}) − (xc(x)^{3}, xc(x)^{2})

and hence

M_{n,k}^{−1} = \frac{2k + 1}{n + k + 1}\binom{2n}{n − k} − \frac{2k + 3}{n + k + 2}\binom{2n}{n − k − 1}
= \frac{2k + 1}{n + k + 1}\binom{2n}{n − k} − \frac{2k + 3}{n + k + 2} \frac{n − k}{n + k + 1}\binom{2n}{n − k}
= \frac{2(2k^{2} + 4k − n + 1)}{(k + n + 1)(k + n + 2)}\binom{2n}{n − k}.

Thus if we apply the matrix M^{−1} to the sequence a_{n} we obtain the image sequence b_{n} given by

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

= ∑_{k=0}^{n} \frac{2k + 1}{n + k + 1}\binom{2n}{n − k}a_{k} − ∑_{k=0}^{n} \frac{2k + 3}{n + k + 2}\binom{2n}{n − k − 1}a_{k}

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

We can obtain a further expression for this image by observing that

M^{−1} = (1, \frac{x}{(1 + x)^{2}} )^{−1} · (1 − x^{2}, x) = (1, xc(x)^{2}) · (1 − x^{2}, x).

We let T_{n,k} be the general term of the matrix (1, xc(x)^{2}). We have T_{0,0} = 1, and

T_{n,k} = \binom{2n − 1}{n − k}\frac{2k}{n + k}

otherwise. Then

b_{n} = ∑_{k=0}^{n} T_{n,k}(a(k) − a^{(2)}(k)),

where if k < 2, a^{(2)}(k) = 0, otherwise a^{(2)}(k) = a(k − 2).

The production matrix [2] of M^{−1} begins

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

We note that the production matrix of the array

(\frac{1}{1 + x}, \frac{x}{(1 + x)^{2}} )^{−1} = (c(x), xc(x)^{2})

is given by the related tri-diagonal matrix

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

which is the Jacobi-Stieltjes matrix for the orthogonal signed Morgan-Voyce polynomials b_{n}(x) = ∑_{k=0}^{n}(−1)^{n−k}\binom{n+k}{2k}x^{k} (see \underline{A085478}).

4 M^{−1} and Hankel transforms

We can characterize the image of the family of sequences rn + 1 under the transformation matrix M^{−1} as follows. Here, r ∈ Z.

Proposition 1. The image of rn + 1 under the matrix M^{−1} is

(rn + 1)C_{n}

with Hankel transform given by

[x^{n}]\frac{1 − (r − 1)^{2}x}{1 − 2x + (r − 1)^{2}x^{2}} .

Proof. The image of rn + 1 has generating function given by

g(r, x) = M^{−1} \frac{(r − 1)x + 1}{(1 − x)^{2}}
= (c(x)(1 − xc(x)^{2}), xc(x)^{2}) · \frac{(r − 1)x + 1}{(1 − x)^{2}}
= c(x)(1 − xc(x)^{2})\frac{(r − 1)xc(x)^{2} + 1}{(1 − xc(x)^{2})^{2}}
= c(x)\frac{(r − 1)xc(x)^{2} + 1}{1 − xc(x)^{2}}
= \frac{(1 − r)(1 − 4x) − (1 − r + 2x(r − 2))\sqrt{1 − 4x}}{2x(1 − 4x)}

which is the generating function of (rn + 1)C_{n}. Then the orthogonal measure associated to g(x, r) (i.e., the measure for which the numbers (rn + 1)C_{n} are the moments) is given by

w(x, r) = \frac{1}{2π} \frac{x(r − 1) − 2(r − 2)}{\sqrt{x(4 − x)}}.

This leads to a modified Jacobi polynomial. Using the techniques of [3] (see also [1, 8]) we see that the β coefficients corresponding to the relevant three term recurrence are given by

−r^{2} + 2r + 1, \frac{−3r^{+}6r + 1}{(r^{2} − 2r − 1)^{2}} , −\frac{−(r^{2} − 27r − 1)7(r^{4} − 47r^{3} − 27r^{2} + 127r + 1)}{(37r^{2} − 67r − 1)^{2}}, …

Thus the Hankel transform is given by [4, 5]

1, −r^{2} + 27r + 1, −37r^{2} + 67r + 1, r^{4} − 47r^{3} − 27r^{2} + 127r + 1, …

which is the expansion of

\frac{1 − (r − 1)^{2}x}{1 − 2x + (r − 1)^{2}x^{2}}

as required.

Similarly, we can look at the image of the power sequences n → r^{n} under M^{−1}. We find

Proposition 2. The Hankel transform of the image of r^{n} under the matrix M^{−1} is given by

[x^{n}]\frac{1 − (r − 1)^{2}x}{1 − (r^{2} − r + 2)x + (r − 1)^{2}x^{2}} .

5 The matrix M̃

The general term M̃_{n,k} of the matrix M̃ is given by

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

The row sums of this matrix are the periodic sequence 1, −1, 0, 1, −1, 0, … with generating function \frac{1−x}{1−x^{3}} . The diagonal sums are the sequence \underline{A078014} with generating function \frac{1−x}{1−x+2x^{3}} . The image of C_{n} under M̃ is

1, −1, 1, −1, …

or (−1)^{n}. Similarly the image of \binom{2n}{n} is (−1)^{n}(n + 1). The image of the Catalan Hankel matrix (C_{n+k}) under M̃ begins

( \begin{matrix}1 & 1 & 2 & 5 & 14 & 42 & … \\ −1 & −2 & −5 & −14 & −42 & −132 & … \\ 1 & 2 & 6 & 19 & 62 & 207 & … \\ −1 & −2 & −6 & −20 & −69 & −242 & … \\ 1 & 2 & 6 & 20 & 70 & 251 & … \\ −1 & −2 & −6 & −20 & −70 & −252 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The inverse matrix M̃^{−1} has general term

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

We have the following proposition concerning the image of r^{n} under the inverse of the matrix M̃.

Proposition 3. The Hankel transform of the image of the sequence n → r^{n} under the matrix M̃^{−1} is given by

[x^{n}]\frac{1 − x}{1 + 2rx + x^{2}} .

6 The positive matrix M^{+} = (\frac{1}{1−x^{2}}, \frac{x}{(1−x)^{2}})

The matrix M^{+} begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 0 & 4 & 4 & 1 & 0 & 0 & … \\ 1 & 6 & 11 & 6 & 1 & 0 & … \\ 0 & 9 & 24 & 22 & 8 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

It has general term

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

The row sums of this matrix are easily seen to have generating function \frac{1−x}{(1+x)(1−3x+x^{2})}. These are the squared Fibonacci numbers F (n + 1)^{2}, \underline{A007598}. Thus we have

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

for instance. The diagonal sums are the Jacobsthal numbers variant \underline{A078008}, with general term \frac{2^{n}}{3} + 2\frac{(−1)^{n}}{3} . The image of the Catalan numbers C_{n} by this matrix are an alternating sum of the large Schröder numbers S_{n} (\underline{A006318}) given by

∑_{k=0}^{n}(−1)^{n−k}S_{k}.

This has generating function

\frac{1 − x − \sqrt{1 − 6x + x^{2}}}{2x(1 + x)} .

Likewise, the image of the central binomial coefficients \binom{2n}{n} is the sequence starting 1, 2, 11, 52, 269, … \underline{A026933} with generating function

\frac{1}{(1 + x)\sqrt{1 − 6x + x^{2}}} .

This is therefore

∑_{k=0}^{n}(−1)^{n−k}D_{k}

where D_{n} is the sequence of central Delannoy numbers \underline{A001850}.

Again, for appropriate families of sequences, the images under the inverse of this matrix can have interesting Hankel transforms. For instance, we have the following result.

Proposition 4. The Hankel transform of the image under M^{+}^{−1} of the generalized Fibonacci numbers with general term

∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}r^{k}

is given by

[x^{n}]\frac{1 + (r − 1)x}{1 + 2x + (r − 1)^{2}x^{2}} .

Finally, we note that the production matrix of the inverse M^{+}^{−1} takes the form

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

7 A one-parameter family of Riordan arrays

We note that

M = (\frac{1}{1 − x^{2}} , \frac{x}{(1 + x)^{2}} ) = (\frac{1}{(1 − x)(1 + x)}, \frac{x}{(1 + x)^{2}} )

is the element M_{1} of the family of Riordan arrays M_{r} defined by

M_{r} = (\frac{1}{(1 − x)(1 + rx)}, \frac{x}{(1 + rx)^{2}} ) .

The general term of M_{r} is given by

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

We can generalize the results of the foregoing to this family. For instance, the row sums of M_{r}^{−1} are precisely r^{n}C_{n}, while the image of the sequence r^{n}\binom{2n}{n} under the matrix M_{r} has general term \frac{1−r^{n+1}}{1−r} = ∑_{k=0}^{n} r^{k}. The production matrix of M_{r}^{−1} begins

( \begin{matrix}r − 1 & 1 & 0 & 0 & 0 & 0 & … \\ r^{2} − r − 1 & 2r & 1 & 0 & 0 & 0 & … \\ −r − 1 & r^{2} & 2r & 1 & 0 & 0 & … \\ −r − 1 & 0 & r^{2} & 2r & 1 & 0 & … \\ −r − 1 & 0 & 0 & r^{2} & 2r & 1 & … \\ −r − 1 & 0 & 0 & 0 & r^{2} & 2r & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

8 Acknowledgements

We are grateful to an anonymous reviewer whose careful reading of the original manuscript has resulted in some important clarifications. Some are incorporated in the above text. We single out two further results here. Firstly, it can be noted that

M_{n,k}^{−1} = [x^{n}](1 − x^{2}c(x)^{2})(xc(x)^{2})^{k}
= \frac{k}{n}\binom{2n}{n − k} − \frac{k + 2}{n}\binom{2n}{n − k − 2}.

Thus for n, k ≥ 1 we obtain the identity

\frac{2k + 1}{n + k + 1}\binom{2n}{n − k} − \frac{2k + 3}{n + k + 2}\binom{2n}{n − k − 1} = \frac{k}{n}\binom{2n}{n − k} − \frac{k + 2}{n}\binom{2n}{n − k − 2}.

Secondly, Proposition 1 can be extended as follows :

Proposition 5. The image of the sequence (rn + s)_{n=0}^{∞} under the matrix M^{−1} is

(rn + s)C_{n},

with Hankel transform given by

[x^{n}]\frac{s − (r − s)^{2}x}{1 − 2sx + (r − s)^{2}x^{2}} .

References

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

[2] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices, Adv. in Appl. Math. 34 (2005), 101–122.

[3] W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Clarendon Press, Oxford, 2003.

[4] C. Krattenthaler, Advanced determinant calculus, math.CO/9902004. Available electronically at http://arxiv.org/abs/math/9902004 .

[5] C. Krattenthaler, Advanced determinant calculus: A complement, Linear Algebra Appl. 411 (2005), 68–166.

[6] J. W. Layman, The Hankel transform and some of its properties, J. Integer Seq. 4 (2001), Article 01.1.5.

[7] P. Peart and W-J. Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq. 3 (2000), Article 00.2.1.

[8] P. M. Rajković, M. D. Petković and P. Barry, The Hankel transform of the sum of consecutive generalized Catalan numbers, Integral Transforms Spec. Funct. 18 (2007), 285–296.

[9] L. W. Shapiro, S. Getu, W-J. Woan and L. C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

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

   cally at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 11B65, 11Y55, 42C05. Keywords: Riordan array, integer sequence, production matrix, Hankel transform, orthogonal polynomial.

(Concerned with sequences \underline{A000027}, \underline{A000108}, \underline{A000984}, \underline{A001850}, \underline{A007598}, \underline{A026933}, \underline{A078008}, \underline{A078014}, \underline{A085478}, and \underline{A158454}.)

Received March 19 2009; revised version received July 6 2009. Published in Journal of Integer Sequences, July 6 2009.

Return to Journal of Integer Sequences home page.