Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays

Paul Barry School of Science Waterford Institute of Technology Ireland

                     pbarry@wit.ie

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

               aoife.hennessy@gmail.com

Abstract

We study constant coefficient four term recurrences for polynomials, in analogy to the three-term recurrences that are associated with orthogonal polynomials. We show that for a family of polynomials obeying such a four-term recurrence, the coefficient array is an ordinary Riordan array of a special type, and vice versa. In certain cases, it is possible to transform these polynomials into related orthogonal polynomials. We characterize the form of the production matrices of the inverse coefficient arrays.

1 Introduction

In this note we shall be concerned with families of monic polynomials P_{n}(x) where P_{n}(x) is of degree n. Thus we will have

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

The matrix of elements a_{n,k} is then a lower-triangular matrix with 1’s on the diagonal, and hence invertible. We shall call this matrix the coefficient array of the polynomial family. The inverse of this matrix will be called the inverse coefficient array. In the case of orthogonal polynomials, the elements of the first column of the inverse coefficient array are the moments of the family [20]. We shall refer to the elements of the first column of a general inverse coefficient array as being generalized (formal) moments.

We recall that an ordinary Riordan array [15, 18] is defined by a pair (g, f) of power series, where g(x) = 1 + g_{1}x + g_{2}x^{2} + ⋯, f(x) = x + f_{2}x^{2} + ⋯, and is associated to the matrix (t_{n,k})_{0≤n,k≤∞} where t_{n,k} = [x]^{n}g(x)f(x)^{k}. (These are proper Riordan arrays). The multiplication law for these pairs, which form a group, is given by

(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̄(x) = Rev_{x}f(x) is the compositional inverse of f. For an invertible matrix L, we define the production matrix P_{L} to be the matrix P_{L} = L^{−1}L̂, where L̂ is the matrix L with its first row removed [5, 6]. When L is a Riordan array (g, f), the first column of P_{L} is generated by Z(x) = \frac{1}{f̄(x)} (1 − \frac{1}{g(f̄(x))}), while the k-th column of P_{L} is generated by x^{k−1}A(x) (taking the first column to be indexed by 0), where A(x) = \frac{x}{f̄(x)}. For a sequence a_{n}, the sequence of determinants h_{n} = |a_{i+j}|_{0≤i,j≤n} is called the Hankel transform [11, 12, 13] of a_{n}. Sequences will be referred to by their OEIS [16, 17] numbers. For instance, the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} = [x^{n}]\frac{1−\sqrt{1−4x}}{2x} are sequence \underline{A000108}.

It is a classical result that a family of monic polynomials P_{n}(x) is a family of orthogonal polynomials [4, 7, 19] if and only if they satisfy a three-term recurrence of the form

P_{n}(x) = (x − α_{n})P_{n−1} − β_{n}P_{n−2},

with appropriate initial conditions. A more recent result [1, 2] is that a Riordan array A is the coefficient array of a family of orthogonal polynomials if and only if the production matrix of A^{−1} is tridiagonal (a result based on previous work [14, 21]). In the case of ordinary Riordan arrays, the coefficients α_{n} and β_{n} are necessarily independent of n. The most general form of ordinary Riordan array that coincides with the coefficient array of a family of orthogonal polynomials is then given by

(\frac{1 − cx − dx^{2}}{1 + ax + bx^{2}} , \frac{x}{1 + ax + bx^{2}} ) ,

for appropriate values of a, b, c, d. In this note, we ask ourselves the question: what can be said about families of polynomials P_{n}(x), that satisfy a four-term recurrence of the form:

P_{n}(x) = (x − α)P_{n−1}(x) − (x − β)P_{n−2}(x) − γP_{n−3}(x).

Note that in this note we are considering the simplest case of constant coefficients.

2 Main results

Our results are encapsulated in the following theorem.

Theorem 1. A family of monic polynomials P_{n}(x) where P_{n}(x) is of degree n, satisfies the four-term recurrence

P_{n}(x) = (x − α + 1)P_{n−1}(x) − (x + β)P_{n−2}(x) − γP_{n−3},

with P_{n}(x) = 0 for n < 0, P_{0}(x) = 1 and P_{1}(x) = x − δ, if and only if the coefficient array of the family P_{n}(x) is given by the Riordan array

(\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} ) .

In addition, for such a family, if γ = 0 (but α + β ≠ 0 and β + δ ≠ 0), then the family of polynomials

Q_{n}(x) = ∑_{k=0}^{n}(−1)^{n−k}\binom{n − 1}{n − k}P_{k}(x + 1)

is a family of orthogonal polynomials that satisfies the three-term recurrence

Q_{n}(x) = (x − α)Q_{n−1}(x) − (α + β)Q_{n−2}(x),

with Q_{0}(x) = 1, and Q_{1}(x) = x − δ + 1. Proof. We let p_{n}(x) be the family of polynomials whose coefficient array is given by the Riordan array

(\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} ) .

Since this array is lower triangular with 1’s on the diagonal, each polynomial p_{n}(x) is monic of degree n. We let

L = (\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} )^{−1} .

Then standard Riordan array techniques show that the production matrix P_{L} of L is given by

P_{L} = ( \begin{matrix}δ & 1 & 0 & 0 & 0 & 0 & … \\ β + δ & α & 1 & 0 & 0 & 0 & … \\ β + δ + γ & α + β & α & 1 & 0 & 0 & … \\ β + δ + γ & α + β + γ & α + β & α & 1 & 0 & … \\ β + δ + γ & α + β + γ & α + β + γ & α + β & α & 1 & … \\ β + δ + γ & α + β + γ & α + β + γ & α + β + γ & α + β & α & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This implies that

( \begin{matrix}δ & 1 & 0 & 0 & 0 & 0 & … \\ β + δ & α & 1 & 0 & 0 & 0 & … \\ β + δ + γ & α + β & α & 1 & 0 & 0 & … \\ β + δ + γ & α + β + γ & α + β & α & 1 & 0 & … \\ β + δ + γ & α + β + γ & α + β + γ & α + β & α & 1 & … \\ β + δ + γ & α + β + γ & α + β + γ & α + β + γ & α + β & α & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( p_{0}(x) ; p_{1}(x) ; p_{2}(x) ; p_{3}(x) ; ⋮ ) = ( xp_{0}(x) ; xp_{1}(x) ; xp_{2}(x) ; xp_{3}(x) ; ⋮ ) .

We deduce the following.

p_{1}(x) + δp_{0}(x) = xp_{0}(x) ⟹ p_{1}(x) = x − δ.
p_{2}(x) + αp_{1}(x) + (β + δ)p_{0}(x) = xp_{1}(x) ⟹ p_{2}(x) = (x − α)p_{1}(x) − (β + δ)

which further implies that

p_{2}(x) = (x − α + 1)p_{1}(x) − p_{1}(x) − (β + δ) = (x − α + 1)p_{1}(x) − (x + β)p_{0}(x). We have

p_{3}(x) + αp_{2}(x) + (α + β)p_{1}(x) + (β + δ + γ)p_{0}(x) = xp_{2}(x)

which implies that

p_{3}(x) = (x − α)p_{2}(x) − (α + β)p_{1}(x) − (β + δ + γ)
= (x − α + 1)p_{2}(x) − p_{2}(x) − (α + β)p_{1}(x) − (β + δ + γ)
= (x − α + 1)p_{2}(x) − (x − α)p_{1}(x) + (β + δ) − (α + β)p_{1}(x) − (β + δ + γ)
= (x − α + 1)p_{2}(x) − (x + β)p_{1}(x) − γp_{0}(x).

In similar fashion we can show that

p_{4}(x) = (x − α + 1)p_{3}(x) − (x + β)p_{2}(x) − γp_{1}(x).

Now assume that

p_{n−1}(x) = (x − α + 1)p_{n−2}(x) − (x + β)p_{n−3}(x) − γp_{n−4}(x).

We have p_{n} = (x−α)p_{n−1}−(α+β)p_{n−2}−(α+β+γ)p_{n−3}−(α+β+γ)p_{n−4}−⋯−(α+β+γ)p_{1}−(β+δ+γ). Then

p_{n} = (x − α + 1)p_{n−1} − p_{n−1} − (α + β)p_{n−2} − (α + β + γ)p_{n−3} − (α + β + γ)p_{n−4} − ⋯, or

\begin{matrix}p_{n} = (x − α + 1)p_{n−1} − (x − α + 1)p_{n−2} + (x + β)p_{n−3} + γp_{n−4}− \\ (α + β)p_{n−2} − (α + β + γ)p_{n−3} − · · · . \end{matrix}

Thus

p_{n} = (x − α + 1)p_{n−1} − (x + β + 1)p_{n−2} − (−x + α + γ)p_{n−3} − (α + β)p_{n−4} − ⋯
= (x − α + 1)p_{n−1} − (x + β)p_{n−2} − p_{n−2} − (−x + α + γ)p_{n−3} − (α + β)p_{n−4} − ⋯
= (x − α + 1)p_{n−1} − (x + β)p_{n−2} − (x − α + 1)p_{n−3} + (x + β)p_{n−4} + γp_{n−5} − ⋯
= (x − α + 1)p_{n−1} − (x + β)p_{n−2} − γp_{n−3} − p_{n−3} + (x − α)p_{n−4} + γp_{n−5} − · · · .

We must now show that

−p_{n−3} + (x − α)p_{n−4} − (α + β)p_{n−5} − (α + β + γ)p_{n−6} − ⋯ − (α + β + γ)p_{1} − (β + δ + γ) = 0.

Since

p_{n−3} = (x − α + 1)p_{n−4} − (x + β)p_{n−5} − γp_{n−6}

this reduces to showing that

−p_{n−4} + (x − α)p_{n−5} − (α + β)p_{n−6} − ⋯ − (α + β + γ)p_{1} − (β + δ + γ) = 0.

Iterating on decreasing n we get

0 = 0.

Thus the family of polynomials p_{n}(x) satisfy the four-term recurrence with the appropriate initial conditions.

Conversely, if we start with a family of monic polynomials P_{n}(x) of degree n that satisfy the four-term recurrence

P_{n}(x) = (x − α + 1)P_{n−1}(x) − (x + β)P_{n−2}(x) − γP_{n−3},

with P_{n}(x) = 0 for n < 0, P_{0}(x) = 1 and P_{1}(x) = x − δ, then the Riordan array

(\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} )

will coincide with the coefficient array of P_{n}(x), since clearly p_{n}(x) = P_{n}(x) for all n as they have the same initial values and obey the same recurrence.

We now form the matrix

(1, \frac{x}{1 + x}) · (\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} ) · (\frac{1}{1 − x}, \frac{x}{1 − x}) .

This evaluates to the Riordan array

(\frac{(1 + (α − δ)x)(1 + x)^{2}}{1 + (α + 1)x + (2α + β)x^{2} + (α + β + γ)x^{3}} , \frac{x(1 + x)}{1 + (α + 1)x + (2α + β)x^{2} + (α + β + γ)x^{3}} ) .

Letting γ = 0, this simplifies to

(\frac{(1 + (α − δ)x)(1 + x)}{1 + αx + (α + β)x^{2}}, \frac{x}{1 + αx + (α + β)x^{2}} ) .

But this is the coefficient array of a family of orthogonal polynomials q_{n}(x) that satisfy

q_{n}(x) = (x − α)q_{n−1} − (α + β)q_{n−2}.

Now the general term of the Riordan array (1, \frac{x}{1−x}) is \binom{n−1}{n−k}, while that of (\frac{1}{1−x}, \frac{x}{1+x}) is \binom{n}{k}. Noting that (x + 1)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k} (binomial theorem) completes the proof.

In general, the production matrix of the triple product

(1, \frac{x}{1 + x}) · (\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} ) · (\frac{1}{1 − x}, \frac{x}{1 − x})

is equal to

( \begin{matrix}δ − 1 & 1 & 0 & 0 & 0 & 0 & … \\ β + δ & α & 1 & 0 & 0 & 0 & … \\ γ & α + β & α & 1 & 0 & 0 & … \\ −γ & γ & α + β & α & 1 & 0 & … \\ γ & −γ & γ & α + β & α & 1 & … \\ −γ & γ & −γ & γ & α + β & α & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We note that the intermediate product

(1, \frac{x}{1 + x}) · (\frac{1 + (α − δ − 1)x}{1 + (α − 1)x + βx^{2} + γx^{3}} , \frac{x(1 − x)}{1 + (α − 1)x + βx^{2} + γx^{3}} )

is equal to

(\frac{(1 + (α − δ)x)(1 + x)^{2}}{1 + (α + 2)x + (2α + β + 1)x^{2} + (α + β + γ)x^{3}} , \frac{x(1 + x)}{1 + (α + 2)x + (2α + β + 1)x^{2} + (α + β + γ)x^{3}} ) .

The inverse of this array has production matrix given by

( \begin{matrix}δ & 1 & 0 & 0 & 0 & 0 & … \\ β + δ & α + 1 & 1 & 0 & 0 & 0 & … \\ γ & α + β & α + 1 & 1 & 0 & 0 & … \\ −γ & γ & α + β & α + 1 & 1 & 0 & … \\ γ & −γ & γ & α + β & α + 1 & 1 & … \\ −γ & γ & −γ & γ & α + β & α + 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Corollary 2. When γ = 0, the polynomials

R_{n}(x) = ∑_{k=0}^{n} \binom{n − 1}{n − k}P_{k}(x)

form the family of orthogonal polynomials satisfying

R_{n}(x) = (x − (α + 1))R_{n−1} − (α + β)R_{n−2}(x),

with R_{0}(x) = 1, R_{1}(x) = x − δ.

3 Examples and further results

Example 3. We take the Riordan array (1−x, x(1−x)) which corresponds to α = 1, δ = 1, β = γ = 0. This is the coefficient array for the polynomials P_{n}(x) = ∑_{k=0}^{n} \binom{k+1}{n−k}(−1)^{n−k}x^{k}, which satisfy

P_{n}(x) = xP_{n−1}(x) − xP_{n−2},

with P_{0}(x) = 1, P_{1}(x) = x − 1. The inverse of the coefficient array (1 − x, x(1 − x)) is the Catalan array (c(x), xc(x)) \underline{A033184} which has production matrix

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

The first column of (c(x), xc(x)) is given by the Catalan numbers \underline{A000108}, and hence we can regard the Catalan numbers as the generalized moments of the family P_{n}(x). Now forming the triple product

(1, \frac{x}{1 + x}) · (1 − x, x(1 − x)) · (\frac{1}{1 − x}, \frac{x}{1 − x})

we obtain the orthogonal polynomial coefficient array given by

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

This is the coefficient array of the orthogonal polynomials Q_{n}(x) for which

Q_{n}(x) = (x − 1)Q_{n−1}(x) − Q_{n−2}(x),

with Q_{0}(x) = 1, Q_{1}(x) = x. The moments of these polynomials are the so-called “Motzkin sums”, \underline{A005043}. These appear as the elements of the first column of the inverse coefficient array, which has production matrix

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

The inverse coefficient array is \underline{A089942}. We note that the Catalan numbers and the Motzkin sums have the same Hankel transform. This is because the Motzkin sums are the inverse binomial transform of the Catalan numbers.

Proposition 4. The moments of the orthogonal polynomials Q_{n}(x) above are the inverse binomial transforms of the generalized moments of the polynomials P_{n}(x). In particular, both sets of moments have the same Hankel transform.

Proof. Consider the triple product

(1, \frac{1}{1 + x}) · A · (\frac{1}{1 − x}, \frac{x}{1 − x}) ,

where A is the coefficient array of P_{n}(x). The (generalized) moments of P_{n}(x) are the elements of the first column of A^{−1}. Now the moments of Q_{n}(x) will be given by the elements of the first column of

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

Thus if A^{−1} = (g, f), where g is the generating function of the moments of P_{n}(x), then the moments of Q_{n}(x) have a generating function given by

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

since the first member of (1, \frac{x}{1−x}) is 1. This proves the first assertion. The Hankel transforms are equal because one sequence is related to another by a binomial transform [10, 13].

Note that the above proof actually proves more, since the case of orthogonal Q_{n}(x) only arises when γ = 0.

Example 5. We look at the case of the Riordan array

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

This is the coefficient array of the polynomials P_{n}(x) that satisfy

P_{n}(x) = (x − 3)P_{n−1}(x) − (x + 3)P_{n−2}(x) − P_{n−3}(x),

with P_{0}(x) = 1, P_{1}(x) = x − 4. The moments of this family are given by \underline{A007297}, which begins

1, 4, 23, 156, 1162, 9192, 75819, 644908, 5616182, …

They count the number of connected graphs on n nodes on a circle without crossing edges. Their g.f. is equal to

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

We remark that \frac{x(1−x)}{(1+x)^{3}} is the generating function of the signed squares

0, 1, −4, 9, −16, 25, …

The production matrix of the inverse coefficient array is

( \begin{matrix}4 & 1 & 0 & 0 & 0 & 0 & … \\ 7 & 4 & 1 & 0 & 0 & 0 & … \\ 8 & 7 & 4 & 1 & 0 & 0 & … \\ 8 & 8 & 7 & 4 & 1 & 0 & … \\ 8 & 8 & 8 & 7 & 4 & 1 & … \\ 8 & 8 & 8 & 8 & 7 & 4 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Passing to the triple product we obtain the Riordan array

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

The production matrix of the inverse coefficient array in this case is given by

( \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 & … \\ 7 & 4 & 1 & 0 & 0 & 0 & … \\ 1 & 7 & 4 & 1 & 0 & 0 & … \\ −1 & 1 & 7 & 4 & 1 & 0 & … \\ 1 & −1 & 1 & 7 & 4 & 1 & … \\ −1 & 1 & −1 & 1 & 7 & 4 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The moments for this coefficient array begin

1, 3, 16, 98, 661, 4731, 35299, …,

which are the inverse binomial transform of \underline{A007297}.

It is instructive to look at the Riordan array

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

In this case, γ = 0. The triple product is then equal to

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

whose inverse has production matrix

( \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 & … \\ 7 & 4 & 1 & 0 & 0 & 0 & … \\ 0 & 7 & 4 & 1 & 0 & 0 & … \\ 0 & 0 & 7 & 4 & 1 & 0 & … \\ 0 & 0 & 0 & 7 & 4 & 1 & … \\ 0 & 0 & 0 & 0 & 7 & 4 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Thus the triple product is the coefficient array of the orthogonal polynomials Q_{n}(x) that satisfy

Q_{n}(x) = (x − 4)Q_{n−1}(x) − 7Q_{n−2},

with Q_{0}(x) = 1, Q_{1}(x) = x − 3. The moments of this family of orthogonal polynomials, which begin

1, 3, 16, 97, 648, 4590, 33888, 257925, 2009464, …

then have g.f. given by

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

The polynomials P_{n}(x) whose coefficient array is

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

can now be recovered through the formula

P_{n}(x) = ∑_{k=0}^{n} \binom{n − 1}{n − k}Q_{k}(x − 1).

The moments of the family P_{n}(x), which begin

1, 4, 23, 155, 1145, 8976, 73347, …,

and which are the binomial transform of the moments of Q_{n}, have g.f. given by

\frac{1}{1 − 4x − \frac{7x^{2}}{1 − 5x − \frac{7x^{2}}{1 − 5x − \frac{7x^{2}}{1 − 5x − ⋯}}}}.

Note that the production matrix of the inverse coefficient array to (\frac{1−x}{1+3x+3x^{2}} , \frac{x(1−x)}{1+3x+3x^{2}} ) is given by

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

Example 6. The case of γ = 0 and β + δ = 0 is illustrated by the Riordan array

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

where α = 0 too. The moments of the polynomials defined by this array are given by (−1)^{n}, with corresponding production matrix

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

The triple product

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

then evaluates to

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

The moments of the polynomials defined by this array are given by (−2)^{n}, and the corresponding production matrix is given by

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

The zero in the (2, 1) position shows that this family is not orthogonal.

Example 7. We illustrate the exceptional case γ = 0 and α + β = 0 by taking α = −1, β = 1 and δ = −1. We obtain the Riordan array

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

which is the Binomial matrix (Pascal’s triangle, \underline{A007318}). The polynomials P_{n}(x) are given by P_{n}(x) = (1 + x)^{n}, and the moments are (−1)^{n}. The production matrix of the inverse coefficient array (which is the inverse binomial matrix) is given by

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

Forming the triple product we get the Riordan array

(\frac{1 + x}{1 − x}, \frac{x}{1 − x}) .

The moments of the corresponding polynomials Q_{n}(x) are then (−2)^{n}, and the associated production array is

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

Clearly the polynomials Q_{n}(x) are not orthogonal. We have Q_{n}(x) = (1 + x)^{n−1}(x + 2) for n > 0, and Q_{0}(x) = 1.

Since all matrices above are invertible, it is possible to reverse the above triple product process. A case of particular interest is the following.

Proposition 8. Let Q_{n}(x) be a family of monic orthogonal polynomials given by

Q_{n}(x) = (x − α)Q_{n−1} − βQ_{n−2}(x),

with Q_{0}(x) = 1, Q_{1}(x) = x − α + 1. Then the polynomials

P_{n}(x) = ∑_{k=0}^{n} \binom{n − 1}{n − k}Q_{k}(x − 1)

satisfy the recurrence

P_{n}(x) = (x − α + 1)P_{n−1}(x) − (x + β − α)P_{n−2},

with P_{0}(x) = 1, P_{1}(x) = x − α.

The coefficient array of the polynomials Q_{n}(x) in the above proposition is given by the Riordan array

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

Forming the triple product

(1, \frac{x}{1 − x}) · (\frac{1 + x}{1 + αx + βx^{2}} , \frac{x}{1 + αx + βx^{2}} ) · (\frac{1}{1 + x}, \frac{x}{1 + x})

we obtain the coefficient array of the polynomials P_{n}(x). This is the Riordan array

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

The production matrix of the inverse of this array is given by

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

The production matrix for the inverse of the coefficient array of the orthogonal polynomials Q_{n}(x) in the proposition is given by

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

Corollary 9. The (generalized) moments associated to the polynomials P_{n}(x) whose coefficient array is given by

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

have generating function expressible as

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

Proof. They are the inverse binomial transform of the moments of Q_{n}(x), which have g.f. given by

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

The result follows since the inverse binomial transform increases the x coefficient by 1 [3].

In fact, we could have proved this result independently of the foregoing.

Proposition 10. The (generalized) moments of the Riordan array

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

have g.f.

g(x) = \frac{1 − rx − \sqrt{1 − 2x(r + 2) + x^{2}(r^{2} − 4s)}}{2x(1 + sx)},

which can be expressed as

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

The production matrix of the inverse array is given by

( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 & … \\ r + s + 1 & r + 1 & 1 & 0 & 0 & 0 & … \\ r + s + 1 & r + s + 1 & r + 1 & 1 & 0 & 0 & … \\ r + s + 1 & r + s + 1 & r + s + 1 & r + 1 & 1 & 0 & … \\ r + s + 1 & r + s + 1 & r + s + 1 & r + s + 1 & r + 1 & 1 & … \\ r + s + 1 & r + s + 1 & r + s + 1 & r + s + 1 & r + s + 1 & r + 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The Hankel transform of the moments is h_{n} = (r + s + 1)^{\binom{n+1}{2}}.

Proof. We have

g(x) = \frac{1}{x}Rev_{x} \frac{x(1 − x)}{1 + rx + sx^{2}} = \frac{1 − rx − \sqrt{1 − 2x(r + 2) + x^{2}(r^{2} − 4s)}}{2x(1 + sx)}.

If we let g_{1}(x) represent the continued fraction, then we have

g_{1}(x) = \frac{1}{1 − (r + 1)x − (r + s + 1)x^{2}u} where u = \frac{1}{1 − (r + 2)x − (r + s + 1)x^{2}u}.

Solving for u and then g_{1}(x) we find that g_{1}(x) = g(x). The production matrix is calculated using standard Riordan array techniques. The expression for the Hankel transform follows directly from [11].

Example 11. We consider the generalized Chebyshev polynomials with coefficient array

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

This is the family of orthogonal polynomials Q_{n}(x) which satisfy

Q_{n}(x) = xQ_{n−1} − Q_{n−2},

with Q_{0}(x) = 1, Q_{1}(x) = x + 1. The moments of this family of orthogonal polynomials are given by u_{n} = (−1)^{n}\binom{n}{⌊ \frac{n}{2} ⌋}, the alternating sign version of the central binomial coefficients \underline{A001405}. We form the polynomials

P_{n}(x) = ∑_{k=0}^{n} \binom{n − 1}{n − k}Q_{k}(x − 1).

We find that the coefficient array of these transformed polynomials is given by

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

whose inverse array has production matrix

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

The first column of the inverse array (generalized moments) is given by the so-called “Motzkin sums”, \underline{A005043}. Again, both moment sequences have the same Hankel transform. This is because both are related by a binomial transform. In this case the polynomials P_{n}(x) satisfy the recurrence

P_{n}(x) = (x + 1)P_{n−1} − (x + 1)P_{n−2},

with P_{0}(x) = 1, P_{1}(x) = x.

Example 12. We consider the Riordan array

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

The moments u_{n} of the orthogonal polynomials Q_{n}(x) generated by this array \underline{A129147} begin

1, 1, 4, 13, 52, 214, 928, …

They can be expressed in closed form as

u_{n} = ∑_{k=0}^{n} \binom{k}{n − k}2^{n−k}C_{k},

and have Hankel transform 3^{\binom{n+1}{2}}. The generating function of this sequence can be expressed as the continued fraction

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

The corresponding family of polynomials P_{n}(x) will have coefficient array

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

The moments of this family of polynomials is the sequence \underline{A064641}, which counts certain Łukasiewicz paths [9]. This sequence has a generating function that can be expressed as

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

The production matrix of the inverse coefficient array is given by

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

Reverting to the initial four-term recurrence, we see that the case of

α + β + γ = 0

is worthy of attention. In this case, β + γ = −α, and the original production matrix P_{L} simplifies to

P_{L} = ( \begin{matrix}δ & 1 & 0 & 0 & 0 & 0 & … \\ β + δ & α & 1 & 0 & 0 & 0 & … \\ −α + δ & α + β & α & 1 & 0 & 0 & … \\ −α + δ & 0 & α + β & α & 1 & 0 & … \\ −α + δ & 0 & 0 & α + β & α & 1 & … \\ −α + δ & 0 & 0 & 0 & α + β & α & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Thus in this case we obtain a family of polynomials that are “almost orthogonal”. They are defined by

P_{n}(x) = (x − α)P_{n−1}(x) − (α + β)P_{n−2} + (α − δ),

with P_{0}(x) = 1, and P_{1}(x) = x − δ. In the special case α + β + γ = 0 and α = δ, we have

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

Hence we obtain the family of orthogonal polynomials

P_{n}(x) = (x − α)P_{n−1}(x) − (α + β)P_{n−2},

with P_{0}(x) = 1, and P_{1}(x) = x − α. The transformed polynomials

Q_{n}(x) = ∑_{k=0}^{n}(−1)^{n−k}P_{k}(x + 1)

then correspond to the Riordan array

(\frac{1 + x}{1 + αx}, \frac{x}{1 + αx}) ,

and can be expressed as

Q_{n}(x) = (x − α)Q_{n−1}(x),

with Q_{0}(x) = 1, Q_{1}(x) = x − α + 1. The production matrix of the inverse to the coefficient array (\frac{1+x}{1+αx}, \frac{x}{1+αx}) is given by

P_{L} = ( \begin{matrix}α − 1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & α & 1 & 0 & 0 & 0 & … \\ 0 & 0 & α & 1 & 0 & 0 & … \\ 0 & 0 & 0 & α & 1 & 0 & … \\ 0 & 0 & 0 & 0 & α & 1 & … \\ 0 & 0 & 0 & 0 & 0 & α & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We can express Q_{n}(x) in closed form as

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

References

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

[2] P. Barry and A. Hennessy, Meixner-type results for Riordan arrays and associated integer sequences, J. Integer Seq., 13 (2010), Article 10.9.4.

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

[4] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

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

[6] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays, Ann. Comb., 13 (2009), 65–85.

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

[8] I. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison–Wesley, 1994.

[9] A. Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, PhD Thesis, Waterford Institute of Technology, 2011.

[10] G. Kowaleski, Einführung in die Determinantentheorie einschliesslich der Fredholmschen Determinanten, Chelsea Publishing Company, 1948.

[11] C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Article B42q., available electronically at http://arxiv.org/abs/math/9902004, 1999.

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

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

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

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

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

   cally at http://oeis.org, 2012.

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

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

[19] G. Szegö, Orthogonal Polynomials, 4th ed., Amer. Math. Soc., 1975.

[20] G. Viennot, Une Théorie Combinatoire des Polynômes Orthogonaux Généraux, UQAM, Montreal, Quebec, 1983.

[21] W.-J. Woan, Hankel matrices and lattice paths, J. Integer Seq., 4 (2001), Article 01.1.2.

2010 Mathematics Subject Classification: Primary 11B73; Secondary 33C45, 42C05, 15B36, 15B05, 11C20, 11B83. Keywords: Riordan array, orthogonal polynomial, three-term recurrence, four-term recurrence, production matrix, Hankel transform.

(Concerned with sequences \underline{A000108}, \underline{A001405}, \underline{A005043}, \underline{A007297}, \underline{A007318}, \underline{A033184}, \underline{A064641}, \underline{A089942}, and \underline{A129147}.)

Received November 14 2011; revised version received March 26 2012. Published in Journal of Integer Sequences, March 26 2012.

Return to Journal of Integer Sequences home page.