Impulse Response Sequences and Construction of Number Sequence Identities

Tian-Xiao He Department of Mathematics Illinois Wesleyan University Bloomington, IL 61702-2900 USA

                      the@iwu.edu

Abstract

In this paper, we investigate impulse response sequences over the integers by presenting their generating functions and expressions. We also establish some of the corresponding identities. In addition, we give the relationship between an impulse response sequence and all linear recurring sequences satisfying the same linear recurrence relation, which can be used to transfer the identities among different sequences. Finally, we discuss some applications of impulse response sequences to the structure of Stirling numbers of the second kind, the Wythoff array, and the Boustrophedon transform.

1 Introduction

Many number and polynomial sequences can be defined, characterized, evaluated, and classified by linear recurrence relations with certain orders. A number sequence {a_{n}} is called a sequence of order r if it satisfies the linear recurrence relation of order r

a_{n} = ∑_{j=1}^{r} p_{j}a_{n−j}, n ≥ r,  (1)

for some constants p_{j}, j = 1, 2, …, r, p_{r} ≠ 0, and initial conditions a_{j} (j = 0, 1, …, r − 1). Linear recurrence relations with constant coefficients are important in subjects including combinatorics, pseudo-random number generation, circuit design, and cryptography, and they have been studied extensively. To construct an explicit formula of the general term of a number sequence of order r, one may use a generating function, a characteristic equation, or a matrix method (See Comtet [4], Niven, Zuckerman, and Montgomery [12], Strang [15], Wilf [16], etc.) Let A_{r} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}. To study the structure of A_{r} with respect to E_{r}, we consider the impulse response sequence (or, IRS for abbreviation) in A_{r}, which is a particular sequence in A_{r} with initials a_{0} = a_{1} = ⋯ = a_{r−2} = 0 and a_{r−1} = 1. The study of impulse response sequences in a finite field has been considerably active in the theory of finite fields. A summary work on this subject can be found in Lidl and Niederreiter [10]. In this paper, we investigate the same concept in ℤ. If r = 2, the IRS in ℤ is the well known Lucas sequence. In this sense, an IRS of order r > 2 is an extension of a Lucas sequence in a high order setting.

In the next section, we will give the generating function and the expression of the IRS of A_{r} and find out the relationship between the IRS and other sequences in the set A_{r}. Several examples of IRS in sets A_{2} and A_{3} will be given in Section 3. The work shown in Sections 2 and 3 is partially motivated by Shiue and the author [8], which presented a method for the construction of general term expressions and identities for the linear recurring sequences of order r = 2 by using the reduction order method. However, the reduction method is too complicated for the linear recurring sequences of order r > 2, although our method can be applied readily to linear recurring sequences with arbitrary order by using their relationship with impulse response sequences. In Section 4, we shall give some applications of IRS in the discussion of the structure of Stirling numbers of the second kind, the Wythoff array, and the Boustrophedon transform.

2 Impulse response sequences

Among all the homogeneous linear recurring sequences satisfying rth order homogeneous linear recurrence relation (1) with a nonzero p_{r} and arbitrary initial conditions {a_{j}}_{j=0}^{r−1}, we define the impulse response sequence (IRS) with respect to E_{r} = {p_{j}}_{j=1}^{r} as the sequence with initial conditions a_{0} = a_{r−2} = 0 and a_{r−1} = 1. In particular, when r = 2, the homogeneous linear recurring sequences with respect to E_{2} = {p_{1}, p_{2}} satisfy

a_{n} = p_{1}a_{n−1} + p_{2}a_{n−2}, n ≥ 2,  (2)

with arbitrary initial conditions a_{0} and a_{1}, or, initial vector (a_{0}, a_{1}). If the initial vector (a_{0}, a_{1}) = (0, 1), the corresponding sequence generated by using (2) is the IRS with respect to E_{2}, is called the Lucas sequence. For instance, the Fibonacci sequence {F_{n}} is the IRS with respect to {1, 1}, the Pell number sequence {P_{n}} is the IRS with respect to {2, 1}, and the Jacobsthal number sequence {J_{n}} is the IRS with respect to {1, 2}.

In the following, we will present the structure of the linear recurring sequences defined by (1) using their characteristic polynomial. This structure provides a way to find the relationship between those sequences and the IRS.

Let A_{r} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}, and let F̃_{n}^{(r)} be the IRS of A_{r}, namely, F̃_{n}^{(r)} satisfies (1) with initial conditions F̃_{0}^{(r)} = ⋯ = F̃_{r−2}^{(r)} = 0 and F̃_{r−1}^{(r)} = 1.

Suppose {a_{n}} ∈ A_{r}. Let B = |p_{1}| + |p_{2}| + ⋯ + |p_{r}|, and for n ∈ ℕ_{0} let M_{n} = max{|a_{0}|, |a_{1}|, …, |a_{n}|}. Thus, for n ≥ r, M_{n} ≤ BM_{n−1}. By induction, |a_{n}| ≤ CB^{n} for some constant A and n = 0, 1, 2, …. A sequence satisfying a bound of this kind is called a sequence having at most exponential growth (see [12]). Therefore, the generating function ∑_{j≥0} a_{j}t^{j} of such sequence has a positive radius of convergence, 0 < c < 1/B. More precisely, if |t| ≤ c, then by comparison with the convergent geometric series ∑_{j≥0} CB^{j}c^{j}, the series ∑_{j≥0} a_{j}t^{j} converges absolutely. In the following, we always assume that {a_{n}} has at most exponential growth.

Proposition 1. Let {a_{n}} ∈ A_{r}, i.e., let {a_{n}} be the linear recurring sequence defined by (1). Then its generating function P_{r}(t) can be written as

P_{r}(t) = {a_{0} + ∑_{n=1}^{r−1} (a_{n} − ∑_{j=1}^{n} p_{j}a_{n−j}) t^{n}}/{1 − ∑_{j=1}^{r} p_{j}t^{j}}.  (3)

Hence, the generating function for the IRS with respect to {p_{j}} is

P̃_{r}(t) = \frac{t^{r−1}}{1 − ∑_{j=1}^{r} p_{j}t^{j}} .  (4)

Proof. Multiplying t^{n} on the both sides of (1) and summing from n = r to infinity yields

∑_{n≥r} a_{n}t^{n} = ∑_{n≥r} ∑_{j=1}^{r} p_{j}a_{n−j}t^{n} = ∑_{j=1}^{r} p_{j} ∑_{n≥r} a_{n−j}t^{n}

= ∑_{j=1}^{r−1} p_{j} (∑_{n≥j} a_{n−j}t^{n} − ∑_{n=j}^{r−1} a_{n−j}t^{n}) + p_{r} ∑_{n≥r} a_{n−r}t^{n}

= ∑_{j=1}^{r−1} p_{j} (t^{j} ∑_{n≥0} a_{n}t^{n} − ∑_{n=j}^{r−1} a_{n−j}t^{n}) + p_{r}t^{r} ∑_{n≥0} a_{n}t^{n}

Denote P_{r}(t) = ∑_{n≥0} a_{n}t^{n}. Then the equation of the leftmost and the rightmost sides can be written as

P_{r}(t) − ∑_{n=0}^{r−1} a_{n}t^{n} = P_{r}(t) ∑_{j=1}^{r−1} p_{j}t^{j} − ∑_{j=1}^{r−1} ∑_{n=j}^{r−1} p_{j}a_{n−j}t^{n} + p_{r}t^{r}P_{r}(t),

which implies

P_{r}(t) (1 − ∑_{j=1}^{r} p_{j}t^{j}) = ∑_{n=0}^{r−1} a_{n}t^{n} − ∑_{n=1}^{r−1} ∑_{j=1}^{n} p_{j}a_{n−j}t^{n}.

Therefore, (4) follows immediately. By substituting a_{0} = ⋯ = a_{r−2} = 0 and a_{r−1} = 1 into (3), we obtain (4).

We now give the explicit expression of F̃_{n}^{(r)} in terms of the zeros of the characteristic polynomial of recurrence relation shown in (1).

Theorem 2. Sequence {F̃_{n}^{(r)}}_{n} is the IRS with respect to {p_{j}} defined by (1) with F̃_{0}^{(r)} = F̃_{1}^{(r)} = ⋯ = F̃_{r−2}^{(r)} = 0 ane F̃_{r−1}^{(r)} = 1 if and only if

F̃_{n}^{(r)} = ∑_{j=1}^{ℓ} \frac{\binom{n}{m_{j}−1}α_{j}^{n−m_{j}+1}}{∏_{k=1,k≠j}^{ℓ}(α_{j} − α_{k})}  (5)

for n ≥ r, where α_{1}, α_{2}, …, α_{ℓ} are the distinct real or complex zeros of characteristic polynomial, p(t) = t^{r} − p_{1}t^{r−1} − ⋯ − p_{r}, of the recurrence relation (1) with the multiplicities m_{1}, m_{2}, …, m_{ℓ}, respectively, and m_{1} + m_{2} + ⋯ + m_{ℓ} = r. In particular, if all α_{1}, α_{2}, …, α_{r} are of multiplicity one, then (5) becomes to

F̃_{n}^{(r)} = ∑_{j=1}^{r} \frac{α_{j}^{n}}{∏_{k=1,k≠j}^{r}(α_{j} − α_{k})}, n ≥ r,  (6)

Proof. First, we prove (6). Then we use it to prove the necessity of (5). Let α_{j}, j = 1, 2, …, ℓ, be ℓ zeros of the characteristic polynomial t^{n} − ∑_{i=1}^{r} p_{i}t^{n−i}. Then from (4)

P̃_{r}(t) = \frac{t^{r−1}}{1 − ∑_{j=1}^{r} p_{j}t^{j}} = \frac{1/t}{(1/t)^{r} − ∑_{j=1}^{r} p_{j}(1/t)^{n−j}}

= \frac{1/t}{∏_{j=1}^{r}(1/t − α_{j})} = \frac{t^{r−1}}{∏_{j=1}^{r}(1 − α_{j}t)}.  (7)

We now prove (6) from (7) by using mathematical induction for r under the assumption that all solutions α_{j} are distinct. Because [t^{n}]P̃_{r}(t) = F̃_{n}^{(r)}, we need to show

[t^{n}]P̃_{r}(t) = [t^{n}]\frac{t^{r−1}}{∏_{j=1}^{r}(1 − α_{j}t)} = ∑_{j=1}^{r} \frac{α_{j}^{n}}{∏_{k=1,k≠j}^{r}(α_{j} − α_{k})}, n ≥ r.  (8)

(8) is obviously true for r = 1. Assume (8) holds for r = m. We find

[t^{n}]P̃_{m+1}(t) = [t^{n}]\frac{t^{m}}{∏_{j=1}^{m+1}(1 − α_{j}t)},

[t^{n}](1 − α_{m+1}t)P̃_{m+1}(t) = [t^{n−1}]\frac{t^{m−1}}{∏_{j=1}^{m}(1 − α_{j}t)} = ∑_{j=1}^{m} \frac{α_{j}^{n−1}}{∏_{k=1,k≠j}^{m}(α_{j} − α_{k})}

because of the induction assumption. Noting [t^{n}]P̃_{m+1}(t) = F̃_{n}^{(m+1)}, from the last equations one may write

F̃_{n}^{(m+1)} − α_{m+1}F̃_{n−1}^{(m+1)} = ∑_{j=1}^{m} \frac{α_{j}^{n−1}}{∏_{k=1,k≠j}^{m}(α_{j} − α_{k})},  (9)

which has the solution

F̃_{n}^{(m+1)} = ∑_{j=1}^{m+1} \frac{α_{j}^{n}}{∏_{k=1,k≠j}^{m+1}(α_{j} − α_{k})}.  (10)

Indeed, we have

α_{m+1}F̃_{n−1}^{(m+1)} + ∑_{j=1}^{m} \frac{α_{j}^{n−1}}{∏_{k=1,k≠j}^{m}(α_{j} − α_{k})}

= α_{m+1} ∑_{j=1}^{m+1} \frac{α_{j}^{n−1}}{∏_{k=1,k≠j}^{m+1}(α_{j} − α_{k})} + ∑_{j=1}^{m} \frac{α_{j}^{n−1}}{∏_{k=1,k≠j}^{m}(α_{j} − α_{k})}

= ∑_{j=1}^{m} \frac{α_{j}^{n−1}}{∏_{k=1,k≠j}^{m+1}(α_{j} − α_{k})} (α_{m+1} + α_{j} − α_{m+1}) + \frac{α_{m+1}^{n}}{∏_{k=1}^{m}(α_{m+1} − α_{k})}

= ∑_{j=1}^{m+1} \frac{α_{j}^{n}}{∏_{k=1,k≠j}^{m+1}(α_{j} − α_{k})} = F̃_{n}^{(m+1)},

and (10) is proved.

To prove (5), it is sufficient to show it holds for the case of one multiple zero, say α_{i} with the multiplicity m_{i}. The formula of F̃_{n}^{(r)} in this case can be derived from (6) by using the limit process. More precisely, let m_{i} zeros of the characteristic polynomial, denoted by α_{i_{j}}, 1 ≤ j ≤ m_{i}, approach α_{i}. Then (6) will be reduced to the corresponding (5) with respect to α_{i}. Indeed, taking the limit as α_{i_{j}}, 1 ≤ j ≤ m_{i}, approaches α_{i} on both sides of (6), yields

lim_{(α_{i_{1}},...,α_{im_{i}})→(α_{i},...,α_{i})} F̃_{n}^{(r)}

= \frac{1}{∏_{k=1,k≠i}^{r−m_{i}+1}(α_{i} − α_{k})} lim_{(α_{i_{1}},...,α_{im_{i}})→(α_{i},...,α_{i})} (\frac{α_{i_{1}}^{n}}{∏_{k=2}^{m_{i}}(α_{i_{1}} − α_{i_{k}})} + \frac{α_{i_{2}}^{n}}{∏_{k=1,k≠2}^{m_{i}}(α_{i_{2}} − α_{i_{k}})}

+ ⋯ + \frac{α_{i_{m_{i}}}^{n}}{∏_{k=1,k≠m_{i}}^{m_{i}}(α_{i_{m_{i}}} − α_{i_{k}})}) + ∑_{j=1,j≠i}^{r} \frac{α_{j}^{n}}{∏_{k=1,k≠j}^{r}(α_{j} − α_{k})}.  (11)

It is obvious that the summation in the parentheses of equation (11) is the expansion of the divided difference of the function f(t) = t^{n}, denoted by f[α_{i_{1}}, α_{i_{2}}, …, α_{i_{m_{i}}}], at nodes α_{i_{1}}, α_{i_{2}}, …, α_{i_{m_{i}}}. Using the mean value theorem (see, for example, [13]) for divided difference (see, for example, [2, Thm. 3.6]), one may obtain

lim_{(α_{i_{1}},...,α_{im_{i}})→(α_{i},...,α_{i})} f[α_{i_{1}}, α_{i_{2}}, …, α_{i_{m_{i}}}] = \frac{f^{(m_{i}−1)}(α_{i})}{(m_{i} − 1)!} = \binom{n}{m_{i} − 1}α_{i}^{n−m_{i}+1}.

Therefore, by taking the limit as α_{i_{j}} → α_{i} for 1 ≤ j ≤ m_{i} on both sides of (11), we obtain

lim_{(α_{i_{1}},...,α_{im_{i}})→(α_{i},...,α_{i})} F̃_{n}^{(r)} = \frac{\binom{n}{m_{i}−1}α_{i}^{n−m_{1}+1}}{∏_{k=1,k≠i}^{r−m_{i}+1}(α_{i} − α_{k})} + ∑_{j=1,j≠i}^{r} \frac{α_{j}^{n}}{∏_{k=1,k≠j}^{r}(α_{j} − α_{k})},

which implies the correctness of (5) for the multiple zero α_{i} of multiplicity m_{i}. Therefore, (5) follows by taking the same argument for each multiple zero of the characteristic polynomial P_{r}(t) shown in Proposition 1.

Finally, we prove sufficiency. For n ≥ r,

∑_{i=1}^{r} p_{i}F̃_{n−i}^{(r)} = ∑_{j=1}^{ℓ} \frac{∑_{i=1}^{r} p_{i}\binom{n}{m_{j}−1}α_{j}^{n−i−m_{j}+1}}{∏_{k=1,k≠j}^{ℓ}(α_{j} − α_{k})}

= ∑_{j=1}^{ℓ} \frac{\binom{n}{m_{j}−1}α_{j}^{−m_{j}+1} ∑_{i=1}^{r} p_{i}α_{j}^{n−i}}{∏_{k=1,k≠j}^{ℓ}(α_{j} − α_{k})}

= ∑_{j=1}^{ℓ} \frac{\binom{n}{m_{j}−1}α_{j}^{n−m_{j}+1}}{∏_{k=1,k≠j}^{ℓ}(α_{j} − α_{k})} = F̃_{n}^{(r)},

where we have used α_{j}^{n} = ∑_{i=1}^{r} p_{i}α_{j}^{n−i} because of p(α_{j}) = 0. Therefore, the sequence {F̃_{n}^{(r)}} satisfies the linear recurrence relation (1) and is the IRS with respect to {p_{j}}.

The IRS of a set of linear recurring sequences is a kind of basis so that every sequence in the set can be represented in terms of the IRS. For this purpose, we need to extend the indices of IRS F̃_{n}^{(r)} of A_{r} to the negative indices down to till n = −r + 1, where A_{r} is the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}, p_{r} ≠ 0. For instance, F̃_{−1}^{(r)} is defined by

F̃_{r−1}^{(r)} = p_{1}F̃_{r−2}^{(r)} + p_{2}F̃_{r−3}^{(r)} + ⋯ + p_{r}F̃_{−1}^{(r)},

which implies F̃_{−1}^{(r)} = 1/p_{r} because F̃_{0}^{(r)} = ⋯ = F̃_{r−2}^{(r)} = 0 and F̃_{r−1}^{(r)} = 1. Similarly, we may use

F̃_{r+j}^{(r)} = p_{1}F̃_{r+j−1}^{(r)} + p_{2}F̃_{r+j−2}^{(r)} + ⋯ + p_{r}F̃_{j}^{(r)}

to define F̃_{j}^{(r)}, j = −2, …, −r+1 successively. The following theorem shows how to represent linear recurring sequences in terms of the extended IRS {F̃_{n}^{(r)}}_{n≥−r+1}.

Theorem 3. Let A_{r} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}, p_{r} ≠ 0, and let {F̃_{n}^{(r)}}_{n≥−r+1} be the (extended) IRS of A_{r}. Then, for any a_{n} ∈ A_{r}, one may write a_{n} as

a_{n} = a_{r−1}F̃_{n}^{(r)} + ∑_{j=0}^{r−2} ∑_{k=j}^{r−2} a_{k}p_{r+j−k}F̃_{n−1−j}^{(r)}.  (12)

Proof. Considering the sequences on the both sides of (12), we find that both sequences satisfy the same recurrence relation (1). Hence, to prove the equivalence of two sequences, we only need to show that they have the same initial vector (a_{0}, a_{1}, …, a_{r−1}) because of the uniqueness of the linear recurring sequence defined by (1) with fixed initial conditions. First, for n = r − 1, the conditions F̃_{0}^{(r)} = ⋯ = F̃_{r−2}^{(r)} = 0 and F̃_{r−1}^{(r)} = 1 are applied on the right-hand side of (12) to obtain its value as a_{r−1}, which shows (12) holds for n = r − 1. Secondly, for all 0 ≤ n ≤ r − 2, one may write the right-hand side RHS of (12) as

RHS = 0 + ∑_{k=0}^{r−2} a_{k} (∑_{j=0}^{k} p_{r+j−k}F̃_{n−1−j}^{(r)}) = ∑_{k=0}^{r−2} a_{k}δ_{k,n} = a_{n},

where the Kronecker delta symbol δ_{k,n} is 1 when k = n and zero otherwise, and the following formula is used:

∑_{j=0}^{k} p_{r+j−k}F̃_{n−1−j}^{(r)} = δ_{k,n}.  (13)

(13) can be proved by splitting it into three cases: n =, >, and < k, respectively. If n = k, we have

∑_{j=0}^{k} p_{r+j−k}F̃_{n−1−j}^{(r)} = ∑_{j=0}^{k} p_{r+j−k}F̃_{k−1−j}^{(r)}

= p_{r}F̃_{−1}^{(r)} + p_{r−1}F̃_{0}^{(r)} + p_{r−2}F̃_{1}^{(r)} + ⋯ + p_{r−k}F̃_{k−1}^{(r)}
= p_{r}F̃_{−1}^{(r)} = 1,

where we use F̃_{−1}^{(r)} = 1/p_{r} and the fact F̃_{j}^{(r)} = 0 for all j = 0, 1, …, k − 1 due to k − 1 ≤ r − 3 and the initial values of F̃_{n}^{(r)} being zero for all 0 ≤ n ≤ r − 2.

If n > k, we have

∑_{j=0}^{k} p_{r+j−k}F̃_{n−1−j}^{(r)} = p_{r}F̃_{n−k−1}^{(r)} + p_{r−1}F̃_{n−k}^{(r)} + ⋯ + p_{r−k}F̃_{n−1}^{(r)} = 0

because F̃_{j}^{(r)} = 0 for all j = n − k − 1, n − k, …, n − 1 due to the definition of F̃_{n}^{(r)} and the condition of −1 < n − k − 1 ≤ j ≤ n − 1 ≤ r − 3.

Finally, for 0 ≤ n < k, we may find

∑_{j=0}^{k} p_{r+j−k}F̃_{n−1−j}^{(r)} = p_{r}F̃_{n−k−1}^{(r)} + p_{r−1}F̃_{n−k}^{(r)} + ⋯ + p_{r−k}F̃_{n−1}^{(r)}

= p_{r}F̃_{n−k−1}^{(r)} + ⋯ + p_{r−k}F̃_{n−1}^{(r)} + p_{r−k−1}F̃_{n}^{(r)} + p_{r−k−2}F̃_{n+1}^{(r)} + ⋯ + p_{1}F̃_{n+r−k−2}^{(r)}
= F̃_{n+r−k−1}^{(r)} = 0,

where the inserted r − k − 1 terms F̃_{j}^{(r)}, j = n, n + 1, … n + r − k − 2, are zero due to the definition of F̃_{n}^{(r)} and 0 ≤ n ≤ j ≤ n + r − k − 2 < r − 2. The last two steps of the above equations are from the recurrence relation (1) and the assumptions of 0 ≤ k ≤ r − 2 and 1 ≤ n + 1 ≤ n + r − k − 1 < r − 1, respectively. This completes the proof of theorem.

By using Theorems 2 and 3, we immediately obtain

Corollary 4. Let A_{r} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}, p_{r} ≠ 0, and let α_{1}, α_{2}, …, α_{ℓ} be the zeros of characteristic polynomial, p(t) = t^{r} − p_{1}t^{r−1} − ⋯ − p_{r}, of the recurrence relation (1) with the multiplicities m_{1}, m_{2}, …, m_{ℓ}, respectively, and m_{1} + m_{2} + ⋯ + m_{ℓ} = r. Then, for any {a_{n}} ∈ A_{r}, we have

a_{n} = a_{r−1} ∑_{j=1}^{ℓ} \frac{\binom{n}{m_{j}−1}α_{j}^{n−m_{j}+1}}{∏_{k=1,k≠j}^{ℓ}(α_{j} − α_{k})} + ∑_{j=0}^{r−2} ∑_{k=j}^{r−2} ∑_{j=1}^{ℓ} a_{k}p_{r+j−k} \frac{\binom{n−j−1}{m_{j}−1}α_{j}^{n−j−m_{j}}}{∏_{k=1,k≠j}^{ℓ}(α_{j} − α_{k})}  (14)

We now establish the relationship between a sequence in A_{r} and the IRS of A_{r} by using Toeplitz matrices. A Toeplitz matrix may be defined as a n × n matrix A with entries a_{i,j} = c_{i−j}, for constants c_{1−n}, …, c_{n−1}. A m × n block Toeplitz matrix is a matrix that can be partitioned into m × n blocks and every block is a Toeplitz matrix.

Theorem 5. Let A_{r} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}, and let F̃_{n}^{(r)} be the IRS of A_{r}. Then, for even r, we may write

F̃_{n}^{(r)} = ∑_{j=r/2}^{r−1} c_{j}a_{n+r−j} + ∑_{j=r}^{(3r/2)−1} c_{j}a_{n+r−j−1},  (15)

where the coefficients c_{j}, r/2 ≤ j ≤ (3r/2) − 1, satisfy A_{e}c :=

[ \begin{matrix}a_{r/2} & a_{(r/2)−1} & ⋯ & a_{1} & a_{−1} & a_{−2} & ⋯ & a_{−r/2} \\ a_{(r/2)+1} & a_{r/2} & ⋯ & a_{2} & a_{0} & a_{−1} & ⋯ & a_{−(r/2)+1} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ a_{r−1} & a_{r−2} & ⋯ & a_{r/2} & a_{(r/2)−2} & a_{(r/2)−3} & ⋯ & a_{−1} \\ a_{r} & a_{r−1} & ⋯ & a_{(r/2)+1} & a_{(r/2)−1} & a_{(r/2)−2} & ⋯ & a_{0} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ a_{(3r/2)−1} & a_{(3r/2)−2} & ⋯ & a_{r} & a_{r−2} & a_{r−3} & ⋯ & a_{(r/2)−1} \end{matrix} ] c = e_{r}

(16)

with c = (c_{r/2}, c_{(r/2)−1}, …, c_{r}, c_{r+1}, c_{r+2}, …, c_{(3r/2)−1})^{T} and e_{r} = (0, 0, …, 0, 1)^{T} ∈ ℝ^{r}. For odd r, we have

F̃_{n}^{(r)} = ∑_{j=(r−1)/2}^{3(r−1)/2} c_{j}a_{n+r−j−1},  (17)

where c_{j}, (r − 1)/2 ≤ j ≤ 3(r − 1)/2, satisfy

A_{o}c :=

[ \begin{matrix}a_{(r−1)/2} & a_{((r−1)/2)−1} & ⋯ & a_{1} & a_{0} & a_{−1} & ⋯ & a_{−(r−1)/2} \\ a_{((r−1)/2)+1} & a_{(r−1)/2} & ⋯ & a_{2} & a_{1} & a_{0} & ⋯ & a_{−(r−1)/2+1} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ a_{(3(r−1)/2)} & a_{(3(r−1)/2)−1} & ⋯ & a_{r} & a_{r−1} & a_{r−2} & ⋯ & a_{(r−1)/2} \end{matrix} ] c = e_{r}

(18)

with c = (c_{(r−1)/2}, c_{((r−1)/2)−1}, …, c_{r−1}, c_{r}, c_{r+1}, …, c_{(3(r−1)/2)})^{T} and e_{r} = (0, 0, …, 0, 1)^{T} ∈ ℝ^{r}. If the 2 × 2 block Toeplitz matrix A_{e} and Toeplitz matrix A_{o} are invertible, then we have unique expressions (15) and (17), respectively.

Proof. Since the operator L : ℤ × ℤ ↦ ℤ, L(a_{n−1}, a_{n−2}, …, a_{n−r}) := p_{1}a_{n−1} + p_{2}a_{n−2} + ⋯ + p_{r}a_{n−r} = a_{n}, is linear, sequence {a_{n}} is uniquely determined by L from a given initial vector (a_{0}, a_{1}, …, a_{r−1}). We may extend {a_{n}}_{n≥0} to a sequence with negative indices using the technique we applied in Theorem 3. For instance, by defining a_{−1} from a_{r−1} = p_{r}a_{−1} + p_{r−1}a_{0} + p_{r−2}a_{1} + ⋯ + p_{1}a_{r−2}), we obtain

a_{−1} = \frac{1}{p_{r}} (a_{r−1} − p_{r−1}a_{0} − p_{r−2}a_{1} − ⋯ − p_{1}a_{r−2}), p_{r} ≠ 0.

Thus, the initial vector (a_{−1}, a_{0}, …, a_{r−2}) generates {a_{n}}_{n≥−1} or {a_{n−1}}_{n≥0} by using the operator L. Since both sequences {a_{n}} and {F̃_{n}^{(r)}} satisfy the recurrence relation (1), they are generated by the same operator L. Hence, for even r, we may write F̃_{n}^{(r)} as a linear combination of a_{n+r−j}, r/2 ≤ j ≤ r − 1, and a_{n+r−j−1}, r ≤ j ≤ (3r/2) − 1, as shown in (15), provided the initial vectors of the sequences on the two sides are the same. Here, we mention again that the initial values with negative indices have been defined by using (1). Therefore, we substitute the initial values of {a_{n}} with their negative extensions to the right-hand side of (15) and enforce the resulting linear combination equal to the initials of the left-hand side of (15), i.e., e_{r}, which derives (16). Under the assumption of the invertibility of A_{e}, Toeplitz system (16) has a unique solution of c = (c_{r/2}, c_{(r/2)−1}, …, c_{r}, c_{r+1}, c_{r+2}, …, c_{(3r/2)−1})^{T}, which shows the uniqueness of the expression of (15). (17) can be proved similarly.

Remark 6. It can be seen that not every Toeplitz matrix generated from the linear recurring sequence (1) is invertible. For example, consider the sequence {a_{n}} generated by the linear recurrence relation a_{n} = a_{n−1} + 3a_{n−2} + a_{n−3} with a_{0} = 1, a_{1} = 0, a_{2} = 1, there hold a_{3} = a_{0} + 3a_{1} + a_{2} = 2 and a_{−1} = a_{2} − a_{1} − 3a_{0} = −2. From (17) :

A_{o} = [ \begin{matrix}0 & 1 & 2 \\ 1 & 0 & 1 \\ −2 & 1 & 0 \end{matrix} ] ,

which is not invertible. If p_{j} = 1, 1 ≤ j ≤ r, and r > 2, the corresponding IRS is a higherorder Fibonacci sequence. For instance, F̃_{n}^{(3)}, F̃_{n}^{(4)}, F̃_{n}^{(5)}, F̃_{n}^{(6)}, F̃_{n}^{(7)}, etc. are Tribonacci numbers (\underline{A000073}), Tetranacci numbers (\underline{A000078}), Pentanacci numbers (\underline{A001591}), Heptanacci numbers (\underline{A122189}), Octanacci numbers (\underline{A079262}), etc., respectively.

3 Examples

We now give some examples of IRS for r = 2 and 3. Let A_{2} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (2) with coefficient set E_{2} = {p_{1}, p_{2}}. Hence, from Theorems 2 and 3 and the definition of the impulse response sequence of A_{2} with respect to E_{2}, we obtain

Corollary 7. Let A_{2} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (2) with coefficient set E_{2} = {p_{1}, p_{2}}, and let {F̃_{n}^{(2)}} be the IRS (i.e., the Lucas sequence) of A_{2}. Suppose α and β are two zeros of the characteristic polynomial of A_{2}, which do not need to be distinct. Then

F̃_{n}^{(2)} = \begin{cases}\frac{α^{n}−β^{n}}{α−β} , & if α ≠ β; \\ nα^{n−1}, & if α = β. \end{cases}  (19)

In addition, every {a_{n}} ∈ A_{2} can be written as

a_{n} = a_{1}F̃_{n}^{(2)} − αβa_{0}F̃_{n−1}^{(2)},  (20)

and a_{n} reduces to a_{1}F̃_{n}^{(2)} − α^{2}a_{0}F̃_{n−1}^{(2)} when α = β.

Conversely, there is an expression for F̃_{n}^{(2)} in terms of {a_{n}} as

F̃_{n}^{(2)} = c_{1}a_{n+1} + c_{2}a_{n−1},  (21)

where

c_{1} = \frac{a_{1} − a_{0}p_{1}}{p_{1}(a_{1}^{2} − a_{0}a_{1}p_{1} − a_{0}^{2}p_{2})}, c_{2} = −\frac{a_{1}p_{2}}{p_{1}(a_{1}^{2} − a_{0}a_{1}p_{1} − a_{0}^{2}p_{2})},  (22)

provided that p_{1} ≠ 0, and a_{1}^{2} − a_{0}a_{1}p_{1} − a_{0}^{2}p_{2} ≠ 0.

Proof. (19) is a special case of (5) and (6) and can be found from (5) and (6) by using the substitution r = 2, a_{0} = 0 and a_{1} = 1. Again from (12) and (14)

a_{n} = a_{1}F̃_{n} + a_{0}p_{2}F̃_{n−1} = a_{1}F̃_{n} − αβa_{0}F̃_{n−1}
= \begin{cases}a_{1} \frac{α^{n}−β^{n}}{α−β} − αβa_{0} \frac{α^{n−1}−β^{n−1}}{α−β} , & if α ≠ β; \\ a_{1}(nα^{n−1}) − α^{2}((n − 1)α^{n−2}), & if α = β \end{cases} .  (23)

By using (15) and (16), we now prove (21) and (22), respectively. Denote by L : ℤ×ℤ ↦ ℤ the operator L(a_{n−1}, a_{n−2}) := p_{1}a_{n−1} + p_{2}a_{n−2} = a_{n}. As presented before, L is linear, and the sequence {a_{n}} is uniquely determined by L from a given initial vector (a_{0}, a_{1}). Define a_{−1} = (a_{1} − p_{1}a_{0})/p_{2}, then (a_{−1}, a_{0}) is the initial vector that generates {a_{n−1}}_{n≥0} by L. Similarly, the vector (a_{1}, p_{1}a_{1} + p_{2}a_{0}) generates sequence {a_{n+1}}_{n≥} by using L. Note the initial vector of F̃_{n}^{(2)} is (0, 1). Thus (21) holds if and only if the initial vectors on the two sides are equal:

(0, 1) = c_{1}(a_{1}, p_{1}a_{1} + p_{2}a_{0}) + c_{2} (\frac{a_{1} − p_{1}a_{0}}{p_{2}} , a_{0}) ,  (24)

which yields the solutions (22) for c_{1} and c_{2} and completes the proof of the corollary.

Recall that [8] presented the following result.

Proposition 8. [8] Let {a_{n}} be a sequence of order 2 satisfying linear recurrence relation (2), and let α and β be two zeros of the characteristic polynomial x^{2} − p_{1}x − p_{2} = 0 of the relation (2). Then

a_{n} = \begin{cases}(\frac{a_{1}−βa_{0}}{α−β} ) α^{n} − (\frac{a_{1}−αa_{0}}{α−β} ) β^{n}, & if α ≠ β; \\ na_{1}α^{n−1} − (n − 1)a_{0}α^{n}, & if α = β. \end{cases}  (25)

The paper [8] also gives a method for finding the expressions of the linear recurring sequences of order 2 and the interrelationship among those sequences. However, [8] also pointed out “the method presented in this paper (i.e., Proposition 8) cannot be extended to the higher order setting.” In Section 2, we have shown our method based on the IRS can be extended to the higher setting. Here, Proposition 8 is an application of our method in a particular case. In addition, it can be easily seen that (25) can be derived from (23).

Corollary 7 presents the interrelationship between a linear recurring sequence with respect to E_{2} = {p_{1}, p_{2}) and its IRS, which can be used to transfer the identities of one sequence to the identities of other sequences in the same set.

Example 9. Let us consider A_{2}, the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (2) with coefficient set E_{2} = {p_{1}, p_{2}}. If E_{2} = \{1, 1\}, then the corresponding characteristic polynomial has zeros α = (1 + \sqrt{5})/2 and β = (1 − \sqrt{5})/2, and (21) gives the expression of the IRS of A_{2}, which is the Fibonacci sequence {F_{n}}:

F_{n} = \frac{1}{\sqrt{5}} \{(\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}\} .

The sequence in A_{2} with the initial vector (2, 1) is the Lucas number sequence (which is different from the Lucas sequence) {L_{n}}. From (20) and (21) and noting αβ = −1, we have the well-known formulas (see, for example, [9]):

L_{n} = F_{n} + 2F_{n−1} = F_{n+1} + F_{n−1}, F_{n} = \frac{1}{5}L_{n−1} + \frac{1}{5}L_{n+1}.

By using the above formulas, one may transfer identities of Fibonacci number sequence to those of Lucas number sequence and vice versa. For instance, the above relationship can be used to prove that the following two identities are equivalent:

F_{n+1}F_{n+2} − F_{n−1}F_{n} = F_{2n+1}
L_{n+1}^{2} + L_{n}^{2} = L_{2n} + L_{2n+2}.

It is clear that both of the identities are equivalent to the Carlitz identity, F_{n+1}L_{n+2} − F_{n+2}L_{n} = F_{2n+1}, shown in [3].

Example 10. Let us consider A_{2}, the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (2) with coefficient set E_{2} = {p_{1} = p, p_{2} = 1}. Then (25) tell us that {a_{n}} ∈ A_{2} satisfies

a_{n} = \frac{2a_{1} − (p − \sqrt{4 + p^{2}})a_{0}}{2\sqrt{4 + p^{2}}} α^{n} − \frac{2a_{1} − (p + \sqrt{4 + p^{2}})a_{0}}{2\sqrt{4 + p^{2}}} (−\frac{1}{α})^{n} ,  (26)

where α is defined by

α = \frac{p + \sqrt{4 + p^{2}}}{2} and β = −\frac{1}{α} = \frac{p − \sqrt{4 + p^{2}}}{2} .  (27)

Similarly, let E_{2} = {1, q}. Then

a_{n} = \begin{cases}\frac{2a_{1}−(1−\sqrt{1+4q})a_{0}}{2\sqrt{1+4q}} α_{1}^{n} − \frac{2a_{1}−(1+\sqrt{1+4q})a_{0}}{2\sqrt{1+4q}} α_{2}^{n}, & if q ≠ −\frac{1}{4}; \\ \frac{1}{2^{n}} (2na_{1} − (n − 1)a_{0}), & if q = −\frac{1}{4}, \end{cases}

where α = \frac{1}{2}(1 + \sqrt{1 + 4q}) and β = \frac{1}{2}(1 − \sqrt{1 + 4q}) are solutions of equation x^{2} − x − q = 0. The first special case (26) was studied by Falbo [5]. If p = 1, the sequence is clearly the Fibonacci sequence. If p = 2 (resp., q = 1), the corresponding sequence is the sequence of numerators (when two initial conditions are 1 and 3) or denominators (when two initial conditions are 1 and 2) of the convergent of a continued fraction to \sqrt{2}: \{\frac{1}{1}, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29} …\}, called the closest rational approximation sequence to \sqrt{2}. The second special case is for the case of q = 2 (resp., p = 1), the resulting {a_{n}} is the Jacobsthal type sequences (See Bergum, Bennett, Horadam, and Moore [1]).

By using Corollary 7, for E_{2} = {p, 1}, the IRS of A_{2} with respect to E_{2} is

F̃_{n}^{(2)} = \frac{1}{\sqrt{4 + p^{4}}} \{(\frac{p + \sqrt{4 + p^{2}}}{2} )^{n} − (\frac{p − \sqrt{4 + p^{2}}}{2} )^{n}\} .

In particular, the IRS for E_{2} = {2, 1} is the well-known Pell number sequence {P_{n}} = {0, 1, 2, 5, 12, 29, …} with the expression

P_{n} = \frac{1}{2\sqrt{2}} \{(1 + \sqrt{2})^{n} − (1 − \sqrt{2})^{n}\} .

Similarly, for E_{2} = {1, q}, the IRS of A_{2} with respect to E_{2} is

F̃_{n}^{(2)} = \frac{1}{\sqrt{1 + 4q}} \{(\frac{1 + \sqrt{1 + 4q}}{2} )^{n} − (\frac{1 − \sqrt{1 + 4q}}{2} )^{n}\} .

In particular, the IRS for E_{2} = {1, 2} is the well-known Jacobsthal number sequence {J_{n}} = {0, 1, 1, 3, 5, 11, 21, …} with the expression

J_{n} = \frac{1}{3} (2^{n} − (−1)^{n}) .

The Jacobsthal-Lucas numbers {j_{n}} in A_{2} with respect to E_{2} = {1, 2} satisfying j_{0} = 2 and j_{1} = 1 has the first few elements as {2, 1, 5, 7, 17, 31, …}. From (20), one may deduce

j_{n} = J_{n} + 4J_{n−1} = 2^{n} + (−1)^{n}.

In addition, the above formula can transform all identities of the Jacobsthal-Lucas number sequence to those of Jacobsthal number sequence and vice-versa. For example, we have

J_{n}^{2} + 4J_{n−1}J_{n} = J_{2n},
J_{m}J_{n−1} − J_{n}J_{m−1} = (−1)^{n}2^{n−1}J_{m−n},
J_{m}J_{n} + 2J_{m}J_{n−1} + 2J_{n}J_{m−1} = J_{m+n}

from

j_{n}J_{n} = J_{2n},
J_{m}j_{n} − J_{n}j_{m} = (−1)^{n}2^{n+1}J_{m−n},
J_{m}j_{n} − J_{n}j_{m} = 2J_{m+n},

respectively. Similarly, we can show that the following two identities are equivalent:

j_{n} = J_{n+1} + 2J_{n−1}, J_{n+1} = J_{n} + 2J_{n−1}.

Remark 11. Corollary 7 can be extended to the linear nonhomogeneous recurrence relations of order 2 with the form: a_{n} = pa_{n−1} + qa_{n−2} + ℓ, ℓ ≠ 0, for p + q ≠ 1. It can be seen that the above recurrence relation is equivalent to the homogeneous form (2) b_{n} = pb_{n−1} + qb_{n−2}, where b_{n} = a_{n} − k and k = \frac{ℓ}{1−p−q}.

Example 12. An obvious example of Remark 11 is the Mersenne number M_{n} = 2^{n} − 1, n ≥ 0, which satisfies the linear recurrence relation of order 2: M_{n} = 3M_{n−1} − 2M_{n−2} ( with M_{0} = 0 and M_{1} = 1) and the non-homogeneous recurrence relation of order 1: M_{n} = 2M_{n−1} + 1 (with M_{0} = 0). It is easy to check that sequence M_{n} = (k^{n} − 1)/(k − 1) satisfies both the homogeneous recurrence relation of order 2, M_{n} = (k + 1)M_{n−1} − kM_{n−2}, and the non-homogeneous recurrence relation of order 1, M_{n} = kM_{n−1} + 1, where M_{0} = 0 and M_{1} = 1. Here, M_{n} is the IRS with respect to E_{2} = {3, −2}. Another example is Pell number sequence that satisfies both homogeneous recurrence relation P_{n} = 2P_{n−1} + P_{n−2} and the non-homogeneous relation P̄_{n} = 2P̄_{n−1} + P̄_{n−2} + 1, where P_{n} = P̄_{n} + 1/2.

Remark 13. Niven, Zuckerman, and Montgomery [12] studied some properties of two sequences, {G_{n}}_{n≥0} and {H_{n}}_{n≥0}, defined respectively by the linear recurrence relations of order 2:

G_{n} = pG_{n−1} + qG_{n−2} and H_{n} = pH_{n−1} + qH_{n−2}

with initial conditions G_{0} = 0 and G_{1} = 1 and H_{0} = 2 and H_{1} = p, respectively. Clearly, G_{n} = F̃_{n}^{(2)}, the IRS of A_{2} with respect to E_{2} = {p_{1} = p, p_{2} = q}. Using Corollary 7, we may rebuild the relationship between the sequences {G_{n}} and {H_{n}}:

H_{n} = pG_{n} + 2qG_{n−1},

G_{n} = \frac{q}{p^{2} + 4q} H_{n−1} + \frac{1}{p^{2} + 4q} H_{n+1}.

We now give more examples of higher order IRS in A_{3}.

Example 14. Consider set A_{3} of all linear recurring sequences defined by (1) with coefficient set E_{3} = {p_{1} = 1, p_{2} = 1, p_{3} = 1}. The IRS of A_{3} is the tribonacci number sequence \{0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …\} (\underline{A000073}). From Proposition 1, the generating function of the tribonacci sequence is

P̃_{3}(t) = \frac{t^{2}}{1 − t − t^{2} − t^{3}} .

Theorem 2 gives the expression of the general term of tribonacci sequence as

F̃_{n}^{(3)} = \frac{α_{1}^{n}}{(α_{1} − α_{2})(α_{1} − α_{3})} + \frac{α_{2}^{n}}{(α_{2} − α_{1})(α_{2} − α_{3})} + \frac{α_{3}^{n}}{(α_{3} − α_{1})(α_{3} − α_{2})},

where

α_{1} = −\frac{1}{3} − \frac{C}{3} + \frac{2}{3C} ,

α_{2} = −\frac{1}{3} + \frac{C}{6} (1 + i\sqrt{3}) − \frac{1}{3C} (1 − i\sqrt{3}),

α_{3} = −\frac{1}{3} + \frac{C}{6} (1 − i\sqrt{3}) − \frac{1}{3C} (1 + i\sqrt{3}),

in which C = ((6\sqrt{33}−34)/2)^{1/3}. The tribonacci-like sequence \{a_{n}\} = \{2, 1, 1, 4, 6, 11, 21, …\} (\underline{A141036}) is in the set A_{3}. From Theorem 3 and its corollary 4, a_{n} can be presented as

a_{n} = a_{2}F̃_{n}^{(3)} + ∑_{j=0}^{1} ∑_{k=j}^{1} a_{k}F̃_{n−j−1}^{(3)}.
= a_{2}F̃_{n}^{(3)} + (a_{0} + a_{1})F̃_{n−1}^{(3)} + a_{1}F̃_{n−2}^{(3)}.  (28)

Using (17) and (18) in Theorem 5, we may obtain the expression

F̃_{n}^{(3)} = \frac{6}{19}a_{n+1} − \frac{4}{19}a_{n} − \frac{1}{19}a_{n−1}, n ≥ 0,  (29)

where a_{−1} := −2 due to the linear recurrence relation a_{n} = a_{n−1} + a_{n−2} + a_{n−3}. It is easy to see the identity

F̃_{n}^{(3)} = 2F̃_{n−1}^{(3)} − F̃_{n−4}^{(3)}, n ≥ 4,

because the right-hand side is equal to F̃_{n−1}^{(3)} + F̃_{n−2}^{(3)} + F̃_{n−3}^{(3)} after substituting into F̃_{n−1}^{(3)} = F̃_{n−2}^{(3)} + F̃_{n−3}^{(3)} + F̃_{n−4}^{(3)}. Thus, by using (29) we have an identity for {a_{n}}:

6a_{n+1} − 16a_{n} + 7a_{n−1} + 2a_{n−2} + 6a_{n−3} − 4a_{n−4} − a_{n−5} = 0

for all n ≥ 5. Similarly from the identity a_{n} = 2a_{n−1} − a_{n−4}, n ≥ 4, and relation (28), we have the identity

F̃_{n}^{(3)} + F̃_{n−1}^{(3)} − 5F̃_{n−2}^{(3)} − 2F̃_{n−3}^{(3)} + F̃_{n−4}^{(3)} + 3F̃_{n−5}^{(3)} + F̃_{n−6}^{(3)} = 0

for all n ≥ 6.

It is easy to see there exists r number sequences, denoted by {a_{n}^{(j)}}, j = 1, 2, …, r, in A_{r} with respect to E_{r} such that for any {a_{n}} ∈ A_{r} we have

a_{n} = ∑_{j=1}^{r} c_{j}a_{n}^{(j)}, n ≥ 0,

where c = (c_{1}, c_{2}, …, c_{r}) can be found from the system consisting of the above equations for n = 0, 1, …, r−1. In this sense, we may call {a_{n}^{(j)}}, j = 1, 2, …, r, a basis of A_{r} with respect to E_{r}. For instance, for r = 2, let {a_{n}^{(1)}} be {F_{n}}, the IRS of A_{2} with respect to E_{2} = {1, 1} (i.e., the Fibonacci sequence), and let {a_{n}^{(2)}} be the Lucas number sequence {L_{n}}. Then {{F_{n}}, {L_{n}}} is a basis of A_{2} because. Thus, for any {a_{n}} ∈ A_{2} with respect to E_{2} = {1, 1} and the initial vector (a_{0}, a_{1}), we have

a_{n} = (a_{1} − \frac{1}{2}a_{0}) F_{n} + \frac{1}{2}a_{0}L_{n},

where the coefficients of the above linear combination are found from the system

[ \begin{matrix}0 & 2 \\ 1 & 1 \end{matrix} ] [ \begin{matrix}c_{1} \\ c_{2} \end{matrix} ] = [ \begin{matrix}a_{0} \\ a_{1} \end{matrix} ] .

Obviously, if {L_{n}} is replaced by any sequence {a_{n}^{(2)}} in A_{2} with respect to E_{2} = {1, 1}, provided the initial vector (a_{0}^{(2)}, a_{1}^{(2)}) of {a_{n}^{(2)}} satisfies

det [ \begin{matrix}0 & a_{0}^{(2)} \\ 1 & a_{1}^{(2)} \end{matrix} ] ≠ 0,  (30)

then {{F_{n}}, {a_{n}^{(2)}}} is a basis of A_{2} with respect to E_{2} = {1, 1}. However, if a_{0}^{(2)} = 1 and a_{1}^{(2)} = 0, then the corresponding a_{n}^{(2)} = F_{n−1}, and the corresponding basis {{F_{n}}, {a_{n}^{(2)} = F_{n−1}}} is called a trivial basis. Thus, for A_{2} with respect to E_{2} = {p_{1}, p_{2}}, {{F̃_{n}^{(2)}}, {a_{n}^{(2)}}} forms a non-trivial basis, if the initial vector (a_{0}^{(2)}, a_{1}^{(2)}) of {a_{n}^{(2)}} satisfies (30) and a_{0}^{(2)} ≠ 1/p_{2} when a_{1}^{(2)} = 0. The second condition guarantees that the basis is not trivial, otherwise a_{n}^{(2)} = F̃_{n−1}^{(2)}.

4 Applications

In this section, we will give the applications of IRS to the Stirling numbers of the second kind, Wythoff array, and the Boustrophedon transform. Let A_{r} be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (1) with coefficient set E_{r} = {p_{1}, p_{2}, …, p_{r}}, and let F̃_{n}^{(r)} be the IRS of A_{r}. Theorems 3 gives expressions of {a_{n}} ∈ A_{r} and the IRS of A_{r} in terms of each other. We will give a different expression of {a_{n}} ∈ A_{r} in terms of F̃_{n}^{(r)} using the generating functions of {a_{n}} and {F̃_{n}^{(r)}} shown in Proposition 1. More precisely, let {a_{n}} ∈ A_{r}. Then Proposition 1 shows that its generating function P (t) can be written as (3). In particular, the generating function for the IRS with respect to {p_{j}} is presented as (4). Comparing the coefficients of P (t) and P̃(t), one finds

Proposition 15. Let {a_{n}} be an element of A_{r}, and let {F̃_{n}^{(r)}} be the IRS of A_{r}. Then

F̃_{n}^{(r)} = [t^{n−r+1}]\frac{1}{1 − ∑_{j=1}^{r} p_{j}t^{j}}  (31)
a_{n} = a_{0}F̃_{n+r−1}^{(r)} + ∑_{k=1}^{r−1}(a_{k} − ∑_{j=1}^{k} p_{j}a_{k−j})F̃_{n+r−k−1}^{(r)}.  (32)

Proof. Eq. (31) comes from

F̃_{n}^{(r)} = [t^{n}]P̃(t) = [t^{n−r+1}]\frac{1}{1 − ∑_{j=1}^{r} p_{j}t^{j}} .

Hence,

a_{n} = [t^{n}]P (t) = a_{0}[t^{n}]\frac{1}{1 − ∑_{j=1}^{r} p_{j}t^{j}} + [t^{n}]\frac{∑_{k=1}^{r−1} (a_{k} − ∑_{j=1}^{k} p_{j}a_{k−j}) t^{k}}{1 − ∑_{j=1}^{r} p_{j}t^{j}}

= a_{0}F̃_{n+r−1}^{(r)} + ∑_{k=1}^{r−1} (a_{k} − ∑_{j=1}^{k} p_{j}a_{k−j}) [t^{n−k}]\frac{1}{1 − ∑_{j=1}^{r} p_{j}t^{j}} ,

which implies (31).

Proposition 16. If

g(t) = \frac{t^{r−1}}{1 − ∑_{j=1}^{r} p_{j}t^{j}}  (33)

is the generating function of a sequence {b_{n}}, then {b_{n}} satisfies

b_{n} = \begin{cases}0, & if n = 0, 1, …, r − 2; \\ 1, & if n = r − 1; \\ ∑_{j=1}^{r} p_{j}b_{n−j}, & if n ≥ r. \end{cases}

Proof. It is clear that

b_{j} = [t^{j}]g(t) = [t^{j−r+1}]\frac{1}{1 − ∑_{j=1}^{r} p_{j}t^{j}}

= [t^{j−r+1}] ∑_{k≥0} (∑_{j=1}^{r} p_{j}t^{j})^{k} = \begin{cases}0 & if 0 ≤ j ≤ r − 2, \\ 1 & if j = r − 1. \end{cases}

For n ≥ r,

∑_{j=1}^{r} p_{j}b_{n−j} = ∑_{j=1}^{r} p_{j}[t^{n−j}]g(t)

= [t^{n}] ∑_{j=1}^{r} t^{r−1} \frac{p_{j}t^{j}}{1 − ∑_{i=1}^{r} p_{i}t^{i}}

= [t^{n}]t^{r−1} (\frac{1}{1 − ∑_{i=1}^{r} p_{i}t^{i}} − 1)
= [t^{n}]g(t) − [t^{n}]t^{r−1} = b_{n},

which completes the proof.

The Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n labelled objects into k unlabeled subsets. We now prove that the sequence {b_{n} = S(n + 1, k)}_{n≥0} is the IRS of A_{k} for any k ∈ ℕ_{0} by using the structure of the triangle of the Stirling numbers of the second kind shown in Table 1.

n\k 0 1 2 3 4 5 6
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1

Table 1. Triangle of the Stirling numbers of the second kind

Theorem 17. Let S(n, k) be the Stirling numbers of the second kind. Then, for any fixed integer k > 0, S(n + 1, k) is the IRS of A_{k}, i.e.,

S(n + 1, k) = F̃_{n}^{(k)},  (34)

where A_{k} is the set of linear recurring sequences {a_{n}} generated by

a_{n} = ∑_{j=1}^{k} p_{j}a_{n−j},  (35)

which has characteristic polynomial

P (t) = t^{k} − ∑_{j=1}^{k} p_{j}t^{k−j} = ∏_{j=1}^{k}(1 − jt).  (36)

Thus, the generating function of {S(n + 1, k)} is

P̃(t) = \frac{t^{k}}{∏_{j=1}^{k}(1 − jt)}.  (37)

Proof. {S(n, k)}_{0≤k≤n} obeys the recurrence relation

S(n + 1, k) = kS(n, k) + S(n, k − 1), 0 ≤ k ≤ n,  (38)

which can be explained by using the definition of S(n, k) shown above. A partition of the n + 1 objects into k nonempty subsets either contains the subset {n + 1} or it does not. The number of ways that {n + 1} is one of the subsets is given by S(n, k − 1), since we must partition the remaining n objects into the available k − 1 subsets. The number of ways that {n + 1} is not one of the subsets is given by kS(n, k) because we partition all elements other than n + 1 into k subsets with k choices for inserting the element n + 1. Summing these two values yields (38). Write (38) as

S(n, k − 1) = S(n + 1, k) − kS(n, k), 0 < k ≤ n.

Denote by g_{k−1}(t) and g_{k}(t) the generating functions of k − 1st and kth columns of the Stirling triangle shown in Table 2. Then the above equation means

[t^{n}]g_{k−1}(t) = S(n, k−1) = S(n+1, k)−kS(n, k) = [t^{n+1}]g_{k}(t)−k[t^{n}]g_{k}(t) = [t^{n+1}](1−kt)g_{k}(t)

for 0 < k ≤ n. Therefore, we have

g_{k}(t) = \frac{t}{1 − kt}g_{k−1}(t).

Since g_{1}(t) = t/(1 − t), we obtain the generating function of {S(n, k)} for k > 0

g_{k}(t) = \frac{t^{k}}{∏_{j=1}^{k}(1 − jt)}.  (39)

Denote b_{n} = S(n + 1, k) and the generating function of {b_{n}} by B(t). Then

b_{n} = [t^{n}]B(t) = S(n + 1, k) = [t^{n+1}]g_{k}(t), 0 < k ≤ n,

which implies the generating function of {b_{n}} is

B(t) = \frac{1}{t}g_{k}(t) = \frac{t^{k−1}}{∏_{j=1}^{k}(1 − jt)}.  (40)

Using Proposition 16, we immediately know that {S(n + 1, k)} is the IRS of A_{k} that has the generating function (37), where A_{k} is the set of linear recurring sequences {a_{n}} generated by recurrence relation (35) with the characteristic polynomial (36).

Example 18. Since the second column of the Stirling triangle, {S(n + 1, 2)}, has the generating function

P̃_{2}(t) = \frac{t}{(1 − t)(1 − 2t)} = \frac{1}{1 − 3t + 2t^{2}} ,

we have the recurrence relation

S(n + 1, 2) = 3S(n, 2) − 2S(n − 1, 2)

with the initial S(1, 2) = 0 and S(2, 2) = 1. Thus we have S(3, 2) = 3, S(4, 2) = 7, S(5, 2) = 15, S(6, 2) = 31, etc.

Similarly, {S(n + 1, 3)} is a linear recurring sequence generated by

S(n + 1, 3) = 6S(n, 3) − 11S(n, 2) + 6S(n, 1)

with initials S(1, 3) = S(2, 3) = 0 and S(3, 3) = 1. From the recurrence relation one may find S(4, 3) = 6, S(5, 3) = 25, S(6, 3) = 90, etc.

If we transfer the entries in the array shown in Table 1 to d_{n,k} = k!S(n+1, k +1)/n!, then the array (d_{n,k})_{0≤k≤n} is a Riordan array. The structure and computation of the Riordan array of the generalized Stirling numbers can be found from [6], while the sequence characterization of the Riordan array is shown in [7].

We now consider the Wythoff array shown in Table 2, in which the two columns to the left of the vertical line consist respectively of the nonnegative integers n, and the lower Wythoff sequence (A201), whose nth term is [(n + 1)α], where α = (1 + \sqrt{5})/2. The rows are linear recurring sequences generated by the Fibonacci rule that each term is the sum of the two previous terms.

0 1  1 2 3 5 8 13 ⋯
1 3  4 7 11 18 29 47 ⋯
2 4  6 10 16 26 42 68 ⋯
3 6  9 15 24 39 63 102 ⋯
4 8  12 20 32 52 84 136 ⋯
5 9  14 23 37 60 97 157 ⋯
6 11  17 28 45 73 118 191 ⋯
7 12  19 31 50 81 131 212 ⋯
⋮ ⋮  ⋮ ⋮ ⋮ ⋮ ⋮  ⋮

Table 2. the Wythoff array

The first row sequence in Table 2 is Fibonacci sequence, i.e., the IRS in A_{2} with respect to E_{2} = {1, 1}. The jth row sequence {a_{n}^{(j)}}_{n≥0} are linear recurring sequences in A_{2} with respect to E_{2} = \{1, 1\} with initials (j, [(j + 1)α]), j = 1, 2, …, where α = (1 + \sqrt{5})/2. From (23) or (25), the expression of a_{n}^{(j)} can be written as

a_{n}^{(j)} = (\frac{[(j + 1)\frac{1+\sqrt{5}}{2}] − j \frac{1−\sqrt{5}}{2}}{\sqrt{5}} ) (\frac{1 + \sqrt{5}}{2})^{n}

− (\frac{[(j + 1)\frac{1+\sqrt{5}}{2}] − j \frac{1+\sqrt{5}}{2}}{\sqrt{5}} ) (\frac{1 − \sqrt{5}}{2})^{n} .  (41)

Since every integer in ℕ_{0} appears exactly once (see [14]), the collection {a_{n}^{(j)}}_{n≥0}, j = 0, 1, …, gives a partition of ℕ_{0}. [(j + 1)α], α = (1 + \sqrt{5})/2, can be considered as the representative of the equivalence class {a_{n}^{(j)} : n = 0, 1, …}.

0 1  2 5 12 29 70 169 ⋯
1 3  7 17 41 99 239 577 ⋯
2 6  14 34 82 198 470 1154 ⋯
3 8  19 46 111 268 647 1562 ⋯
4 11  26 63 152 367 886 2139 ⋯
⋮ ⋮  ⋮ ⋮ ⋮  ⋮  ⋮  ⋮

Table 3. the Pell-Wythoff array

a_{0} = b_{0}
a_{1} →  b_{1} = a_{0} + a_{1}
b_{2} = a_{1} + a_{2} + b_{1} ← a_{2} + b_{1} ← a_{2}
a_{3} →  a_{3} + b_{2} → a_{2} + a_{3} + b_{1} + b_{2} → b_{3} = 2a_{2} + a_{3} + b_{1} + b_{2}

Table 4. Triangle of the boustrophedon transform

The Wythoff array can be extended to similar arrays associated with different linear recurrence relations. For instance, one may define the Pell-Wythoff array shown in Table 3.

The first row sequence in Table 2 is the Pell sequence, which is also the IRS in A_{2} with respect to E_{2} = {2, 1}. The jth row sequence {b_{n}^{(j)}}_{n≥0} are linear recurring sequences in A_{2} with respect to E_{2} = \{2, 1\} with initials (j, [(j + 1)r] − 1), j = 1, 2, …, where r = 1 + \sqrt{2}.

Noting (23) or (25), we obtain the expression of b_{n}^{(j)} as

b_{n}^{(j)} = (\frac{[(j + 1)(1 + \sqrt{2})] − j(1 − \sqrt{2}) − 1}{2\sqrt{2}}) (1 + \sqrt{2})^{n}

− (\frac{[(j + 1)(1 + \sqrt{2})] − j(1 + \sqrt{2}) − 1}{2\sqrt{2}}) (1 − \sqrt{2})^{n} .  (42)

Millar, Sloane, and Young [11] showed that the boustrophedon transform of a given sequence {a_{n}}_{n≥0} is the sequence produced by the triangle shown in Table 4.

Formally, the entries T_{n,k}, n ≥ k ≥ 0, of the above triangle are defined by

T_{n,0} = a_{n} n ≥ 0,
T_{n+1,k+1} = T_{n+1,k} + T_{n,n−k} n ≥ k ≥ 0,  (43)

and then b_{n} = T_{n,n} for all n ≥ 0. Denote the (exponential) generating functions of sequences {a_{n}} and {b_{n}} by A(t) and B(t). Then Theorem 1 of [11] gives

B(t) = (sec t + tan t)A(t),

which implies a relationship of the generating function P̃_{r}(t) of the IRS {F̃_{n}^{(r)}} of A_{r} and the generating function (BP_{r})(t) of the boustrophedon transform sequence of {F̃_{n}^{(r)}}:

(BP_{r})(t) = (sec t + tan t)P_{r}(t) = (sec t + tan t)\frac{t^{r−1}}{1 − ∑_{j=1}^{r} p_{j}t^{j}} .  (44)

5 Acknowledgements

The author would like to express his gratitude to the editor and the anonymous referee for their helpful comments and remarks. The author also thank Michael Dancs for his proofreading of the manuscript.

References

[1] G. E. Bergum, L. Bennett, A. F. Horadam, and S. D. Moore, Jacobsthal polynomials and a conjecture concerning Fibonacci-like matrices, Fibonacci Quart. 23 (1985), 240– 248.

[2] R. L. Burden and J. D. Faires, Numerical Methods, 8th Edition, Brooks/Cole Publishing Co., 2005.

[3] L. Carlitz, Problem B-110, Fibonacci Quart. 5 (1967), 469–470.

[4] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Comp., 1974.

[5] C. Falbo, The golden ratio — a contrary viewpoint, College Math. J. 36 (2005), 123–134.

[6] T. X. He, Expression and computation of generalized Stirling numbers, J. Combin. Math. Combin. Comput., 86 (2013), 239–268.

[7] T. X. He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math., 309 (2009), 3962–3974.

[8] T. X. He and P. J.-S. Shiue, On sequences of numbers and polynomials defined by second order recurrence relations, Int. J. Math. Math. Sci., 2009 (2009), Article ID 709386, 1–21.

[9] T. Koshy, Fibonacci and Lucas Numbers with Applications, Pure and Applied Mathematics, Wiley-Interscience, 2001.

[10] R. Lidl and H. Niederreiter, Finite Fields, With a foreword by P. M. Cohn, 2nd edition, Encyclopedia of Mathematics and its Applications, Vol. 20, Cambridge University Press, Cambridge, 1997.

[11] J. Millar, N. J. A. Sloane, and N. E. Young, A new operation on sequences: the boustrophedon transform, J. Combin. Theory, Series A, 76 (1996), 44–54.

[12] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, John Wiley & Sons, Inc., 1991.

[13] W. Rudin, Principles of Mathematical Analysis, 3rd edition, International Series in Pure and Applied Mathematics. McGraw-Hill Book Co., 1976.

[14] N. J. A. Sloane, My favorite integer sequences, AT&T Lab Research Preprint,

    http://www2.research.att.com/~njas/doc/sg.pdf.

[15] G. Strang, Linear Algebra and Its Applications, 2nd edition, Academic Press, 1980.

[16] H. S. Wilf, Generatingfunctionology, 2nd edition, Academic Press, 1990.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 05A15, 11B73, 11B75, 05A19, 11Y55.

Keywords: number sequence, linear recurrence relation, Stirling number of the second kind, generating function, Wythoff array, Boustrophedon transform, Fibonacci number, Pell number, Jacobsthal number, Lucas number, Lucas sequence, Riordan array.

(Concerned with sequences \underline{A000073}, \underline{A000078}, \underline{A001591}, \underline{A079262}, \underline{A122189}, and \underline{A141036}.)

Received March 27 2013; revised versions received March 29 2013; June 21 2013; August 27 2013. Published in Journal of Integer Sequences, October 12 2013.

Return to Journal of Integer Sequences home page.