Generalized Catalan Recurrences, Riordan Arrays, Elliptic Curves, and Orthogonal Polynomials

Paul Barry School of Science Waterford Institute of Technology Ireland

                     pbarry@wit.ie

Abstract

We show that the Catalan-Schroeder convolution recurrences and their higher order generalizations can be solved using Riordan arrays and the Catalan numbers. We investigate the Hankel transforms of many of the recurrence solutions, and indicate that Somos-4 sequences often arise. We exhibit relations between recurrences, Riordan arrays, elliptic curves and Somos-4 sequences. We furthermore indicate how one can associate a family of orthogonal polynomials to a point on an elliptic curve, whose moments are related to recurrence solutions.

This paper, which concerns generalized Catalan recurrences, their solutions using Riordan arrays, and applications to elliptic curve sequences, is arranged in the following sections.

1. A motivating example

2. Preliminaries

3. Generalized Catalan recurrences

4. A third-order recurrence

5. A further recurrence

6. Conversion of parameters 7. From elliptic curve to recurrences and Somos sequences

8. The family E_{t} : y^{2} + 4xy + y = x^{3} + (t − 1)x + tx

9. The case of E : y^{2} + axy + y = x^{3} + bx^{2} + cx

10. Conclusions

11. Appendix: Orthogonal polynomials, Riordan arrays and the Hankel transform.

1 A motivating example

The elliptic curve

E : y^{2} − xy + y = x^{3} − 2x + x

passes through the point P (0, 0). The division polynomials of this curve, ψ_{n}, evaluated at the multiples nP of the point P (0, 0), are given by

ψ_{n}(0, 0) = (−1)^{\binom{n}{2}}F_{n},

where F_{n} is the n-th Fibonacci number \underline{A000045}. A consequence of this is that the coordinates of nP are

x_{n} = x(nP) = \frac{F_{n}F_{n+2}}{F_{n+1}^{2}} ,

and

y_{n} = y(nP) = \frac{(−1)^{n}F_{n}}{F_{n+1}^{3}} .

The ratio y_{n}/x_{n} is then given by

\frac{y_{n}}{x_{n}} = \frac{(−1)^{n}}{F_{n+1}F_{n+2}} .

We now form a generating function expressed as a continued fraction

ã(x) = g_{E,P} (t) = \frac{1}{1 + t + \frac{x_{1}t^{2}}{1 + \frac{y_{1}}{x_{1}} t + \frac{x_{2}t^{2}}{1 + \frac{y_{2}}{x_{2}} t + \frac{x_{3}t^{2}}{1 + \frac{y_{3}}{x_{3}} t + ⋯}}}}.

In this case, the generating function g_{E,P} (t) expands to give the sequence ã_{n} that begins 1, −1, −1, 2, 2, −5, −5, 14, 14, −42, −42, ….

The general term of this sequence is

ã_{n} = (−1)^{\binom{n+1}{2}}C_{⌊ \frac{n+1}{2} ⌋}.

Here, we have C_{n} = \frac{1}{n+1} \binom{2n}{n} is the n-th Catalan number.

The Hankel transform h_{n} = |a_{i+j}|_{0≤i,j≤n} of ã_{n} begins

1, −2, −3, 5, 8, −13, −21, 34, 55, −89, −144, …,

with general term

h_{n} = (−1)^{\binom{n+1}{2}}F_{n+2}.

Thus we have

h_{n} = (−1)^{n+1}ψ_{n+2}(0, 0).

On the other hand, we can solve the equation y^{2} − xy + y = x^{3} − 2x^{2} + x for y. We find that

y = \frac{(1 − x)(\sqrt{1 + 4x} − 1}{2} = (1 − x)xC(−x), or y = −\frac{(1 − x)(1 + \sqrt{1 + 4x})}{2}.

Here,

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

is the generating function of the Catalan numbers. The first solution expands to give the sequence that begins

0, 1, −2, 3, −7, 19, −56, 174, −561, 1859, −6292,

while the second solution begins

−1, 0, 2, −3, 7, −19, 56, −174, 561, −1859, 6292, ….

We are interested in the common part of these sequences, namely the sequence that begins

2, −3, 7, −19, 56, −174, 561, −1859, 6292, ….

This has its generating function given by

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

We wish to work with a sequence with initial term 1, which has essentially the same Hankel transform as this sequence. Thus we take the generating function

f_{1}(x) = \frac{1}{1 − x − x^{2}f(x)} = \frac{2}{1 − 3x + (1 − x)\sqrt{(}1 + 4x)} = \frac{−(x − 1)\sqrt{1 + 4x} − 3x + 1}{2x(x^{2} − 4x + 2)}.

Using the fundamental theorem of Riordan arrays [2, 17], we can express this as

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

We now revert xf_{1}(x), and divide the result by x, to obtain the generating function a(x) given by

a(x) = \frac{1 + 3x + 4x^{2} − (1 + x)\sqrt{1 + 4x + 8x^{2}}}{2x^{3}} .

This expands to give a sequence a_{n} that begins

1, −1, −1, 8, −22, 33, 7, −212, 702, −1202, −58, ….

This sequence satisfies the convolution recurrence (generalized Catalan recurrence)

a_{n} = −3a_{n−1} − 4a_{n−2} + 2a_{n−3} + ∑_{k=1}^{n−4} a_{k}a_{n−k−3},

with a_{0} = 1, a_{1} = −1, a_{2} = −1, a_{3} = 8. The Hankel transform of this sequence begins

1, −2, −3, 5, 8, −13, −21, 34, 55, −89, −144, ….

Thus we now have a sequence a_{n}, constructed from the elliptic curve equation, that has the same Hankel transform as ã_{n}. Moreover, we know the generating function of a_{n}. We can express a(x) as

a(x) = (\frac{1 + 2x}{1 + 3x + 4x^{2}} , \frac{x^{3}(1 + 2x)}{(1 + 3x + 4x^{2})^{2}} ) · C(x).

It remains to relate ã(x) = g_{E,P} (x) to a(x).

In this special case, the solution is quite easy to state. We have

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

In other words, the generating function g_{E}(x) of ã_{n} = (−1)^{\binom{n+1}{2}}C_{⌊ \frac{n+1}{2} ⌋} is given by taking the second inverse binomial transform of the generating function of the sequence (−1)^{n}a_{n}. We can verify this algebraically as follows. We take the generating function

a(x) = \frac{1 + 3x + 4x^{2} − (1 + x)\sqrt{1 + 4x + 8x^{2}}}{2x^{3}} .

We now form the generating function of (−1)^{n}a_{n} which is

a(−x) = −\frac{1 − 3x + 4x^{2} − (1 − x)\sqrt{1 − 4x + 8x^{2}}}{2x^{3}} .

Taking the second inverse binomial transform now gives us

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

We can verify independently that this last generating function is indeed the generating function of ã_{n} = (−1)^{\binom{n+1}{2}}C_{⌊ \frac{n+1}{2} ⌋}.

We have

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

The sequence ã_{n} is the moment sequence (see the Appendix) of the family of orthogonal polynomials P_{n}(t) defined by the three-term recurrence

P_{n}(t) = (t + \frac{x_{n−1}}{y_{n−1}} )P_{n−1}(t) + x_{n−1}P_{n−2}(t)

= (t − \frac{(−1)^{n}}{F_{n}F_{n+1}} ) P_{n−1}(t) + \frac{F_{n−1}F_{n+1}}{F_{n}^{2}} P_{n−2}(t),

with P_{0}(t) = 1, P_{1}(t) = t + 1.

The coefficient array of the family P_{n}(t) then begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3/2 & 1/2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 7/3 & 2/3 & 1 & 0 & 0 & 0 \\ 8/5 & 7/5 & 17/5 & 3/5 & 1 & 0 & 0 \\ 1 & 31/8 & 17/8 & 35/8 & 5/8 & 1 & 0 \\ 21/13 & 31/13 & 95/13 & 35/13 & 70/13 & 8/13 & 1 \end{matrix} ) .

The inverse of this matrix, which is the moment matrix, begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1/2 & 1 & 0 & 0 & 0 & 0 \\ 2 & −2 & −2/3 & 1 & 0 & 0 & 0 \\ 2 & 3/2 & −3 & −3/5 & 1 & 0 & 0 \\ −5 & 5 & 8/3 & −4 & −5/8 & 1 & 0 \\ −5 & −9/2 & 9 & 3 & −5 & −8/13 & 1 \end{matrix} ) .

This exhibits the sequence ã_{n} as a moment sequence.

We note that the denominators in the coefficient matrix of the orthogonal polynomials are the Fibonacci numbers. Scaling up by these, we get the integer matrix that begins as follows.

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 2 & 0 & 0 & 0 & 0 \\ 3 & 7 & 2 & 3 & 0 & 0 & 0 \\ 8 & 7 & 17 & 3 & 5 & 0 & 0 \\ 8 & 31 & 17 & 35 & 5 & 8 & 0 \\ 21 & 31 & 95 & 35 & 70 & 8 & 13 \end{matrix} ) .

The row sums of this matrix are given by F_{n+1}F_{n+2}.

The generating function of ã_{n} can be described using Riordan arrays as follows.

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

A consequence of this is that the sequence ã_{n} satisfies the convolution recurrence

ã_{n} = −ã_{n−1} − 2ã_{n−2} − 2ã_{n−3} − ∑_{k=1}^{n−4} ã_{k}ã_{n−k−3},

with a_{0} = 1, a_{1} = −1, a_{2} = −1, a_{3} = 2.

2 Preliminaries

The product of two power series

a(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ⋯ = ∑_{n=0}^{∞} a_{n}x^{n}

and

b(x) = b_{0} + b_{1}x + b_{2}x^{2} + b_{3}x^{3} + ⋯ = ∑_{n=0}^{∞} b_{n}x^{n}

is given by

a(x)b(x) = a_{0}b_{0} + (a_{0}b_{1} + a_{1}b_{0})x + (a_{0}b_{1} + a_{1}b_{1} + a_{1}b_{0})x^{2} + · · · .

That is,

a(x)b(x) = ∑_{n=0}^{∞} (∑_{k=0}^{n} a_{k}b_{n−k}) x^{n}.

The term ∑_{k=0}^{n} a_{k}b_{n−k} is called the convolution of a_{0}, a_{1}, ⋯, a_{n} with b_{0}, b_{1}, …, b_{n}. Note that if we multiply the shifted sequences a_{1} + a_{2}x + a_{3}x^{2} + ⋯ and b_{1} + b_{2}x + b_{3}x^{2} + ⋯, then the product will begin

a_{1}b_{1} + (a_{1}b_{2} + a_{2}b_{1})x + (a_{1}b_{3} + a_{2}b_{2} + a_{3}b_{1})x^{2} + ⋯,

or

∑_{n=0}^{∞} (∑_{k=1}^{n+1} a_{k}b_{n+2−k}) x^{n}.

This can be also be written as

∑_{n=0}^{∞} (∑_{k=0}^{n} a_{k+1}b_{n+1−k}) x^{n}.

Expressions such as ∑_{k=0}^{n} a_{k}b_{n−k} are known as convolutions, and equations involving terms of a sequence and such convolutions are known as convolution recurrences. For instance,

C_{n} = ∑_{k=0}^{n−1} C_{k}C_{n−1−k},

where we stipulate C_{0} = 1, is a well known convolution recurrence. Note that we have C_{1} = C_{0}C_{0}, C_{2} = C_{0}C_{1} + C_{1}C_{0}, C_{3} = C_{0}C_{2} + C_{1}C_{1} + C_{2}C_{0}, and so on.

Starting from C_{0} = 1, we obtain C_{0} = 1, 1, 2, 5, 14, 42, . . .. These are the Catalan numbers \underline{A000108}. If we let C(x) = ∑_{n=0}^{∞} C_{n}x^{n}, then we see that

C_{1} + C_{2}x + C_{3}x^{2} + ⋯ = C_{0}C_{0} + (C_{0}C_{1} + C_{1}C_{0})x + … = C(x) × C(x) = C(x)^{2}.

Thus,

C(x) = C_{0} + C_{1}x + C_{2}x^{2} + ⋯ = C_{0} + x(C_{1} + C_{2}x + C_{3}x^{2} + …) = 1 + xC(x)^{2}.

This means that C(x), the generating function of the Catalan numbers, is a solution of the quadratic equation

u = 1 + xu^{2}, or xu^{2} − u + 1 = 0.

We obtain two solutions,

u(x) = \frac{1 − \sqrt{1 − 4x}}{2x} and \frac{1 + \sqrt{1 − 4x}}{2x}.

When x = 0, the second solution leads to a division by zero, so we choose the first solution. Thus

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

is the generating function of the Catalan numbers. In this note, shall seek to solve more generalized convolution recurrences. The Catalan numbers C_{n} and their generating function C(x) will play an important role in this discussion. This will arise because we will often be solving quadratic equations, as above. Thus if we consider a quadratic equation such as

au^{2} + bu + c = 0

then the solution

u = \frac{−b + \sqrt{b^{2} − 4ac}}{2a}

can be expressed as follows. We have

\frac{−c}{b}C (\frac{ac}{b^{2}}) = \frac{c}{b} (\frac{1 − \sqrt{1 − 4\frac{ac}{b^{2}}}}{2\frac{ac}{b^{2}}} )

= \frac{−b}{2a} (1 − \sqrt{1 − 4\frac{ac}{b^{2}}})

= \frac{1}{2a} (−b + b\sqrt{1 − 4\frac{ac}{b^{2}}})

= \frac{1}{2a} (−b + \sqrt{b^{2} − 4ac}) .

The squared terms that give rise to the quadratic expressions to be solved will in turn be explained in part by the presence of the convolution elements. For instance, if we multiply a shifted power sequence a_{1} + a_{2}x + a_{3}x^{2} + ⋯ by itself, thus getting a power series that begins

a_{1}a_{1} + (a_{1}a_{2} + a_{2}a_{1})x + (a_{1}a_{3} + a_{2}a_{2} + a_{3}a_{1})x^{2} + ⋯,

then the generating function of this expression will be

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

where

a(x) = ∑_{n=0}^{∞} a_{n}x^{n}

is the generating function of the sequence a_{0}, a_{1}, a_{2}, . . .. (We have taken a_{0} = 1 for simplicity here).

The expression \frac{−c}{b}C (\frac{ac}{b^{2}}) is reminiscent of the fundamental theorem of Riordan arrays [2, 17], and in the cases that we shall consider, it will indeed be an instance of this result. We shall therefore use Riordan arrays [2, 16, 17] extensively. A Riordan array can be defined by a pair (g, f) of power series

g(x) = g_{0} + g_{1}x + g_{2}x^{2} + ⋯, g_{0} ≠ 0,

and

f(x) = f_{1}x + f_{2}x^{2} + f_{3}x^{3} + ⋯,

with indeterminate x and coefficients drawn from a suitable ring. To this pair we can associate the lower-triangular matrix with general (n, k)-th term T_{n,k} given by

T_{n,k} = [x^{n}]g(x)f(x)^{k}.

Here, [x^{n}] is the functional on power series that extracts the coefficient of x^{n} [14]. Thus this matrix is the “Riordan array” associated with the pair (g, f). In practice, we refer to either as a Riordan array. The fundamental theorem of Riordan arrays asserts that the action of the pair (g, f) acting on the generating function h(x) as defined by

(g(x), f(x)) · h(x) = g(x)f(h(x))

is mirrored by multiplying the (infinite) vector whose elements are given by the expansion of h(x) by the matrix (T_{n,k}).

When f_{1} ≠ 0 the matrices have a non-zero diagonal and hence they are invertible. If f_{1} = 0 we have arrays that are often described as “stretched”, which are not invertible in the usual sense. The fundamental theorem still holds.

Somos-4 sequences are defined using the Weierstrass σ function for appropriate elliptic curves. The link between this σ function and the Hankel transform [11, 12, 13] explains the importance of the Hankel transform in this note. The motivating example shows how the x− and y− coordinates of the multiples of special points on an elliptic curve can give rise to integer sequences whose Hankel transform is then the Somos-4 sequence for that point. The link to the title of this note is that these sequences satisfy a recurrence of the desired type.

Where we encounter sequences that appear in the On-Line Encyclopedia of Integer Sequences [18, 19], we refer to them by their Annnnnn number.

The r-th binomial transform b_{n} of the sequence a_{n} has general term b_{n} = ∑_{k=0}^{n} \binom{n}{k}r^{n−k}a_{k}. If the sequence a_{n} has a generating sequence g(x), then the sequence b_{n} has generating function \frac{1}{1−rx}g (\frac{x}{1−rx}).

The Invert(a) transform of the sequence a_{n} whose generating function is g(x) will have a generating function given by \frac{g(x)}{1−axg(x)} = (g(x), xg(x)) · \frac{1}{1−ax}.

If the generating function g(x) of a sequence a_{n} can be expressed as a Stieltjes continued fraction

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

then the r-th binomial transform of a_{n} will have a generating function given by

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

The Invert(a) transform of a_{n} will have a generating function given by

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

The generating function g(x) above will be designated by J (α_{0}, α_{1}, …; β_{1}, β_{2}, …).

If a sequence a_{0}, a_{1}, … with generating function g(x) has a Hankel transform that begins h_{0}, h_{1}, … then the sequence with generating function \frac{1}{1−x−x^{2}g(x)} will have a Hankel transform that begins 1, h_{0}, h_{1}, . . .. In addition, this new sequence will have its initial term equal to 1.

More information on orthogonal polynomials, Riordan arrays and Hankel transforms may be found in the Appendix.

3 Generalized Catalan recurrences

We let C_{n} = \frac{1}{n+1} \binom{2n}{n} denote the n-th Catalan numbers \underline{A000108}. The sequence of Catalan numbers has generating function C(x) = \frac{1−\sqrt{1−4x}}{2x}. The Catalan numbers begin

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….

The large Schroeder numbers S_{n} \underline{A006318} can then be defined by

S_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}C_{k}.

These numbers begin

1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, ….

Using the theory of Riordan arrays, we see that the generating function S(x) of the large Schroeder numbers is given by an application of the fundamental theorem of Riordan arrays [2, 17], which in this case says that

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

This follows since the matrix representation of the Riordan array (\frac{1}{1−x}, \frac{x}{(1−x)^{2}} ) has general term

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

Simplifying, we find that

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

We now consider the generating function \frac{C(x)+C(−x)}{2} = \frac{\sqrt{1+4x}+\sqrt{1−4x}}{2x}, which expands to give the sequence

1, 0, 2, 0, 14, 0, 132, 0, 1430, 0, 16796, …,

which is the aerated sequence of Catalan numbers of even index \underline{A048990}. We once again apply the Riordan array (\frac{1}{1−x}, \frac{x}{(1−x)^{2}} ) to this sequence, resulting in the sequence that begins

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ….

The generating function of this sequence, which is called the sequence of little Schroeder numbers s_{n} \underline{A001003}, is then given by

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

We deduce that

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

We can further use Riordan arrays to characterize these two sequences. The theory of Riordan arrays and orthogonal polynomials [2, 3, 4] allows us to derive the following result.

Proposition 1. The large Schroeder numbers S_{n} are the moments of the family of orthogonal polynomials whose coefficient array is given by the Riordan array

(\frac{1}{1 + 2x}, \frac{x}{1 + 3x + 2x^{2}} )

and the little Schroeder numbers s_{n} are the moments of the family of orthogonal polynomials whose coefficient array is given by the Riordan array

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

One consequence of this result is the following.

Corollary 2. The Hankel transform H_{n} = |S_{i+j}|_{0≤i,j≤n} of the large Schroeder numbers, and the Hankel transform h_{n} = |s_{i+j}|_{0≤i,j≤n} of the little Schroeder numbers satisfy

H_{n} = h_{n} = 2^{\binom{n+1}{2}}.

Another corollary, which we can prove independently, is that the generating function S(x) of the large Schroeder numbers has the following Jacobi continued fraction [5, 23] form:

S(x) = \frac{1}{1 − 2x − \frac{2x^{2}}{1 − 3x − \frac{2x^{2}}{1 − 3x − \frac{2x^{2}}{1 − 3x − ⋯}}}},

which we express as

S(x) = J (2, 3, 3, 3, …; 2, 2, 2, …).

We solve for v in the equation

v = \frac{1}{1 − 3x − 2x^{2}v} ,

then we verify that

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

We similarly have

s(x) = J (1, 3, 3, 3, …; 2, 2, 2, …).

The Schroeder number sequences S_{n} and s_{n} each satisfy a simple convolution recurrence. For S_{n}, we have [15]

S_{n} = 3S_{n−1} + ∑_{k=0}^{n−3} S_{k+1}S_{n−k−2},

with initial conditions S_{0} = 1, S_{1} = 2. Note that we can write this as

S_{n} = 3S_{n−1} + ∑_{k=1}^{n−2} S_{k}S_{n−k−1}.

The summation in the recurrence is then equal to

S_{1}S_{n−2} + S_{2}S_{n−3} + ⋯ + S_{n−2}S_{1}.

For s_{n}, we have

s_{n} = 3s_{n−1} + 2 ∑_{k=0}^{n−3} s_{k+1}s_{n−k−2},

with initial conditions s_{0} = 1, s_{1} = 1. These recurrences, and their generalizations, will be the subject of this note.

Proposition 3. We consider the generalized Catalan-Schroeder recurrence

a_{n} = sa_{n−1} + t ∑_{k=0}^{n−3} a_{k+1}a_{n−k−2},

with initial conditions a_{0} = 1, a_{1} = p. Then the generating function of the sequence a_{n} is given by

(\frac{1 + (p − s + t)x}{1 − (s − 2t)x}, \frac{tx(1 + (p − s + t)}{(1 − (s − 2t)x)^{2}}) · C(x).

Note that when p = 2, s = 3 and t = 1, we obtain

(\frac{1 + (2 − 3 + 1)x}{1 − (3 − 2)x}, \frac{x(1 + (2 − 3 + 1)x)}{(1 − (3 − 2)x)^{2}}) · C(x) = (\frac{1}{1 − x}, \frac{x}{(1 − x)^{2}} ) · C(x) = S(x),

while when p = 1, s = 3 and t = 2, we obtain

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

Note that this last result gives us that

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

Proof. The terms a_{1}a_{n−2} + ⋯ + a_{n−2}a_{1}, for n ≥ 3, successively contribute the terms a_{1}a_{1},

a_{1}a_{2} + a_{2}a_{1},
a_{1}a_{3} + a_{2}a_{2} + a_{3}a_{1}, ….

These correspond to the coefficients in the product

(a_{1} + a_{2}x + a_{3}x^{2} + ⋯)(a_{1} + a_{2}x + a_{3}x^{2} + ⋯).

This product has generating function

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

Thus we can convert the recurrence

a_{n} = sa_{n−1} + t ∑_{k=0}^{n−3} a_{k+1}a_{n−k−2}, n ≥ 2

into the following statement about the generating function u(x) = ∑_{n=0}^{∞} a_{n}x^{n} = 1 + px + ∑_{n=2}^{∞} a_{n}x^{n}:

u = 1 + px + sx(u − 1) + tx(u^{2} − 2u + 1).

Solving this, we get

u(x) = \frac{1 − (s − 2t)x − \sqrt{1 − 2sx + (s^{2} − 4pt)x^{2}}}{2tx} .

This is equal to

(\frac{1 + (p − s + t)x}{1 − (s − 2t)x}, \frac{tx(1 + (p − s + t)x)}{1 − (s − 2t)x}) · C(x).

Corollary 4. The generating function

(\frac{1 + ax}{1 + bx}, \frac{mx(1 + ax)}{(1 + bx)^{2}}) · C(x)

expands to give the sequence solution of the convolution recurrence

a_{n} = (−b + 2m)a_{n−1} + m ∑_{k=0}^{n−3} a_{k+1}a_{n−k−3},

with a_{0} = 1, a_{1} = a − b + m.

Example 5. We calculate the general term T_{n,k} of the Riordan array (\frac{1+ax}{1+bx}, \frac{mx(1+ax)}{(1+bx)^{2}}). We have

T_{n,k} = [x^{n}]\frac{1 + ax}{1 + bx} (\frac{mx(1 + ax)}{1 + bx})^{k}

= m^{k}[x^{n−k}]\frac{(1 + ax)^{k+1}}{(1 + bx)^{2k+1}}

= m^{k}[x^{n−k}] ∑_{j=0}^{k+1} \binom{k + 1}{j}a^{j}x^{j} ∑_{i=0}^{∞} \binom{−(2k + 1)}{i}b^{i}x^{i}

= m^{k}[x^{n−k}] ∑_{j=0}^{k+1} \binom{k + 1}{j}a^{j}x^{j} ∑_{i=0}^{∞} \binom{2k + 1 + i − 1}{i}(−1)^{i}b^{i}x^{i}

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

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

Thus the expansion of \frac{1+ax}{1+bx}C (\frac{mx(1+ax)}{1+bx}) has general term given by

a_{n} = ∑_{k=0}^{n}(∑_{j=0}^{k+1} \binom{k + 1}{j}\binom{n + k − j}{2k}a^{j}(−b)^{n−k−j})m^{k}C_{k}.

Note that in practice care has to be taken with the terms T_{0,k} using the above formula so we have the following correction (for a ≠ 0).

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

We denote the general solution of the recurrence

a_{n} = sa_{n−1} + t ∑_{k=0}^{n−3} a_{k+1}a_{n−k−2},

with initial conditions a_{0} = 1, a_{1} = p by a_{n}(p, s, t).

Example 6. When (p, s, t) = (1, 1, 1), we get the sequence a_{n}(1, 1, 1) that begins

1, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, ….

These are the Motzkin numbers, with a 1 prepended. The Hankel transform of this sequence has generating function \frac{1−x}{1−x+x^{2}} , beginning

1, 0, −1, −1, 0, 1, 1, 0, −1, ….

The Hankel transform of the shifted sequence (the Motzkin numbers) is known to be the given by the all 1’s sequence 1, 1, 1, 1, . . .. The generating function of the Motzkin numbers is J (1, 1, 1, …; 1, 1, 1, …).

Example 7. When (p, s, t) = (1, 1, 2), we get the sequence a_{n}(1, 1, 2) that begins

1, 1, 1, 3, 7, 21, 61, 191, 603, 1961, 6457, 21595, ….

This is the sequence \underline{A025235} with a prepended 1. The sequence \underline{A025235} counts Motzkin paths with the up step in two colors. The Hankel transform of a_{n}(1, 1, 2) begins

1, 0, −4, −16, 128, 6144, 65536, −20971520, −3758096384, …

while that of the shifted sequence u_{n+1}(1, 1, 2) or \underline{A025235} is 2^{\binom{n+1}{2}}. This follows from the fact that the generating function of this latter sequence is J (1, 1, 1, …; 2, 2, 2, …).

Example 8. When (p, s, t) = (1, 2, 1), the sequence a_{n}(1, 2, 1) that we get is the sequence of Catalan numbers C_{n}. This corresponds to a bijection between 2-colored Motzkin paths (where the level step can have one of two colors) of length n − 1 and Dyck paths. It is a classical result that the Hankel transforms of this sequence and its shift C_{n+1} are the all 1’s sequence.

With regard to the shifted sequence a_{n+1}(p, s, t), we have the following result.

Proposition 9. The sequence \frac{1}{p}a_{n+1}(p, s, t) has generating function J (s, s, s, …; pt, pt, pt, …),

and Hankel transform (pt)^{\binom{n+1}{2}} (for p ≠ 0).

Proof. The sequence with generating function J (s, s, s, …; pt, pt, pt, …) has a generating function g(x) that satisfies

g(x) = \frac{1}{1 − sx − ptx^{2}g(x)}.

Solving this equation gives us

g(x) = \frac{1 − sx − \sqrt{1 − 2sx + (s^{2} − 4pt)x^{2}}}{2ptx^{2}} .

We see that this is the generating function of \frac{1}{p}a_{n+1}(p, s, t).

Corollary 10. The sequence \frac{1}{p}a_{n+1}(p, s, t) is the moment sequence for the family of orthogonal polynomials whose coefficient array is given by the Riordan array

(\frac{1}{1 + sx + ptx^{2}} , \frac{x}{1 + sx + ptx^{2}} ) .

Corollary 11. We have the moment representation

\frac{1}{p}a_{n+1}(p, s, t) = \frac{1}{2π} ∫_{s−2\sqrt{pt}}^{s+2\sqrt{pt}} x^{n} \frac{\sqrt{−x^{2} + 2sx + 4pt − s^{2}}}{pt} dt.

Proof. We apply the Stieltjes-Perron transform [9] to the generating function of a_{n+1}.

Corollary 12. If s = 0 and t ≠ 0, we have

a_{n}(p, 0, t) = \frac{1}{2π} ∫_{−2\sqrt{pt}}^{2\sqrt{pt}} x^{n} \frac{\sqrt{4pt − x^{2}}}{tx} dx + 0^{n}.

Corollary 13. If s ≠ 0 and t ≠ 0, we have

a_{n}(p, s, t) = \frac{1}{2π} ∫_{s−2\sqrt{pt}}^{s+2\sqrt{pt}} x^{n} \frac{\sqrt{−x^{2} + 2sx + 4pt − s^{2}}}{tx} dx+0^{n} (1 − \frac{s}{2t} − sgn(4pt − s^{2})\frac{\sqrt{s^{2} − 4pt}}{2t}) .

We can formulate the following conjecture concerning the Hankel transform of the sequence a_{n}(p, s, t).

Conjecture 14. The Hankel transform h_{n}(p, s, t) of the sequence a_{n}(p, s, t) is given by

h_{n}(p, s, t) = t^{\binom{n}{2}}p^{\binom{n+1}{2}}[x^{n}]\frac{1 − px}{1 − sx + ptx^{2}}

= t^{\binom{n}{2}}p^{\binom{n+1}{2}} (∑_{i=0}^{n} \binom{i}{n − i}(−pt)^{n−i}s^{2i−n} − p ∑_{i=0}^{n−1} \binom{i}{n − i − 1}(−pt)^{n−i−1}s^{2i−n+1}) .

We note that we have

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

Thus the Hankel transform h_{n}(p, s, t) is given by the evaluation of a sequence of scaled orthogonal polynomials, since the Riordan array (\frac{1−x}{1+ptx^{2}} , \frac{x}{1+ptx^{2}} ) is the coefficient matrix of a family of orthogonal polynomials [4].

We have the following conjecture concerning the Hankel transforms h_{n}(p, s, t) and Somos-4 sequences. Recall that a (α, β) Somos-4 sequence is a sequence e_{n} that satisfies

e_{n} = \frac{αe_{n−1}e_{n−3} + βe_{n−2}^{2}}{e_{n−4}}

for given e_{0}, e_{1}, e_{2}, e_{3}. Somos-4 sequences are closely related to elliptic curves [10, 25].

Conjecture 15. The Hankel transform h_{n}(p, s, t) of the generalized Schroeder numbers a_{n}(p, s, t) is a ((pst)^{2}, (pt)^{3}(pt − s^{2})) Somos-4 sequence.

Example 16. We consider the sequence a_{n}(1, −1, −1) which begins

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

Its Hankel transform is the signed Fibonacci sequence

1, −2, −3, 5, 8, −13, …

with general term (−1)^{\binom{n}{2}}F_{n+1}. This is a (trivial) (1, 2) Somos-4 sequence.

Example 17. The sequence a_{n}(2, 1, 1) begins

1, 2, 2, 6, 14, 42, 122, 382, 1206, 3922, 12914, ….

This is \underline{A014431}. Its Hankel transform begins

1, −2, −24, −64, 5120, 229376, ….

This is a (4, 8) Somos-4 sequence.

4 A third-order recurrence

We begin this section by looking at the generalized Catalan recurrence

a_{n} = ra_{n−1} + sa_{n−2} + t ∑_{k=1}^{n−3} a_{k}a_{n−k−2},

with a_{0} = 1, a_{1} = p and a_{2} = q. This may equivalently be written as

a_{n} = ra_{n−1} + sa_{n−2} + t ∑_{i=0}^{n−4} a_{i+1}a_{n−i−3},

with a_{0} = 1, a_{1} = p and a_{2} = q. Thus in the summation part, the sum is

a_{1}a_{n−3} + ⋯ + a_{n−3}a_{1}.

We shall denote the solution of this recurrence by a_{n}(p, q, r, s, t). This sequence begins

1, p, q, ps + qr, p^{2}t + prs + q(r^{2} + s), p^{2}rt + p(2qt + r^{2}s + s^{2}) + qr(r^{2} + 2s), ….

We let u(x) = u(x; p, q, r, s, t) be the generating function of this solution sequence. We have the following proposition.

Proposition 18. The generating function u(x) is given by

(\frac{1 − (r − p)x − (−q + pr + s − t)x^{2}}{1 − rx − (s − 2t)x^{2}} , \frac{tx^{2}(1 − (r − p)x − (−q + pr + s − t)x^{2})}{(1 − rx − (s − 2t)x^{2})^{2}}) · C(x).

Proof. We translate the recurrence (for n ≥ 3) and the initial conditions into the following equation for the generating function u(x) = ∑_{n=0}^{∞} a_{n}(p, q, r, s, t)x^{n}.

u(x) = 1 + px + qx^{2} + rx(u − 1 − xp) + sx^{2}(u − 1) + tx^{2}(u^{2} − 2u + 1).

Then the solution is given by

u(x) = \frac{1 − rx − (s − 2t)x^{2} − \sqrt{1 − 2rx + (r^{2} − 2s)x^{2} + 2(rs − 2pt)x^{3} + (s^{2} − 4qt + 4prt)x^{4}}}{2tx^{2}} .

This is equal to

(\frac{1 − (r − p)x − (−q + pr + s − t)x^{2}}{1 − rx − (s − 2t)x^{2}} , \frac{tx^{2}(1 − (r − p)x − (−q + pr + s − t)x^{2}}{(1 − rx − (s − 2t)x^{2})^{2}} ) · C(x).

Example 19. The sequence a_{n}(1, 2, 2, 1, 1) begins

1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, ….

This is \underline{A086581}, which counts the number of Dyck paths of semi-length n that avoid DDUU. In this case we have

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

The generating function is

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

Example 20. The sequence a_{n}(1, 2, 1, 2, 1) coincides with the Motzkin numbers M_{n}. The generating function is

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

so that

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

Example 21. The sequence a_{n}(1, 2, 2, 2, 1) begins

1, 1, 2, 6, 17, 50, 150, 458, 1420, 4460, 14165, ….

This is \underline{A025272}(n + 1). It has as generating function the power series given by

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

The Hankel transform of the shifted sequence a_{n+1} in this case begins

1, 2, 3, −5, −28, −67, −411, −506, 10855, 74231, 664776, ….

This is the (1, −2) Somos-4 sequence \underline{A178376}(n + 1), which is defined by the elliptic curve y^{2} + y = x^{3} + 3x^{2} + x.

Example 22. The sequence −a_{n+1}(−1, 2, −2, −1, −1) begins

1, −2, 3, −3, −1, 15, −47, 98, −133, 17, 579, …,

It has its generating function given by

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

Its Hankel transform begins

1, −1, 1, 2, −1, −3, …

which is a (1, 1) Somos-4 sequence. This is a variant of \underline{A006769}, which is the elliptic divisibility sequence associated with elliptic curve E : y^{2} + y = x^{3} − x and multiples of the point (0, 0). In this case, the sequence a_{n}(−1, 2, −2, −1, −1) begins

1, −1, 2, −3, 3, 1, −15, 47, −98, 133, −17, −579, …

and its Hankel transform is the (1, 1)-Somos sequence beginning

1, 1, −2, −1, 3, −5, …,

which is (−1)^{n+1}\underline{A006769}(n + 3).

Example 23. The sequence a_{n}(−1, −2, 2, −1, −1) begins

1, −1, −2, −3, −5, −11, −27, −65, −154, −371, −917, −2303, ….

Its generating function is given by

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

Its Hankel transform begins

1, −3, 2, 11, −29, −21, …

which is a (1, 1) Somos-4 sequence. It is a variant of \underline{A178384}, which is associated to the elliptic curve y^{2}+y = x^{3}+x. The shifted sequence −a_{n+1} in this case has a Hankel transform that begins

1, −1, −3, −2, 11, 29, ….

We have the following two conjectures regarding these sequences, their Hankel transforms, and Somos-4 sequences. The first conjecture claims that in all cases, the sequence \frac{1}{p}a_{n+1}(p, q, r, s, t) has a Somos-4 Hankel transform.

Conjecture 24. The Hankel transform of the sequence \frac{1}{p}a_{n+1}(p, q, r, s, t) is a ((pt)^{2}, −t^{2}(p^{2}s+ pqr − q^{2})) Somos-4 sequence.

Conjecture 25. If r = 1, t = 1 and s = q − p + 1, then the sequence a_{n}(p, q, r, s, t) = a_{n}(p, q, 1, q − p + 1, 1) has a Hankel transform that is a (p^{2}, p^{3} − pq + q^{2} − p^{2}(1 + q)) Somos-4 sequence.

We note that in this last case, the generating function of the sequence a_{n} will be given by

(\frac{1 − (1 − p)x}{1 − x + (p + q − 1)x^{2}} , \frac{x^{2}(1 − (1 − p)x)}{(1 − x + (p + q − 1)x^{2})^{2}} ) · C(x).

In another direction, it is interesting to consider sequences with generating functions of the form

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

For these, we have the following conjecture.

Conjecture 26. The Hankel transform h_{n} of the sequence with generating function

\frac{1 − x − αx^{2}}{1 − x − x^{2}} C (\frac{x^{2}(1 − x − αx^{2})}{(1 − x − x^{2})^{2}})

is given by

h_{n} = (2 − α)^{⌊ \frac{(n+1)^{2}}{4} ⌋}[x^{n}]\frac{(1 + x)(1 + (α − 2)x^{2})}{1 − 3x^{2} − (α − 2)x^{4}}.

Note that

\frac{(1 + x)(1 + (α − 2)x^{2})}{1 − 3x^{2} − (α − 2)x^{4}} = (1 + x)f(x^{2}; α),

where

f(x; α) = \frac{1 + (α − 2)x}{1 − 3x − (α − 2)x^{2}} .

For instance, when α = 1, we get the generating function \frac{1−x}{1−3x+x^{2}} of the bisected Fibonacci numbers F_{2n+1} 1, 2, 5, 13, 34, 89, … \underline{A001519}(n + 1). In general, if we set

d_{n} = ∑_{k=0}^{n} \binom{k}{n − k}(α − 2)^{n−k}3^{2k−n} + (α − 2) ∑_{k=0}^{n} \binom{k}{n − k − 1}(α − 2)^{n−k−1}3^{2k−n+1}

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

then we have

h_{n} = (2 − α)^{⌊ \frac{(n+1)^{2}}{4} ⌋}d_{⌊ \frac{n}{2} ⌋}.

Note that here \binom{k}{n−k} + 3\binom{k}{n−k−1} is the general term of the Riordan array (1 + 3x, x(1 + x)). In fact, we have

f(x; α) = (1 + (α − 2)x, x (1 + \frac{α − 2}{3}x))) · \frac{1}{1 − 3x}.

Example 27. We take α = 1, to get the equation

(1 − x, x (1 − \frac{x}{3})) · \frac{1}{1 − 3x} = \frac{1 − x}{1 − 3x + x^{2}} = ∑_{n=0}^{∞} F_{2n+1}x^{n},

which is the generating function of the Fibonacci bisection F_{2n+1} that begins 1, 2, 5, 13, 34, . . .. We have 2 − α = 1. In this case the sequence we get begins

1, 0, 1, 1, 4, 7, 20, 43, 112, 263, 669, 1640, 4166, …

with generating function

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

The Hankel transform is then given by F_{2⌊ \frac{n}{2} ⌋+1}, or

1, 1, 2, 2, 5, 5, 13, 13, 34, 34, ….

Example 28. We take α = −1. Then 2 − α = 3. The sequence in question has generating function

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

We obtain the sequence that begins

1, 0, 3, 3, 12, 21, 66, 147, 426, 1065, 3009, 7986, 22476, ….

The Hankel transform begins

1, 3, 0, 0, −2187, −59049, −4782969, ….

Dividing this by 3^{⌊ \frac{(n+1)^{2}}{4} ⌋}, we obtain

1, 1, 0, 0, −3, −3, −9, …

which is the expansion of (1 + x)(1 − 3x^{2})/(1 − 3x^{2} + 3x^{4}). This is the doubling of the sequence

1, 0, −3, −9, −18, −27, −27, 0, 81, 243, 486, …

which has generating function \frac{1−3x}{1−3x+3x^{2}} .

Example 29. The case of α = 2 is of special interest. We have 2 − α = 0, so that the Hankel transform is just the sequence 1, 0, 0, 0, . . .. This is explained by the fact that

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

A choice of parameters (p, q, r, s, t) that satisfies this context is given by (p, q, r, s, t) = (0, 2 − α, 1, 3, 1). Thus the recurrence

a_{n} = a_{n−1} + 3a_{n−2} + ∑_{k=1}^{n−3} a_{k}a_{n−k−2},

with a_{0} = 1, a_{1} = 0, a_{2} = α − 2 will have a solution with generating function given by \frac{1−x−αx^{2}}{1−x−x^{2}} C (\frac{x^{2}(1−x−αx^{2})}{(1−x−x^{2})^{2}}). We can reformulate our conjecture in the following manner.

Conjecture 30. The solution a_{n}(β) of the recurrence

a_{n} = a_{n−1} + 3a_{n−2} + ∑_{k=1}^{n−3} a_{k}a_{n−k−2},

with a_{0} = 1, a_{1} = 0, a_{2} = β has a Hankel transform h_{n}(β) given by

h_{n}(β) = β^{⌊ \frac{(n+1)^{2}}{4} ⌋}[x^{n}]\frac{(1 + x)(1 − βx^{2})}{1 − 3x^{2} + βx^{4}}.

We can convert from the recurrence to the Riordan array and vice versa. Thus given (p, q, r, s, t), we obtain (a, b, c, d, m) as follows:

a = p − r
b = q − pr − s + t
c = −r
d = −s + 2t
m = t

Given (a, b, c, d, m), we obtain (p, q, r, s, t) as follows.

p = a − c
q = −ac + b + c^{2} − d + m
r = −c
s = −d + 2m
t = m.

A related result is the following. Proposition 31. Assume that a_{n} satisfies the following convolution recursion relation:

a_{n} = \begin{cases}1, & if n = 0; \\ r, & if n = 1; \\ ra_{n−1} + sa_{n−2} + t ∑_{i=0}^{n−2} a_{i}a_{n−2−i}, & if n > 1. \end{cases}

Then the sequence a_{n} has generating function

(\frac{1}{1 − rx − sx^{2}} , \frac{tx^{2}}{(1 − rx − sx^{2})^{2}} ) · C(x),

and the Hankel transform of a_{n} is a ((pt)^{2}, t^{2}(t + s)^{2} − r^{2}t^{3}) Somos-4 sequence. Note that ∑_{i=0}^{n−2} a_{i}a_{n−2−i} expands to give (a_{0}a_{n−2} + ⋯ + a_{n−2}a_{0}).

Proof. For a proof of the Hankel transform assertion, see [6]. We translate the recurrence to the equality

u(x) = 1 + rxu(x) + sx^{2}u(x) + tx^{2}u(x)^{2}.

Solving for u(x) now gives the result.

Examples of such sequences are given in the following table.

(r, s, t) Annnnnn  Description
(1, 1, 1) \underline{A128720}  Skew Dyck paths avoiding UUU
(2, 1, 1) \underline{A085139}(n + 1) G.f. is J (2, 1, 2, 2, 1, 2, 2, 1, 2, …; 2, 2, 1, 2, 2, 1, …)
(1, 2, 1) \underline{A174171}  Chebyshev transform of Motzkin numbers
(2, 2, 1) \underline{A174403}  Hankel transform is \underline{A174404}
(3, 1, 1) \underline{A084782}(n + 1)  \underline{A084782}(n) = ∑_{j=0}^{n} ∑_{i=0}^{j} a_{i}a_{j−i}F_{n−j}
(1, 2, −1) \underline{A187256}  Peakless Motzkin paths, with level steps in two colors

The sequence a_{n} begins

1, r, r^{2} + s + t, r(r^{2} + 2s + 3t), r^{4} + r^{2}(3s + 6t) + s^{2} + 3st + 2t^{2}, ….

The sequence with prepended 1 that begins 1, 1, r, r^{2} + s + t, … then has generating function

(\frac{1 − (r − t − 1)x − sx^{2}}{1 − (r − 2t)x − sx^{2}} , \frac{x(1 − (r − t − 1)x − sx^{2}}{(1 − (r − 2t)x − sx^{2})^{2}} ) · C(x).

When t = 1, we get

(1, \frac{x}{1 − (r − 2)x − sx^{2}} ) · C(x).

In fact, we can modify the above proposition as follows.

Proposition 32. Assume that a_{n} satisfies the following convolution recursion relation:

a_{n} = \begin{cases}1, & if n = 0; \\ p, & if n = 1; \\ ra_{n−1} + sa_{n−2} + t ∑_{i=0}^{n−2} a_{i}a_{n−2−i}, & if n > 1. \end{cases}

Then the sequence a_{n} has generating function

(\frac{1 + (p − r)x}{1 − rx − sx^{2}} , \frac{tx^{2}(1 + (p − r)x}{(1 − rx − sx^{2})^{2}}) · C(x),

and the Hankel transform of a_{n} is a ((pt)^{2}, t^{2}((t + s)^{2} − p^{2}s + prs + prt − 2p^{2}t) Somos-4 sequence.

5 A further recurrence

We now consider the recurrence

a_{n} = ua_{n−1} + va_{n−2} + wa_{n−3} + t ∑_{k=1}^{n−4} a_{k}a_{n−k−3},

with a_{0} = 1, a_{1} = p, a_{2} = q, and a_{3} = s. We note that the term ∑_{k=1}^{n−4} a_{k}a_{n−k−3} here expands to give (a_{1}a_{n−4} + ⋯ + a_{n−4}a_{1}). We denote the solution of this recurrence by a_{n}(p, q, s, u, v, w, t). We then have the following result.

Proposition 33. The generating function of the sequence a_{n}(p, q, s, u, v, w, t) is given by

(\frac{1 + (p − u)x − (v + pu − q)x^{2} − (w − s − t + qu + pv)x^{3}}{1 − ux − vx^{2} − (w − 2t)x^{3}} ,

\frac{tx^{3}(1 + (p − u)x − (v + pu − q)x^{2} − (w − s − t + qu + pv)x^{3})}{(1 − ux − vx^{2} − (w − 2t)x^{3})^{2}}) · C(x).

Example 34. The sequence a_{n}(1, 1, 2, 1, 1, 1, 1) begins

1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, ….

This is \underline{A004149}(n + 1), which gives the number of Motzkin paths of length n with no peaks or valleys. The generating function of this sequence is given by

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

Example 35. The sequence a_{n}(1, 2, 3, 1, 1, 1, 1) which begins

1, 1, 2, 3, 6, 12, 25, 53, 114, 249, 550, 1227, 276, …

is \underline{A162985}. It counts the number of Dyck paths of semi-length n avoiding UUU, DDD and UUDUDD (Deutsch). Its generating function is given by

\frac{1}{1 − x − x^{2} + x^{3}} C (\frac{x^{3}}{(1 − x − x^{2} + x^{3})^{2}} ) .

Note that this generating function can be expressed as the continued fraction

\frac{1}{1 − x − x^{2} + x^{3} − \frac{x^{3}}{1 − x − x^{2} + x^{3} − \frac{x^{3}}{1 − x − x^{2} + x^{3} ⋯}}}.

Example 36. The sequence a_{n}(1, 1, 2, 1, 0, 2, 1) which begins

1, 1, 1, 2, 4, 7, 13, 26, 52, 104, 212, 438, 910, 1903, 4009, 8494, …

is \underline{A023431}. It counts the number of Motzkin paths of length n with no peaks and no double rises. Its generating function is given by

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

We then have

a_{n}(1, 1, 2, 1, 0, 2, 1) = ∑_{k=0}^{n} \binom{n − k}{2k}C_{k}.

It is interesting to note that the Riordan array (g(x), xg(x)) is a pseudo-involution in the Riordan group [1]. More generally, if

g(x; α) = (\frac{1}{1 − αx}, \frac{x^{3}}{(1 − αx)^{2}} ) · C(x)

then the Riordan array (g(x; α), xg(x; α)) is a pseudo-involution. For example, g(x; 2) is the generating function of a_{n}(2, 4, 9, 2, 0, 2, 1). We will then have

a_{n}(2, 4, 9, 2, 0, 2, 1) = ∑_{k=0}^{⌊ \frac{n}{3} ⌋} \binom{n − k}{2k}2^{n−3k}C_{k}.

This sequence is \underline{A091561} [1]. Its Hankel transform is the sequence

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

with generating function \frac{1−x}{1−x+x^{2}} .

Example 37. The sequence a_{n}(1, 2, 4, 1, 1, 2, 1) is the RNA sequence that begins

1, 1, 2, 4, 8, 17, 37, 82, 185, 423, 978, 2283, 5373, ….

This is \underline{A004148}, with generating function

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

The related sequence with generating function

\frac{1 − x}{1 − x − x^{2}} C (\frac{x^{3}(1 − x)}{(1 − x − x^{2})^{2}} )

begins

1, 0, 1, 2, 3, 7, 14, 28, 60, 126, 268, 579, 1253, ….

Its Hankel transform begins

1, 1, −2, −3, −7, 5, 32, 83, 87, −821, −2366, ….

This is a (1, −1) Somos-4 sequence. Example 38. The sequence a_{n}(1, 3, 6, 1, 2, 2, 1) begins

1, 1, 3, 6, 14, 33, 79, 194, 482, 1214, 3090, 7936, ….

This sequence has its generating function given by

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

Its Hankel transform begins

1, 2, 1, −7, −16, −57, −113, 670, 3983, 23647, ….

This is a (1, −2) Somos-4 sequence.

In general, we can conjecture that the sequences with generating function

\frac{1}{1 − x − αx^{2}} C (\frac{x^{3}}{(1 − x − αx^{2})^{2}} )

have Hankel transforms that are (1, −α) Somos-4 sequences. Such Hankel transforms begin

1, α, −1 + α, −1 + α − α^{3}, −2α + 3α^{2} − α^{3} − α^{4}, 1 − 3α + 3α^{2} − 2α^{3} + α^{4} − α^{6},

1 − 3α + 3α^{2} + 3α^{3} − 9α^{4} + 6α^{5} + α^{6} − 2α^{7},
3α − 12α^{2} + 19α^{3} − 11α^{4} − 3α^{5} + 5α^{6} + 2α^{7} − 3α^{8} + α^{10}, ….

For instance, the Hankel transform of the sequence with generating function

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

is the (1, 1) Somos-4 sequence \underline{A178627}(n + 1). The sequence \underline{A178627} is defined by the elliptic curve

E : y^{2} + xy − y = x^{3} − x^{2} + x.

These examples show that such sequences merit more study. Further evidence of this is given by the following conjecture concerning their Hankel transforms.

Conjecture 39. The Hankel transform of the sequence with generating function

\frac{1 − x − x^{2} − αx^{3}}{1 − x − x^{2} − x^{3}} C (\frac{x^{3}(1 − x − x^{2} − αx^{3})}{(1 − x − x^{2} − x^{3})^{2}})

is given by

h_{n} = A_{n}(α)(2 − α)^{B_{n}}

where

A_{n}(α) = [x^{n}]\frac{1 + (α − 2)x^{2} − (α − 2)x^{3} + (4α − 5)x^{5} − (α − 1)(α − 2)x^{8}}{1 + 3x^{3} − (α − 2)x^{6}} ,

and

B_{n} = [x^{n}]\frac{x(1 − x + 2x^{2} − 2x^{3} + 3x^{4} − 3x^{5} + x^{6})}{(1 − x)^{2}(1 − x^{3})}.

The sequence B_{n} begins

0, 1, 1, 3, 4, 7, 9, 11, 15, 18, 21, 26, 30, ….

The quasi-polynomial sequence \underline{A236337} is related to this. Example 40. For α = 2, we find that

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

Thus the Hankel transform is the sequence 1, 0, 0, 0, . . .. Example 41. When α = −1, we obtain the sequence that begins

1, 0, 0, 3, 3, 6, 18, 33, 69, 165, 351, 768, 1758, 3921, 8811, 20130, ….

The Hankel transform of this begins

1, 0, −9, 0, 0, 0, −59049, 0, 43046721, 3486784401, 0, ….

This is given by

h_{n} = 3^{B_{n}}[x^{n}]\frac{1 − 3x^{2} + 3x^{3} − 9x^{5} − 6x^{8}}{1 + 3x^{3} + 3x^{6}} .

6 Conversion of parameters

Given a generating function of the form

g(x) = (\frac{1 + ax + bx^{2} + cx^{3}}{1 + dx + ex^{2} + fx^{3}} , \frac{mx^{3}(1 + ax + bx^{2} + cx^{3})}{(1 + dx + ex^{2} + fx^{3})^{2}}) · C(x),

what are the corresponding parameters p, q, s, u, v, w, t? We find the following.

p = a − d
q = −ad + b + d^{2} − e
s = a(d^{2} − e) + c − bd − d^{3} + 2de − f + m
u = −d
v = −e
w = −f + 2m
t = m.

Example 42. The doubly aerated large Schroeder numbers, with generating function

(\frac{1}{1 − x^{3}} , \frac{x^{2}}{(1 − x^{3})^{2}} ) · C(x),

correspond to the recurrence with parameters (0, 0, 2, 0, 0, 3, 1). This is the recurrence

a_{n} = 3a_{n−3} + ∑_{k=1}^{n−4} a_{k}a_{n−k−3},

with a_{0} = 1, a_{1} = 0, a_{2} = 0 and a_{3} = 2. The resulting sequence

1, 0, 0, 2, 0, 0, 6, 0, 0, 22, 0, 0, 90, 0, 0, 394, 0, 0, …

has a Hankel transform which begins

1, 0, −4, −8, 0, 128, 512, 0, −32768, −262144, 0, ….

Dividing this by 2^{n} gives us the sequence that begins

1, 0, −1, −1, 0, 4, 8, 0, −128, −512, 0, ….

This suggests that the generating function of this Hankel transform may satisfy the functional equation

1 − x^{2} − x^{3}f(x) − f(x/2) = 0.

7 From elliptic curve to recurrences and Somos sequences

We consider a particular example which illustrates a process that starts with an elliptic curve. Thus we consider the elliptic curve

E : y^{2} − 3xy − y = x^{3} − x.

We start by solving this for y. We get two solutions,

y^{−} = \frac{1 + 3x − \sqrt{1 + 2x + 9x^{2} + 4x^{3}}}{2} ,

and

y^{+} = \frac{1 + 3x + \sqrt{1 + 2x + 9x^{2} + 4x^{3}}}{2} .

Expanding the right hand side of the first solution y^{−}, we get

0, 1, −2, 1, 3, −7, −4, 38, −27, −175, 384, ….

Expanding the right hand side of the second solution y^{+}, we get

1, 2, 2, −1, −3, 7, 4, −38, 27, 175, −384, ….

The solution y^{−} has a generating function that can be expressed as

\frac{x(1 − x^{2})}{1 + 3x}C (\frac{x(1 − x)^{2}}{(1 + 3x)^{2}} ) .

Thus the sequence that begins

1, −2, 1, 3, −7, −4, 38, −27, −175, 384, …

has n-th term given by

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

We are interested in the terms (apart from sign) that are common to these two solutions. We thus truncate the sequence to start with 2, −1, −3, 7, 4, −38, 27, 175, −384, . . .. This leads to the new generating function

g(x) = (\frac{1 + 3x + \sqrt{1 + 2x + 9x^{2} + 4x^{3}}}{2} − 1 − 2x) /x^{2} = \frac{\sqrt{1 + 2x + 9x^{2} + 4x^{3}} − x − 1}{2x^{2}}.

This sequence has general term

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

or equivalently,

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

Now we find that

g(x) = \frac{2 + x}{1 + x}C (\frac{−x^{2}(2 + x)}{(1 + x)^{2}}) = \frac{\sqrt{1 + 2x + 9x^{2} + 4x^{3}} − x − 1}{2x^{2}}.

Re-writing this as

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

we see that the sequence 2, −1, −3, 7, 4, −38, 27, 175, −384, … defined by the elliptic curve is 2d_{n}, where d_{n} is the solution of the recurrence

d_{n} = −d_{n−1} − 4d_{n−2} − 2 ∑_{k=1}^{n−3} d_{k}d_{n−k−2},

with

d_{0} = 1, d_{1} = −\frac{1}{2}, d_{2} = −\frac{3}{2}.

The Hankel transform of this sequence 2d_{n} begins

2, −7, −57, 670, 23647, −833503, −147165662, …

which is a (1, 16) Somos-4 sequence.

We now form the generating function

\frac{1}{1 − x + x^{2}g(x)} = \frac{2}{1 − 3x + \sqrt{1 + 2x + 9x^{2} + 4x^{3}}} .

This gives us a sequence whose initial term is 1 and whose Hankel transform prepends a 1 to the previous transform. Multiplying this by x and reverting, and then dividing by x, we obtain the generating function

\frac{1 + 3x − \sqrt{1 + 6x + 9x^{2} − 4x^{3} − 8x^{4}}}{2x^{3}} = \frac{1 + 2x}{1 + 3x}C (\frac{x^{2}(1 + 2x)}{(1 + 3x)^{2}}) .

This expands to give the sequence a_{n} that begins

1, −1, 3, −8, 22, −59, 155, −396, 978, −2310, 5122, …,

which is thus the solution to the recurrence

a_{n} = −3a_{n−1} + 2a_{n−3} + ∑_{k=1}^{n−4} a_{k}a_{n−k−3},

with a_{0} = 1, a_{1} = −1, a_{2} = 3, a_{3} = −8. The Hankel transform of this sequence begins

1, 2, 1, −7, −16, −57, −113, 670, 3983, 23647, 140576, ….

This is a (1, −2) Somos-4 sequence. It is \underline{A178622}(n + 2). We note that the previous Hankel transform 2, −7, −57, 670, 23647, −833503, −147165662, … is a bisection of this latter sequence.

Taking the second binomial transform ∑_{k=0}^{n} \binom{n}{k}2^{n−k}a_{k} of the sequence a_{n}, we obtain the sequence that begins

1, 1, 3, 6, 14, 33, 79, 194, 482, 1214, 3090, 7936, ….

We have met this already. It is a_{n}(1, 3, 6, 1, 2, 2, 1) with generating function

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

It is interesting to note that the sequence b_{n} that begins

0, 2, 1, 1, 3, 6, 14, 33, 79, 194, 482, 1214, 3090, 7936, …

satisfies the recurrence

b_{n} = b_{n−1} + ∑_{i=0}^{n−3} b_{i}b_{n−i−1},

with b_{0} = 0, b_{1} = 2, b_{2} = 1. See also \underline{A025243}.

We have the following coordinates for the points nP (0, 0) on the elliptic curve

E : y^{2} − 3xy − y = x^{3} − x.

\begin{matrix}x(nP) & 0 & −2 & −\frac{1}{4} & 14 & \frac{16}{49} & \frac{−399}{256} & \frac{−1808}{3249} \\ y(nP) & 0 & −3 & \frac{5}{8} & 78 & \frac{55}{343} & \frac{−11921}{4096} & \frac{68464}{185193} \\ \frac{y}{x} & 1 & \frac{3}{2} & −\frac{5}{2} & \frac{39}{7} & \frac{55}{122} & \frac{703}{912} & −\frac{4279}{6441} \end{matrix}

We form the continued fraction

\frac{1}{1 + x − \frac{2x^{2}}{1 + \frac{3x}{2} − \frac{\frac{x^{2}}{4}}{1 − \frac{5x}{2} + \frac{14x^{2}}{1 + \frac{39x}{7} + \frac{\frac{16x^{2}}{49}}{1 + \frac{55x}{112} − \frac{\frac{399x^{2}}{256}}{1 − …}}}}}}.

This expands to give the sequence ã_{n}

1, −1, 3, −8, 22, −59, 155, −396, 978, −2310, 5122, …

with g.f

(\frac{1 + 2x}{1 + 3x}, \frac{x^{3}(1 + 2x)}{(1 + 3x)^{2}}) · C(x).

We have

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

In this case, we have ã_{n} = a_{n}, where a_{n} is the sequence obtained starting from solving the elliptic curve equation.

We briefly look at the shifted sequence

−1, −3, 7, 4, −38, 27, 175, −384, …

of the sequence first encountered in this section. This has a generating function given by

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

It has a Hankel transform that begins

−1, −16, 113, 3983, −140576, −14871471, ….

Again, this is a (1, 16) Somos-4 sequence.

The elliptic curve

E : y^{2} − 3xy − y = x^{3} − x

thus gives rise to the following Riordan arrays

• (\frac{1−x^{2}}{1+3x}, \frac{x(1−x^{2})}{(1+3x)^{2}})

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

• (\frac{1+4x}{1+x+4x^{2}} , \frac{x^{3}(1+4x)}{(1+x+4x^{2})^{2}} )

• (\frac{1}{1−3x}, \frac{x(2+x^{2})}{(1−3x)^{2}})

• (\frac{1+2x}{1+3x}, \frac{x^{3}(1+2x)}{(1+3x)^{2}})

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

with their corresponding recurrences.

8 The family E_{t} : y^{2} + 4xy + y = x^{3} + (t − 1)x^{2} + tx

The family of elliptic curves

E_{t} : y^{2} + 4xy + y = x^{3} + (t − 1)x^{2} + tx

has the property that each of its curves passes through the points (0, 0), (−1, 1) and (−1, 2). Solving the equation

y^{2} + 4xy + y = x^{3} + (t − 1)x^{2} + tx

gives

y = −\frac{1 + 4x ± \sqrt{1 + 4(t + 2)x + 4(t + 3)x^{2} + 4x^{3}}}{2} .

For instance, −^{\frac{1+4x−\sqrt{1+4(t+2)x+4(t+3)x^{2}+4x^{3}}}{2}} expands to give

0, t, −(t^{2} + 3t + 1), 2t^{3} + 10t^{2} + 14t + 5, ….

The generating function of this sequence can be expressed as

\frac{x(t + x(t − 1) + x^{2}}{1 + 4x} C (\frac{−x(t + x(t − 1) + x^{2})}{(1 + 4x)^{2}}) .

As before, we are interested in the terms (up to sign) that are common to the two solutions. Thus we focus on the sequence b_{n} that begins

(t^{2} + 3t + 1), −(2t^{3} + 10t^{2} + 14t + 5), ….

This has generating function

g(x) = \frac{1 + 3t + t^{2} − x}{1 + 2(t + 2)x}C (\frac{x^{2}(1 + 3t + t^{2} − x)}{(1 + 2(t + 2)x)^{2}}) .

We have the following conjecture.

Conjecture 43. The Hankel transform of b_{n} is an

((2t^{3} + 10t^{2} + 14t + 5)^{2}, −3t^{8} − 40t^{7} − 222t^{6} − 666t^{5}−
1173t^{4} − 1230t^{3} − 740t^{2} − 29(8t + 1))

Somos-4 sequence.

The generating function \frac{1}{1−x−x^{2}g(x)} will now give us a sequence whose initial term is 1, which has the same Hankel transform, with a prepended 1. We obtain that

\frac{1}{1 − x − x^{2}g(x)} = \frac{1}{1 − 2(t + 3)x}C (\frac{−x(x^{2} − (t + 2)(t + 3)x + 2t + 5)}{(1 − 2(t + 3)x)^{2}}) .

We now revert the generating function \frac{x}{1−x−x^{2}g(x)}, and divide the result by x, to get the generating function

a(x) = \frac{1 + (2t + 5)x}{1 + 2(t + 3)x + (t + 2)(t + 3)x^{2}} C (\frac{x^{3}(1 + (2t + 5)x)}{(1 + 2(t + 3)x + (t + 2)(t + 3)x^{2})^{2}} ) .

This expands to give a sequence a_{n} that begins

1, −1, −t(t + 3), 2t^{3} + 13t^{2} + 23t + 7, −3t^{4} − 30t^{3} − 103t^{2} − 134t − 44, ….

The sequence a_{n} therefore satisfies the following recurrence.

a_{n} = −2(t + 3)a_{n−1} − (t + 2)(t + 3)a_{n−2} + 2a_{n−3} + ∑_{k=1}^{n−k−4} a_{k}a_{n−k−3},

with a_{0} = 1, a_{1} = −1, a_{2} = −t(t + 3), a_{3} = 2t^{3} + 13t^{2} + 23t + 7. We have the following conjecture concerning the Hankel transform of this sequence.

Conjecture 44. The Hankel transform of the sequence whose generating function is given by

\frac{1 + (2t + 5)x}{1 + 2(t + 3)x + (t + 2)(t + 3)x^{2}} C (\frac{x^{3}(1 + (2t + 5)x)}{(1 + 2(t + 3)x + (t + 2)(t + 3)x^{2})^{2}} )

is a (1, t^{2} + 3t + 1) Somos-4 sequence.

Example 45. When t = 0, we get the sequence with generating function

\frac{1 + 5x}{1 + 6x + 6x^{2}} C (\frac{x^{3}(1 + 5x)}{(1 + 6x + 6x^{2})^{2}} ) ,

which begins

1, −1, 0, 7, −44, 223, −1060, 4920, −22626, 103719, −475214, ….

This sequence satisfies then the recurrence

a_{n} = −6a_{n−1} − 6a_{n−3} + 2a_{n−3} + ∑_{k=1}^{n−4} a_{k}a_{n−k−3}

with

a_{0} = 1, a_{1} = −1, a_{2} = 0, a_{3} = 7.

The Hankel transform of this sequence is then the (1, 1) Somos-4 sequence \underline{A157101} which begins

1, −1, −5, −4, 29, 129, −65, −3689, −16264, ….

The associated elliptic curve is

E_{0} : y^{2} + 4xy + y = x^{3} − x^{2}.

Example 46. When t = −3, we obtain the sequence a_{n} with generating function

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

which begins

1, −1, 0, 1, −2, 1, 2, −6, 6, 3, −20, ….

This sequence then satisfies the recurrence

a_{n} = 2a_{n−3} + ∑_{k=1}^{n−4} a_{k}a_{n−k−3}

with

a_{0} = 1, a_{1} = −1, a_{2} = 0, a_{3} = 1.

Its Hankel transform is the (1, 1) Somos-4 sequence \underline{A006769}(n + 2) that begins

1, −1, 1, 2, −1, −3, −5, 7, −4, −23, 29, ….

The associated elliptic curve is

E_{(−3)} : y^{2} + 4xy + y = x^{3} − 4x^{2} − 3x.

We can relate the sequence to the coordinates of the multiples of the point (0, 0) on this curve in the following way. Taking the second binomial transform of (−1)^{n}a_{n}, given by

d_{n} = ∑_{k=0}^{n} 2^{n−k}(−1)^{k}a_{k},

and then taking the Invert(4) transform of d_{n}, we arrive at the sequence ã_{n} that begins

1, −1, 0, −1, −2, −5, −10, −14, 6, 145, 720, 2618, 7850, 19389, 35016, ….

Due to the invariance of the Hankel transform under binomial and Invert transforms, this sequence has the same Somos-4 Hankel transform as a_{n}. The sequence ã_{n} has a generating function that can be expressed as

\frac{1 − x}{1 + 4x − 4x^{2}} C (\frac{x(4 − 4x − x^{2} − x^{3})}{(1 + 4x − 4x^{2})^{2}}) .

We can express this as the continued fraction

\frac{1}{1 + x + \frac{x^{2}}{1 − 2x − \frac{x^{2}}{1 − x + \frac{2x^{2}}{1 − \frac{7x}{2} + \frac{\frac{x^{2}}{4}}{1 − \frac{9x}{2} + \frac{6x^{2}}{1 − …}}}}}}.

This corresponds to the following x and y coordinates of the multiples of P (0, 0) on E_{(−3)}.

\begin{matrix}x(nP) & 0 & 1 & −1 & 2 & \frac{1}{4} & 6 & −\frac{5}{9} \\ y(nP) & 0 & −2 & 1 & −7 & −\frac{9}{8} & 2 & \frac{38}{27} \\ \frac{y}{x} & 1 & 2 & −1 & \frac{−7}{2} & \frac{−9}{2} & \frac{1}{3} & −\frac{38}{15} \end{matrix}

Thus we can write the generating function ∑_{n=0}^{∞} ã_{n}t^{n} as

\frac{1}{1 + z(0)t + \frac{x(1)t^{2}}{1 + z(1)t + \frac{x(2)t^{2}}{1 + z(2)t + ⋯}}},

where z(n) = \frac{y(nP)}{x(nP)} and x(n) = x(nP). The sequence ã_{n} is the moment sequence for the family of orthogonal polynomials Q_{n}(x) with a coefficient matrix that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & 1 & 0 & 0 & 0 & 0 \\ 0 & −1 & −2 & 1 & 0 & 0 & 0 \\ −2 & 3/2 & 8 & −11/2 & 1 & 0 & 0 \\ 9 & −9 & −35 & 35 & −10 & 1 & 0 \\ −9 & 15 & 82/3 & −57 & 107/3 & −29/3 & 1 \end{matrix} ) .

The inverse M of this matrix (the moment matrix) contains ã_{n} as its first column. The matrix M begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ −1 & 3 & 2 & 1 & 0 & 0 & 0 \\ −2 & 7 & 3 & 11/2 & 1 & 0 & 0 \\ −5 & 15 & −1 & 22 & 10 & 1 & 0 \\ −10 & 24 & −30 & 147/2 & 61 & 29/3 & 1 \end{matrix} ) .

The production matrix of M then begins

( \begin{matrix}−1 & 1 & 0 & 0 & 0 & 0 & 0 \\ −1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & −2 & 7/2 & 1 & 0 & 0 \\ 0 & 0 & 0 & −1/4 & 9/2 & 1 & 0 \\ 0 & 0 & 0 & 0 & −6 & −1/3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 5/9 & 38/15 \end{matrix} ) .

The tri-diagonal nature of this production matrix shows that we are in the presence of a family of orthogonal polynomials. The diagonal and sub-diagonal contain the x coordinates and the y/x-ratios of the multiples of the point P (0, 0) on E_{(−3)}.

The family Q_{n}(t) is defined by the three-term recurrence

Q_{n}(t) = (t + \frac{x((n − 1)P)}{y((n − 1)P)}) Q_{n−1}(t) + x((n − 1)P)Q_{n−2}(t),

where P = (0, 0) on E_{(−3)} and we have Q_{0}(t) = 1, Q_{1}(t) = t + 1.

Using results about the divisibility polynomials ψ_{n} of an elliptic curve [20], we can express the x and y coordinates of multiples of the point P (0, 0) for the curve E_{(−3)} as follows.

x(nP) = \frac{−ψ_{n−1}ψ_{n+1}}{ψ_{n}^{2}} ,

and

y(nP) = \frac{1}{2} (\frac{ψ_{2n}}{ψ_{n}^{4}} − (1 − 4\frac{ψ_{n−1}ψ_{n+1}}{ψ_{n}^{2}} )) ,

where we have used the shorthand ψ_{n} = ψ_{n}(0, 0) in the above expressions. Alternatively, we have

x((n + 1)P) = \frac{−h̃_{n−1}h̃_{n+1}}{h̃_{n}^{2}} ,

and

y((n + 1)P) = \frac{1}{2} (\frac{h̃_{2(n+1)}}{h̃_{n}^{4}} + a_{1} \frac{h̃_{n−1}h̃_{n+1}}{h̃_{n}^{2}} − a_{3}) ,

where a_{1} = 4 and a_{3} = 1. Here, h̃_{n} is the Hankel transform of ã_{n}.

We note finally that an application of the Stieltjes-Perron transform suggests that the absolutely continuous part of the associated measure is given by

\frac{1}{π} \frac{\sqrt{−x^{4} − 4(2x^{3} + 6x^{2} + 7x + 3)}}{2(4x^{2} − 1)}.

9 The case of E : y^{2} + axy + y = x^{3} + bx^{2} + cx

We let P = P (0, 0) be the point (0, 0) on the elliptic curve

E : y^{2} + axy + y = x^{3} + bx^{2} + cx,

and let ã_{n} be the sequence with generating function

ã(t) = \frac{1}{1 + t + \frac{x_{1}t^{2}}{1 + \frac{y_{1}}{x_{1}} t + \frac{x_{2}t^{2}}{1 + \frac{y_{2}}{x_{2}} t + \frac{x_{3}t^{2}}{1 + \frac{y_{3}}{x_{3}} t + ⋯}}}},

where x_{n} = x(nP) and y_{n} = y(nP) are the coordinates of the multiples nP of the point P on the curve. We can conjecture that the generating function of ã_{n} is given by

(g(x), f(x)) · C(x),

where

g(x) = \frac{1}{1 − (a + 2γ)x − (b − 2γ(a + c))x^{2}} ,

and

f(x) = \frac{x(x^{3}(a + c)(γ^{2}(a + c) − bγ + 1) − x^{2}(2cγ^{2} + γ(a^{2} + a(3Δc − 2) − b) + 1) + xγ(2a + 2c − 1) − γ)}{(1 − (a + 2γ)x − (b − 2γ(a + c))x^{2})^{2}}.

Here, we have used the notation

γ = c − 1.

We see that there are simplifications when c = 1. In this case, we find that the generating function of ã_{n} is given by

\frac{1 − (a + 1)x}{1 − ax − bx^{2}} C (\frac{−x^{3}(1 − (a + 1)x)}{(1 − ax − bx^{2})^{2}}) .

This allows us to give a closed form expression for ã_{n} when c = 1.

ã_{n} = ∑_{k=0}^{n}(∑_{j=0}^{k+1} \binom{k + 1}{j}(−a − 1)^{j} ∑_{i=0}^{n−3k−j} \binom{2k + i}{i}\binom{i}{n − 3k − i − j}b^{n−3k−i−j}a^{2i+3k+j−n})(−1)^{k}C_{k}.

This sequence begins

1, −1, b − a, −a^{2} + ab − b − 1, −a^{3} + a^{2}b − a(2b + 1) + b^{2} + 2,
−a^{4} + a^{3}b − a^{2}(3b + 1) + a(2b^{2} + 4) − b^{2} − 3b − 1, …,

with a Hankel transform that begins

1, −a + b − 1, −a^{2} + a(b − 3) + 2b − 3,
a^{3} + a^{2}(2 − 3b) + a(3b^{2} − 5b) − b^{3} + 3b^{2} − b − 2, …,

which we conjecture to be a (1, a − b + 1) Somos-4 sequence.

The sequence ã_{n} for c = 1 satisfies the convolution recurrence

ã_{n} = aã_{n−1} + bã_{n−2} − 2ã_{n−3} − ∑_{k=1}^{n−k−4} ã_{k}ã_{n−k−3},

with ã_{0} = 1, ã_{1} = −1, ã_{2} = b − a, ã_{3} = −a^{2} + ab − b − 1.

For the related sequence a_{n}, calculated from the solution of the elliptic curve equation, we can calculate that its generating function is given by

(g(x), f(x)) · C(x)

where

g(x) = \frac{1 + (1 + a + 2c)x}{1 + (a + 2c + 2)x + (a(c + 1) + (c + 1)^{2} − b)x^{2}} ,

f(x) = \frac{x^{3}(1 + (1 + a + 2c)x)}{(1 + (a + 2c + 2)x + (a(c + 1) + (c + 1)^{2} − b)x^{2})^{2}} .

This means that a_{n} satisfies the following convolution recurrence.

a_{n} = −(a + 2(c + 1))a_{n−1} + (b − a(c + 1) − (c + 1)^{2})a_{n−2} + 2a_{n−3} + ∑_{k=1}^{n−4} a_{k}a_{n−k−3},

with a_{0} = 1, a_{1} = −1, a_{2} = 1 + b − ac − c^{2}, a_{3} = (3 + a + 2c)(−b + c(a + c)).

The relationship between the generating function ã(x) = ∑_{n=0}^{∞} ã_{n}x^{n} and the generating function a(x) = ∑_{n=0}^{∞} a_{n}x^{n} is the following: ã(x) is the Invert(−(c + 1)) of the (c + 1)-st binomial transform of a(−x).

10 Conclusions

We have found that the language of Riordan arrays is an appropriate one to investigate structural aspects of the solutions of generalized Catalan or Schroeder recurrences. The appearance of the Catalan numbers is explained by the quadratic nature of the convolution recurrences. This quadratic theme is continued in terms of solving elliptic curve equations in the quadratic term, which leads to generating functions that are Riordan array solutions of convolution equations. Often, the Hankel transform of the solution sequences give rise to Somos-4 sequences. By using the x and y coordinates of multiples of a special point on the elliptic curves, we can obtain Stieltjes continued fraction expressions for the generating functions of related integer sequences. In specific instances, this leads to orthogonal polynomials and their three-term recurrences, opening the door to the investigation of associated measures. Note that we work with points on curves for which the division polynomials never evaluate to 0.

The association of Somos-4 sequences and the Hankel transform is implicit in previous work (see the Appendix) [10, 21, 20]. What is apparently new is the use of the \frac{y(nP)}{x(nP)} ratios to define integer sequences whose Hankel transforms furnish Somos sequences.

Proofs of results concerning Hankel transforms and Somos sequences can be elusive (but see [10, 11, 12, 24, 25], hence we couch some proposed results as conjectures. It is hoped that further insight will remedy this in the future.

11 Acknowledgments

The author would like to thank an anonymous reviewer for their careful reading of the manuscript and for their comments, which will have led to a more readable paper.

12 Appendix: Orthogonal polynomials, Riordan arrays and the Hankel transform

By an orthogonal polynomial sequence (p_{n}(x))_{n≥0} we shall understand [7, 8] an infinite sequence of polynomials p_{n}(x), n ≥ 0, of degree n, with real coefficients (often integer coefficients) that are mutually orthogonal on an interval [x_{0}, x_{1}] (where x_{0} = −∞ is allowed, as well as x_{1} = ∞), with respect to a weight function w : [x_{0}, x_{1}] → ℝ:

∫_{x_{0}}^{x_{1}} p_{n}(x)p_{m}(x)w(x)dx = δ_{nm}\sqrt{h_{n}h_{m}},

where

∫_{x_{0}}^{x_{1}} p_{n}^{2}(x)w(x)dx = h_{n}.

We assume that w is strictly positive on the interval (x_{0}, x_{1}). Every such sequence obeys a so-called “three-term recurrence”:

p_{n+1}(x) = (a_{n}x + b_{n})p_{n}(x) − c_{n}p_{n−1}(x)

for coefficients a_{n}, b_{n} and c_{n} that depend on n but not x. We note that if

p_{j}(x) = k_{j}x^{j} + k′_{j}x^{j−1} + ⋯ j = 0, 1, …

then

a_{n} = \frac{k_{n+1}}{k_{n}} ,  b_{n} = a_{n} (\frac{k′_{n+1}}{k_{n+1}} − \frac{k′_{n}}{k_{n}} ) ,  c_{n} = a_{n} (\frac{k_{n−1}h_{n}}{k_{n}h_{n−1}} ) ,

where

h_{i} = ∫_{x_{0}}^{x_{1}} p_{i}(x)^{2}w(x) dx.

Since the degree of p_{n}(x) is n, the coefficient array of the polynomials is a lower triangular (infinite) matrix. In the case of monic orthogonal polynomials the diagonal elements of this array will all be 1. In this case, we can write the three-term recurrence as

p_{n+1}(x) = (x − α_{n})p_{n}(x) − β_{n}p_{n−1}(x),  p_{0}(x) = 1,  p_{1}(x) = x − α_{0}.

The moments associated to the orthogonal polynomial sequence are the numbers

μ_{n} = ∫_{x_{0}}^{x_{1}} x^{n}w(x)dx.

We can find p_{n}(x), α_{n} and β_{n} from a knowledge of these moments. To do this, we let Δ_{n} be the Hankel determinant |μ_{i+j}|_{i,j≥0}^{n} and Δ_{n,x} be the same determinant, but with the last row equal to 1, x, x^{2}, . . .. Then

p_{n}(x) = \frac{Δ_{n,x}}{Δ_{n−1}} .

More generally, we 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}}. 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}} .

Of importance to this study are the following results (the first is the well-known “Favard theorem”), which we essentially reproduce from [12]:

Theorem 47. [12] (Cf. [22], Théorème 9 on p.I-4, or [23], Theorem 50.1). Let (p_{n}(x))_{n≥0} be a sequence of monic polynomials, the polynomial p_{n}(x) having degree n = 0, 1, … Then the sequence (p_{n}(x)) is (formally) orthogonal if and only if there exist sequences (α_{n})_{n≥0} and (β_{n})_{n≥1} with β_{n} ≠ 0 for all n ≥ 1, such that the three-term recurrence

p_{n+1} = (x − α_{n})p_{n}(x) − β_{n}(x), for n ≥ 1,

holds, with initial conditions p_{0}(x) = 1 and p_{1}(x) = x − α_{0}.

Theorem 48. [12] (Cf. [22], Proposition 1, (7), on p. V-5, or [23], Theorem 51.1). Let (p_{n}(x))_{n≥0} be a sequence of monic polynomials, which is orthogonal with respect to some functional L. Let

p_{n+1} = (x − α_{n})p_{n}(x) − β_{n}(x), for n ≥ 1,

be the corresponding three-term recurrence which is guaranteed by Favard’s theorem. Then the generating function

g(x) = ∑_{k=0}^{∞} μ_{k}x^{k}

for the moments μ_{k} = L(x^{k}) satisfies

g(x) = \frac{μ_{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 − ⋯}}}}.

Given a family of monic orthogonal polynomials

p_{n+1}(x) = (x − α_{n})p_{n}(x) − β_{n}p_{n−1}(x),  p_{0}(x) = 1,  p_{1}(x) = x − α_{0},

we can write

p_{n}(x) = ∑_{k=0}^{n} a_{n,k}x^{k}.

Then we have

∑_{k=0}^{n+1} a_{n+1,k}x^{k} = (x − α_{n}) ∑_{k=0}^{n} a_{n,k}x^{k} − β_{n} ∑_{k=0}^{n−1} a_{n−1,k}x^{k}

from which we deduce

a_{n+1,0} = −α_{n}a_{n,0} − β_{n}a_{n−1,0}  (1)

and

a_{n+1,k} = a_{n,k−1} − α_{n}a_{n,k} − β_{n}a_{n−1,k}  (2)

The question immediately arises as to the conditions under which a Riordan array (g, f) can be the coefficient array of a family of orthogonal polynomials. A partial answer is given by the following proposition.

Proposition 49. Every Riordan array of the form

(\frac{1}{1 + rx + sx^{2}} , \frac{x}{1 + rx + sx^{2}} )

is the coefficient array of a family of monic orthogonal polynomials.

We note that in this case the three-term recurrence coefficients α_{n} and β_{n} are constants. We can strengthen this result as follows.

Proposition 50. Every Riordan array of the form

(\frac{1 − λx − μx^{2}}{1 + rx + sx^{2}} , \frac{x}{1 + rx + sx^{2}} )

is the coefficient array of a family of monic orthogonal polynomials.

Proposition 51. The elements in the left-most column of

L = (\frac{1 − λx − μx^{2}}{1 + rx + sx^{2}} , \frac{x}{1 + rx + sx^{2}} )^{−1}

are the moments corresponding to the family of orthogonal polynomials with coefficient array L^{−1}.

We have in fact the following proposition, which characterizes those orthogonal polynomials that can be defined by Riordan arrays in terms of the Chebyshev polynomials of the second kind.

Proposition 52. The Riordan array (\frac{1}{1+rx+sx^{2}} , \frac{x}{1+rx+sx^{2}} ) is the coefficient array of the modified Chebyshev polynomials of the second kind given by

P_{n}(x) = (\sqrt{s})^{n}U_{n} (\frac{x − r}{2\sqrt{s}}) , n = 0, 1, 2, …

Corollary 53. The Riordan array (\frac{1−λx−μx^{2}}{1+rx+sx^{2}} , \frac{x}{1+rx+sx^{2}} ) is the coefficient array of the generalized Chebyshev polynomials of the second kind given by

Q_{n}(x) = (\sqrt{s})^{n}U_{n} (\frac{x − r}{2\sqrt{s}})−λ(\sqrt{s})^{n−1}U_{n−1} (\frac{x − r}{2\sqrt{s}})−μ(\sqrt{s})^{n−2}U_{n−2} (\frac{x − r}{2\sqrt{s}}) , n = 0, 1, 2, …

The Hankel transform [13] of a sequence a_{n} is the sequence h_{n} of determinants |a_{i+j}|_{0≤i,j≤n}. For instance, the Hankel transform of the Catalan numbers is given by the all 1’s sequence

1, 1, 1, 1, 1, ….

The Hankel transform can have combinatorial significance; for instance, the Hankel transform of the ternary numbers begins

1, 2, 11, 170, 7429, 920460, 323801820, 323674802088, ….

This sequence (\underline{A051255}) counts the number of cyclically symmetric transpose complement plane partitions in a (2n + 2) × (2n + 2) × (2n + 2) box.

If the sequence a_{n} has a generating function g(x), then the bivariate generating function of the Hankel matrix |a_{i+j}|_{i,j≥0} is given by

\frac{xg(x) − yg(y)}{x − y}.

In the case that a sequence a_{n} has g.f. g(x) expressible in the continued fraction form [23]

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 the Heilermann formula [12]

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

Note that this independent from α_{n}.

We note that α_{n} and β_{n} are in general not integers (even if both a_{n} and h_{n} are integer valued). It is clear also that a Hankel transform has an infinite number of pre-images, since we are free to assign values to the α_{n} coefficients. For instance, a sequence a_{n} and its binomial transform ∑_{k=0}^{n} \binom{n}{k} have the same Hankel transform, and the expansion of the Invert transform of g(x) given by \frac{g(x}{1−xg(x)} and that of g(x) will have the same Hankel transform.

Somos-4 sequences are most commonly associated with the x-coordinate of rational points on an elliptic curve [10, 20, 21]. The link between these sequences and Hankel transforms is made explicit in Theorem 7.1.1 of [20], for instance. Letting nP 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 + nP ≠ O (the point at infinity on E), by (x_{n}, y_{n}) the coordinates of the point Q + nP. 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},

and we see that this is in the form of a Hankel transform.

References

[1] P. Barry, Riordan pseudo-involutions, continued fractions and Somos 4 sequences,

preprint, 2018. Available at https://arxiv.org/abs/1807.05794.

[2] P. Barry, Riordan Arrays: A Primer, Logic Press, 2017.

[3] P. Barry and A. Mwafise, Classical and semi-classical orthogonal polynomials defined by Riordan arrays, and their moment sequences, J. Integer Sequences 21 (2018), Article 18.1.5.

[4] P. Barry, Riordan arrays, orthogonal polynomials as moments, and Hankel transforms, J. Integer Sequences 14 (2011), Article 11.2.2.

[5] P. Barry, Continued fractions and transformations of integer sequences, J. Integer Sequences 12 (2009), Article 09.7.6.

[6] X.-K. Chang and X.-B. Hu, A conjecture based on Somos-4 sequence and its extension, Linear Algebra Appl. 436 (2012) 4285–4295.

[7] T. S. Chihara, An Introduction to Orthogonal Polynomials, Dover Publications, 2011.

[8] W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Clarendon Press, 2004.

[9] P. Henrici, Applied and Computational Complex Analysis, Vol. 3, John Wiley & Sons, 1993.

[10] A. Hone, Elliptic curves and quadratic recurrence sequences, Bull. Lond. Math. Soc. 37 (2005), 161–171.

[11] C. Krattenthaler, Lattice path enumeration, in M. Bona, editor, Handbook of Enumerative Combinatorics, Chapman & Hall/CRC Press, 2015. Available electronically at

https://arxiv.org/abs/1503.05930.

[12] C. Krattenthaler, Advanced determinant calculus: a complement, Lin. Alg. Appl. 411 (2005), 68—166.

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

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

[15] F. Qi and B.-N. Guo, Some explicit and recursive formulas of the large and little Schröder numbers, Arab J. Math. Sci. 23 (2017), 141–147.

[16] L. Shapiro, A survey of the Riordan group, available electronically at Center for Combinatorics, Nankai University, 2018.

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

[18] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org, 2021.

[19] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Notices Amer. Math. Soc. 50 (2003), 912–915.

[20] C. S. Swart, Elliptic curves and related sequences, Ph.D. Thesis, University of London, 2003.

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

[22] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Lecture Notes, UQAM, Montreal, Quebec, 1984. Available at http://www.xavierviennot.

    org/xavier/polynomes_orthogonaux.html.

[23] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 2001.

[24] G. Xin, Proof of the Somos-4 Hankel determinants conjecture, Adv. in Appl. Math. 42 (2009), 152–156.

[25] F. Yura, Hankel determinant solution for elliptic sequences, preprint, 2014. Available

    at https://arxiv.org/abs/1411.6972.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11B83, 15B36,11B37, 05A15, 11Y55, 14H52, 42C05. Keywords: convolution recurrence, generating function, Catalan number, Schröder numbers, Riordan array, Hankel transform, Somos sequence, elliptic curve, orthogonal polynomial.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A001003}, \underline{A001519}, \underline{A004148}, \underline{A004149}, \underline{A006318}, \underline{A006769}, \underline{A014431}, \underline{A023431}, \underline{A025235}, \underline{A025243}, \underline{A025272}, \underline{A048990}, \underline{A084782}, \underline{A085139}, \underline{A086581}, \underline{A091561}, \underline{A128720}, \underline{A157101}, \underline{A162985}, \underline{A174171}, \underline{A174403}, \underline{A174404}, \underline{A178376}, \underline{A178384}, \underline{A178622}, \underline{A178627}, \underline{A187256}, and \underline{A236337}.)

Received March 28 2019; revised version received April 19 2021. Published in Journal of Integer Sequences, April 19 2021.

Return to Journal of Integer Sequences home page.