Matrix Transformations of Integer Sequences

Clark Kimberling Department of Mathematics University of Evansville 1800 Lincoln Avenue Evansville, IN 47722 ck6@evansville.edu

Abstract: The integer sequences with first term 1 comprise a group G under convolution, namely, the Appell group, and the lower triangular infinite integer matrices with all diagonal entries 1 comprise a group 𝔾 under matrix multiplication. If A ∈ G and M ∈ 𝔾, then MA ∈ G. The groups G and 𝔾 and various subgroups are discussed. These include the group 𝔾^{(1)} of matrices whose columns are identical except for initial zeros, and also the group 𝔾^{(2)} of matrices in which the odd-numbered columns are identical except for initial zeros and the same is true for even-numbered columns. Conditions are determined for the product of two matrices in 𝔾^{(m)} to be in 𝔾^{(1)}. Conditions are also determined for two matrices in 𝔾^{(2)} to commute.

1 Introduction

Let G be the set of integer sequences (a_{1}, a_{2}, a_{3}, …) for which a_{1} = 1. The notations A = (a_{1}, a_{2}, a_{3}, …), B = (b_{1}, b_{2}, b_{3}, …), C = (c_{1}, c_{2}, c_{3}, …) will always refer to elements of G. The finite sequence (a_{1}, a_{2}, a_{3}, …, a_{n}) will be denoted by A_{n}, and likewise for B_{n} and C_{n}. Let ⋆ denote convolution; i.e., if C = A ⋆ B, then

c_{n} = ∑_{k=1}^{n} a_{k}b_{n−k+1},

which we shall sometimes write as A_{n} ⊛ B_{n}, so that A ⋆ B is the sequence having A_{n} ⊛ B_{n} as nth term. Formally,

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

In particular, if c_{1} = 1 and c_{k} = 0 for k ≥ 2, then the sequence B has generating function 1/(a_{1} + a_{2}x + a_{3}x^{2} + ⋯), and A and B are a pair of convolutory inverses.

Let G_{n} denote the group of finite sequences A_{n} under ⋆; the identity is I_{n} = (1, 0, 0, …, 0), and A_{n}^{−1} is the sequence B_{n} given inductively by b_{1} = 1 and

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

for n ≥ 2. The algebraic system (G, ⋆) is a commutative group known as the Appell subgroup of the Riordan group. Its elements, the Appell sequences, are special cases of the Sheffler sequences, which play a leading role in the umbral calculus [2, Chapter 4]; however, the umbral developments are not used in this paper. In G, the identity and A^{−1} are the limits of I_{n} and A_{n}^{−1}. (Here, limits are of the combinatorial kind: suppose j_{1}, j_{2}, j_{3}, … is an unbounded nondecreasing sequence of positive integers and {a_{i,j}} is a sequence of sequences such for each i,

(a_{k,1}, a_{k,2}, a_{k,3}, …, a_{k,j_{i}}) = (a_{i,1}, a_{i,2}, a_{i,3}, …, a_{i,j_{i}})

for every k > i. Then

lim_{i→∞}(a_{i,1}, a_{i,2}, a_{i,3}, …)

is defined as the sequence (a_{1}, a_{2}, a_{3}, …) such that for every n there exists i_{0} such that if i > i_{0}, then

(a_{1}, a_{2}, a_{3}, …, a_{n}) = (a_{i,1}, a_{i,2}, a_{i,3}, …, a_{i,n}).)

The study of the group (G, ⋆), we shall soon see, is essentially that of a certain group of matrices. However, we shall consider first a more general group of matrices.

For any positive integer n, let 𝔾_{n} be the set of lower triangular n × n integer matrices with all diagonal entries 1, and let · denote matrix multiplication. Then (𝔾_{n}, ·) is a noncommutative group. Now let 𝔾 denote the set of lower triangular infinite integer matrices with all diagonal entries 1. In such a matrix, every column, excluding the zeros above the diagonal, is an element of G, and (𝔾, ·) is a noncommutative group. Properties of matrices in 𝔾 arise via limits of those of matrices in 𝔾_{n}. For example, if M = (m_{ij}) ∈ 𝔾, then the matrix M_{n} := (m_{ij}), where 1 ≤ i ≤ n and 1 ≤ j ≤ n, is an element of 𝔾_{n}, and

M^{−1} = lim_{n→∞} M_{n}^{−1}.

It is easy to check that if A ∈ G and M ∈ 𝔾, then M · A ∈ G; here A is regarded as an infinite column vector.

Among subgroups of 𝔾 is the Riordan group (in the case that the coefficients are all integers) introduced in [3]. Although the Riordan group will not be further discussed in this paper, the reader may wish to consult the references listed at A053121 (the Catalan triangle) in [4].

Suppose T = (t_{1}, t_{2}, t_{3}, …) ∈ G. Let 𝕋 be the matrix in 𝔾 whose ith row is

t_{i}, t_{i−1}, …, t_{1}, 0, 0 …,

so that the first column of 𝕋 is T, and each subsequent column contains T as a subsequence. Let 𝔾^{(1)} be the set of all such matrices 𝕋. If 𝕋 and 𝕌 in 𝔾^{(1)} have first columns T and U, respectively, then the first column of 𝕋 · 𝕌 is the sequence T ⋆ U, and 𝕋 · 𝕌 ∈ 𝔾^{(1)}. Clearly, (𝔾^{(1)}, ·) is isomorphic to (G, ⋆). Matrices in 𝔾^{(1)} will be called sequential matrices.

One more property of the group 𝔾, with easy and omitted proof, will be useful: if M = (m_{ij}) ∈ 𝔾 and f(M) := ((−1)^{i+j}m_{ij}), then

(f(M))^{−1} = f(M^{−1}).  (2)

2 The Appell group (G, ⋆)

The first theorem in this section concerns the convolutory inverse of a linear recurrence sequence of order m ≥ 2.

Theorem 1. Suppose m ≥ 2, and a_{1} = 1, a_{2}, …, a_{m} are initial values of an mth order recurrence sequence given by

a_{n} = u_{1}a_{n−1} + u_{2}a_{n−2} + ⋯ + u_{m}a_{n−m} + r_{n−m}  (3)

for n ≥ m + 1, where u_{1}, u_{2}, …, u_{m} and r_{1}, r_{2}, r_{3}, … are integers and u_{m} ≠ 0. Then the convolutory inverse, B, of A, is a sequence

(1, b_{2}, …, b_{m}, b_{m+1}, b_{m+2}, …)

for which the subsequence (b_{m+2}, b_{m+3}, …) satisfies

b_{n} = ∑_{k=1}^{m−1} b_{n−k}c_{k} − B_{n−m} ⊛ R_{n−m},

where

c_{k} = −a_{k+1} + ∑_{j=1}^{k} u_{j}a_{k+1−j}

for n ≥ m + 2.

Proof: By (1), b_{1} = a_{1} = 1. Also, b_{2} = −a_{2}, and

b_{n} = −a_{n}b_{1} − a_{n−1}b_{2} − ⋯ − a_{2}b_{n−1}

for n ≥ 3. For the rest of this proof, assume that n ≥ m + 2, and for later convenience, let

s_{n} = −a_{n}b_{1} − a_{n−1}b_{2} − ⋯ − a_{m+2}b_{n−m−1}.

For n ≥ m + 2 (but not generally for n = m + 1), the recurrence (1) gives

∑_{k=1}^{m} u_{k}b_{n−k} = − ∑_{j=1}^{n−m−1} b_{j} ∑_{k=1}^{m} u_{k}a_{n−k−j+1} − U,

where

U = ∑_{k=1}^{m−1} u_{k} ∑_{j=2}^{m−k+1} a_{j}b_{n−k−j+1}.

Then

∑_{k=1}^{m} u_{k}b_{n−k} = − ∑_{j=1}^{n−m−1} b_{j}(a_{n+1−j} − r_{n+1−j−m}) − U

= s_{n} + ∑_{j=1}^{n−m−1} b_{j}r_{n+1−j−m} − U

= b_{n} + ∑_{j=2}^{m+1} a_{j}b_{n+1−j} + ∑_{j=1}^{n−m−1} b_{j}r_{n+1−j−m} − U,

so that

b_{n} = ∑_{k=1}^{m} u_{k}b_{n−k} − ∑_{j=2}^{m+1} a_{j}b_{n+1−j} − ∑_{j=1}^{n−m−1} b_{j}r_{n+1−j−m} + U.  (4)

Now put n = m + 1 into (3) and substitute in (4) for a_{m+1}. The resulting coefficient of b_{n−m} is −r_{1}, and (4) simplifies to

b_{n} = ∑_{k=1}^{m−1} u_{k}b_{n−k} − ∑_{j=2}^{m} a_{j}b_{n+1−j} + ∑_{k=1}^{m−2} u_{k} ∑_{j=2}^{m−k} a_{j}b_{n−k−j+1} − ∑_{j=1}^{n−m} b_{j}r_{n+1−j−m}

= ∑_{k=1}^{m−1} b_{n−k}(−a_{k+1} + ∑_{j=1}^{k} u_{j}a_{k+1−j}) − ∑_{j=1}^{n−m} b_{j}r_{n+1−j−m.}  ■

Corollary 1. If the recurrence for A in (3) is homogeneous of order m ≥ 2, then the recurrence for the sequence (b_{4}, b_{5}, b_{6}, …) is of order m − 1. If m = 2, then the convolutory inverse of A is the sequence

(b_{1}, b_{2}, b_{3}, …) = (1, − a_{2}, f, (u_{1} − a_{2})f, (u_{1} − a_{2})^{2}f, (u_{1} − a_{2})^{3}f, …),

where f = a_{2}^{2} − a_{3}.

Proof: Homogeneity of a means that r_{n} = 0 for n ≥ 1, so that b_{n} = ∑_{k=1}^{m−1} c_{k}b_{n−k} for n ≥ m + 2. ■

Example 1. The Fibonacci sequence, A = (1, 1, 2, 3, 5, 8, …), has inverse (1, −1, −1, 0, 0, 0, 0, 0, …).

Example 2. The Lucas sequence, A = (1, 3, 4, 7, 11, 18, …), has inverse, (1, −3, 5, −10, 20, −40, 80, …), recurrent with order 1 beginning at the third term.

Example 3. Let A be the 2nd-order nonhomogeneous sequence given by a_{1} = 1, a_{2} = 1, and a_{n} = a_{n−1} + a_{n−2} + n − 2 for n ≥ 3. The inverse of A is the sequence B = (1, −1, −2, −1, 1, 4, 6, 4, −4, −11, …) given for n ≥ 4 by

b_{n} = −B_{n−2} ⊛ R_{n−2} = −(b_{1}, b_{2}, ⋯, b_{n−2}) ⋆ (1, 2, 3, …, n − 2).

Example 4. Suppose that A and C are sequences in G. Since G is a group, there exists B in G such that A = B ⋆ C. For example, if A and C are the Fibonacci and Lucas sequences of Examples 1 and 2, then

B = A ⋆ C^{−1} = (1, −2, 4, −8, 16, …),

a 1st-order sequence.

Theorem 2. Let B = (1, b_{2}, b_{3}, …) be the convolutory inverse of A = (1, a_{2}, a_{3}, …), and let Â = (1, −a_{2}, a_{3}, −a_{4}, a_{5}, −a_{6}, …). Then the convolutory inverse of Â is the sequence B̂ = (1, −b_{2}, b_{3}, −b_{4}, b_{5}, −b_{6}, …).

Proof: Apply (2) to the subgroup 𝔾^{(1)} of sequential matrices. ■

Example 5. Let A be the sequence given by a_{n} = ⌊nτ⌋, where τ = (1 + \sqrt{5})/2. Then

A = (1, 3, 4, 6, 8, 9, 11, 12, …) and A^{−1} = (1, −3, 5, −9, 17, −30, 52, −90, …).

Let A be the sequence given by a_{n} = (−1)^{n−1}⌊nτ⌋. Then

A = (1, −3, 4, −6, 8, −9, 11, −12, …) and A^{−1} = (1, 3, 5, 9, 17, 30, 52, 90, …).

Example 6. Let A be the Catalan sequence, given by a_{n} = \frac{1}{n} ( \begin{matrix}2n − 2 \\ n − 1 \end{matrix} ) . Then

A = (1, 1, 2, 5, 14, 42, 132, 429, 1430, …)
A^{−1} = (1, −1, −1, −2, −5, −14, −42, −132, …).

Example 7. Let A be the sequence of central binomial coefficients, given by a_{n} =

( \begin{matrix}2n − 2 \\ n − 1 \end{matrix} ) , Then

A = (1, 2, 6, 20, 70, 252, 924, …) and A^{−1} = (1, −2, −2, −4, −10, −28, −84, −264, …),

with obvious connections to the Catalan sequence.

Certain operations on sequences in G are easily expressed in terms of convolution. Two of these operations are given as follows. Suppose x is an integer, and A = (1, a_{2}, a_{3}, …) is a sequence in G, with inverse B = (1, b_{2}, b_{3}, …). Then

(1, xa_{2}, xa_{3}, xa_{4,} …) = (1, (1 − x)b_{2}, (1 − x)b_{3}, (1 − x)b_{4}, …) ⋆ A

and

(1, x, a_{2}, a_{3}, …) = (1, x + b_{2}, (x − 1)b_{2} + b_{3}, (x − 1)b_{3} + b_{4}, …) ⋆ A.

Stated in terms of power series

a(t) = 1 + a_{2}t + a_{3}t^{2} + ⋯ and 1/a(t) = b(t) = 1 + b_{2}t + b_{3}t^{2} + ⋯,

the two operations correspond to the identities

xa(t) + 1 − x = [(1 − x)b(t) + x]a(t);
ta(t) + 1 + (x − 1)t = {b(t) + [(x − 1)b(t) + 1]t}a(t).

3 The group (𝔾^{(m)}, ·)

Recall that the set 𝔾 consists of the lower triangular infinite integer matrices with all diagonal entries 1. Define ′ on 𝔾 as follows: if A ∈ 𝔾, then A′ is the matrix that remains when row 1 and column 1 of A are removed. Clearly A′ ∈ 𝔾. Define

A^{(0)} = A, A^{(n)} = (A^{(n−1)})′

for n ≥ 1. Let

𝔾^{(m)} = {A ∈ 𝔾 : A^{(m)} = A}

for m ≥ 0. Note that (𝔾^{(1)}, ·) is the group of sequential matrices introduced in Section 1, and 𝔾^{(m)} ⊂ 𝔾^{(d)} if and only if d|m.

Theorem 3. (G^{(m)}, ·) is a group for m ≥ 0.

Proof: (𝔾^{(0)}, ·) is the group (𝔾, ·). For m ≥ 1, first note that (AB)′ = A′B′, so that, inductively, (AB)^{(q)} = A^{(q)}B^{(q)} for all q ≥ 1. In particular, if A and B are in 𝔾^{(m)}, then

(AB)^{(m)} = A^{(m)}B^{(m)} = AB,

so that AB ∈ 𝔾^{(m)}. Moreover,

(A^{−1})^{(m)} = (A^{(m)})^{−1} = A^{−1},

so that A^{−1} ∈ 𝔾^{(m)}. ■

4 The group (𝔾^{(2)}, ·)

Suppose that A, B, C, D are sequences in G. Let ⟨A; B⟩ denote the matrix in 𝔾^{(2)} whose first column is A = (a_{1}, a_{2}, …) and whose second column is (0, b_{1}, b_{2}, …), where a_{1} = b_{1} = 1. We shall see that the product ⟨A; B⟩ · ⟨C; D⟩ is given by certain “mixed convolutions.” Write ⟨A; B⟩ · ⟨C; D⟩ as ⟨U; V ⟩ . Then

u_{n} = \{ \begin{matrix}(a_{1}, b_{2}, a_{3}, …, b_{n−1}, a_{n}) ⋆ (c_{1}, c_{2}, …, c_{n}), & if n is odd; \\ (b_{1}, a_{2}, b_{3}, …, b_{n−1}, a_{n}) ⋆ (c_{1}, c_{2}, …, c_{n}), & if n is even; \end{matrix}

v_{n} = \{ \begin{matrix}(b_{1}, a_{2}, b_{3}, …, a_{n−1}, b_{n}) ⋆ (d_{1}, d_{2}, …, d_{n}), & if n is odd; \\ (a_{1}, b_{2}, a_{3}, …, a_{n−1}, b_{n}) ⋆ (d_{1}, d_{2}, …, d_{n}), & if n is even. \end{matrix}

In particular ⟨A; B⟩ · ⟨B; A⟩ is the sequential matrix of the sequence A ⋆ B.

Recursive formulas for columns of ⟨A; B⟩^{−1} can also be given: write ⟨A; B⟩^{−1} as ⟨X; Y ⟩ , so that ⟨A; B⟩ · ⟨X; Y ⟩ is the identity matrix. Each nondiagonal entry of ⟨A; B⟩ · ⟨X; Y ⟩ is zero, so that, solving inductively for x_{1}, x_{2}, x_{3}, … and y_{1}, y_{2}, y_{3}, … gives

x_{n} = \{ \begin{matrix}−a_{n} − b_{n−1}x_{2} − a_{n−2}x_{3} − ⋯ − b_{2}x_{n−1}, & if n is odd; \\ −a_{n} − b_{n−1}x_{2} − a_{n−2}x_{3} − ⋯ − a_{2}x_{n−1}, & if n is even; \end{matrix}  (5)

y_{n} = \{ \begin{matrix}−b_{n} − a_{n−1}y_{2} − b_{n−2}y_{3} − ⋯ − a_{2}y_{n−1}, & if n is odd; \\ −b_{n} − a_{n−1}y_{2} − b_{n−2}y_{3} − ⋯ − b_{2}y_{n−1}, & if n is even. \end{matrix}  (6)

Example 8. Example 6 shows that the Catalan sequence satisfies the equation

(1, a_{2}, a_{3}, …)^{−1} = (1, −1, −a_{2}, −a_{3}, …),

which we abbreviate as A^{−1} = (1, −A). It is natural to ask whether there are sequences A and B for which

⟨A; B⟩^{−1} = ⟨1, −A; B⟩ .  (7)

This problem is solved as follows. Write the first and second columns of ⟨1, −A; B⟩ as (1, x_{2}, x_{3}, …) and (0, 1, y_{2}, y_{3}, …), respectively. Equation (7) implies x_{n} = −a_{n−1} and y_{n} = b_{n} for n ≥ 2. Thus, b_{2} = y_{2}, but also, by (6), y_{2} = −b_{2}, so that b_{2} = 0. Inductively,

(6) and (7) imply b_{n} = 0 for all n ≥ 3, so that B is the convolutory identity sequence: B = (1, 0, 0, 0, …). Using this fact together with (5) gives

x_{n} = \{ \begin{matrix}−a_{n} − a_{n−2}x_{3} − a_{n−4}x_{5} − ⋯ − a_{2}x_{n−1}, & if n is even; \\ −a_{n} − a_{n−2}x_{3} − a_{n−4}x_{5} − ⋯ − a_{3}x_{n−2}, & if n is odd; \end{matrix}

so that, substituting x_{k} = −a_{k−1}, we have a recurrence for A:

a_{n} = \{ \begin{matrix}a_{n−1} + a_{n−2}a_{2} + a_{n−4}a_{4} + ⋯ + a_{2}a_{n−2} & if n is even; \\ a_{n−1} + a_{n−2}a_{2} + a_{n−4}a_{4} + ⋯ + a_{3}a_{n−3} & if n is odd; \end{matrix}

with intial values a_{1} = 1, a_{2} = 1. This sequence, listed as A047749 in [4], is given by

a_{n} = \{ \begin{matrix}\frac{1}{2m+1} ( \begin{matrix}3m \\ m \end{matrix} ), & if n = 2m; \\ \frac{1}{2m+1} ( \begin{matrix}3m + 1 \\ m + 1 \end{matrix} ), & if n = 2m + 1. \end{matrix}

Example 9. Let a_{n} = 1 and b_{n} = F_{n} for n ≥ 1, where F_{n} denotes the Fibonacci sequence in Example 1. Let C be the sequence given by c_{1} = 1, c_{2} = −1, c_{3} = 0, c_{4} = 1, and c_{n} = 2^{⌊(n−5)/2⌋} for n ≥ 5. Let D be the sequence given by d_{1} = 1, d_{2} = −1, d_{3} = −1, and d_{n} = −c_{n+1} for n ≥ d_{4}. Then ⟨A; B⟩^{−1} = ⟨C; D⟩ .

Theorem 4. If any three of four sequences A, B, C, D in G are given, then the fourth sequence is uniquely determined by the condition that ⟨A; B⟩ · ⟨C; D⟩ be a sequential matrix.

Proof: The requirement that ⟨A; B⟩ · ⟨C; D⟩ be a sequential matrix is equivalent to an infinite system of equations, beginning with

d_{1} = 1
b_{2} + d_{2} = a_{2} + c_{2}
b_{3} + a_{2}d_{2} + d_{3} = a_{3} + b_{2}c_{2} + c_{3}.

For n ≥ 3, the system can be expressed as follows:

b_{n} + a_{n−1}d_{2} + b_{n−2}d_{3} + ⋯ + h_{2}d_{n−1} + d_{n}
= a_{n} + b_{n−1}c_{2} + a_{n−2}c_{3} + ⋯ + h′_{2}c_{n−1} + c_{n},  (8)

where h_{2} = a_{2} if n is odd, h_{2} = b_{2} if n is even; and h′_{2} = b_{2} if n is odd, h′_{2} = a_{2} if n is even.

Equations (8) show that each of the four sequences is determined by the other three. ■

Example 10. By (8), D is determined by A, B, C in accord with the recurrence

d_{n} = a_{n} + c_{2}b_{n−1} + c_{3}a_{n−2} + c_{4}b_{n−3} + ⋯ + c_{n−1}h′_{2} + c_{n}
−b_{n} − d_{2}a_{n−1} − d_{3}b_{n−2} − d_{4}a_{n−3} ⋯ − d_{n−1}h_{2}.  (9)

Suppose a_{n} = b_{n} = c_{n−2} = 0 for n ≥ 3. Then by (9),

d_{n} = \{ \begin{matrix}−b_{2}d_{n−1} − a_{3}d_{n−2}, & if n is even; \\ −a_{2}d_{n−1} − b_{3}d_{n−2}, & if n is odd; \end{matrix}

for n ≥ 4, with d_{1} = 1, d_{2} = a_{2} − b_{2}, d_{3} = a_{3} − a_{2}d_{2} − b_{3}d_{1}. If (a_{1}, a_{2}, a_{3}) = (1, −1, −1) and (b_{1}, b_{2}, b_{3}) = (1, −2, −1) and c_{1} = 1, then

D = (1, 1, 1, 3, 4, 11, 15, 41, 56, 153, …),

which, except for the initial 1, is the sequence of denominators of the convergents to \sqrt{3}, indexed in [4] as A002530. In this example, ⟨A; B⟩ · ⟨C; D⟩ is the sequential matrix with first three terms 1, −1, −1 and all others zero.

Theorem 5. If A, B, C in G are given and |a_{2}| = 1, then there exists a unique sequence D in G such that ⟨A; B⟩ · ⟨C; D⟩ = ⟨C; D⟩ · ⟨A; B⟩.

Proof: Write ⟨A; B⟩ · ⟨C; D⟩ as (s_{ij}) and ⟨C; D⟩ · ⟨A; B⟩ as (t_{ij}). Equating s_{n+1,1} and t_{n+1,1} and solving for d_{n} give

d_{n} = \frac{1}{a_{2}} (u_{n} − v_{n})  (10)

for n ≥ 3, where

u_{n} = \{ \begin{matrix}c_{2}b_{n} + c_{3}a_{n−1} + c_{4}b_{n−2} + ⋯ + c_{n}a_{2}, & if n is odd; \\ c_{2}b_{n} + c_{3}a_{n−1} + c_{4}b_{n−2} + ⋯ + c_{n}b_{2}, & if n is even; \end{matrix}
v_{n} = \{ \begin{matrix}a_{3}c_{n−1} + a_{4}d_{n−2} + ⋯ + a_{n}c_{2}, & if n is odd; \\ a_{3}c_{n−1} + a_{4}d_{n−2} + ⋯ + a_{n}d_{2}, & if n is even; \end{matrix}

with d_{1} = 1, d_{2} = b_{2}c_{2}/a_{2}. A sequence D is now determined by (10); we shall refer to the foregoing as part 1.

It is necessary to check that the equations s_{n+1,2} = t_{n+1,2} implied by

⟨A; B⟩ · ⟨C; D⟩ = ⟨C; D⟩ · ⟨A; B⟩

do not impose requirements on the sequence D that are not implied by those already shown to determine D. In fact, the equations s_{n+1,2} = t_{n+1,2} with initial value d_{1} = 1 determine exactly the same sequence D. To see that this is so, consider the mapping ⟨A; B⟩′ = ⟨B; A⟩ . It is easy to prove the following lemma:

(⟨A; B⟩ · ⟨C; D⟩)′ = ⟨B; A⟩ · ⟨D; C⟩ .

By part 1 applied to ⟨B; A⟩ · ⟨D; C⟩ and ⟨D; C⟩ · ⟨B; A⟩ , the first column of ⟨B; A⟩ · ⟨D; C⟩ equals the first column of ⟨D; C⟩ · ⟨B; A⟩ . Therefore, by the lemma, the second column of ⟨A; B⟩·⟨C; D⟩ equals the second column of ⟨C; D⟩·⟨A; B⟩ , which is to say that the equations s_{n+1,2} = t_{n+1,2} hold. ■

Example 11. Let a_{1} = 1, a_{2} = 1, and a_{n} = 0 for n ≥ 3. Let B be the Fibonacci sequence. Let C = (1, 1, 0, 1, 0, 0, …), with c_{n} = 0 for n ≥ 5. Then D is given by d_{1} = 1, d_{2} = 1, d_{3} = 2, and d_{n} = L_{n−1} for n ≥ 4, where (L_{n}) is the Lucas sequence, as in Example 1. Writing ⟨A; B⟩ · ⟨C; D⟩ as ⟨U, V ⟩ , we have ⟨U, V ⟩ = ⟨C; D⟩ · ⟨A; B⟩, where U = (1, 2, 1, 3, 4, 7, 11, 18, …) and V = (1, 2, 5, 9, 20, 32, 66, 105, 207, …).

5 Generalization of Theorem 4

It is natural to ask what sort of generalization Theorem 4 has for m ≥ 3. The notation ⟨A; B⟩ used for matrices in 𝔾^{(2)} is now generalized in the obvious manner to ⟨A_{1}, A_{2}, …, A_{m}⟩ in 𝔾^{(m)}, where A_{i} is a sequence (a_{i1}, a_{i2}, …) having a_{i1} = 1, for i = 1, 2, …, m.

Theorem 4A. Suppose A_{1}, A_{2}, …, A_{m} and B_{i} for some i satisfying 1 ≤ i ≤ m are given. Then sequences B_{j} for j ≠ i are uniquely determined by the condition that ⟨A_{1}, A_{2}, …, A_{m}⟩· ⟨B_{1}, B_{2}, …, B_{m}⟩ be a sequential matrix. Conversely, suppose B_{1}, B_{2}, …, B_{m} and A_{i} for some i satisfying 1 ≤ i ≤ m are given. Then sequences A_{j} for j ≠ i are uniquely determined by the condition that ⟨A_{1}, A_{2}, …, A_{m}⟩ · ⟨B_{1}, B_{2}, …, B_{m}⟩ be a sequential matrix. Proof: Let U = AB. For given A, each column of B uniquely determines the corresponding column of U, and each column of U determines the corresponding column of B. Thus, under the hypothesis that a particular column B_{i} of B is given, the equation U = AB determines the corresponding column of U. Consequently, as U is a sequential matrix, every column of U is determined, and this implies that every column of B is determined.

For the converse, suppose B, together with just one column A_{i} of A, are given, and that the product U = AB is sequential. As a first induction step,

a_{21}b_{11} + a_{22}b_{21} = a_{32}b_{22} + a_{33}b_{32} = · · · .  (11)

As a_{i+1,i} is given, equations (11) show that a_{h+1,h} is determined for all h ≥ 1. Assume for arbitrary k ≥ 1 that a_{h+j,h} is determined for all j satisfying 1 ≤ j ≤ k, for all h ≥ 1. As U is sequential,

a_{k+1,1}b_{11} + a_{k+1,2}b_{21} + ⋯ + a_{k+1,k+1}b_{k+1,1}
= a_{k+2,2}b_{22} + a_{k+2,3}b_{32} + ⋯ + a_{k+2,k+2}b_{k+2,2}
= · · · .  (12)

As a_{k+i,i} is given, equations (12) and the induction hypothesis show that a_{k+h,h} is determined for all h ≥ 1. Thus, by induction, A is determined. ■

Theorem 4A shows that Theorem 4 extends to 𝔾^{(m)}. The method of proof of Theorem 4A clearly applies to 𝔾, so that Theorem 4A extends to 𝔾.

6 Transformations involving divisors

We return to the general group (𝔾, ·) for a discussion of several specific matrix transformations involving divisors of integers. The first is given by the left summatory matrix,

T (n, k) = \{ \begin{matrix}1, & if k|n; \\ 0, & otherwise. \end{matrix}

The inverse of T is the left Möbius transformation matrix. The matrices T and T^{−1} are indexed as A077049 and A077050 in [4], where transformations by T and T^{−1} of selected sequences in G are referenced. In general, if A is a sequence written as an infinite column vector, then

T · A = {∑_{k|n} a_{k}}  and  T^{−1} · A = {∑_{k|n} μ(k)a_{k}},

that is, the summatory sequence of A and the Möbius transform of A, respectively.

Next, define the left summing matrix S = {s(n, k)} and the left differencing matrix D = {d(n, k)} by

s(n, k) = \{ \begin{matrix}1, & if k ≤ n; \\ 0, & otherwise. \end{matrix}
d(n, k) = \{ \begin{matrix}(−1)^{n+k}, & if k = n or k = n − 1; \\ 0, & otherwise. \end{matrix}

Note that D = S^{−1}.

Example 12. Suppose that a sequence C = (1, c_{2}, c_{3}, …) in G is transformed to a sequence A = (1, a_{2}, a_{3}, …) by the sums a_{n} = ∑_{k=1}^{n} c_{k}⌊n/k⌋. In order to solve this system of equations, let U(n, k) = ⌊n/k⌋ for k ≥ 1, n ≥ 1. Then U = S · T, so that U^{−1} = T^{−1} · D, which means that

c_{n} = ∑_{d|n} μ(d)(a_{n/d} − a_{n/d−1}),

where a_{0} := 0. If a_{n} = 1 for every n ≥ 1, then c_{n} = μ(n). If a_{n} = n, then C is the convolutory

identity, (1, 0, 0, 0, …). If a_{n} = ( \begin{matrix}n + 1 \\ 2 \end{matrix} ) , then c_{n} = φ(n). If a_{n} = ( \begin{matrix}n + 2 \\ 3 \end{matrix} ) , then C is

the sequence indexed as A000741 in [4] and discussed in [1] in connection with compositions of integers with relatively prime summands.

References

[1] H. W. Gould, Binomial coefficients, the bracket function, and compositions with relatively prime summands, Fibonacci Quart. 2 (1964) 241–260.

[2] Steven Roman, The Umbral Calculus, Academic Press, New York, 1984.

[3] Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan, and Leon C. Woodson, The Riordan group, Disc. Appl. Math. 34 (1991) 229–239.

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

   http://www.research.att.com/~njas/sequences.

2000 Mathematics Subject Classification: Primary 11A25. Keywords: Appell sequence, convolution, Fibonacci sequence, linear recurrence, Riordan group, sequential matrix.

(Concerned with sequences \underline{A000045}, \underline{A000108} \underline{A000142} \underline{A000201} \underline{A000204} \underline{A000741} \underline{A000984} \underline{A002530} \underline{A047749} \underline{A077049} \underline{A077050} \underline{A077605} \underline{A077606}.)

Received November 13, 2002; revised versions received January 28, 2003; September 2, 2003. Published in Journal of Integer Sequences, September 8, 2003.

Return to Journal of Integer Sequences home page.