An Approach to the Construction of Linear Divisibility Sequences of Higher Orders

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

                          the@iwu.edu

Peter J.-S. Shiue^{∗} Department of Mathematical Sciences University of Nevada, Las Vegas Las Vegas, NV 89154-4020 USA

                     shiue@unlv.nevada.edu

Abstract We present a unified approach to construct divisibility sequences of higher orders

by using divisibility sequences of order 2.

1 Introduction

Let ℤ be the ring of integers. A sequence (a_{n})_{n≥0} of elements in ℤ is called a divisibility sequence (DS for abbreviation) if m|n implies a_{m}|a_{n}. In this paper, we discuss DSs that are recursive sequences (a_{n}) satisfying linear homogeneous recurrence relations with constant coefficients, which are called linear divisibility sequences (LDSs for abbreviation). A wellknown example is the sequence of Fibonacci numbers. It has long been an open question whether all divisibility sequences are, essentially, just termwise products of second order recursive sequences generalizing the Fibonacci numbers. Some earlier discussion about the question can be found in Ward [25]. Bézivin, Pethö, and van der Poorten [2] characterize all divisibility sequences by employing the factorization theory for exponential polynomials and a deep arithmetic result on the Hadamard quotient of rational functions. Some interesting results of divisibility sequences of order 3 and 4 can be found in Hall [6] and Williams and Guy [27, 28], respectively. In this paper, we will present a different unified approach to construct LDSs of higher order by using LDSs of order 2. Of course, we are aware that in literature the notion “divisibility sequence” need not entail that the sequence is a recursive sequence. However, we prefer to follow the original definition to limit the LDS in the ring of linear homogeneous recursive sequences.

∗This work was completed while on sabbatical leave from the University of Nevada, Las Vegas, and the author would like to thank UNLV for its support.

We present a necessary and sufficient condition for a second order LDS in the next section. Then, a large class of the second order number and polynomial divisibility sequences are given. In Section 3, we will give a unified approach to construct higher order LDSs by using second order LDSs and the Hadamard product of sequences (see, for example, Everest, Poorten, Shparlinski, and Ward [4, p. 65]), namely, (a_{n}) ∗ (b_{n}) = (a_{n}b_{n}).

2 Second order linear divisibility sequences

In this section, we discuss the conditions that make a second order linear homogeneous recursive sequence (a_{n}) an LDS. Here, a number sequence (a_{n}) is called linear homogeneous recursive sequence of order 2, if it satisfies the following linear homogenous recurrence relation of order 2:

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

for a constant p, a nonzero constant q, and initial conditions a_{0} and a_{1}. Mansour [18] call the sequence defined by (1) a Horadam sequence, which was introduced in 1965 by Horadam [12]. Mansour [18] also obtain the generating functions for powers of a Horadam sequence. A survey on the Horadam sequences is given by Larcombe, Bagdasar, and Fennessey [15]. For the sake of readers’ convenience, we prove the following theorem of the second order LDSs by using our results in [7].

Theorem 1. Let (a_{n}) be a second order linear homogeneous recursive sequence defined by (1) with an arbitrary a_{1}. Then (a_{n}) is an LDS if and only if the initial condition a_{0} = 0, while the initial condition a_{1} is arbitrary.

Proof. Let α and β be two roots of the characteristic polynomial x^{2} − px − q of (a_{n}). They may be the same. From [7], we have the expression of a_{n} in terms of α and β:

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}  (2)

Particularly, for a_{0} = 0, we have

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

It is easy to check that m|n implies a_{m}|a_{n}. Hence, (a_{n}) is an LDS, which proves the sufficiency.

For the necessity, we consider a second order linear homogenous recursive sequence (F_{n}), where F_{n} = F_{n−1} + F_{n−2} with initial conditions F_{0} = F_{1} = 1. It is obvious that (F_{n}) is not an LDS, as for instance F_{2} = 2 is not a divisor of F_{4} = 5. From (2), if a_{n} is an LDS and α, β ≠ 0, then a_{1}|a_{2} implies

a_{1}| (a_{1}(α + β) − a_{0}αβ) .

Consequently, a_{0} = 0 for an arbitrary a_{1}. Similarly, for other cases one can show that a second order linear homogenous recursive sequence (a_{n}) defined by (1) with an arbitrary a_{1} is an LDS, and its initial condition a_{0} must be zero.

Remark 2. In the articles by Florez, Higuita, and Mukherjees [5], Hilton, Pedersen, Vrancken [8], Hoggatt and Bicknell-Johnson [9], and McDaniel [19], the GCD properties of Fibonacci numbers and polynomials, Lucas numbers, the Morgan-Voyce polynomials, the Chebyshev polynomials, and more general polynomials are studied, in which the condition of that the first initial condition of the recurrence relation must be zero is not needed. Here elements in a GCD set is a recursive sequence {a_{n}} satisfying gcd(a_{n}, a_{m}) = a_{gcd(n,m)}. The collection of all LDS is a subset of GCD set because a (recursive) LDS sequence {a_{n}} has the property that n|m implies a_{n}|a_{m} means gcd(a_{n}, a_{m}) = a_{n} = a_{gcd(n,m)}. Hence, the set of LDS is the subset of GCD set characterized by a_{0} = 0.

Example 3. From Theorem 1, the Fibonacci number sequence (F_{n}), where F_{n} = F_{n−1}+F_{n−2} (n ≥ 2) with initial conditions F_{0} = 0 and F_{1} = 1, the Pell number sequence (P_{n}), where P_{n} = 2P_{n−1} + P_{n−2} (n ≥ 2) with initial conditions P_{0} = 0 and P_{1} = 1, and the Mersenne number sequence (M_{n}), where M_{n} = 3M_{n−1} − 2M_{n−2} (n ≥ 2) with the initial conditions M_{0} = 0 and M_{1} = 1 are LDSs.

Based on Theorem 1 and equation (3), we consider a class of the LDS (w_{n}) defined by

w_{n} = c\frac{α^{n} − β^{n}}{α − β} ,  (4)

where c, α, and β are constants, and α ≠ β. We have the following result.

Theorem 4. Let α and β be distinct real (or complex) numbers, and let sequence (w_{n}) be defined by (4). Then (w_{n}) is a second order linear homogenous recursive sequence with w_{0} = 0 and w_{1} = c. Also, (w_{n}) is an LDS of order 2.

Proof. From (3), we know that (w_{n}) is a linear homogeneous recursive sequence with initial values w_{0} = 0 and w_{1} = c, and the recurrence relation w_{n+2} = (α + β)w_{n+1} − αβw_{n}. Since w_{0} = 0, (w_{n}) is an LDS.

Example 5. It is obvious that all sequences shown in Example 3 belong to the class (w_{n}). Particularly, the alternative form (w_{n}) of the Fibonacci sequence (F_{n}) is the Binet formula:

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

Remark 6. Let D = p^{2} + 4q, where p and q are the coefficients of the recurrence relation (1), and let (\frac{D}{r}) be the Legendre symbol, i.e.,

(\frac{D}{r}) ≡ D^{(r−1)/2} (mod r),

where r is any odd prime. From Euler’s criterion, (\frac{D}{r}) = −1 if there is no integer x such that D ≡ x^{2} (mod r), otherwise (\frac{D}{r}) = 1. Niven, Zuckerman, and Montgomery [21, p. 202 and p. 205] give the following results of (a_{n}) defined by (1) with a_{0} = 0 and a_{1} = 1:

(1) If (\frac{D}{r}) = −1, then r|a_{r+1}.

(2) If (\frac{D}{r}) = 1, then a_{r+1} ≡ p (mod r).

(3) If (\frac{D}{r}) = 1, then qa_{r−1} ≡ 0 (mod r).

(4) a_{r} ≡ (\frac{D}{r}) (mod r).

Thus, for k ∈ ℕ we have the following results on the divisibility of (w_{n}) shown in (4) with c = 1, accordingly:

(1) If (\frac{D}{r}) = −1, then r|w_{k(r+1)}.

(2) If (\frac{D}{r}) = 1 and p ≡ 0 (mod r), then r|w_{k(r+1)}.

(3) If (\frac{D}{r}) = 1 and gcd(q, r) = 1, then r|w_{k(r−1)}.

(4) If r|D, then r|w_{kr}.

The result shown in Theorem 4 has a higher order analogy. For instance, Roettger [22] and Mülcer, Roettger, and Williams [20] use the third order linear homogenous recurrence relation with the characteristic polynomial x^{3} − P_{1}x^{2} + P_{2}x − P_{3} to construct the following order 6 LDS

C_{n} = (\frac{α^{n} − β^{n}}{α − β} ) (\frac{β^{n} − γ^{n}}{β − γ} ) (\frac{γ^{n} − α^{n}}{γ − α} ) ,

where α, β, and γ are the roots of x^{3} − P_{1}x^{2} + P_{2}x − P_{3}. The results for C_{n} is stated more generally in [2, Section 1.3].

3 Higher order divisibility sequences

If an LDS satisfies a linear recurrence relation of order r, we call it an LDS of order r. Here, r is the degree of the characteristic polynomial of the recurrence. The best known example of such a sequence of order 2 is the Lucas sequence. In Section 2, we present some general results on the LDSs of order 2 and many examples. In this section we use LDSs of order 2 and the Hadamard product of sequences to discuss higher order LDSs. Some algebraic structure of linearly recursive sequences under the Hadamard product can be found in Larson and Taft [16].

Let (a_{n}) be an rth order linear homogeneous recursive sequence satisfying

c_{0}a_{n} + c_{1}a_{n−1} + ⋯ + c_{r}a_{n−r} = 0  (5)

for 1 ≤ r ≤ n with c_{0}, c_{r} ≠ 0. If (α_{k})_{k=1}^{r} are the distinct roots of the characteristic equation

P_{r}(x) = c_{0}x^{r} + c_{1}x^{r−1} + ⋯ + c_{r−1}x + c_{r} = 0,  (6)

then

a_{n} = A_{1}(α_{1})^{n} + A_{2}(α_{2})^{n} + ⋯ + A_{r}(α_{r})^{n},  (7)

where A_{k} are determined by the (c_{k}) and the initial conditions. Hence, if (a_{n}) is known, then the characteristic polynomial of (a_{n}) can be written as

P_{r}(x) = c_{0}(x − α_{1})(x − α_{2}) ⋯ (x − α_{r}),  (8)

which is equivalent to the linear homogeneous recurrence relation (5). Based on this observation, we give a unified approach of the construction of higher order linear homogeneous recursive sequences. We start from the fourth order linear homogeneous recursive sequences.

Theorem 7. Let (a_{n}) and (b_{n}) be two second order linear homogenous recursive sequences defined by (1) with initials a_{0} = b_{0} = 0 and arbitrary initials a_{1} and b_{1} as well as different recursive coefficient pairs (p_{1}, q_{1}) and (p_{2}, q_{2}). Suppose the roots of the equation x^{2} − p_{1}x − q_{1} = 0, denoted by α_{1} and β_{1}, are distinct, and the roots α_{2} and β_{2} of the equation and x^{2} − p_{2}x − q_{2} = 0 are distinct. Then the sequence (a_{n}b_{n}) is a fourth order LDS with initial conditions a_{i}b_{i}, 0 ≤ i ≤ 3, where a_{0}b_{0} = 0.

Proof. Sequences (a_{n}) and (b_{n}) are LDSs by Theorem 1. We may use (3) to write a_{n}b_{n} as the following expressions based on the different type of the roots of the characteristic equations x^{2} − p_{1}x − q_{1} = 0 and x^{2} − p_{2}x − q_{2} = 0 of the sequences (a_{n}) and (b_{n}), respectively.

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

Clearly, (a_{n}b_{n}) is also an LDS. Furthermore, we have

a_{n}b_{n} = \frac{a_{1}b_{1}}{(α_{1} − β_{1})(α_{2} − β_{2})} (α_{1}^{n} − β_{1}^{n}) (α_{2}^{n} − β_{2}^{n})

= \frac{a_{1}b_{1}}{(α_{1} − β_{1})(α_{2} − β_{2})} ((α_{1}α_{2})^{n} − (α_{1}β_{2})^{n} − (α_{2}β_{1})^{n} + (β_{1}β_{2})^{n}) .

Hence, the sequence (a_{n}b_{n}) satisfies a linear homogenous recurrence relation with the characteristic equation

(x − α_{1}α_{2})(x − α_{1}β_{2})(x − β_{1}α_{2})(x − β_{1}β_{2})
= x^{4} − p_{1}p_{2}x^{3} − (p_{1}^{2}q_{2} + p_{2}^{2}q_{1} + 2q_{1}q_{2})x^{2} − p_{1}p_{2}q_{1}q_{2}x + q_{1}^{2}q_{2}^{2} = 0,

(9)

which implies that (a_{n}b_{n}) is a fourth order linear homogeneous recursive sequence with initial conditions a_{i}b_{i}, 0 ≤ i ≤ 3, where a_{0}b_{0} = 0.

Example 8. Let (F_{n}), (P_{n}), and (M_{n}) be the Fibonacci number sequence, the Pell number sequence, and the Mersenne number sequence, respectively. From Theorem 7 and Example 3, all of the following sequences are fourth order LDSs:

(F_{n}P_{n}), (F_{n}M_{n}), and (P_{n}M_{n})

with characteristic equations x^{4} − 2x^{3} − 7x^{2} − 2x + 1 = 0, x^{4} − 3x^{3} − 3x^{2} + 6x + 4 = 0, and x^{4} − 6x^{3} + 3x^{2} + 12x + 4 = 0, and initial conditions F_{i}P_{i}, F_{i}M_{i}, and P_{i}M_{i}, 0 ≤ i ≤ 3, respectively.

Using a similar argument, one may construct high even order LDSs, such as a sixth order LDS, (F_{n}P_{n}M_{n})_{n≥0}.

We now consider the construction of high odd order LDSs based on the following result.

Theorem 9. Let (a_{n}) be a second order linear homogenous recursive sequence defined by (1) with initial conditions a_{0} = 0 and a_{1} = 1. Suppose the roots of the characteristic equation x^{2} − px − q = 0 of (a_{n}) are distinct and denoted by α and β. Then the sequence (a_{n}^{2}) is a third order LDS with the characteristic equation

x^{3} − (p^{2} + q)x^{2} − q(p^{2} + q)x + q^{3} = 0  (10)

with initial conditions a_{0}^{2} = 0, a_{1}^{2}, and a_{2}^{2}.

Proof. Equation (3) implies

a_{n}^{2} = \frac{(α^{n} − β^{n})^{2}}{(α − β)^{2}} = \frac{1}{(α − β)^{2}} ((α^{2})^{n} − 2(αβ)^{n} + (β^{2})^{n})

for n ≥ 2. Thus, (7) and (8) imply the following characteristic polynomial

(x − α^{2})(x − αβ)(x − β^{2})
= x^{3} − ((α + β)^{2} − αβ)x^{2} + αβ(α^{2} + β^{2} + αβ)x − (αβ)^{3}
= x^{3} − (p^{2} + q)x^{2} − q(p^{2} + q)x + q^{3}.

Recall that αβ = −q and α + β = p. We have that (w_{n} = a_{n}^{2}) is an LDS satisfying the third linear homogeneous recurrence relation

w_{n+3} = (p^{2} + q)w_{n+2} + q(p^{2} + q)w_{n+1} − q^{3}w_{n}, q ≠ 0.

The above recurrence relation is linear homogeneous because the powers of the sequences are 1 and it has no constant term, which completes the proof.

Example 10. Let (F_{n}), (P_{n}), and (M_{n}) be the Fibonacci number sequence, the Pell number sequence, and the Mersenne number sequence, with initial conditions F_{0} = 0 and F_{1} = 1, initial conditions P_{0} = 0 and P_{1} = 1, and the initial conditions M_{0} = 0 and M_{1} = 1, respectively. Then (w_{n} = F_{n}^{2}) is a third order LDS satisfying the linear homogeneous recurrence relation

w_{n+3} = 2w_{n+2} + 2w_{n+1} − w_{n}

with initial conditions w_{0}, w_{1}, and w_{2}. The sequence (u_{n} = P_{n}^{2}) is a third order LDS with linear homogeneous recurrence relation

u_{n+3} = 5u_{n+2} + 5u_{n+1} − u_{n}

with initial conditions u_{0}, u_{1}, and u_{2}. The sequence (v_{n} = M_{n}^{2}) is a third order LDS satisfying the linear homogeneous recurrence relation

v_{n+3} = 7v_{n+2} − 14v_{n+1} + 8v_{n}

with initial conditions v_{0}, v_{1}, and v_{2}.

Similarly, we may construct higher odd order LDSs, such as a fifth order LDS, (F_{n}^{2}P_{n}). An analogy of Theorem 9 is shown below.

Theorem 11. Let (a_{n}) be a second order linear homogenous recursive sequence defined by (1) with initial conditions a_{0} = 0 and a_{1} = 1. Suppose the roots of the characteristic equation x^{2} − px − q = 0 of (a_{n}) are distinct and denoted by α and β. Then the sequence (a_{n}^{3}) is a fourth order LDS with the characteristic equation

x^{4} − p(p^{2} + 2q)x^{3} − q((p^{2} + 2q)^{2} − 2q^{2} − p^{2}q)x^{2} + pq^{3}(p^{2} + 2q)x + q^{6} = 0  (11)

with initial conditions a_{0}^{3} = 0 and a_{i}^{3}, 1 ≤ i ≤ 3.

Proof. Similar to the proof of Theorem 9, Equation (3) implies

a_{n}^{3} = \frac{(α^{n} − β^{n})^{3}}{(α − β)^{3}} = \frac{1}{(α − β)^{3}} ((α^{3})^{n} − 3(α^{2}β)^{n} + 3(αβ^{2})^{n} − (β^{3})^{n})

for n ≥ 2. Thus, (7) and (8) imply the following characteristic polynomial

(x − α^{3})(x − α^{2}β)(x − αβ^{2})(x − β^{3})
= x^{4} − [α^{3} + αβ(α + β) + β^{3}]x^{3} + αβ[α^{4} + αβ(α + β)^{2} + β^{4}]x^{2}
−α^{3}β^{3}[α^{2}(α + β) + β^{2}(α + β)]x + (αβ)^{6}
= x^{4} − (α + β)(α^{2} + β^{2})x^{3} + αβ((α^{2} + β^{2})^{2} − 2(αβ)^{2} + αβ(α + β)^{2})x^{2}
−(αβ)^{3}(α + β)(α^{2} + β^{2})x + (αβ)^{6}
= x^{4} − p(p^{2} + 2q)x^{3} − q((p^{2} + 2q)^{2} − 2q^{2} − p^{2}q)x^{2} + pq^{3}(p^{2} + 2q)x + q^{6}.

Recall that αβ = −q and α + β = p. We have that (w_{n} = a_{n}^{3}) is an LDS satisfying the third order linear homogeneous recurrence relation

w_{n+4} = p(p^{2} + 2q)w_{n+3} + q[(p^{2} + 2q)^{2} − 2q^{2} − p^{2}q]w_{n+2}
−pq^{3}(p^{2} + 2q)w_{n+1} − q^{6}w_{n}.

The proof is complete.

Example 12. Let (F_{n}), (P_{n}), and (M_{n}) be the Fibonacci number sequence, the Pell number sequence, and the Mersenne number sequence, with initial conditions F_{0} = 0 and F_{1} = 1, initial conditions P_{0} = 0 and P_{1} = 1, and the initial conditions M_{0} = 0 and M_{1} = 1, respectively. Then (w_{n} = F_{n}^{3}) is a fourth order LDS satisfying the linear homogeneous recurrence relation

w_{n+4} = 3w_{n+3} + 6w_{n+2} − 3w_{n+1} − w_{n}

with initial conditions w_{0}, w_{1}, w_{2}, and w_{3}. The sequence (u_{n} = P_{n}^{3}) is a fourth order LDS with linear homogeneous recurrence relation

u_{n+4} = 12u_{n+3} + 30u_{n+2} − 12u_{n+1} − u_{n}

with initial conditions u_{0}, u_{1}, u_{2}, and u_{3}. The sequence (v_{n} = M_{n}^{3}) is a fourth order LDS satisfying linear homogeneous recurrence relation

v_{n+4} = 15v_{n+3} − 70v_{n+2} + 120v_{n+1} − 64v_{n}

with initial conditions v_{0}, v_{1}, v_{2}, and v_{3}.

Bala [1] showed the following fourth order LDS given by Williams and Guy, W_{n} = W_{n}(P_{1}, P_{2}, Q) with integer parameters P_{1}, P_{2}, and Q:

W_{n} = \frac{t_{n}(α, Q) − t_{n}(β, Q)}{α − β}, n ≥ 1,  (12)

where α + β = P_{1}, αβ = −P_{2}, and t_{n}(x, Q) denote the nth monic Dickson polynomial of the first kind with parameter Q. The first few monic Dickson polynomials are

t_{0}(x, Q) = 2,
t_{1}(x, Q) = x,
t_{2}(x, Q) = x^{2} − 2Q,
t_{3}(x, Q) = x^{3} − 3xQ,
⋮

The recurrence equation for the sequence W_{n} is

W_{n} = P_{1}W_{n−1} + (P_{2} − 2Q)W_{n−2} + P_{1}QW_{n−3} − Q^{2}W_{n−4},  (13)

where the initial conditions can be found by using the Dickson polynomials shown above, namely,

W_{0} = \frac{t_{0}(α, Q) − t_{0}(β, Q)}{α − β} = \frac{2 − 2}{α − β} = 0,

W_{1} = \frac{t_{1}(α, Q) − t_{1}(β, Q)}{α − β} = \frac{α − β}{α − β} = 1,

W_{2} = \frac{t_{2}(α, Q) − t_{2}(β, Q)}{α − β} = \frac{α^{2} − β^{2}}{α − β} = α + β = P_{1},

W_{3} = \frac{t_{3}(α, Q) − t_{3}(β, Q)}{α − β} = \frac{α^{3} − β^{3}}{α − β} − 3Q

= (α + β)^{2} − αβ − 3Q = P_{1}^{2} + P_{2} − 3Q.

Hence, we establish the following result.

Theorem 13. The Williams and Guy fourth order LDS (W_{n}) defined in (12) by using the second order characteristic equation x^{2} − P_{1}x − P_{2} = 0 and the Dickson polynomial sequence of the first kind with parameter Q is equivalent to our fourth order LDS shown in Theorem 7.

Proof. From their recurrence relation (13), we obtain the characteristic equation of (W_{n}) as

x^{4} − P_{1}x^{3} − (P_{2} − 2Q)x^{2} − P_{1}Qx + Q^{2} = 0.  (14)

Comparing (14) and the characteristic equation (9),

x^{4} − p_{1}p_{2}x^{3} − (p_{1}^{2}q_{2} + p_{2}^{2}q_{1} + 2q_{1}q_{2})x^{2} − p_{1}p_{2}q_{1}q_{2}x + q_{1}^{2}q_{2}^{2} = 0,

of the fourth order LDS shown in Theorem 7, we know they are equivalent when

P_{1} = p_{1}p_{2},
P_{2} = p_{1}^{2}q_{2} + p_{2}^{2}q_{1} + 4q_{1}q_{2},
Q = q_{1}q_{2},

where p_{i} = α_{i} + β_{i} and q_{i} = −α_{i}β_{i}, i = 1 and 2. Furthermore,

W_{1} = 1 = a_{1}b_{1},

W_{2} = P_{1} = p_{1}p_{2} = (α_{1} + β_{1})(α_{2} + β_{2}) = \frac{α_{1}^{2} − β_{1}^{2}}{α_{1} − β_{1}} \frac{α_{2}^{2} − β_{2}^{2}}{α_{2} − β_{2}} = a_{2}b_{2},

W_{3} = P_{1}^{2} + P_{2} − 3Q = (p_{1}p_{2})^{2} + p_{1}^{2}q_{2} + p_{2}^{2}q_{1} + 4q_{1}q_{2} − 3q_{1}q_{2} = (p_{1}^{2} + q_{1})(p_{2}^{2} + q_{2}) = ((α_{1} + β_{1})^{2} − α_{1}β_{1}) ((α_{2} + β_{2})^{2} − α_{2}β_{2})

= \frac{α_{1}^{3} − β_{1}^{3}}{α_{1} − β_{1}} \frac{α_{2}^{3} − β_{2}^{3}}{α_{2} − β_{2}} = a_{3}b_{3}.

Hence (a_{n}b_{n}) = (W_{n}), completing the proof of the theorem.

Remark 14. In an attempt to extend the second order linear divisibility sequences to sequences of order 4, it becomes necessary to examine odd and even divisibility sequences. Williams and Guy [28] produce some conditions under which certain divisibility sequences of order 4 will be either even or odd.

Remark 15. Recently, B. Torrence and R. Torrence [24] point out that if (a_{n}) is any sequence satisfying the recurrence a_{n+1} = a_{n} + a_{n−1}, then

a_{n+2} = 3a_{n} − a_{n−2},  (15)

which can be simply proved by substituting a_{n+2} = a_{n+1} + a_{n} = 2a_{n} + a_{n−1} on the left-hand side and reducing it to a_{n} = a_{n−1} + a_{n−2}. The Fibonacci and Lucas number sequences, (F_{n}) and (L_{n}), satisfy a_{n+1} = a_{n} + a_{n−1}. Consequently, they also satisfy (15). Thus (F_{n}) with F_{0} = 0 can be considered as an LDS of order 4. Thus, the recurrence relation (15) inspires a way to lift the order of an LDS. We now extend this idea to lift an LDS to any order. For instance, from a_{n+2} = a_{n+1} + a_{n}, we have

a_{n+3} = a_{n+2} + a_{n+1} = 2a_{n+1} + a_{n},

which implies that (F_{n}) with F_{0} = 0 is an LDS of order 3. From a_{n+3} = 2a_{n+1} + a_{n} we can also obtain

a_{n+4} = 2a_{n+2} + a_{n+1} = 2a_{n+2} + (a_{n+2} − a_{n}) = 3a_{n+2} − a_{n},

which is (15). This process can continue to lift an LDS satisfying a_{n+2} = a_{n+1} + a_{n} with a_{0} = 0 to any order.

Remark 16. For Fibonacci sequence (F_{n}), Brualdi [3, p. 258] mention the following fifth order LDS, which can be derived from the second order linear recurrence relation.

F_{n} = 5F_{n−4} + 3F_{n−5},

where F_{0} = 0, F_{1} = 1, F_{2} = 1, F_{3} = 2, and F_{4} = 3. It can be seen from the above formula that 5|F_{n} if and only if 5|n. Similarly, 2|F_{n} if and only if 3|n, 3|F_{n} if and only if 4|n, and 4|F_{n} if and only if 6|n.

4 Polynomial divisibility sequences

Similar to number LDSs, we may define polynomial LDSs. Polynomial LDSs are recursive polynomial sequences (a_{n}(x)) satisfying linear homogeneous recurrence relations with constant coefficients, with the property that whenever m|n, then a_{m}(x)|a_{n}(x). We now start from the second order divisibility polynomial sequences, i.e., divisibility polynomial sequences satisfying linear homogeneous recurrence relations of the second order. If the coefficients of the linear recurrence relation of a function sequence (a_{n}(x)) of order 2 are real or complex-value functions of variable x, i.e.,

a_{n}(x) = p(x)a_{n−1}(x) + q(x)a_{n−2}(x),  (16)

where p^{2}(x) + 4q(x) ≥ 0 is assumed, we obtain a function sequence of order 2 with initial conditions a_{0}(x) and a_{1}(x). In particular, if all of p(x), q(x), a_{0}(x) and a_{1}(x) are polynomials, then the corresponding sequence (a_{n}(x)) is a polynomial sequence of order 2. Denote the solutions of

t^{2} − p(x)t − q(x) = 0

by α(x) and β(x). Then

α(x) = \frac{1}{2}(p(x) + \sqrt{p^{2}(x) + 4q(x)}), β(x) = \frac{1}{2}(p(x) − \sqrt{p^{2}(x) + 4q(x)}).  (17)

Similar to Theorem 1, we have

Theorem 17. Let (a_{n}(x)) be a second order linear homogeneous recursive polynomial sequence defined by (16). Then (a_{n}(x)) is a divisibility sequence if and only if the initial condition a_{0}(x) = 0, while the initial condition a_{1}(x) is arbitrary.

Proof. Let (a_{n}(x)) be a sequence of order 2 satisfying the linear recurrence relation (16). Then by [7] we have

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

where α(x) and β(x) are shown in (17). If a_{0}(x) = 0, then

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

which implies that (a_{n}(x)) is a divisibility sequence. The sufficiency is proved. Conversely, we may prove the necessity.

Example 18. Some second order polynomial LDSs can be found in various literature. For instance, Webb and Parberry [26] show that the second order linear homogeneous recursive polynomial sequence (P_{n}(x)) defined by

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

with P_{0}(x) = 0 and P_{1}(x) = 1 is an LDS. (P_{n}(x)) is the Fibonacci polynomial sequence. Obviously, when x = 1 and x = 2, the sequences (P_{n}(1) = F_{n}) and (P_{n}(2) = P_{n}) are the Fibonacci number sequence and the Pell number sequence, respectively.

Hoggatt Jr., Bicknell, and King [10] and Koshy [14, p. 461] show the second order divisibility polynomial sequence (P_{n}(x)) defined by

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

where P_{0}(x) = 0 and P_{1}(x) = 1. Schur [23, p. 17] suggest the modification of the degree of Dickson polynomials E_{n}^{∗}(x, a) as follows:

E_{n+1}^{∗}(x, a) = 2xE_{n}^{∗}(x, a) − aE_{n−1}^{∗}(x, a)

with the initial conditions E_{0}^{∗}(x, a) = 0 and E_{1}^{∗}(x, a) = 1, which can also be seen in Lidl, Mullen, and Turnwald [17, p. 17 ]. Then (E_{n}^{∗}(x, a)) is a second order divisibility polynomial sequence.

The above results on the linear homogeneous recursive polynomial sequence of one variable can be easily extended to the case of multivariate polynomials. Hence, a divisibility multivariate polynomial sequence can be defined similarly. For instance, Hoggatt and Long [11] present a bivariate second order divisibility polynomial sequence (U_{n}(x, y)), whose elements can be written as

U_{n}(x, y) = xU_{n−1}(x, y) + yU_{n−2}(x, y), n ≥ 2,

where U_{0}(x, y) = 0 and U_{1}(x, y) = 1.

We may use (16) to define the linear homogeneous recursive multivariate polynomial sequence, in which the only change is to consider all functions a_{n}(x), p(x), q(x), as well as the corresponding root functions α(x) and β(x) as the mappings from ℝ^{n} to ℝ. As an analogy to Theorems 7 and 9, we have the following results.

Theorem 19. Let (a_{n}(x)) and (b_{n}(x)) be two second order linear homogenous recursive polynomial sequences defined by (16) of n variables with initial zero condition a_{0}(x) = b_{0}(x) = 0 and arbitrary a_{1}(x) and b_{1}(x) as well as different recursive coefficient pairs (p_{1}(x), q_{1}(x)) and (p_{2}(x), q_{2}(x)). Suppose the roots of the equation t^{2} − p_{1}(x)t − q_{1}(x) = 0 are distinct and denoted by α_{1}(x) and β_{1}(x), and the roots α_{2}(x) and β_{2}(x) of the equation and t^{2} − p_{2}(x)t − q_{2}(x) = 0 are distinct. Then the sequence (a_{n}(x)b_{n}(x)) is a fourth order LDS with initial conditions a_{i}(x)b_{i}(x), 0 ≤ i ≤ 3, where a_{0}(x)b_{0}(x) = 0.

Theorem 20. Let (a_{n}(x)) be a second order linear homogenous recursive polynomial sequence defined by (16) with the initial zero condition a_{0}(x) = 0 and arbitrary condition a_{1}(x). Suppose the roots of the characteristic equation t^{2} − p(x)t − q(x) = 0, q(x) ≠ 0, of (a_{n}(x)) are distinct and denoted by α(x) and β(x). Then the sequence (a_{n}(x)^{2}) is a third order LDS with initial conditions a_{0}^{2}(x) = 0, a_{1}^{2}(x), and a_{2}^{2}(x).

The proofs of Theorems 19 and 20 are similar to the proofs of Theorems 7 and 9 and are omitted.

5 Acknowledgments

The authors thank Mr. Scott MacDonald from the Mathematics Learning Center at UNLV for his comments and corrections on an earlier version of this manuscript and the proof reading. The authors thank the referee and editor for their careful reading and helpful suggestions.

References

[1] P. Bala, Linear divisibility sequences and Chebyshev polynomials, manuscript, March

    2014. Available at https://oeis.org/A100047/a100047.pdf.

[2] J.-P. Bézivin, A. Pethö, and A. J. van der Poorten, A full characterization of divisibility sequences, Amer. J. Math. 112 (1990), 985–1001.

[3] R. A. Brualdi, Introductory Combinatorics, Fifth edition. Pearson Prentice Hall, 2010.

[4] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, AMS, 2003.

[5] R. Florez, R. Higuita, and A. Mukherjees, Characterization of the Fibonacci GCD property for generalized Fibonacci polynomials, https://arxiv.org/abs/1701.06722.

[6] M. Hall, Divisibility sequences of third order, Am. J. Math. 58 (1936), 577–584.

[7] T. -X. He and P. J.-S. Shiue, On sequences of numbers and polynomials defined by linear recurrence relations of order 2, Int. J. Math. Math. Sci. 2009, Art. ID 709386.

[8] P. Hilton, J. Pedersen, and L. Vrancken, On certain arithmetic properties of Fibonacci and Lucas numbers, Fibonacci Quart. 33 (1995), 211–217.

[9] V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Divisibility properties of polynomials in Pascal’s triangle, Fibonacci Quart. 16 (1978), 501–513.

[10] V. E. Hoggatt Jr., M. Bicknell, and E. L. King, Fibonacci and Lucas triangles. Fibonacci Quart. 10 (1972), 555–560.

[11] V. E. Hoggatt, Jr., and C. T. Long, Divisibility properties of generalized Fibonacci polynomials, Fibonacci Quart. 12 (1974), 113–122.

[12] A. F. Horadam, Basic properties of a certain generalized sequence of numbers, Fibonacci Quart. 3 (1965), 161–176.

[13] P. Ingram and J. H. Silverman, Primitive divisors in elliptic divisibility sequences, in D. Goldfeld, J. Jorgenson, P. Jones, D. Ramakrishnan, K. A. Ribet, and J. Tate, eds., Number Theory, Analysis, and Geometry, In Memory of Serge Lang, Springer, 2012, pp. 243–271.

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

[15] P. J. Larcombe, O. Bagdasar, and E. J. Fennessey, Horadam sequences: a survey, Bull. Inst. Combin. Appl. 67 (2013), 49–72.

[16] R. G. Larson and E. J. Taft, The algebraic structure of linearly recursive sequences under Hadamard product, Israel J. Math. 72 (1990), 118–132.

[17] R. Lidl, G. L. Mullen, and G. Turnwald, Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Mathematics, Vol. 65. Longman Scientific & Technical and John Wiley & Sons, Inc., 1993.

[18] T. Mansour, A formula for the generating functions of powers of Horadam’s sequence, Australasian J. Combin., 30 (2004), 207–212.

[19] W. L. McDaniel, The G.C.D. in Lucas sequences and Lehmer number sequences, Fibonacci Quart. 29 (1991), 24–29.

[20] S. Müller, E. Roettger, and H. C. Williams, A cubic extension of the Lucas functions, Ann. Sci. Math. Québec, 33 (2009), 185–224.

[21] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, Fifth Ed., John Wiley & Sons, Inc., 1991.

[22] E. Roettger, A Cubic Extension of the Lucas Functions, Ph.D. thesis, University of Calgary, 2009.

[23] I. Schur, Gesammelte Abhandlungen, Band III. Springer-Verlag, 1973.

[24] B. Torrence and R. Torrence, Fibonacci, Lucas, and a game of chance, Math. Mag. 89 (2016), 342–351.

[25] M. Ward, A note on divisibility sequences, Bull. Amer. Math. Soc. 45 (1939), 334–336.

[26] W. A. Webb and E. A. Parberry, Divisibility properties of Fibonacci polynomials, Fibonacci Quart. 7 (1969), 457–463.

[27] H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Int. J. Number Theory, 7 (2011), 1255–1277.

[28] H. C. Williams and R. K. Guy, Odd and even linear divisibility sequences of order 4, Integers, 15 (2015), Paper No. A33.

2010 Mathematics Subject Classification: Primary 11B39, Secondary 11B37, 05A15, 33C45. Keywords: linear homogeneous recursive sequence, divisibility sequence, Fibonacci sequence, Lucas sequence, Fibonacci polynomial.

(Concerned with sequence \underline{A100047}.)

Received March 25 2017; revised versions received April 2 2017; August 26 2017; September 5 2017; September 7 2017. Published in Journal of Integer Sequences, September 8 2017.

Return to Journal of Integer Sequences home page.