Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract We study families of generalized Catalan numbers, defined by convolution recurrence equations. We explore their relations to series reversion, Riordan array transforms, and in a special case, to Somos-4 sequences via the mechanism of the Hankel transform.

1 Introduction

This note is concerned with the solutions to the following two convolution recurrences:

a_{n} = \begin{cases}1, & if n = 0; \\ αa_{n−1} + β ∑_{k=0}^{n−1} a_{k}a_{n−1−k}, & if n > 0. \end{cases}  (1)

and

a_{n} = \begin{cases}1, & if n = 0; \\ α, & if n = 1; \\ αa_{n−1} + βa_{n−2} + γ ∑_{k=0}^{n−2} a_{k}a_{n−2−k}, & if n > 1. \end{cases}  (2)

We call the elements of these sequences generalized Catalan numbers, since the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} satisfy equation (1) with α = 0 and β = 1:

C_{n} = \begin{cases}1, & if n = 0; \\ ∑_{k=0}^{n−1} C_{k}C_{n−1−k}, & if n > 0. \end{cases}  (3)

Many of the sequences that we will encounter have interesting Hankel transforms [1, 3, 8], and many will have generating functions that we can describe using Riordan arrays [2, 11, 14] and continued fractions [18]. Many interesting examples of sequences and Riordan arrays can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences (OEIS), [12, 13]. Sequences are frequently referred to by their Annnnnn OEIS number.

For instance, the Motzkin numbers M_{n} \underline{A001006} satisfy equation (2) with α = 1, β = 0 and γ = 1:

M_{n} = \begin{cases}1, & if n = 0; \\ 1, & if n = 1; \\ M_{n−1} + ∑_{k=0}^{n−2} M_{k}M_{n−2−k}, & if n > 1. \end{cases}  (4)

To see why this should be so, we translate this equation into the corresponding algebraic equation for generating functions:

G(x) = 1 + xG(x) + x^{2}G(x)^{2},

with solution

m(x) = G(x) = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}} .

Now we can express the g.f. m(x) of the Motzkin numbers in terms of the g.f. of the Catalan numbers \underline{A000108}, which is

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

Thus we have

m(x) = \frac{1}{1 − x}c (\frac{x^{2}}{(1 − x)^{2}} ) .  (5)

In other words, the generating function of the Motzkin numbers, solution of equation (4), results from operating on the generating function c(x) of the Catalan numbers by the (generalized, or stretched) Riordan array

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

We immediately obtain that

M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}.

Now since the g.f. c(x) of the Catalan numbers may be expressed as the continued fraction

c(x) = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − ⋯}}},  (6)

we can infer from equation (5) that the continued fraction expression for m(x) is given by

m(x) = \frac{1}{1 − x − \frac{x^{2}}{1 − x − \frac{x^{2}}{1 − ⋯}}}.  (7)

Thus m(x) satisfies the relation

m(x) = \frac{1}{1 − x − x^{2}m(x)}.

The continued fraction expression in equation (7) shows in particular that the Hankel transform of the Motzkin numbers is given by the all 1’s sequence 1, 1, 1, . . ..

In the next section, we will review known results concerning Riordan arrays and Hankel transforms that will be useful in the sequel.

2 Preliminaries on integer sequences, Riordan arrays and Hankel transforms

For an integer sequence a_{n}, that is, an element of ℤ^{ℕ}, the power series f(x) = ∑_{k=0}^{∞} a_{k}x^{k} is called the ordinary generating function or g.f. of the sequence. a_{n} is thus the coefficient of x^{n} in this series. We denote this by a_{n} = [x^{n}]f(x). For instance, F_{n} = [x^{n}]\frac{x}{1−x−x^{2}} is the n-th Fibonacci number \underline{A000045}, while C_{n} = [x^{n}]\frac{1−\sqrt{1−4x}}{2x} is the n-th Catalan number \underline{A000108}. We use the notation 0^{n} = [x^{n}]1 for the sequence 1, 0, 0, 0, …, \underline{A000007}. Thus 0^{n} = [n = 0] = δ_{n,0} = \binom{0}{n}.

For a power series f(x) = ∑_{n=0}^{∞} a_{n}x^{n} with f(0) = 0 and f′(0) ≠ 0 we define the reversion or compositional inverse of f to be the power series f̄(x) (also written as f^{[−1]}(x)) such that f(f̄(x)) = x. We sometimes write f̄ = Revf.

The aeration of a sequence with g.f. f(x) is the sequence with g.f. f(x^{2}).

For a lower triangular matrix (a_{n,k})_{n,k≥0} the row sums give the sequence with general term ∑_{k=0}^{n} a_{n,k} while the diagonal sums form the sequence with general term

∑_{k=0}^{⌊ \frac{n}{2} ⌋} a_{n−k,k}.

The Riordan group [11, 14], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + ⋯ and f(x) = f_{1}x + f_{2}x^{2} + ⋯ where f_{1} ≠ 0 [14]. The associated matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair g, f is denoted by (g, f) or R(g, f). The group law is then given by

(g, f) · (h, l) = (g, f)(h, l) = (g(h ∘ f), l ∘ f).

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f.

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)′ is an integer sequence with ordinary generating function A(x), then the sequence Ma has ordinary generating function g(x)A(f(x)). The (infinite) matrix (g, f) can thus be considered to act on the ring of integer sequences ℤ^{ℕ} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series ℤ[[x]] by

(g, f) : A(x) ↦ (g, f) · A(x) = g(x)A(f(x)).

Example 1. The so-called binomial matrix B \underline{A007318} is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. It has general element \binom{n}{k}, and hence as an array coincides with Pascal’s triangle. More generally, B^{m} is the element (\frac{1}{1−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

Example 2. If a_{n} has generating function g(x), then the generating function of the sequence

b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} a_{n−2k}

is equal to

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

while the generating function of the sequence

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

is equal to

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

The row sums of the matrix (g, f) have generating function

(g, f) · \frac{1}{1 − x} = \frac{g(x)}{1 − f(x)}

while the diagonal sums of (g, f) (sums of left-to-right diagonals in the North East direction) have generating function g(x)/(1 − xf(x)). These coincide with the row sums of the “generalized” Riordan array (g, xf):

(g, xf) · \frac{1}{1 − x} = \frac{g(x)}{1 − xf(x)}.

For instance the Fibonacci numbers F_{n+1} are the diagonal sums of the binomial matrix B given by (\frac{1}{1−x}, \frac{x}{1−x}):

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

while they are the row sums of the “generalized” or “stretched” (using the nomenclature of [2] ) Riordan array (\frac{1}{1−x}, \frac{x^{2}}{1−x}):

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

It is often the case that we work with “generalized” Riordan arrays, where we relax some of the defining conditions above. Thus for instance [2] discusses the notion of the “stretched” Riordan array. In this note, we shall encounter “vertically stretched” arrays of the form (g, h) where now f_{0} = f_{1} = 0 with f_{2} ≠ 0. Such arrays are not invertible, but we may explore their left inversion. In this context, standard Riordan arrays as described above are called “proper” Riordan arrays. We note for instance that for any proper Riordan array (g, f), its diagonal sums are just the row sums of the vertically stretched array (g, xf) and hence have g.f. g/(1 − xf).

The Hankel transform of a given sequence A = {a_{0}, a_{1}, a_{2}, ...} is the sequence of Hankel determinants {h_{0}, h_{1}, h_{2}, …} where h_{n} = |a_{i+j}|_{i,j=0}^{n}, i.e

A = \{a_{n}\}_{n∈ℕ_{0}} → h = \{h_{n}\}_{n∈ℕ_{0}} : h_{n} = | \begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & & a_{n+1} \\ ⋮ & & ... \\ a_{n} & a_{n+1} & & a_{2n} \end{matrix} | .  (8)

The Hankel transform of a sequence a_{n} and that of its binomial transform are equal.

In the case that a_{n} has g.f. g(x) expressible in the form

g(x) = \frac{a_{0}}{1 − α_{0}x − \frac{β_{1}x^{2}}{1 − α_{1}x − \frac{β_{2}x^{2}}{1 − α_{2}x − \frac{β_{3}x^{2}}{1 − α_{3}x − ⋯}}}}

then we have [7, 6, 18]

h_{n} = a_{0}^{n}β_{1}^{n−1}β_{2}^{n−2} ⋯ β_{n−1}^{2}β_{n} = a_{0}^{n} ∏_{k=1}^{n} β_{k}^{n−k}.  (9)

Note that this independent from α_{n}.

We note that α_{n} and β_{n} are in general not integers. Now let H ( \begin{matrix}u_{1} & ⋯ & u_{k} \\ v_{1} & ⋯ & v_{k} \end{matrix} ) be the

determinant of Hankel type with (i, j)-th term μ_{u_{i}+v_{j}} [5, 17]. Let

Δ_{n} = H ( \begin{matrix}0 & 1 & ⋯ & n \\ 0 & 1 & ⋯ & n \end{matrix} ) , Δ′ = H ( \begin{matrix}0 & 1 & ⋯ & n − 1 & n \\ 0 & 1 & ⋯ & n − 1 & n + 1 \end{matrix} ) .

Then we have

α_{n} = \frac{Δ′_{n}}{Δ_{n}} − \frac{Δ′_{n−1}}{Δ_{n−1}} ,  β_{n} = \frac{Δ_{n−2}Δ_{n}}{Δ_{n−1}^{2}} .  (10)

An integer sequence t_{n} is said to have the generalized Somos-4 property if there exists a pair of integers (r, s) such that

t_{n} = \frac{rt_{n−1}t_{n−3} + st_{n−2}^{2}}{t_{n−4}} , n ≥ 4.  (11)

Alternatively (to avoid division by zero), we require that

t_{n}t_{n−4} = rt_{n−1}t_{n−3} + st_{n−2}^{2}, n ≥ 4.  (12)

Note that it is sometimes useful to relax the integer condition on the pair (r, s) and to allow them to be rational integers. Somos-4 sequences are most commonly associated with the xcoordinate of rational points on an elliptic curve [4, 15, 16]. The link between these sequences and Hankel transforms is made explicit in Theorem 7.1.1 of [15], for instance. Letting [n]P denote the n-fold sum P + ⋯ + P of points on an elliptic curve E, this result implies the following: if P = (x̄, ȳ) and Q = (x_{0}, y_{0}) are two distinct non-singular rational points on an elliptic curve E, denote, for all n ∈ ℤ such that Q + [n]P ≠ O (the point at infinity on E), by (x_{n}, y_{n}) the coordinates of the point Q + [n]P. Then under these circumstances the numbers determined by

s_{n} = (−1)^{\binom{n+1}{2}}(x_{n−1} − x̄)(x_{n−2} − x̄)^{2} ⋯ (x_{1} − x̄)^{n−1}(x_{0} − x̄)^{n}s_{0} (\frac{s_{0}}{s_{−1}} )^{n}

are elements of a Somos 4 sequence (given appropriate s_{0}, s_{−1} ≠ 0). We can re-write this as

s_{n} = s_{0} (\frac{s_{0}}{s_{−1}} )^{n} ∏_{k=0}^{n−1}(x̄ − x_{k})^{n−k}.

3 The equation a_{n} = αa_{n−1} + β ∑_{k=0}^{n−1} a_{k}a_{n−1−k}, n > 0, a_{0} = 1

In this section, we look in more detail at the solution to the equation (1):

a_{n} = \begin{cases}1, & if n = 0; \\ αa_{n−1} + β ∑_{k=0}^{n−1} a_{k}a_{n−1−k}, & if n > 0. \end{cases}

We have the following proposition: Proposition 3. We let a_{n} be a solution of the convolution recurrence

a_{n} = \begin{cases}1, & if n = 0; \\ αa_{n−1} + β ∑_{k=0}^{n−1} a_{k}a_{n−1−k}, & if n > 0. \end{cases}

Then the g.f. of a_{n} is given by

g(x) = \frac{1}{1 − αx}c (\frac{βx}{(1 − αx)^{2}} ) .  (13)

The g.f. g(x) may be expressed in continued fraction form as follows:

g(x) = \frac{1}{1 − \frac{(α + β)x}{1 − \frac{βx}{1 − \frac{(α + β)x}{1 − \frac{βx}{1 − ⋯}}}}}

= \frac{1}{1 − αx − \frac{βx}{1 − αx − \frac{βx}{1 − ⋯}}}

= \frac{1}{1 − (α + β)x − \frac{β(α + β)x^{2}}{1 − (α + 2β)x − \frac{β(α + β)x^{2}}{1 − (α + 2β)x − \frac{β(α + β)x^{2}}{1 − ⋯}}}}.

We have the following expressions for a_{n}:

a_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}C_{k}α^{n−k}β^{k}

= ∑_{k=0}^{n} \binom{2n − k}{k}C_{n−k}α^{k}β^{n−k}

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{n}{k − 1}β^{n−k}(α + β)^{k}, n > 0, a_{0} = 1

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{n}{k + 1}β^{k}(α + β)^{n−k}, n > 0, a_{0} = 1.

In addition, we have

a_{n} = [x^{n+1}]Rev\frac{x(1 − βx)}{1 + αx}.  (14)

Proof. The g.f. g(x) of the solution a_{n} of equation (1) satisfies the equation

g(x) = 1 + αxg(x) + βxg(x)^{2}.

Hence

g(x) = \frac{1 − αx − \sqrt{1 − 2x(α + 2β) + α^{2}x^{2}}}{2βx} .  (15)

Thus

g(x) = \frac{1}{1 − αx}c (\frac{βx}{(1 − αx)^{2}} ) .

Now the reversion of the expression \frac{x(1−βx)}{1+αx} is the solution u = u(x) of the equation

\frac{u(1 − βu)}{1 + αu} = x.

We find that

u(x) = \frac{1 − αx − \sqrt{1 − 2x(α + 2β) + α^{2}x^{2}}}{2β} = xg(x).  (16)

Thus

a_{n} = [x^{n+1}]Rev\frac{x(1 − βx)}{1 + αx}.

We deduce from the fact that

g(x) = \frac{1}{1 − αx}c (\frac{βx}{(1 − αx)^{2}} )
= (\frac{1}{1 − αx}, \frac{βx}{(1 − αx)^{2}} ) · c(x)

that

a_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}C_{k}α^{n−k}β^{k}

and the other expressions follow. From the fact that g(x) = \frac{1}{1−αx}c (\frac{βx}{(1−αx)^{2}} ) we can infer that

g(x) = \frac{1}{1 − αx − \frac{βx}{1 − αx − \frac{βx}{1 − ⋯}}}.

The expression

g(x) = \frac{1}{1 − \frac{(α + β)x}{1 − \frac{βx}{1 − \frac{(α + β)x}{1 − \frac{βx}{1 − ⋯}}}}}

follows from the fact that the equation

v = \frac{1}{1 − \frac{(α + β)x}{1 − βxv}}

has solution v = g(x). Finally standard contraction techniques [10] for continued fractions allow us to transform this last expression to

g(x) = \frac{1}{1 − (α + β)x − \frac{β(α + β)x^{2}}{1 − (α + 2β)x − \frac{β(α + β)x^{2}}{1 − (α + 2β)x − \frac{β(α + β)x^{2}}{1 − ⋯}}}}.

Corollary 4. The Hankel transform of a_{n} is given by (β(α + β))^{\binom{n+1}{2}}.

Corollary 5. The Hankel transform of a_{n} is a (β^{3}(α + β)^{3}, 0) Somos-4 sequence, and a (0, β^{4}(α + β)^{4}) Somos 4 sequence.

Notable examples of these sequences are the little Schröder numbers \underline{A001003} (α = −1, β = 2), the Catalan numbers \underline{A000108} (α = 0, β = 1), and the large Schröder numbers \underline{A006318} (α = 1, β = 1).

4 The equation a_{n} = αa_{n−1} + βa_{n−2} + γ ∑_{k=0}^{n−2} a_{k}a_{n−2−k}.

In this section, we shall consider solutions to the equation

a_{n} = \begin{cases}1, & if n = 0; \\ α, & if n = 1; \\ αa_{n−1} + βa_{n−2} + γ ∑_{k=0}^{n−2} a_{k}a_{n−2−k}, & if n > 1. \end{cases}

Example 6. We take the example of α = β = γ = 1. In this case, we find that the solution to

a_{n} = \begin{cases}1, & if n = 0; \\ 1, & if n = 1; \\ a_{n−1} + a_{n−2} + ∑_{k=0}^{n−2} a_{k}a_{n−2−k}, & if n > 1; \end{cases}

is given by

a_{n} = [x^{n}]\frac{1}{1 − x − x^{2}} c (\frac{x^{2}}{(1 − x − x^{2})^{2}} ) = [x^{n}]\frac{1}{1 − x^{2}} m (\frac{x}{1 − x^{2}} ) .

Thus

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

This is \underline{A128720}. We now observe the following. We have

\frac{1}{1 − x − x^{2}} c (\frac{x^{2}}{(1 − x − x^{2})^{2}} ) = \frac{1 − x − x^{2} − \sqrt{1 − 2x − 5x^{2} + 2x^{3} + x^{4}}}{2x^{2}}

from which we can deduce the following integral representation (using the Stieltjes transform) for a_{n}:

a_{n} = \frac{1}{π} ∫_{\frac{\sqrt{5}}{2} − \frac{1}{2}}^{\frac{3}{2} + \frac{\sqrt{13}}{2}} x^{n} \frac{\sqrt{−1 − 2x + 5x^{2} + 2x^{3} − x^{4}}}{2x} dx−\frac{1}{π} ∫_{\frac{−\sqrt{5}}{2} − \frac{1}{2}}^{\frac{3}{2} − \frac{\sqrt{13}}{2}} x^{n} \frac{\sqrt{−1 − 2x + 5x^{2} + 2x^{3} − x^{4}}}{2x} dx

or

a_{n} = \frac{1}{π} ∫_{\frac{\sqrt{5}}{2} − \frac{1}{2}}^{\frac{3}{2} + \frac{\sqrt{13}}{2}} x^{n} \frac{\sqrt{−(1 + 3x − x^{2})(1 − x − x^{2})}}{2x} dx−\frac{1}{π} ∫_{\frac{−\sqrt{5}}{2} − \frac{1}{2}}^{\frac{3}{2} − \frac{\sqrt{13}}{2}} x^{n} \frac{\sqrt{−(1 + 3x − x^{2})(1 − x − x^{2})}}{2x} dx.

We now observe that the Hankel transform h_{n} of a_{n} satisfies a (1, 3) Somos-4 relation:

h_{n} = \frac{h_{n−1}h_{n−3} + 3h_{n−2}^{2}}{h_{n−4}} .

In this case, we obtain the sequence h_{n} that starts

1, 2, 5, 17, 109, 706, 9529, 149057, 3464585, 141172802, …,

which is \underline{A174168}.

In the general case, we have the following proposition: Proposition 7. We let a_{n} be the solution of the convolution recurrence

a_{n} = \begin{cases}1, & if n = 0; \\ α, & if n = 1; \\ αa_{n−1} + βa_{n−2} + γ ∑_{k=0}^{n−2} a_{k}a_{n−2−k}, & if n > 1. \end{cases}

Then the g.f. g(x) of a_{n} is given by

g(x) = \frac{1}{1 − αx − βx^{2}} c (\frac{γx^{2}}{(1 − αx − βx^{2})^{2}} ) .

The general term of the sequence a_{n} is given by

a_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=0}^{n−2k} \binom{2k + j}{j}\binom{j}{n − 2k − j}α^{2k+2j−n}β^{n−2k−j}γ^{k}C_{k}.  (17)

The g.f. g(x) of a_{n} has the continued fraction expansion

g(x) = \frac{1}{1 − αx − βx^{2} − \frac{γx^{2}}{1 − αx − βx^{2} − \frac{γx^{2}}{1 − ⋯}}}.  (18)

Proof. The g.f. g(x) of the solution a_{n} of equation (2) satisfies the equation

g(x) = 1 + αxg(x) + βx^{2}g(x) + γx^{2}g(x)^{2}.

Solving this equation for g(x) we find that

g(x) = \frac{1 − αx − βx^{2} − \sqrt{1 − 2αx + (α^{2} − 2β − 4γ)x^{2} + 2αβx^{3} + β^{2}x^{4}}}{2γx^{2}} ,

which is equal to

\frac{1}{1 − αx − βx^{2}} c (\frac{γx^{2}}{(1 − αx − βx^{2})^{2}} ) .

Now

\frac{1}{1 − αx − βx^{2}} c (\frac{γx^{2}}{(1 − αx − βx^{2})^{2}} ) = (\frac{1}{1 − αx − βx^{2}} , \frac{γx^{2}}{(1 − αx − βx^{2})^{2}} ) · c(x),

where the general term of the stretched Riordan array (\frac{1}{1−αx−βx^{2}} , \frac{γx^{2}}{(1−αx−βx^{2})^{2}} ) is given by

∑_{j=0}^{n−2k} \binom{2k + j}{j}\binom{j}{n − 2k − j}α^{2k+2j−n}β^{n−2k−j}γ^{k}.

The second assertion follows from this. The continued fraction expansion follows directly from

g(x) = \frac{1}{1 − αx − βx^{2}} c (\frac{γx^{2}}{(1 − αx − βx^{2})^{2}} )

and the form of the continued fraction expansion (Eq. (6)) for c(x).

Corollary 8. If β = 0, then we have

a_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}α^{n−2k}γ^{k}C_{k}.

Proof. This follows since in this case, we have

g(x) = \frac{1}{1 − αx}c (\frac{γx^{2}}{(1 − αx)^{2}} )

and the fact that the general element of the Riordan array (\frac{1}{1−αx}, \frac{x}{(1−αx)^{2}} ) is \binom{n+k}{2k}α^{n−k}.

Note that in this case, the Hankel transform of a_{n} is γ^{\binom{n+1}{2}}. We also have, in this case,

a_{n} = [x^{n+1}]Rev\frac{x}{1 + αx + γx^{2}} .

Corollary 9. If α = 0, then we have

a_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{\frac{n+2k}{2}}{2k}\frac{1 + (−1)^{n−2k}}{2} β^{\frac{n−2k}{2}} γ^{k}C_{k}.

Proof. In this case, we have

a_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=0}^{n−2k} \binom{2k + j}{j}\binom{j}{n − 2k − j}0^{2k+2j−n}β^{n−2k−j}γ^{k}C_{k}.

Thus the surviving element of the j-summation occurs when j = \frac{n−2k}{2}.

Note that when α = 0, we have

g(x) = \frac{1}{1 − βx^{2}} c (\frac{γx^{2}}{(1 − βx^{2})^{2}} ) .

Thus a_{n} in this case is an aerated sequence.

5 A Somos-4 conjecture

We can now state the following conjecture. Conjecture 10. Let a_{n} be the solution to the second order convolution recurrence

a_{n} = \begin{cases}1, & if n = 0; \\ α, & if n = 1; \\ αa_{n−1} + βa_{n−2} + γ ∑_{k=0}^{n−2} a_{k}a_{n−2−k}, & if n > 1; \end{cases}

and let h_{n} be the Hankel transform of a_{n}. Then h_{n} is a (α^{2}γ^{2}, γ^{2}(γ^{2} + γ(2β − α^{2}) + β^{2})) Somos-4 sequence. Example 11. We return to the Example 6, where α = β = γ = 1. A simple calculation shows that then α^{2}γ^{2} = 1 and γ^{2}(γ^{2} + γ(2β − α^{2}) + β^{2}))=3. Example 12. We take α = 1, β = 0 and γ = −1. a_{n} then begins

1, 1, 0, −2, −3, 1, 11, 15, −13, −77, −86, …

which is a variant of the sequence \underline{A007440}, derived from the series reversion of the g.f. of the Fibonacci numbers. Then the Hankel transform of a_{n} is h_{n} = (−1)^{\binom{n+1}{2}}, which is a (trivial) (1, 2) Somos-4 sequence. Example 13. We take α = 1, β = 2 and γ = −1. Then the sequence a_{n} begins

1, 1, 2, 2, 1, −3, −11, −21, −23, 7, 104, …,

and has a Hankel transform h_{n} which begins

1, 1, −3, −1, 17, −49, −209, −1249, 8739, −26399, −888577, …

By the conjecture, h_{n} is a (1, 2) Somos-4 sequence.

The following table gives a small sample of (α, β, γ) values and corresponding Somos-4 (r, s) values.

\begin{matrix}α & β & γ & (r, s) \\ 2 & −2 & −1 & (4, 13) \\ −1 & −2 & −1 & (1, 10) \\ −1 & 0 & −1 & (1, 2) \\ 1 & 2 & −1 & (1, 2) \\ 3 & −3 & −1 & (9, 25) \\ 3 & 3 & 1 & (9, 7) \\ −2 & −2 & 1 & (4, −3) \\ 1 & −1 & 1 & (1, −1) \\ 1 & 1 & −1 & (1, 1) \\ 1 & 3 & −1 & (1, 5) \\ 1 & 2 & −2 & (4, 8) \\ 1 & 0 & 2 & (4, 8) \\ 1 & 2 & 1 & (1, 8) \\ −1 & −3 & 1 & (1, 3) \\ −1 & 1 & 1 & (1, 3) \\ 1 & −1 & 1 & (1, −1) \\ 1 & −1 & 1 & (1, −1) \end{matrix}

An approach to the proof of this conjecture would be to employ the methods of [1, 3]. As indicated by the form of the density functions in Example 6, this would lead to an excursion into the area of elliptic orthogonal polynomials. This is outside the scope of the current study. An alternative approach would be to characterize the Hankel transforms of sequences with generating functions of the form given in Eq. (18).

6 Acknowledgements

The author would like to thank the anonymous referees for their careful reading and cogent suggestions which have hopefully led to clearer paper.

References

[1] P. Barry, P. Rajković & M. Petković, An application of Sobolev orthogonal polynomials to the computation of a special Hankel determinant, in W. Gautschi, G. Rassias, and M. Themistocles, eds., Approximation and Computation, Springer, 2010.

[2] C. Corsani, D. Merlini, R. Sprugnoli, Left-inversion of combinatorial sums, Discrete Math. 180 (1998), 107–122.

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

[4] A. N. W. Hone, Elliptic curves and quadratic recurrence sequences, Bull. London Math. Soc., 37 (2006), 161–171.

[5] W. Jones and W. Thron, Continued Fractions: Analytic Theory and Applications, Vol. 11 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2009.

[6] C. Krattenthaler, Advanced Determinant Calculus, available electronically at

   http://arxiv.org/PS cache/math/pdf/9902/9902004.pdf, 2006.

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

[8] J. W. Layman, The Hankel Transform and some of its properties, J. Integer Sequences, 4 (2001), Article 01.1.5.

[9] D. Merlini, R. Sprugnoli and M. C. Verri, The method of coefficients, Amer. Math. Monthly, 114 (2007), 40–57.

[10] T. Muir, The condensation of continuants, Proc. Edinburgh Math. Soc. 23 (1904), 35–39.

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

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

   cally at http://www.research.att.com/~njas/sequences/, 2010.

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices Amer. Math. Soc. 50 (2003), 912–915.

[14] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[15] C. S. Swart, Elliptic curves and related sequences, PhD Thesis, Royal Holloway, University of London, 2003.

[16] Alfred J. van der Poorten, Elliptic curves and continued fractions, J. Integer Sequences 8 (2005), Article 05.2.5.

[17] G. Viennot, A combinatorial theory for general orthogonal polynomials with extensions and applications, in: Polynomes Orthogonaux et Applications, Lecture Notes in Mathematics, Vol. 1171, Springer, 1985, pp. 139–157.

[18] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 2000.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 11B37, 11C20, 15B05, 15B36. Keywords: Integer sequence, linear recurrence, Riordan arrays, continued fraction, Hankel transform, Somos sequence.

(Concerned with sequences \underline{A000007}, \underline{A000045}, \underline{A000108}, \underline{A001003}, \underline{A001006}, \underline{A006318}, \underline{A007318}, \underline{A007440}, \underline{A128720}, and \underline{A174168}.)

Received May 10 2010; revised version received June 23 2010. Published in Journal of Integer Sequences, July 9 2010.

Return to Journal of Integer Sequences home page.