Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

We study a family of symmetric third-order recurring sequences with the aid of Riordan arrays and Chebyshev polynomials. Formulas involving both Chebyshev polynomials and Fibonacci numbers are established. The family of sequences defined by the product of consecutive terms of the first family of sequences is also studied, and links to the Chebyshev polynomials are again established, including continued fraction expressions. A multiplicative result is established relating Chebyshev polynomials to sequences of doubled Chebyshev polynomials. Links to a special Catalan related Riordan array are explored.

1 Introduction

In a posting to the seqfan mailing list, the forum for contributors to the OEIS [7], Richard Guy invited comments on the ‘symmetric third-order recurring sequences’. This note explores some links between these sequences and Riordan arrays [6, 9]. Riordan arrays provide a convenient vehicle for exploring many integer sequences, and can provide insight into the algebraic relationships that exist between them. These can then often be translated into binomial identities.

We can illustrate the context of this note by taking a simple example, based on the Fibonacci numbers F_{n}, where F_{0} = 0, F_{1} = 1. The sequence of “golden rectangle numbers” is the sequence of products F_{n}F_{n+1}. Thus we have (where we start at index 1)

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\ F_{n} & 1 & 1 & 2 & 3 & 5 & 8 & 13 & … \\ F_{n+1} & 1 & 2 & 3 & 5 & 8 & 13 & 21 & … \\ F_{n}F_{n+1} & 1 & 2 & 6 & 15 & 40 & 104 & 273 & … \end{matrix}

The generating function of the product sequence is given by

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

Thus the product sequence satisfies a “symmetric third-order recurrence”. It is also equal to an alternating sum of the terms of the sequence with generating function

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

Thus

F_{n}F_{n+1} = ∑_{k=0}^{n}(−1)^{n−k}F_{2k},

since F_{2n} is the sequence with g.f. \frac{x}{1−3x+x^{2}} . This motivates us to rearrange the table above in a “zig-zag” fashion.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\ v_{n+1} & 1 & 2 & 2 & 5 & 5 & 13 & 13 & … \\ u_{n} & 1 & 1 & 3 & 3 & 8 & 8 & 21 & … \\ F_{n}F_{n+1} & 1 & 2 & 6 & 15 & 40 & 104 & 273 & … \end{matrix}

Thus the sequence F_{n}F_{n+1} has another factorization, involving doubled sequences. The sequence u_{n} or 1, 1, 3, 3, 8, 8, … has g.f.

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

while the sequence v_{n} or 1, 1, 2, 2, 5, 5, … has g.f.

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

We note four points.

1. The “base” sequence F_{n} has generating function

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

2. The elements F_{2n+2} of the sequence 1, 3, 8, 13, … are values of Chebyshev polynomials

of the second kind :

F_{2n+2} = U_{n}(3/2).

Thus

F_{n+1}F_{n+2} = ∑_{k=0}^{n}(−1)^{n−k}U_{k}(3/2).

3. The sequence 1, 2, 5, 13, … represents the first differences of 1, 3, 8, 21, . . .. Thus the product sequence has another factorization u_{n}v_{n+1} involving the doubling of a (Chebyshev) sequence and its first differences.

4. We have

∑_{i=0}^{n} F_{i}F_{i+1} = ∑_{i=0}^{n} ∑_{j=0}^{i}(−1)^{i−j}F_{2j} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} F_{2(n−2k)} = ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} U_{n−2k−1}(3/2).

The goal of this paper is to show that all sequences with generating functions of the form

\frac{1}{1 − kx − kx^{2} + x^{4}}

enjoy similar properties to those of the products of consecutive Fibonacci numbers: they are all the product of consecutive terms of a related “base” sequence, and both sequences (base and product sequence) may be expressed in terms of Chebyshev polynomials. We employ the techniques of Riordan arrays to establish other interesting properties of these sequences. The plan of the paper is as follows:

1. This Introduction

2. Notation and recall of results

3. The polynomial sequences a(n; r), product sequences b(n; r) and Riordan arrays

4. a(n; r) and Chebyshev polynomials

5. b(n; r) and Chebyshev polynomials

6. From b(n; r) to a(n; r)

7. A Chebyshev product result

8. Additional Riordan array factorizations

9. A left inverse

10. The matrix (\frac{1−x}{1+x^{4}} , \frac{x}{1+x^{2}} )

11. Appendix

12. Acknowledgements

2 Notation and recall of results

For an integer sequence a_{n}, that is, an element of Z^{N}, the power series f(x) = ∑_{k=0}^{∞} a_{k}x^{k} is called the ordinary generating function or g.f. of the sequence. a_{n} is thus the coefficient of x^{n} in this series. We denote this by a_{n} = [x^{n}]f(x). For instance, F_{n} = [x^{n}]\frac{x}{1−x−x^{2}} is the n-th Fibonacci number, while C_{n} = [x^{n}]\frac{1−\sqrt{1−4x}}{2x} is the n-th Catalan number.

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

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

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

A Riordan array of the form (g(x), x), where g(x) is the generating function of the sequence a_{n}, is called the sequence array of the sequence a_{n}. Its general term is a_{n−k}. Such arrays are also called Appell arrays as they form the elements of the Appell subgroup.

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

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

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

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

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

is equal to

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

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

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

while the diagonal sums of (g, f) (sums of left-to-right diagonals in the North East direction) have generating function g(x)/(1 − xf(x)). These coincide with the row sums of the “generalized” Riordan array (g, xf). Thus the Fibonacci numbers F_{n+1} are the diagonal sums of the binomial matrix B given by (\frac{1}{1−x}, \frac{x}{1−x}):

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

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

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

We note that

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 ; x ; x^{2} ; x^{3} ; x^{4} ; x^{5} ; ⋮ ) = ( 1 ; x + 1 ; (x + 1)^{2} ; (x + 1)^{3} ; (x + 1)^{4} ; (x + 1)^{5} ; ⋮ )

while a second application of this matrix will send x^{n} to (x + 2)^{n}.

To each proper Riordan matrix (f_{1} ≠ 0)

(g(x), f(x)) = (g(x), xh(x)) = (M_{n,k})_{n,k≥0}

there exist [2] two sequences α = (α_{0}, α_{1}, α_{2}, …)(α_{0} ≠ 0) and ξ = (ξ_{0}, ξ_{1}, ξ_{2}, …) such that

1. Every element in column 0 can be expressed as a linear combination of all the elements in the preceding row, the coefficients being the elements of the sequence ξ, i.e.

M_{n+1,0} = ξ_{0}M_{n,0} + ξ_{1}M_{n,1} + ξ_{2}M_{n,2} + …

2. Every element M_{n+1,k+1} not lying in column 0 or row 0 can be expressed as a linear combination of the elements of the preceding row, starting from the preceding column on, the coefficients being the elements of the sequence α, i.e.

M_{n+1,k+1} = α_{0}M_{n,k} + α_{1}M_{n,k+1} + α_{2}M_{n,2} + …

The sequences α and ξ are called the α-sequence and the ξ-sequence of the Riordan matrix. It is customary to use the same symbols α and ξ as the names of the corresponding generating functions. The functions g(x), f(x), α(x) and ξ(x) are connected as follows :

f(x) = xα(f(x)), g(x) = \frac{M_{0,0}}{1 − xξ(f(x))}.

The α-sequence is sometimes called the A-sequence of the array and then we write A(x) = α(x).

Many interesting examples of Riordan arrays can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences, [7], [8]. Sequences are frequently referred to by their OEIS number. For instance, the matrix B is \underline{A007318}.

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

Each Riordan array (g(x), f(x)) has bi-variate generating function given by

\frac{g(x)}{1 − yf(x)}.

For instance, the binomial matrix B has generating function

\frac{\frac{1}{1−x}}{1 − y \frac{x}{1−x}} = \frac{1}{1 − x(1 + y)}.

For a sequence a_{0}, a_{1}, a_{2}, … with g.f. g(x), the “aeration” of the sequence is the sequence a_{0}, 0, a_{1}, 0, a_{2}, … with interpolated zeros. Its g.f. is g(x^{2}). The sequence a_{0}, a_{0}, a_{1}, a_{1}, a_{2}, … is called the “doubled” sequence. It has g.f. (1 + x)g(x^{2}).

The Chebyshev polynomials of the second kind, U_{n}(x), are defined by

U_{n}(x) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}(−1)^{k}(2x)^{n−2k}

Alternatively,

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

They satisfy the three-term recurrence

U_{n+1} = 2xU_{n}(x) − U_{n−1}(x), U_{0}(x) = 1, U_{1}(x) = 2x.  (1)

The generating function for U_{n}(x) is given by

∑_{k=0}^{∞} U_{n}(x)y^{n} = \frac{1}{1 − 2xy + y^{2}} .  (2)

We note that the coefficient array of the polynomials U_{n}(x/2) which begin 1, x, x^{2} − 1, x^{3} − 2x, x^{4} − 3x^{2} + 1, …, begins

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

This is the Riordan array

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

This follows since

\frac{\frac{1}{1+x^{2}}}{1 − y \frac{x}{1+x^{2}}} = \frac{1}{1 − xy + y^{2}} = \frac{1}{1 − 2\frac{x}{2}y + y^{2}} .

This matrix is \underline{A049310}. Thus

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ −1 & 0 & 1 & 0 & 0 & 0 & … \\ 0 & −2 & 0 & 1 & 0 & 0 & … \\ 1 & 0 & −3 & 0 & 1 & 0 & … \\ 0 & 3 & 0 & −4 & 0 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 ; x ; x^{2} ; x^{3} ; x^{4} ; x^{5} ; ⋮ ) = ( 1 ; x ; x^{2} − 1 ; x^{3} − 2x ; x^{4} − 3x^{2} + 1 ; x^{5} − 4x^{3} + 3x ; ⋮ ) .

Similarly, the polynomials U_{n} (\frac{x+2}{2}) have coefficient array given by

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

In matrix terms, this gives us

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 0 & 0 & 0 & … \\ 3 & 4 & 1 & 0 & 0 & 0 & … \\ 4 & 10 & 6 & 1 & 0 & 0 & … \\ 5 & 20 & 21 & 8 & 1 & 0 & … \\ 6 & 35 & 56 & 36 & 10 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 ; x ; x^{2} ; x^{3} ; x^{4} ; x^{5} ; ⋮ ) = ( 1 ; x + 2 ; x^{2} + 4x + 3 ; x^{3} + 6x^{2} + 10x + 4 ; x^{4} + 8x^{3} + 21x^{2} + 20x + 5 ; x^{5} + 10x^{4} + 36x^{3} + 56x^{2} + 35x + 6 ; ⋮ ) .

This coefficient matrix is \underline{A078812}, whose general term is \binom{n+k+1}{2k+1}. The polynomials so defined are the Morgan-Voyce polynomials [10]

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

The Morgan-Voyce polynomials m(n, x) are defined by

m(n, x) = ∑_{k=0}^{n} \binom{n + k}{2k}x^{k} = ∑_{k=0}^{n} \binom{n + k}{n − k}x^{k}.

The coefficient array for these polynomials, which has general term \binom{n+k}{2k}, is the Riordan array

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

This is \underline{A085478}. For this, we have

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 6 & 5 & 1 & 0 & 0 & … \\ 1 & 10 & 15 & 7 & 1 & 0 & … \\ 1 & 15 & 35 & 28 & 9 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 ; x ; x^{2} ; x^{3} ; x^{4} ; x^{5} ; ⋮ ) = ( 1 ; x + 1 ; x^{2} + 3x + 1 ; x^{3} + 5x^{2} + 6x + 1 ; x^{4} + 7x^{3} + 15x^{2} + 10x + 1 ; x^{5} + 9x^{4} + 28x^{3} + 35x^{2} + 15x + 1 ; ⋮ ) .

The Morgan-Voyce polynomials can be defined by a three-term recurrence as follows :

m(0, x) = 1, m(1, x) = 1 + x, m(n, x) = (x + 2)m(n − 1, x) − m(n − 2, x) (3)

and

M(0, x) = 1, M(1, x) = 2 + x, M(n, x) = (x + 2)M(n − 1, x) − M(n − 2, x). (4)

In the sequel, we shall use the notation i = \sqrt{−1}.

3 The polynomial sequences a(n; r), product sequences

b(n; r) and Riordan arrays

We wish to study sequences of polynomials of the form

a(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}r^{⌊ \frac{n−2k}{2} ⌋},

with generating function

g_{a}(x; r) = \frac{1 + x − x^{2}}{1 − (r + 2)x^{2} + x^{4}}

and the related sequences b(n; r) with generating function

g_{b}(x; r) = \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}} .

Examples of these sequences in the OEIS [7] are given below.

r  a(n; r)  b(n; r)
0  \underline{A157329}  \underline{A008619}
1 \underline{A000045}(n + 1) \underline{A001654}(n + 1)
2 \underline{A002530}(n + 1) \underline{A109437}(n + 1)
3 \underline{A136211}(n + 1)  \underline{A099025}
4  \underline{A041011}  \underline{A084158}(n + 1)
5 \underline{A152119}(n + 1)  \underline{A157335}

In each of the cases above, we have

b(n; r) = a(n; r)a(n + 1; r).

Elements of the family {a(n; r)} are images of the doubled sequences 1, 1, r, r, r^{2}, r^{2}, … with generating function \frac{1+x}{1−rx^{2}} by the Riordan array

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

(closely related to the Chebyshev polynomials). This is so since we have

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

the generating function of a(n; r). An immediate consequence of this is the fact that

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

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

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

a(n; r) thus represents the diagonal sums of the number triangle with general term \binom{n}{k}r^{⌊ \frac{n−k}{2} ⌋}. It is clear that a(n; r) is a polynomial in r. We can express a(n; r) directly in terms of ascending powers of r by noticing that the coefficient array of the polynomials a(n; r), which begins

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

is the (generalized) Riordan array

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

with general term

\binom{⌊\frac{n+2k+1}{2}⌋}{⌊\frac{n−2k}{2}⌋}.

(A proof of this assertion is indicated in the Appendix). Thus we have

a(n; r) = ∑_{k=0}^{n} \binom{⌊\frac{n+2k+1}{2}⌋}{⌊\frac{n−2k}{2}⌋}r^{k}.  (5)

This translates the algebraic identity

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

The family of polynomials a(n; r) begins

1, 1, r + 1, r + 2, r^{2} + 3r + 1, r^{2} + 4r + 3, r^{3} + 5r^{2} + 6r + 1, …

We note that if we define a family of polynomials P(n, x) as

P(0, x) = 1, P(1, x) = 1, P(n, x) = P(n − 1, x) + xP(n − 2, x), n > 1

then we have

a(n, r) = r^{⌊ \frac{n}{2} ⌋}P (n, \frac{1}{r}) .

We further have

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

where the last matrix is not invertible (due to the factor (1 + x, x^{2})). We can describe a(n; r) in terms of the Morgan-Voyce polynomials as follows : Proposition 3. We have

a(2n; r) = m(n, r), a(2n + 1; r) = M(n, r).

Proof. We have

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

The case of a(2n + 1; r) follows in like manner. Corollary 4.

a(n; r) = m(n/2, r)\frac{1 + (−1)^{n}}{2} + M((n − 1)/2, r)\frac{1 − (−1)^{n}}{2} .

The main result of this paper is that the observation

b(n; r) = a(n; r)a(n + 1; r)

holds in general. Theorem 5. Let a(n; r) be the sequence of polynomials with generating function

g_{a}(x; r) = \frac{1 + x − x^{2}}{1 − (r + 2)x^{2} + x^{4}} .

Also let b(n; r) be the sequence of polynomials with generating function

g_{b}(x; r) = \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}} .

Then we have, for all n, r ∈ ℤ,

b(n; r) = a(n; r)a(n + 1; r).

Proof. We have

g_{a}(x; r) = \frac{1 + x − x^{2}}{1 − (r + 2)x^{2} + x^{4}} = A(x)

so that

A(x) − (r + 2)x^{2}A(x) + x^{4}A(x) = 1 + x − x^{2}.

Extracting the coefficient of x^{n+4}, we obtain

[x^{n+4}]A(x) − (r + 2)[x^{n+2}]A(x) + [x^{n}]A(x) = [x^{n+4}](1 + x − x^{2})

A_{n+4} − (r + 2)A_{n+2} + A_{n} = 0.  (6)

By direct inspection, the first terms of the sequence A_{n} = a(n; r) are

1, 1, 1 + r, 2 + r, 1 + 3r + r^{2}, 3 + 4r + r^{2}, . . ..

We now set B_{n} = A_{n}A_{n+1} and T_{n} = A_{n}A_{n+3}, and try to determine the corresponding generating functions. From recurrence (6), we have

A_{n+4} = (r + 2)A_{n+2} − A_{n}
A_{n+5} = (r + 2)A_{n+3} − A_{n+1}.

Multiplying, we obtain

A_{n+4}A_{n+5} = (r + 2)^{2}A_{n+2}A_{n+3} − (r + 2)A_{n+1}A_{n+2} − (r + 2)A_{n}A_{n+3} + A_{n}A_{n+1}.

This can be written as:

B_{n+4} = (r + 2)^{2}B_{n+2} − (r + 2)B_{n+1} − (r + 2)T_{n} + B_{n}.  (7)

Now multiplying equation (6) by A_{n+3}, we obtain

A_{n+3}A_{n+4} = (r + 2)A_{n+2}A_{n+3} − A_{n}A_{n+3},

or

B_{n+3} = (r + 2)B_{n+2} − T_{n}.  (8)

We can now use the method of coefficients [5] to pass from the recurrences to the corresponding generating functions B(x) and T (x). In order to do so, we note that the coefficients of the sequence generated by B(x) begin:

1, 1 + r, 2 + 3r + r^{2}, 2 + 7r + 5r^{2} + r^{3}, . . ..

Equation (7) becomes

\frac{B(x) − 1 − (1 + r)x − (2 + 3r + r^{2})x^{2} − (2 + 7r + 5r^{2} + r^{3})x^{3}}{x^{4}} ; = (r + 2)\frac{B(x) − 1 − (1 + r)x}{x^{2}} − (r + 2)\frac{B(x) − 1}{x} − (r + 2)T (x) + B(x)  (9)

while Equation (8) becomes:

\frac{B(x) − 1 − (1 + r)x − (2 + 3r + r^{2})x^{2}}{x^{3}} = (r + 2)\frac{B(x) − 1 − (1 + r)x}{x^{2}} − T (x).  (10)

We now have two linear equations for the two unknowns B(x) and T (x). Solving, we find that

B(x) = \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}} = g_{b}(x; r)

as required.

Corollary 6.

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

is the generating function of the product a(n; r)a(n + 3; r).

The author is indebted to an anonymous reviewer for the form of this proof.

We note that this theorem establishes the binomial identity

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

where the left hand side follows from the Cauchy form of the product of two polynomials and the right hand side is an expression for the general term of the b(n; r) coefficient array (\frac{1}{(1−x)(1−x^{2})}, \frac{x}{(1−x)^{2}} ).

4 a(n; r) and Chebyshev polynomials

We can express a(n; r) in terms of Chebyshev polynomials. This is the content of the following proposition.

Proposition 7.

a(n; r) = i^{n}\{\frac{\sqrt{r} + 1}{2\sqrt{r}}U_{n} (−i\frac{\sqrt{r}}{2}) + \frac{\sqrt{r} − 1}{2\sqrt{r}}U_{n} (i\frac{\sqrt{r}}{2}) \}.  (12)

Proof. We recall that the g.f. of a(n; r) is \frac{1+x−x^{2}}{1−(r+2)x^{2}+x^{4}} . Now

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

The assertion follows from this, given Eq. (2). Corollary 8.

a(n; r) = i^{n}U_{n} (i\frac{\sqrt{r}}{2}) \{(−1)^{n} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\}.  (13)

Proof. We have U_{n}(−x) = (−1)^{n}U_{n}(x). The result follows from this. This now allows us to characterize the product a(n; r)a(n + 1; r) in terms of Chebyshev polynomials. Proposition 9.

a(n; r)a(n + 1; r) = i(−1)^{n+1} \frac{U_{n} (i\frac{\sqrt{r}}{2}) U_{n+1} (i\frac{\sqrt{r}}{2})}{\sqrt{r}}.  (14)

Proof.

a(n; r)a(n + 1; r) = i(−1)^{n}U_{n} (i\frac{\sqrt{r}}{2}) U_{n+1} (i\frac{\sqrt{r}}{2}) \{(−1)^{n} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\} ·

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

= i(−1)^{n}U_{n} (i\frac{\sqrt{r}}{2}) U_{n+1} (i\frac{\sqrt{r}}{2}) \frac{1}{4r}(−(\sqrt{r} + 1)^{2} + (\sqrt{r} − 1)^{2})
= i(−1)^{n}U_{n} (i\frac{\sqrt{r}}{2}) U_{n+1} (i\frac{\sqrt{r}}{2}) \frac{1}{4r}. − 4\sqrt{r}
= i(−1)^{n+1} \frac{U_{n} (i\frac{\sqrt{r}}{2}) U_{n+1} (i\frac{\sqrt{r}}{2})}{\sqrt{r}}.

The following proposition provides a link between the polynomials a(n; r) and continued fractions.

Proposition 10.

a(n + 2; r) = a(n + 1; r)\frac{r(1 + (−1)^{n}) + 1 − (−1)^{n}}{2} + a(n; r)  (15)

Proof. We have

a(n + 2; r) = i^{n+2}U_{n+2} (\frac{i\sqrt{r}}{2}) \{(−1)^{n+2} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\}
= −i^{n} (2i\frac{\sqrt{r}}{2}U_{n+1} (\frac{i\sqrt{r}}{2}) − U_{n} (\frac{i\sqrt{r}}{2})) \{(−1)^{n+2} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\}
= −i^{n+1}\sqrt{r}U_{n+1} (\frac{i\sqrt{r}}{2}) \{(−1)^{n} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\} +

i^{n}U_{n} (\frac{i\sqrt{r}}{2}) \{(−1)^{n} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\}

= a(n + 2; r)\frac{−\sqrt{r}\{(−1)^{n} \frac{\sqrt{r}+1}{2\sqrt{r}} + \frac{\sqrt{r}−1}{2\sqrt{r}}\}}{\{(−1)^{n+1} \frac{\sqrt{r}+1}{2\sqrt{r}} + \frac{\sqrt{r}−1}{2\sqrt{r}}\}} + a(n; r)
= a(n + 1; r)\frac{r(1 + (−1)^{n}) + 1 − (−1)^{n}}{2} + a(n; r).

Inspired by [4], we now define a family of rational functions R(n, r) as follows :

R(n, r) = \{ \begin{matrix}1 & if n = 0 \\ 1 & if n = 1 \\ \frac{1}{1+ \frac{1}{r} R(n−1,r)} & if n > 1 \end{matrix}

The first elements of the family are

1, 1, \frac{r}{r + 1}, \frac{r + 1}{r + 2}, \frac{r(r + 2)}{r^{2} + 3r + 1}, \frac{r^{2} + 3r + 1}{r^{2} + 4r + 3}, …

Proposition 11.

a(n; r) = Denominator(R(n, r))

Proof. Induction, using Eq. (15). Noting that

R(n, r) = \frac{i\sqrt{r}U_{n−1} (\frac{i\sqrt{r}}{2})}{U_{n} (\frac{i\sqrt{r}}{2})}, n > 0,

we have

a(n; r) = Denominator (\frac{i\sqrt{r}U_{n−1} (\frac{i\sqrt{r}}{2})}{U_{n} (\frac{i\sqrt{r}}{2})}) .  (16)

Finally, we can use the expression

U_{n}(x) = 2^{n} ∏_{k=1}^{n} (x − cos (\frac{kπ}{n + 1}))

and Corollary 13 to give another characterization of a(n; r). Proposition 12.

a(n; r) = ∏_{k=1}^{⌊ \frac{n}{2} ⌋} (r + 4 cos^{2} (\frac{kπ}{n + 1})) .  (17)

Proof. We begin with the case n = 2m. Then

i^{n}U_{n} (\frac{i\sqrt{r}}{2}) = i^{n}2^{n} ∏_{k=1}^{n} (\frac{i\sqrt{r}}{2} − cos (\frac{kπ}{n + 1}))
= i^{n} ∏_{k=1}^{n} (i\sqrt{r} − 2 cos (\frac{kπ}{n + 1}))
= i^{n} ∏_{k=1}^{m} (i\sqrt{r} − 2 cos (\frac{kπ}{n + 1})) (i\sqrt{r} + 2 cos (\frac{kπ}{n + 1}))
= i^{n} ∏_{k=1}^{m} (−r − 4 cos^{2} (\frac{kπ}{n + 1}))
= i^{2m}(−1)^{m} ∏_{k=1}^{m} (r + 4 cos^{2} (\frac{kπ}{n + 1}))
= ∏_{k=1}^{⌊ \frac{n}{2} ⌋} (r + 4 cos^{2} (\frac{kπ}{n + 1})) .

Note that in the product expansion we have used a first with last, second with next-to-last, etc coupling. We now turn to the case n = 2m + 1. We obtain

i^{n}U_{n} (\frac{i\sqrt{r}}{2}) = i^{n}2^{n} ∏_{k=1}^{n} (\frac{i\sqrt{r}}{2} − cos (\frac{kπ}{n + 1}))

= i^{n} ∏_{k=1}^{n} (i\sqrt{r} − 2 cos (\frac{kπ}{n + 1}))

= i^{n}\{ ∏_{k=1}^{m} (i\sqrt{r} − 2 cos (\frac{kπ}{n + 1})) (i\sqrt{r} + 2 cos (\frac{kπ}{n + 1})) \} ·

(i\sqrt{r} − 2 cos (\frac{(m + \frac{1}{2})π}{2m + 1} ))

= i^{n} ∏_{k=1}^{m} (−r − 4 cos^{2} (\frac{kπ}{n + 1})) (i\sqrt{r} − 2 cos (\frac{π}{2} ))

= i^{2m+1}(−1)^{m} ∏_{k=1}^{m} (r + 4 cos^{2} (\frac{kπ}{n + 1})) (i\sqrt{r} − 2 cos (\frac{π}{2} ))

= ∏_{k=1}^{⌊ \frac{n}{2} ⌋} (r + 4 cos^{2} (\frac{kπ}{n + 1})) (−\sqrt{r}).

The result follows now from the fact that

a(n; r) = i^{n}U_{n} (i\frac{\sqrt{r}}{2}) \{(−1)^{n} \frac{\sqrt{r} + 1}{2\sqrt{r}} + \frac{\sqrt{r} − 1}{2\sqrt{r}}\}

where (−1)^{n} \frac{\sqrt{r}+1}{2\sqrt{r}} + \frac{\sqrt{r}−1}{2\sqrt{r}} is the sequence

1, −\frac{1}{\sqrt{r}}, 1, −\frac{1}{\sqrt{r}}, 1, −\frac{1}{\sqrt{r}}, ….

We note that the case r = 5 of this result is noted in \underline{A152119} (Roger L. Bagula and Gary W. Adamson).

5 b(n; r) and Chebyshev polynomials

We can also express the second sequence family b(n; r) in terms of Chebyshev polynomials.

Proposition 13.

b(n; r) = ∑_{k=0}^{n}(−1)^{n−k}U_{k} (\frac{r + 2}{2}) .  (18)

Proof. We have

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

as an easy calculation will verify. This implies that for the sequence b(n; r) with generating function

g_{b}(x; r) = \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}}

we have

b(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n−k}U_{k} (\frac{r + 2}{2}) .

Corollary 14. b(n; r) is the first difference of the sequence with general term

w(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} U_{n−2k} (\frac{r + 2}{2}) .

Proof. We have

b(n; r) = ∑_{k=0}^{n}(−1)^{n−k}U_{k} (\frac{r + 2}{2})

= U_{n} (\frac{r + 2}{2}) − U_{n−1} (\frac{r + 2}{2}) + U_{n−2} (\frac{r + 2}{2}) − …
= U_{n} (\frac{r + 2}{2}) + U_{n−2} (\frac{r + 2}{2}) + … − U_{n−1} (\frac{r + 2}{2}) − U_{n−3} (\frac{r + 2}{2}) − …

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

Corollary 15.

b(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \{U_{n−2k+1} (\frac{r + 2}{2}) − (r + 1)U_{n−2k} (\frac{r + 2}{2}) \}.

Proof. We use the Chebyshev recurrence

U_{n+1} = 2xU_{n}(x) − U_{n−1}(x), U_{0}(x) = 1, U_{1}(x) = 2x.

We note that the results above also follow directly from the observation that

g_{b}(x; r) = \frac{1}{(1 + x)(1 − (r + 2)x + x^{2})} = (1 − x) · \frac{1}{1 − x^{2}} · \frac{1}{1 − (r + 2)x + x^{2}} .

Now the general term of the Riordan array

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

can be expressed as

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

This is \underline{A158909}, which has row sums given by the product of consecutive Fibonacci numbers F (n + 1)F (n + 2) and diagonal sums given by the Jacobsthal numbers \underline{A001045}. The array begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 3 & 1 & 0 & 0 & 0 & … \\ 2 & 7 & 5 & 1 & 0 & 0 & … \\ 3 & 13 & 16 & 7 & 1 & 0 & … \\ 3 & 22 & 40 & 29 & 9 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We thus have

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

The polynomials b(n; x) begin

1, x + 1, x^{2} + 3x + 2, x^{3} + 5x^{2} + 7x + 2, x^{4} + 7x^{3} + 16x^{2} + 13x + 3, …

We note that

1 = 1
x + 1 = 1 · (1 + x)
x^{2} + 3x + 2 = (1 + x)(2 + x)
x^{3} + 5x^{2} + 7x + 2 = (2 + x)(1 + 3x + x^{2})
x^{4} + 7x^{3} + 16x^{2} + 13x + 3 = (1 + 3x + x^{2})(3 + 4x + x^{2}) …

Alternative (and more esoteric) expressions can be found for b(n; r) by taking other factorizations of the coefficient array. For instance,

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

leads to the expression

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

6 From b(n; r) to a(n; r)

We now show that we can find a transformation from the sequences b(n; r) with generating function

g_{b}(x; r) = \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}}

to the sequences a(n; r) with generating function g_{a}(x; r) = \frac{1+x−x^{2}}{1−(r+2)x^{2}+x^{4}} . This follows since

g_{a}(x; r) = \frac{1 + x − x^{2}}{1 − (r + 2)x^{2} + x^{4}}
= (\frac{1 + x − x^{2}}{(1 − x^{2})^{2}} , \frac{x^{2}}{(1 − x^{2})^{2}} ) · \frac{1}{1 − rx}
= (\frac{1 + x − x^{2}}{(1 − x^{2})^{2}} , \frac{x^{2}}{(1 − x^{2})^{2}} ) · (\frac{1}{(1 − x)(1 − x^{2})}, \frac{x}{(1 − x)^{2}} )^{−1} · \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}}
= (\frac{1 + x − x^{2}}{(1 − x^{2})^{2}} , \frac{x^{2}}{(1 − x^{2})^{2}} ) · (c(−x)^{2} + xc(−x)^{4}, 1 − c(−x)) · \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}}
= (1 + x + x^{3} − x^{4}, x^{2}) · \frac{1}{1 − (r + 1)x − (r + 1)x^{2} + x^{3}}
= (1 + x + x^{3} − x^{4}, x^{2}) · g_{b}(x; r).

Here, we have used the notation

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

for the generating function of the Catalan numbers \underline{A000108}. For instance, we have

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ −1 & 0 & 1 & 0 & 0 & 0 & … \\ 0 & 1 & 1 & 0 & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 5 30 174 1015 5915 ⋮ ) = ( 1 1 5 6 29 35 ⋮ )

which displays the sequence with g.f. \frac{1+x−x^{2}}{1−6x^{2}+x^{4}} and general term

a(n; 4) = ∑_{j=0}^{⌊ \frac{n}{2} ⌋} \binom{n − j}{j}4^{⌊ \frac{n−2j}{2} ⌋}

as the image of the sequence with g.f. \frac{1}{1−5x−5x^{2}+x^{3}} and general term

b(n; 4) = a(n; 4)a(n + 1; 4).

We thus have the following proposition.

Proposition 16. The sequence b(n; r) with generating function

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

is transformed into the sequence a(n; r) with generating function \frac{1+x−x^{2}}{1−(r+2)x^{2}+x^{4}} and general term

a(n; r) = ∑_{j=0}^{⌊ \frac{n}{2} ⌋} \binom{n − j}{j}r^{⌊ \frac{n−2j}{2} ⌋}

by the (generalized) Riordan array

(1 + x + x^{3} − x^{4}, x^{2}).

We note that this transformation is not invertible. In terms of invertible transforms, we have the following result.

Proposition 17. a(n; r) is the image under the Riordan array (1 + x + x^{3} − x^{4}, x) of the aeration of b(n; r).

Proof. We have

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

Corollary 18. The aeration of b(n; r) is the image of a(n; r) under the Riordan array (\frac{1}{1+x+x^{3}−x^{4}} , x).

We now note that the Riordan array (\frac{1}{1+x+x^{3}−x^{4}} , x) is the sequence array for the sequence with general term

∑_{j=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n−j}F (n − 2j + 1).

Hence we have

Corollary 19.

b(n; r) = ∑_{k=0}^{2n} ∑_{j=0}^{⌊ \frac{2n−k}{2} ⌋}(−1)^{2n−k−j}F (2n − k − 2j + 1)a(k; r).  (20)

7 A Chebyshev product result

In this section, we observe that the polynomials

w(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} U_{n−2k} (\frac{r + 2}{2})

exhibit a multiplicative property. To this end, we let U_{n}^{d}(x) represent a “doubled” Chebyshev polynomial, defined by

U_{n}^{d}(x) = U\frac{n}{2} (x)\frac{1 + (−1)^{n}}{2} + U_{\frac{n−1}{2}} (x)\frac{1 − (−1)^{n}}{2} .

Clearly,

U_{n}^{d}(x) = ∑_{k=0}^{⌊ \frac{n}{4} ⌋} \binom{⌊\frac{n}{2}⌋ − k}{k}(−1)^{k}(2x)^{⌊ \frac{n}{2} ⌋−2k}.

The generating function for the polynomials U_{n}^{d}(x) is then given by

\frac{1 + y}{1 − 2xy^{2} + y^{4}} .

The generating function of ∑_{k=0}^{⌊ \frac{n}{2} ⌋} U_{n−2k}(x) is similarly given by

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

Theorem 20. We have

∑_{k=0}^{⌊ \frac{n}{2} ⌋} U_{n−2k}(x) = U_{n}^{d}(x)U_{n+1}^{d}(x).  (21)

Proof. The proof follows the same method as the proof of Theorem 5. For completeness, we give the details. We let

\frac{1 + y}{1 − 2xy^{2} + y^{4}} = A(y)

so that

A(y) − 2xy^{2}A(y) + y^{4}A(y) = 1 + y.

Extracting the coefficient of y^{n+4}, we obtain

[y^{n+4}]A(y) − 2x[y^{n+2}]A(y) + [y^{n}]A(y) = [y^{n+4}](1 + y)

A_{n+4} − 2xA_{n+2} + A_{n} = 0.  (22)

By direct inspection, the first terms of the sequence A_{n} = a(n; r) are

1, 1, 2x, 2x, 4x^{2} − 1, 4x^{2} − 1, . . ..

We now set B_{n} = A_{n}A_{n+1} and T_{n} = A_{n}A_{n+3}, and try to determine the corresponding generating functions. From recurrence (22), we have

A_{n+4} = 2xA_{n+2} − A_{n}
A_{n+5} = 2xA_{n+3} − A_{n+1}.

Multiplying, we obtain

A_{n+4}A_{n+5} = 4x^{2}A_{n+2}A_{n+3} − 2xA_{n+1}A_{n+2} − 2xA_{n}A_{n+3} + A_{n}A_{n+1}.

This can be written as:

B_{n+4} = 4x^{2}B_{n+2} − 2xB_{n+1} − 2xT_{n} + B_{n}.  (23)

Now multiplying equation (22) by A_{n+3}, we obtain

A_{n+3}A_{n+4} = 2xA_{n+2}A_{n+3} − A_{n}A_{n+3},

or

B_{n+3} = 2xB_{n+2} − T_{n}.  (24)

We can now use the method of coefficients to pass from the recurrences to the corresponding generating functions B(y) and T (y). In order to do so, we note that the coefficients of the sequence generated by B(y) begin:

1, 2x, 4x^{2}, 2x(4x^{2} − 1), . . ..

Equation (23) becomes

\frac{B(y) − 1 − 2xy − 4x^{2}y^{2} − 2x(4x^{2} − 1)y^{3}}{y^{4}} ; = 4x^{2} \frac{B(y) − 1 − 2xy}{y^{2}} − 2x\frac{B(y) − 1}{y} − 2xT (y) + B(y)  (25)

while Equation (24) becomes:

\frac{B(y) − 1 − 2xy − 4x^{2}y^{2}}{y^{3}} = 2x\frac{B(y) − 1 − 2xy}{y^{2}} − T (y).  (26)

We now have two linear equations for the two unknowns B(y) and T (y). Solving, we find that

B(y) = \frac{1}{(1 − y^{2})(1 − 2xy + y^{2})}

as required.

We note that we also obtain

T (y) = \frac{2x − y}{(1 − y^{2})(1 − 2xy + y^{2})}.

This theorem then implies that

w(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} U_{n−2k} (\frac{r + 2}{2}) = U_{n}^{d} (\frac{r + 2}{2}) U_{n+1}^{d} (\frac{r + 2}{2}) .  (27)

An immediate consequence of this result is that we have

b(n; r) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} U_{n−2k} (\frac{r + 2}{2}) − ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} U_{n−2k−1} (\frac{r + 2}{2})
= U_{n}^{d} (\frac{r + 2}{2}) U_{n+1}^{d} (\frac{r + 2}{2}) − U_{n−1}^{d} (\frac{r + 2}{2}) U_{n}^{d} (\frac{r + 2}{2})
= U_{n}^{d} (\frac{r + 2}{2}) (U_{n+1}^{d} (\frac{r + 2}{2}) − U_{n−1}^{d} (\frac{r + 2}{2}))

This exhibits b(n; r) as the product of a Chebyshev related polynomial and its first difference.

8 Additional Riordan array factorizations

We note that

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

and hence

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

Thus

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

Here, (\frac{1}{1−x}, \frac{x}{1−x}) represents the standard binomial transformation. We also have

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

A consequence of this last factorization is the fact that

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

9 A left inverse

We now seek a left inverse [1] for the array (1 + x + x^{3} − x^{4}, x^{2}). To this end we let t = \sqrt{x}. Then

[x^{n}]\frac{\sqrt{x}^{k}}{1 + \sqrt{x} + \sqrt{x}^{3} − \sqrt{x}^{4}} = [t^{2n}]\frac{t^{k}}{1 + t + t^{3} − t^{4}}
= [t^{2n−k}]\frac{1}{1 + t + t^{3} − t^{4}}
= [t^{2n−k}] ∑_{j=0}^{∞} u_{j}x^{j}
= u_{2n−k}

where

u_{n} = (−1)^{n}F (⌊\frac{n + 2}{2}⌋)F (⌊\frac{n + 3}{2}⌋).

We deduce from this that

b(n; r) = ∑_{k=0}^{2n}(−1)^{k}F (⌊\frac{2n − k + 2}{2}⌋)F (⌊\frac{2n − k + 3}{2}⌋) ∑_{j=0}^{⌊ \frac{k}{2} ⌋} \binom{k − j}{j}r^{⌊ \frac{k−2j}{2} ⌋}  (28)
= ∑_{k=0}^{2n}(−1)^{k}F (n + 1 − ⌊\frac{k}{2}⌋)F (n + 1 − mod(k, 2) − ⌊\frac{k}{2}⌋)a(k; r).  (29)

An alternative expression is given by

b(n; r) = ∑_{k=0}^{2n} ∑_{j=0}^{\frac{2n−k}{3}} ∑_{m=0}^{j} \binom{2n − k − 2j − m}{j}\binom{j}{m}a(k; r).  (30)

In matrix terms, we have, taking a(n; 2) (\underline{A002530}), for example,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 … \\ 1 & −1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 … \\ 4 & −2 & 1 & −1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 … \\ 9 & −6 & 4 & −2 & 1 & −1 & 1 & 0 & 0 & 0 & 0 … \\ 25 & −15 & 9 & −6 & 4 & −2 & 1 & −1 & 1 & 0 & 0 … \\ 64 & −40 & 25 & −15 & 9 & −6 & 4 & −2 & 1 & −1 & 1 … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 1 3 4 11 15 41 56 153 209 571 ⋮ ) = ( 1 3 12 44 165 615 ⋮ ) .

10 The matrix (\frac{1−x}{1−x^{4}}, \frac{x}{1+x^{2}}) and its inverse

We recall that

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

We have

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

where the last matrix is closely linked to the Chebyshev polynomials of the second kind. The matrix (\frac{1−x}{1−x^{4}} , \frac{x}{1+x^{2}} ) is \underline{A165620}. We let T_{n,k} denote the general element of (\frac{1−x}{1−x^{4}} , \frac{x}{1+x^{2}} ). The general term of (\frac{1}{1+x}, x) is [k ≤ n](−1)^{n−k} while that of (\frac{1}{1+x^{2}} , \frac{x}{1+x^{2}} ) is given by

(−1)^{\frac{n−k}{2}} \frac{(1 + (−1)^{n−k}}{2} \binom{\frac{n+k}{2}}{k}.

Thus we have

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

We can then express b(n; r) as

b(n; r) = ∑_{k=0}^{n} T_{n,k}(r + 2)^{k}

= ∑_{k=0}^{n} T_{n,k} ∑_{j=0}^{k} \binom{k}{j}r^{j}2^{k−j}

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

This could also have been deduced from the fact that

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

The row sums of (\frac{1−x}{1−x^{4}} , \frac{x}{1+x^{2}} ) have g.f. \frac{1}{1+x^{3}} while the diagonal sums are the sequence (−1)^{n}. The inverse of this matrix is given by

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

This matrix (\underline{A165621}) begins

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

where the first column is the sequence

1, 1, 1, 2, 2, 5, 5, 14, 14, 42, …

of doubled Catalan numbers, which has moment representation

\frac{1}{2π} ∫_{−2}^{2} x^{n}(1 + x)\sqrt{4 − x^{2}}dx

and Hankel transform [3]

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

A number of interesting observations may be made about this matrix. Since g(x) = c(x^{2}), the A-sequence of this matrix has generating function A(y) = 1 + y^{2}. This then implies that

M_{n+1,k+1} = M_{n,k} + M_{n,k+2}.

The row sums of this matrix are the central binomial coefficients \binom{n+1}{⌊ \frac{n+1}{2} ⌋}. The diagonal sums are \underline{A026008}. The transform of the sequence 1, 0, 1, 0, 1, 0, … by this matrix is \binom{n}{⌊ \frac{n}{2} ⌋}, \underline{A001405}. The transform of (−1)^{n} is the aerated Catalan numbers 1, 0, 1, 0, 2, 0, …, while the transform of (−2)^{n} is a sequence whose Hankel transform is F (2n + 1). In general, the transform of the sequence with general term r^{n} will have Hankel transform with g.f. \frac{1−x}{1+(r−1)x+x^{2}} and general term

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

It is interesting to take the Hankel transform of the columns of this matrix. We obtain a matrix which begins

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

(where we have multiplied the columns by (−1)^{\binom{k+1}{2}}).

11 Appendix

In this section, we indicate a proof that the general term of the generalized Riordan array

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

is given by

\binom{⌊\frac{n+2k+1}{2}⌋}{⌊\frac{n−2k}{2}⌋}.

We note first that

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

Now the Riordan array

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

which is the unsigned version of \underline{A053122}, has general term

\binom{n + k + 1}{2k + 1}.

Thus the matrix

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

which represents an aeration of the matrix with general term \binom{n+k+1}{2k+1}, has general term

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

Considering now the generalized Riordan matrix

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

is to effect the transformation n → n − k in the above formula. We thus obtain that the general element of the generalized Riordan array

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

is given by

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

Thus the general term of

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

is given by the sum

\binom{\frac{n}{2} + k + 1}{2k + 1}\frac{1 + (−1)^{n}}{2} + \binom{\frac{n−1}{2} + k + 1}{2k + 1}\frac{1 + (−1)^{n−1}}{2} − \binom{\frac{n−2}{2} + k + 1}{2k + 1}\frac{1 + (−1)^{n−2}}{2}

or

\binom{\frac{n}{2} + k + 1}{2k + 1}\frac{1 + (−1)^{n}}{2} + \binom{\frac{n}{2} + k + \frac{1}{2}}{2k + 1}\frac{1 − (−1)^{n}}{2} − \binom{\frac{n}{2} + k}{2k + 1}\frac{1 + (−1)^{n}}{2}

which simplifies to

\frac{2(2k + 1)}{n − 2k}\binom{\frac{n}{2} + k + 1}{2k + 1}\frac{1 + (−1)^{n}}{2} + \binom{\frac{n}{2} + k + \frac{1}{2}}{2k + 1}\frac{1 − (−1)^{n}}{2} .

By considering alternately the cases n = 2m and n = 2m + 1 we can establish that this last term coincides with

\binom{⌊\frac{n+2k+1}{2}⌋}{⌊\frac{n−2k}{2}⌋}.

12 Acknowledgements

The author would like to thank the anonymous referees for their cogent suggestions which have led to the current expanded and hopefully clearer paper. In particular, the author acknowledges the input of one referee in alerting us to the use of the method of coefficients used in the proofs of Theorems 5 and 20. Acknowledgements are due also to Richard Guy, whose observations initiated this study.

References

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

[2] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays,

   http://arxiv.org/abs/math/0702638v1, February 22 2007.

[3] J. W. Layman, The Hankel Transform and Some of Its Properties, Journal of Integer Sequences, 4, Article 01.1.5, 2001.

[4] T. Mansour, A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 7 (1) (2000) #R17.

[5] D. Merlini, R. Sprugnoli and M. C. Verri, The Method of Coefficients, Amer. Math. Monthly, 114 (2007), pp. 40–57.

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

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

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

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices of the AMS, 50 (2003), pp. 912–915.

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

[10] E. Weisstein, Morgan-Voyce Polynomials, from MathWorld–A Wolfram Web Resource.

   http://mathworld.wolfram.com/Morgan-VoycePolynomials.html, 2009

2000 Mathematics Subject Classification: Primary 11B83; Secondary 11A55, 11B37, 11Y55, 33C45. Keywords: Integer sequence, linear recurrence, Riordan arrays, Chebyshev polynomials, continued fraction.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A001045}, \underline{A001405}, \underline{A001654}, \underline{A002530}, \underline{A008619}, \underline{A026008}, \underline{A041011}, \underline{A049310}, \underline{A053122}, \underline{A078812}, \underline{A084158}, \underline{A085478}, \underline{A099025}, \underline{A109437}, \underline{A136211}, \underline{A152119}, \underline{A157329}, \underline{A157335}, \underline{A158909}, \underline{A165620}, and \underline{A165621}.)

Received February 27 2009; revised versions received March 30 2009; June 8 2009; December 3 2009. Published in Journal of Integer Sequences, December 3 2009.

Return to Journal of Integer Sequences home page.