Greatest Common Divisors of Shifted Horadam Sequences

Kwang-Wu Chen and Yu-Ren Pan^{1}^{,}^{2}

Department of Mathematics University of Taipei No. 1, Aiguo West Road, Taipei 10048 Taiwan

                 kwchen@uTaipei.edu.tw
               YuRen.Pan.0117@gmail.com

Abstract

A Horadam sequence is a sequence generated by the second-order linear homogeneous recurrence relation W_{n} = pW_{n−1} − qW_{n−2}; W_{0} = a, W_{1} = b. The sequence of Fibonacci numbers is a particular case of a Horadam sequence. For any fixed integers s, t, and k, we investigate the boundedness and periodicity of the sequence (gcd(W_{n} + s, W_{n+k} + t)) in this paper.

1 Introduction

The general second-order linear homogeneous recurrence relation

W_{n} = pW_{n−1} − qW_{n−2}; W_{0} = a, W_{1} = b,  (1)

with arbitrary values a, b, p, and q generates the sequence W(a, b; p, q) = (W_{n}(a, b; p, q))_{n∈ℤ} which we call a Horadam sequence after the work of Horadam [5]. In general, we also call (W_{n}(a, b; p, q)) a second-order recurrence sequence. We usually omit the (a, b; p, q) if it does not cause ambiguity. For any sequence (W_{n}), we define [5, Eq. (1.9)]

1This work is partially supported by the Ministry of Science and Technology of Taiwan under Grant No.

MOST 107CFA9600025.

2Corresponding author.

e(W) := pab − qa^{2} − b^{2} = W_{0}W_{2} − W_{1}^{2}.

Let U(p, q) = (U_{n}(p, q))_{n∈ℤ} and V(p, q) = (V_{n}(p, q))_{n∈ℤ} denote the Lucas sequence of the first kind and the second kind respectively, which can be defined by

U(p, q) = W(0, 1; p, q) and V(p, q) = W(2, p; p, q).

Fibonacci numbers (F_{n}) = U(1, −1) and Lucas numbers (L_{n}) = V(1, −1) are the most famous particular cases of Lucas sequences. Conversely, the families of sequences W(a, b; p, q), U(p, q), and V(p, q) can be seen as generalizations of Fibonacci numbers and Lucas numbers.

Horadam and Lucas sequences have several relations, such as the fact [5, Eq. (4.10)] that

V_{n} = U_{2n}/U_{n},  (2)

and the known expression [5, Eq. (2.14)]

W_{n} = bU_{n} − aqU_{n−1}.  (3)

Also, for any integers n, m, and k, we have the identity [5, p. 171]

W_{n}W_{m} − W_{n+1}W_{m−1} = q^{k}(W_{n−k}W_{m−k} − W_{n−k+1}W_{m−k−1}).  (4)

The sequence (W_{n}) = W(a, b; p, q) can be defined in any number system, but it is often considered in integers. Although (W_{n}) is usually considered with indices in natural numbers, we can extend the indices to include negative integers by the relation W_{n−2} = pW_{n−1}/q − W_{n}/q if q ≠ 0. Note that if (W_{n}) takes integer values at non-negative indices and |q| = 1, then the terms with negative index are also integers.

For any sequence (W_{n}) and any integer s, we consider a slightly different sequence (W_{n} + s) which we call a shifted sequence. Chen [1] showed that the gcds of shifted Fibonacci numbers gcd(F_{n} + s, F_{n+1} + s) are bounded if s ≠ ±1. This case is not unique. Ray and Pradhan [9] found that the gcds of shifted balancing numbers gcd(B_{n}−s, B_{n+1}−6s) with (B_{n}) := U(6, 1) are also bounded when s ≠ ±1. Additionally, for f(n) := W_{n}(a, b; p, −1), Spilker [10] showed that t_{s}(n) := gcd(f(n) + s, f(n + 1) + s) divides an integer m depending on a, b, p, and s. Spilker also proved that t_{s}(n) is simply periodic if m ≠ 0.

Motivated by those three results, we consider a more general case: the greatest common divisor of two shifted sequences (W_{n} + s) and (W_{n+k} + t) with |q| = 1. Not only the Fibonacci and the balancing numbers but also some famous sequences of numbers are under the domain we considered. We list some of the sequences of numbers as follows.

name  a b p q OEIS number
Fibonacci numbers  F_{n} 0 1 1 −1  \underline{A000045}
Lucas numbers  L_{n} 2 1 1 −1  \underline{A000032}
Pell numbers  P_{n} 0 1 2 −1  \underline{A000129}
Pell-Lucas numbers  Q_{n} 2 2 2 −1  \underline{A002203}
balancing numbers  B_{n} 0 1 6 1  \underline{A001110}
Lucas-balancing numbers C_{n} 1 3 6 1  \underline{A001541}

Table 1: Some second-order recurrence sequences with |q| = 1.

In this paper, we settle down all the values of (gcd(W_{n} + s, W_{n+k} + t))_{n∈ℤ} with |q| = 1 for any given s, t, and k. If (gcd(W_{n} + s, W_{n+k} + t)) is bounded, then it must be periodic. If (gcd(W_{n} + s, W_{n+k} + t)) is unbounded, then we can give a method to justify its boundedness and compute the values of the unbounded greatest common divisors gcd(W_{n} + s, W_{n+k} + t).

Let ⟦W ⟧(s, t)_{n} := gcd(W_{n} + s, W_{n+1} + t) for any integers s, t, and any sequence (W_{n}). In this paper, we study the values of ⟦W ⟧(s, t)_{n} with |q| = 1 for any integer n. In Section 2, we extend the methods inspired by Spilker [10] and use them to find a multiple and a period of (⟦W ⟧(s, t)_{n}). The first theorem we proved in Section 2 is the following:

Theorem 1. For any integers s, t, and n,

⟦W(a, b; p, q)⟧(s, t)_{n} divides q^{n} e(W(a, b; p, q)) − e(W(s, t; p, q)).  (5)

For our convenience, let (S_{n}) = W(s, t; p, q) denote the sequence generated by the given shift values s and t. Theorem 1 shows that if q^{n} e(W) − e(S) ≠ 0 and |q| = 1, then the terms of (⟦W ⟧(s, t)_{n}) are bounded by |q^{n} e(W) − e(S)|. We can see how this result helps us determine the value of each bounded term of (⟦W ⟧(s, t)_{n}) in Section 2.

In Section 3, we derive two theorems. The first theorem gives us a way to apply our work to the general case gcd(W_{n} + s, W_{n+k} + t) where n and k are any integers. The second theorem, which provides a way to reduce problems into basic cases, is the following:

Theorem 2. For any integers n and k, if |q| = 1, then we have

⟦W ⟧(S_{0}, S_{1})_{n} = ⟦W ⟧(S_{k}, S_{k+1})_{n+k}.  (6)

In Sections 4 and 5, we use a method inspired by Chen’s work [1] and Conway’s topograph [2, Lecture 1] to compute the values of unbounded (⟦W ⟧(s, t)_{n}) when q^{n} e(W) − e(S) = 0. In Section 6, we show some examples of some famous sequences of numbers.

2 Boundedness and periodicity of (⟦W ⟧(s, t)_{n})

Spilker’s work [10, p. 478] gave a way to find a multiple of ⟦W(a, b; p, −1)⟧(s, s)_{n}. In the following proof, we generalize Spilker’s result into a more general case.

Proof of Theorem 1. By (4), we get

W_{n−1}W_{n+1} − W_{n}^{2} = q^{n−1}(W_{0}W_{2} − W_{1}^{2}) = q^{n−1} e(W).

Let d be the gcd of W_{n} + s and W_{n+1} + t, that is, d = ⟦W ⟧(s, t)_{n}. Then we have

qW_{n−1}W_{n+1} − qW_{n}^{2} = (pW_{n} − W_{n+1})W_{n+1} − qW_{n}^{2}
≡ pst − t^{2} − qs^{2} = e(S) (mod d).

Consequently, we have ⟦W ⟧(s, t)_{n} divides q^{n} e(W) − e(S).

We see that the multiple m = q^{n} e(W)−e(S) could be getting bigger for large n if |q| > 1. However, when |q| = 1, m become some constants as a function of n (depending only on (W_{n}), (S_{n}), and the parity of n). Moreover, if the multiple m is a nonzero constant, then the terms of (⟦W ⟧(s, t)_{n}) are bounded by |m|. We let (W_{n}^{⊕}) and (W_{n}^{⊖}) denote the cases that q = 1 and q = −1 respectively for any sequence (W_{n}).

Corollary 3. For any integers s, t, and n,

⟦W^{⊕}⟧(s, t)_{n} divides e(W^{⊕}) − e(S^{⊕}).

Corollary 4. For any integers s, t, and n,

1. ⟦W^{⊖}⟧(s, t)_{2n−1} divides e(W^{⊖}) + e(S^{⊖});

2. ⟦W^{⊖}⟧(s, t)_{2n} divides e(W^{⊖}) − e(S^{⊖}).

Example 5 ([9, Thm. 3.6, 3.7]). Let (G_{n}^{B}) = W(a, b; 6, 1) be the generalized balancing-like sequences. For any integers s and n, if a^{2} + b^{2} − 6ab − s^{2} ≠ 0, then we have

⟦G^{B}⟧(−s, −6s)_{n} ≤ |a^{2} + b^{2} − 6ab − s^{2}|.

Proof. Since q = 1, (S_{n}^{⊕}) = W(−s, −6s; 6, 1). Then by Corollary 3, for any n,

⟦G^{B}⟧(−s, −6s)_{n} divides e(G^{B}) − e(S^{⊕})
= (6ab − a^{2} − b^{2}) − (6(−s)(−6s) − (−s)^{2} − (−6s)^{2}) = 6ab − a^{2} − b^{2} + s^{2}.

As we mentioned before, if the common multiple 6ab − a^{2} − b^{2} + s^{2} is not zero, then the terms of (⟦G^{B}⟧(−s, −6s)_{n}) are bounded by |6ab − a^{2} − b^{2} + s^{2}|.

Example 6 ([1, Thm. 1, 2]). Let (G_{n}^{F} ) = W(a, b; 1, −1) be the generalized Fibonacci sequences (in Chen’s paper [1], G_{n+1} = G_{n}^{F}). For any integers s and n,

1. if a^{2} − b^{2} + ab + s^{2} ≠ 0, then we have ⟦G^{F} ⟧(s, s)_{2n−1} ≤ |a^{2} − b^{2} + ab + s^{2}|;

2. if a^{2} − b^{2} + ab − s^{2} ≠ 0, then we have ⟦G^{F} ⟧(s, s)_{2n} ≤ |a^{2} − b^{2} + ab − s^{2}|.

Proof. Since q = −1, (S_{n}^{⊖}) = W(s, s; 1, −1). Then by Corollary 4, for any n,

⟦G^{F} ⟧(s, s)_{2n−1} divides e(G^{F}) + e(S^{⊖})
= (ab + a^{2} − b^{2}) + (s^{2} + s^{2} − s^{2}) = ab + a^{2} − b^{2} + s^{2};
⟦G^{F} ⟧(s, s)_{2n} divides e(G^{F}) − e(S^{⊖})
= (ab + a^{2} − b^{2}) − (s^{2} + s^{2} − s^{2}) = ab + a^{2} − b^{2} − s^{2}.

As we mentioned before, on the one hand, if the common multiple ab + a^{2} − b^{2} + s^{2} is not zero, then the terms of (⟦G^{F} ⟧(s, s)_{2n−1}) are bounded by |a^{2} − b^{2} + ab + s^{2}|. On the other hand, if the common multiple ab + a^{2} − b^{2} − s^{2} is not zero, then the terms of (⟦G^{F} ⟧(s, s)_{2n}) are bounded by |a^{2} − b^{2} + ab − s^{2}|.

By using the method inspired by Spilker [10, p. 478], we can find a period of the function n ↦ ⟦W ⟧(s, t)_{n}. The period can help us determine the values of (⟦W ⟧(s, t)_{n}), that is, we only need to compute the values of one period.

Theorem 7. For any linear integer function ϕ(n), if ⟦W ⟧(s, t)_{ϕ(n)} divides a nonzero integer constant m for all integers n, then the function n ↦ ⟦W ⟧(s, t)_{ϕ(n)} is simply periodic. That is to say, there exists an integer ω ≤ m^{2} such that ⟦W ⟧(s, t)_{ϕ(n)} = ⟦W ⟧(s, t)_{ϕ(n+ω)} for all n.

Proof. Since the vector-valued mapping

n ↦ (\begin{matrix}W_{n} mod m \\ W_{n+1} mod m \end{matrix})

has only finitely many values, there are integers ω_{1} and ω_{2} such that 0 ≤ ω_{1} < ω_{2} ≤ m^{2} and

W_{ω_{1}} ≡ W_{ω_{2}} (mod m),  W_{ω_{1}+1} ≡ W_{ω_{2}+1} (mod m).

By the recurrence relation (1), we get W_{ω_{1}+n} ≡ W_{ω_{2}+n} (mod m) for all integer n; together with ω := ω_{2} − ω_{1} ≤ m^{2}, we obtain

W_{n+ω} ≡ W_{n} (mod m) ∀n ∈ ℤ.

Suppose that ϕ(n) = cn + k where c and k are integers. Since ⟦W ⟧(s, t)_{ϕ(n)} divides m for all integers n, we finally get

⟦W ⟧(s, t)_{ϕ(n)} = gcd(W_{ϕ(n)} + s, W_{ϕ(n)+1} + t, m)
= gcd(W_{ϕ(n)+cω} + s, W_{ϕ(n)+cω+1} + t, m) = ⟦W ⟧(s, t)_{ϕ(n+ω)}

This result may not give a way to find the smallest period. Nevertheless, analogously to Spilker’s work, a period ω ≤ m^{2} can be chosen by

W_{ω} ≡ W_{0} = a (mod m),  W_{ω+1} ≡ W_{1} = b (mod m).

3 Transformations

Although our principal work is about ⟦W ⟧(s, t)_{n} = gcd(W_{n} + s, W_{n+1} + t) in this paper, we can still apply our results to gcd(W_{n} + s, W_{n+k} + t) for any integer k. The crucial part is the following lemma, which lets us be able to transform the problems about (W_{n}, W_{n+k}) into problems about (W_{n}, W_{n+1}). That is, we can just study the (W_{n}, W_{n+1})-cases and deal with the demands for (W_{n}, W_{n+k})-cases. Kiliç and Stănică [6, Lem. 1] have proved the following lemma. However, we give a self-contained proof below.

Lemma 8. For any sequence (W_{n}), a subsequence (J_{n}) = (W_{kn+t})_{n∈ℤ} with indices in an arithmetic sequence is again a second-order recurrence sequence; moreover,

(W_{kn+t}) = (J_{n}) = W(W_{t}, W_{k+t}; V_{k}, q^{k}).  (7)

Proof. Let γ = W_{kn−k+t}, and γ^{+} = W_{kn−k+t+1}. By shifting the indices, we have

J_{n−1} = γ = W_{0}(γ, γ^{+}; p, q), J_{n} = W_{k}(γ, γ^{+}; p, q), and J_{n+1} = W_{2k}(γ, γ^{+}; p, q).

By (3), we get J_{n} = γ^{+}U_{k} − γqU_{k−1}, so that γ^{+} = (1/U_{k})J_{n} + γq(U_{k−1}/U_{k}). Then by (2) and (3), we obtain

J_{n+1} = γ^{+}U_{2k} − γqU_{2k−1}

= \frac{U_{2k}}{U_{k}} J_{n} − γq (U_{2k−1} − \frac{U_{k−1}}{U_{k}} U_{2k}) = V_{k}J_{n} − q (\frac{U_{2k−1}U_{k} − U_{2k}U_{k−1}}{U_{k}} ) J_{n−1}.

Applying (4) with k − 1, since U_{0} = 0 and U_{1} = 1, we have

J_{n+1} = V_{k}J_{n} − q^{k} (\frac{U_{k}U_{1} − U_{k+1}U_{0}}{U_{k}} ) J_{n−1} = V_{k}J_{n} − q^{k}J_{n−1},

which form a recurrence relation (1) for any n. In conclusion, W_{kn+t} = J_{n} = W_{n}(A, B; P, Q) where A = J_{0} = W_{t}, B = J_{1} = W_{k+t}, P = V_{k}, and Q = q^{k}.

Example 9. By Lemma 8, we get U_{kn} = W_{k}(0, U_{n}; V_{n}, q^{n}) = U_{n} · U_{k}(V_{n}, q^{n}). Then we can conclude that

\frac{U_{2n}}{U_{n}} = U_{2}(V_{n}, q^{n}) = V_{n}, \frac{U_{3n}}{U_{n}} = U_{3}(V_{n}, q^{n}) = V_{n}^{2} − q^{n}.

Theorem 10. For any integers s, t, n, and k, if there exist integers m and r such that n = km + r, then we have

gcd(W_{n} + s, W_{n+k} + t) = ⟦W(W_{r}, W_{k+r}; V_{k}, q^{k})⟧(s, t)_{m}.  (8)

Proof. By Lemma 8, W_{km+r} = J_{m} = W_{m}(W_{r}, W_{k+r}; V_{k}, q^{k}) for any integer n, so that

gcd(W_{n} + s, W_{n+k} + t) = gcd(J_{m} + s, J_{m+1} + t).

Theorem 10 shows that we can focus only on the gcds with indices in (n, n + 1) and deal with the demands for the gcds with indices in (n, n + k). Note that if |q| = 1, then |q^{k}| = 1.

Theorem 1 shows that if (S_{n}) = W(s, t; p, q), then ⟦W ⟧(s, t)_{n} divides q^{n} e(W) − e(S). Moreover, by (4), we get S_{k}S_{k+2} − S_{k+1}^{2} = q^{k}(S_{0}S_{2} − S_{1}^{2}) for any integer k. Therefore, we can conclude that

⟦W ⟧(S_{k}, S_{k+1})_{n} divides q^{n} e(W) − q^{k} e(S),

which can be seen as a generalization of Theorem 1. However, when |q| = 1, we have a stronger result.

Proof of Theorem 2. Since W_{n+2} = pW_{n+1} − qW_{n}, S_{n+2} = pS_{n+1} − qS_{n}, and |q| = 1, we obtain

⟦W ⟧(S_{0}, S_{1})_{n} = gcd(W_{n} + S_{0}, W_{n+1} + S_{1})
= gcd(−qW_{n} − qS_{0}, W_{n+1} + S_{1})
= gcd(W_{n+2} + S_{2}, W_{n+1} + S_{1}) = ⟦W ⟧(S_{1}, S_{2})_{n+1}.

Continuing in this manner gives the result.

Theorem 2 gives us a new perspective on the shift values, which is to regard the shift values as the k-th and (k +1)-th terms of a recurrence sequence (S_{n}) = W(s, t; p, q) for some s, t, and k. It also makes the result of Theorem 1 more reasonable. By Theorem 2, we can reduce the shift values to some small numbers. Conversely, we can also apply the results of small shifts to big numbers.

Example 11. Let (F_{n}) = U(1, −1) be the Fibonacci numbers, we have, for any n,

gcd(F_{2n} + 2, F_{2n+2} + 4) = ⟦W(0, 1; 3, 1)⟧(2, 2)_{n−1};
gcd(F_{2n+1} + 2, F_{2n+3} + 4) = ⟦W(1, 2; 3, 1)⟧(2, 2)_{n−1}.

Proof. By Theorem 10 with V_{2}(1, −1) = L_{2} = 3 and (−1)^{2} = 1, we have

gcd(F_{2n+r} + 2, F_{2n+r+2} + 4) = ⟦W(F_{r}, F_{r+2}; 3, 1)⟧(2, 4)_{n}.

Then by Theorem 2 with (S_{n}) = W(2, 2; 3, 1) = (2, 2, 4, 10, 26, …), we get

⟦W(F_{r}, F_{r+2}; 3, 1)⟧(2, 4)_{n} = ⟦W(F_{r}, F_{r+2}; 3, 1)⟧(2, 2)_{n−1}.

Since (F_{n}) = (0, 1, 1, 2, 3, 5, 8, …), we can conclude the result.

The result of Example 11 shows that we can get the values of (gcd(F_{2n} + 2, F_{2n+2} + 4)) and (gcd(F_{2n+1} + 2, F_{2n+3} + 4)) by only computing the values of (⟦W(0, 1; 3, 1)⟧(2, 2)_{n}) and (⟦W(1, 2; 3, 1)⟧(2, 2)_{n}).

4 Computing methods and unbounded cases

4.1 Chen’s method

The following lemma and theorem are inspired by Chen’s work [1, p. 3], which is to turn the shift values (s, t) into a sequence (T_{n}) and then change the indices of (T_{n}) and (W_{n}) into some adjacent integers. The following lemma use a fact [5, Eq. (2.17)] that

U_{−n} = −q^{−n}U_{n}.  (9)

Lemma 12. For any integers a, b, p, q, and n,

W_{−n}(a, b; p, q) = q^{−(n+1)}W_{n+1}(b, qa; p, q).  (10)

Proof. By (3) and (9), we get

W_{−n}(a, b; p, q) = bU_{−n} − aqU_{−n−1}
= −q^{−n}bU_{n} + q^{−n}aU_{n+1}
= q^{−(n+1)}(qaU_{n+1} − bqU_{n}).

Using (3) again, we obtain

q^{−(n+1)}(qaU_{n+1} − bqU_{n}) = q^{−(n+1)}W_{n+1}(b, qa; p, q).

Next, we let (T_{n}) = W(t, qs; p, q) denote the sequence generated by t and qs, where s and t are the given shift values. By Lemma 12, we have

S_{−n} = q^{−(n+1)}T_{n+1}.

Theorem 13. For any integers s, t, n, and k,

⟦W ⟧(s, t)_{n} = \begin{cases}gcd(W_{n−k} + T_{k+1}, W_{n−k+1} + T_{k}), & if q = 1; \\ gcd(W_{n−k} + T_{k+1}, W_{n−k+1} − T_{k}), & if q = −1, k odd; \\ gcd(W_{n−k} − T_{k+1}, W_{n−k+1} + T_{k}), & if q = −1, k even, \end{cases}  (11)

where (T_{n}) = W(t, qs; p, q). Proof. By Theorem 2, we have

⟦W ⟧(s, t)_{n} = ⟦W ⟧(S_{−k}, S_{−k+1})_{n−k} = gcd(W_{n−k} + S_{−k}, W_{n−k+1} + S_{−k+1}).

Since S_{−n} = q^{−(n+1)}T_{n+1}, we get

gcd(W_{n−k} + S_{−k}, W_{n−k+1} + S_{−k+1})

= gcd(W_{n−k} + q^{−(k+1)}T_{k+1}, W_{n−k+1} + q^{−k}T_{k})

= \begin{cases}gcd(W_{n−k} + T_{k+1}, W_{n−k+1} + T_{k}), & if q = 1; \\ gcd(W_{n−k} + T_{k+1}, W_{n−k+1} − T_{k}), & if q = −1, k odd; \\ gcd(W_{n−k} − T_{k+1}, W_{n−k+1} + T_{k}), & if q = −1, k even. \end{cases}

Theorem 13 is useful for computing the values of ⟦W ⟧(s, t)_{n} if we can somehow turn (W_{n}) and (T_{n}) into the same sequence or some related sequences.

4.2 Conway’s topograph

If a sequence of numbers have a nonzero common multiple m, then the sequence is bounded by |m|. Therefore, we see from Corollary 3 that (⟦W^{⊕}⟧(s, t)_{n}) is bounded if e(W^{⊕})−e(S^{⊕}) ≠ 0. And we see from Corollary 4 that (⟦W^{⊖}⟧(s, t)_{2n−1}) and (⟦W^{⊖}⟧(s, t)_{2n}) are bounded if e(W^{⊖}) + e(S^{⊖}) ≠ 0 and e(W^{⊖}) − e(S^{⊖}) ≠ 0, respectively.

We define the quadratic forms depending on q = ±1:

f_{p}^{⊕}(x, y) = x^{2} − pxy + y^{2}, and f_{p}^{⊖}(x, y) = x^{2} + pxy − y^{2}.

We see that f_{p}^{⊕}(s, t) = − e(S^{⊕}) and f_{p}^{⊖}(s, t) = e(S^{⊖}). Thus, the sequence (⟦W ⟧(s, t)_{n}) is unbounded only when (s, t) is a solution to the following equations:

\begin{cases}f_{p}^{⊕}(x, y) = − e(W^{⊕}), & for (⟦W^{⊕}⟧(s, t)_{n}); \\ f_{p}^{⊖}(x, y) = e(W^{⊖}), & for the even part of (⟦W^{⊖}⟧(s, t)_{n}); \\ f_{p}^{⊖}(x, y) = − e(W^{⊖}), & for the odd part of (⟦W^{⊖}⟧(s, t)_{n}). \end{cases}  (12)

Conway [2, Lecture 1] gave an algorithmic way to find all the values of any given quadratic form, which is by using the tree-like topograph [2, p. 6] to show the values of a quadratic form f. The topograph starts from two linearly independent primitive vectors e_{1} and e_{2} (we usually choose e_{1} = (\begin{matrix}0 \\ 1 \end{matrix}) and e_{2} = (\begin{matrix}1 \\ 0 \end{matrix})). Each region in the topograph corresponds to a lax vector ±v and the value of f(v). (Since f(v) = f(−v) for any vector v, we consider the pair ±v as the same vector, which we call a lax vector [2, p. 5].)

Figure 1: The topograph which start from vectors e_{1} and e_{2}.

Since the fact that f(v_{1} + v_{2}) + f(v_{1} − v_{2}) = 2(f(v_{1}) + f(v_{2})) for any two vectors v_{1} and v_{2}, the value of each region is easy to compute. Conway also showed that the positive regions and the negative regions are separated by a connected path which we thicken in the topograph and call the river [2, p. 18]. Moreover, for integer-valued forms, the surroundings of the river repeat periodically [2, p. 20]. In each topograph picture of this paper, we mark off one period with two red dots on the river, and write out the corresponding lax vector ±(\begin{matrix}x \\ y \end{matrix}) and the value of f(x, y) for each region. Figures 2 and 3 show Conway’s topograph for the quadratic form f_{p}^{⊕}(x, y) and f_{p}^{⊖}(x, y), respectively.

Figure 2: Conway’s topograph for f_{p}^{⊕}(x, y), where |p| > 2, δ = sgn(p).

Figure 3: Conway’s topograph for f_{p}^{⊖}(x, y), where p ≠ 0, δ = sgn(p).

By Conway’s topograph, we can find the solutions (s, t) to the equations (12). Moreover, if e(W) is not a square-free integer, that is, there is an integer c such that e(W)/(c^{2}) is again an integer, then (cs′, ct′) is also a solution to (12) where (s′, t′) is a solution to f_{p}(x, y) = ± e(W)/(c^{2}).

We see from Figures 2 and 3 that the sequence of vectors (E_{0}, E_{1}, E_{2}, E_{3}, …) which contains (\begin{matrix}0 \\ 1 \end{matrix}) and (\begin{matrix}1 \\ 0 \end{matrix}) in Figure 4 form a recurrence sequence W(E_{0}, E_{1}; p, ±1). Since A_{n} = E_{n−1} ± mE_{n} for any n, the sequence (A_{n}) is also a recurrence sequence, and so are (B_{n}) and (C_{n}) = (A_{n} ± B_{n}). Therefore, for q = 1, all we need to find is the regions in just one period of the topograph. For q = −1, we only need to find the regions in the positive half of one period. That is, if (s, t) is a solution we found in one (half-)period, then the corresponding solution in other (half-)periods must be one of ±(S_{k}, S_{k+1}).

Figure 4: Conway’s topographs for f_{p}^{⊕}(x, y) (left) and f_{p}^{⊖}(x, y) (right).

In the following example, we present how to find all (s, t) such that (⟦W ⟧(s, t)_{n}) may be unbounded.

Example 14. Let (W_{n}) = W(1, 3; 4, −1). Thus, e(W) = 4 and the corresponding quadratic form is f(x, y) = x^{2} + 4xy − y^{2}. We use Conway’s topograph to get Figure 5:

Figure 5: Conway’s topograph for f(x, y) = x^{2} + 4xy − y^{2}.

Since e(W) = 4 = 2^{2}, we need to find all the vectors with the values of f(x, y) being ±1 and ±4. So in Figure 5, the corresponding vectors in one half-period are (1, 0), (1, 1), (1, 3). We have to multiply 2 back to the vector (1, 0) such that the value of f(x, y) being ±4. These give three sequences: W(2, 0; 4, −1), W(1, 1; 4, −1), W(1, 3; 4, −1). The sequence (⟦W ⟧(s, t)_{n}) is unbounded only when (s, t) = ±(S_{k}, S_{k+1}) for some k where (S_{n}) is any one of these three sequences.

4.3 Trivial unbounded cases

According to Theorem 2, we do not really need to compute the whole solution set of (s, t). Instead, we can only consider some (S_{n}, S_{n+1}) which are easier to compute. Moreover, if (s, t) is a solution of f_{p}(x, y), then we can easily to prove that the only other solution with the same first term s is (s, sp − t).

However, if (S_{n}^{⊕}) = W(s, sp − t; p, 1), then S_{−1}^{⊕} = t. Applying Theorem 2, we have

⟦W^{⊕}⟧(s, sp − t)_{n} = ⟦W^{⊕}⟧(S_{0}^{⊕}, S_{1}^{⊕})_{n} = ⟦W^{⊕}⟧(S_{−1}^{⊕}, S_{0}^{⊕})_{n−1} = ⟦W^{⊕}⟧(t, s)_{n−1}.

Thus, we can compute (⟦W^{⊕}⟧(±t, ±s)_{n}) instead of computing (⟦W^{⊕}⟧(±s, ±(sp − t))_{n}).

Similarly, we have ⟦W^{⊖}⟧(s, sp − t)_{2n} = ⟦W^{⊖}⟧(−t, s)_{2n−1} and ⟦W^{⊖}⟧(t, s + tp)_{2n−1} = ⟦W^{⊖}⟧(s, t)_{2n−2}. Thus, we can compute (⟦W^{⊖}⟧(∓t, ±s)_{2n−1}) and (⟦W^{⊖}⟧(±s, ±t)_{2n}) instead of computing (⟦W^{⊖}⟧(±s, ±(sp − t))_{2n}) and (⟦W^{⊖}⟧(±t, ±(s + tp))_{2n−1}), respectively.

Now we combine all the above results together. We indicate the trivial unbounded situations for the following three cases:

1. Since f_{p}^{⊕}(a, b) = − e(W^{⊕}), there are two trivial solutions (a, b) and (a, ap − b) to the equation f_{p}^{⊕}(x, y) = − e(W^{⊕}). We compute ⟦W^{⊕}⟧(±a, ±b)_{n} and ⟦W^{⊕}⟧(±b, ±a)_{n} to tell that these values are unbounded.

2. Since f_{p}^{⊖}(a, b) = e(W^{⊖}), there are two trivial solutions (a, b) and (a, ap − b) to the equation f_{p}^{⊖}(x, y) = e(W^{⊖}). We compute ⟦W^{⊖}⟧(±a, ±b)_{2n} and ⟦W^{⊖}⟧(∓b, ±a)_{2n−1} to tell that these values are unbounded.

3. Since f_{p}^{⊖}(b, −a) = − e(W^{⊖}), there are two trivial solutions (b, −a) and (b, a+bp) to the equation f_{p}^{⊖}(x, y) = − e(W^{⊖}). We compute ⟦W^{⊖}⟧(±b, ∓a)_{2n−1} and ⟦W^{⊖}⟧(±a, ±b)_{2n} to tell that these values are unbounded.

5 Computations for trivial unbounded cases

In the following propositions, we use Theorem 13 to compute the actual values of (⟦W ⟧(s, t)_{n}) where (s, t) is one of the above pairs (±a, ±b), (±b, ±a), and (∓b, ±a). As a result, these values are all unbounded.

Proposition 15. For any integer n,

⟦W^{⊕}⟧(a, b)_{n} = \begin{cases}gcd(a + b, pa − 2b) |U_{m}^{⊕} − U_{m−1}^{⊕}| , & if n = 2m − 1; \\ gcd(a, b) |V_{m}^{⊕}| , & if n = 2m. \end{cases}  (13)

⟦W^{⊕}⟧(−a, −b)_{n} = \begin{cases}gcd(a − b, 2a − pb) |U_{m}^{⊕} + U_{m−1}^{⊕}| , & if n = 2m − 1; \\ gcd(2b − pa, pb − 2a) |U_{m}^{⊕}| , & if n = 2m. \end{cases}  (14)

Proof. By (3) and (11) with q = 1, (T_{n}^{⊕}) = W(b, a; p, 1), and k = n, we get

⟦W^{⊕}⟧(a, b)_{2n−1} = gcd(W_{n−1}^{⊕} + T_{n+1}^{⊕}, W_{n}^{⊕} + T_{n}^{⊕})
= gcd(bU_{n−1}^{⊕} − aU_{n−2}^{⊕} + aU_{n+1}^{⊕} − bU_{n}^{⊕}, bU_{n}^{⊕} − aU_{n−1}^{⊕} + aU_{n}^{⊕} − bU_{n−1}^{⊕})
= gcd((a + pa − b)(U_{n}^{⊕} − U_{n−1}^{⊕}), (a + b)(U_{n}^{⊕} − U_{n−1}^{⊕}))
= gcd(a + b, pa − 2b) |U_{n}^{⊕} − U_{n−1}^{⊕}| ,
⟦W^{⊕}⟧(a, b)_{2n} = gcd(W_{n}^{⊕} + T_{n+1}^{⊕}, W_{n+1}^{⊕} + T_{n}^{⊕})
= gcd(bU_{n}^{⊕} − aU_{n−1}^{⊕} + aU_{n+1}^{⊕} − bU_{n}^{⊕}, bU_{n+1}^{⊕} − aU_{n}^{⊕} + aU_{n}^{⊕} − bU_{n−1}^{⊕})
= gcd(a(pU_{n}^{⊕} − 2U_{n−1}^{⊕}), b(pU_{n}^{⊕} − 2U_{n−1}^{⊕}))
= gcd(a, b) |V_{n}^{⊕}| .

By (3) and (11) with q = 1, (T_{n}^{⊕}) = W(−b, −a; p, 1), and k = n, we get

⟦W^{⊕}⟧(−a, −b)_{2n−1} = gcd(W_{n−1}^{⊕} + T_{n+1}^{⊕}, W_{n}^{⊕} + T_{n}^{⊕})
= gcd(bU_{n−1}^{⊕} − aU_{n−2}^{⊕} − aU_{n+1}^{⊕} + bU_{n}^{⊕}, bU_{n}^{⊕} − aU_{n−1}^{⊕} − aU_{n}^{⊕} + bU_{n−1}^{⊕})
= gcd((a − pa + b)(U_{n}^{⊕} + U_{n−1}^{⊕}), (−a + b)(U_{n}^{⊕} + U_{n−1}^{⊕})),
= gcd(a − b, 2a − pb) |U_{n}^{⊕} + U_{n−1}^{⊕}| ,
⟦W^{⊕}⟧(−a, −b)_{2n} = gcd(W_{n}^{⊕} + T_{n+1}^{⊕}, W_{n+1}^{⊕} + T_{n}^{⊕})
= gcd(bU_{n}^{⊕} − aU_{n−1}^{⊕} − aU_{n+1}^{⊕} + bU_{n}^{⊕}, bU_{n+1}^{⊕} − aU_{n}^{⊕} − aU_{n}^{⊕} + bU_{n−1}^{⊕})
= gcd((2b − pa)U_{n}^{⊕}, (pb − 2a)U_{n}^{⊕})
= gcd(2b − pa, pb − 2a) |U_{n}^{⊕}| .

Proposition 16. For any integer n,

⟦W^{⊕}⟧(b, a)_{n} = \begin{cases}gcd(2, p) |W_{m}^{⊕}| , & if n = 2m − 1; \\ |W_{m}^{⊕} + W_{m−1}^{⊕}| , & if n = 2m − 2. \end{cases}  (15)

⟦W^{⊕}⟧(−b, −a)_{n} = \begin{cases}|pW_{m}^{⊕} − 2W_{m−1}^{⊕}| , & if n = 2m − 1; \\ |W_{m}^{⊕} − W_{m−1}^{⊕}| , & if n = 2m − 2. \end{cases}  (16)

Proof. By (11) with q = 1, (T_{n}^{⊕}) = W(a, b; p, 1) = (W_{n}^{⊕}), and k = n, we get

⟦W^{⊕}⟧(b, a)_{2n−1} = gcd(W_{n−1}^{⊕} + T_{n+1}^{⊕}, W_{n}^{⊕} + T_{n}^{⊕})
= gcd(pW_{n}^{⊕}, 2W_{n}^{⊕}) = gcd(2, p) |W_{n}^{⊕}| ,
⟦W^{⊕}⟧(b, a)_{2n−2} = gcd(W_{n−2}^{⊕} + T_{n+1}^{⊕}, W_{n−1}^{⊕} + T_{n}^{⊕})
= gcd(0, W_{n}^{⊕} + W_{n−1}^{⊕}) = |W_{n}^{⊕} + W_{n−1}^{⊕}| .

By (11) with q = 1, (T_{n}^{⊕}) = W(−a, −b; p, 1) = (−W_{n}^{⊕}), and k = n, we get

⟦W^{⊕}⟧(−b, −a)_{2n−1} = gcd(W_{n−1}^{⊕} + T_{n+1}^{⊕}, W_{n}^{⊕} + T_{n}^{⊕})
= gcd(−pW_{n}^{⊕} + 2W_{n−1}^{⊕}, 0) = |pW_{n}^{⊕} − 2W_{n−1}^{⊕}| ,
⟦W^{⊕}⟧(−b, −a)_{2n−2} = gcd(W_{n−2}^{⊕} + T_{n+1}^{⊕}, W_{n−1}^{⊕} + T_{n}^{⊕})
= gcd(0, W_{n}^{⊕} − W_{n−1}^{⊕}) = |W_{n}^{⊕} − W_{n−1}^{⊕}| .

Example 17 ([9, Thm. 3.1]). Let (B_{n}) = U(6, 1) = (0, 1, 6, 35, 204, …) be the balancing numbers. We see that e(B) − e(S) = 0 where (S_{n}) = W(−1, −6; 6, 1). By Theorem 2 and (14), we have

⟦B⟧(−1, −6)_{n} = ⟦B⟧(0, −1)_{n−1} = \begin{cases}B_{m} + B_{m−1}, & if n = 2m; \\ 2B_{m}, & if n = 2m + 1. \end{cases}

Proposition 18. For any integer n,

⟦W^{⊖}⟧(a, b)_{2n} = \begin{cases}gcd(2a + pb, pa − 2b) |U_{n}^{⊖}| , & if n odd; \\ gcd(a, b) |V_{n}^{⊖}| , & if n even. \end{cases}  (17)

⟦W^{⊖}⟧(−a, −b)_{2n} = \begin{cases}gcd(a, b) |V_{n}^{⊖}| , & if n odd; \\ gcd(2a + pb, pa − 2b) |U_{n}^{⊖}| , & if n even. \end{cases}  (18)

Proof. By (3) and (11) with q = −1, (T_{n}^{⊖}) = W(b, −a; p, −1), and k = n, we get

⟦W^{⊖}⟧(a, b)_{4n−2} = gcd(W_{2n−2}^{⊖} − T_{2n+1}^{⊖}, W_{2n−1}^{⊖} + T_{2n}^{⊖}) = gcd(bU_{2n−2}^{⊖} + aU_{2n−3}^{⊖} + aU_{2n+1}^{⊖} − bU_{2n}^{⊖}, bU_{2n−1}^{⊖} + aU_{2n−2}^{⊖} − aU_{2n}^{⊖} + bU_{2n−1}^{⊖}) = gcd((p^{2}a + 2a − pb)U_{2n−1}^{⊖}, (−pa + 2b)U_{2n−1}^{⊖}) = gcd(2a + pb, pa − 2b) |U_{2n−1}^{⊖}| ,

⟦W^{⊖}⟧(a, b)_{4n} = gcd(W_{2n}^{⊖} − T_{2n+1}^{⊖}, W_{2n+1}^{⊖} + T_{2n}^{⊖}) = gcd(bU_{2n}^{⊖} + aU_{2n−1}^{⊖} + aU_{2n+1}^{⊖} − bU_{2n}^{⊖}, bU_{2n+1}^{⊖} + aU_{2n}^{⊖} − aU_{2n}^{⊖} + bU_{2n−1}^{⊖}) = gcd(a(pU_{2n}^{⊖} + 2U_{2n−1}^{⊖}), b(pU_{2n}^{⊖} + 2U_{2n−1}^{⊖})) = gcd(a, b) |V_{2n}^{⊖}| .

By (3) and (11) with q = −1, (T_{n}^{⊖}) = W(−b, a; p, −1), and k = n, we get

⟦W^{⊖}⟧(−a, −b)_{4n−2} = gcd(W_{2n−2}^{⊖} − T_{2n+1}^{⊖}, W_{2n−1}^{⊖} + T_{2n}^{⊖}) = gcd(bU_{2n−2}^{⊖} + aU_{2n−3}^{⊖} − aU_{2n+1}^{⊖} + bU_{2n}^{⊖}, bU_{2n−1}^{⊖} + aU_{2n−2}^{⊖} + aU_{2n}^{⊖} − bU_{2n−1}^{⊖}) = gcd((−pa + b)(pU_{2n−1} + 2U_{2n−2}), a(pU_{2n−1} + 2U_{2n−2})), = gcd(a, b) |V_{2n−1}^{⊖}| ,

⟦W^{⊖}⟧(−a, −b)_{4n} = gcd(W_{2n}^{⊖} − T_{2n+1}^{⊖}, W_{2n+1}^{⊖} + T_{2n}^{⊖}) = gcd(bU_{2n}^{⊖} + aU_{2n−1}^{⊖} − aU_{2n+1}^{⊖} + bU_{2n}^{⊖}, bU_{2n+1}^{⊖} + aU_{2n}^{⊖} + aU_{2n}^{⊖} − bU_{2n−1}^{⊖}) = gcd((−pa + 2b)U_{2n}^{⊖}, (2a + pb)U_{2n}^{⊖}) = gcd(2a + pb, pa − 2b) |U_{2n}^{⊖}| .

Proposition 19. For any integer n,

⟦W^{⊖}⟧(−b, a)_{2n−1} = \begin{cases}gcd(2, p) |W_{n}^{⊖}| , & if n even; \\ |pW_{n}^{⊖} + 2W_{n−1}^{⊖}| , & if n odd. \end{cases}  (19)

⟦W^{⊖}⟧(b, −a)_{2n−1} = \begin{cases}|pW_{n}^{⊖} + 2W_{n−1}^{⊖}| , & if n even; \\ gcd(2, p) |W_{n}^{⊖}| , & if n odd. \end{cases}  (20)

Proof. By (11) with q = −1, (T_{n}^{⊖}) = W_{n}(a, b; p, −1) = (W_{n}^{⊖}), and k = n, we get

⟦W^{⊖}⟧(−b, a)_{4n−1} = gcd(W_{2n−1}^{⊖} − T_{2n+1}^{⊖}, W_{2n}^{⊖} + T_{2n}^{⊖})
= gcd(−pW_{2n}^{⊖}, 2W_{2n}^{⊖}) = gcd(2, p) |W_{2n}^{⊖}| ,
⟦W^{⊖}⟧(−b, a)_{4n+1} = gcd(W_{2n+1}^{⊖} − T_{2n+1}^{⊖}, W_{2n+2}^{⊖} + T_{2n}^{⊖})
= gcd(0, pW_{2n+1}^{⊖} + 2W_{2n}^{⊖}) = |pW_{2n+1}^{⊖} + 2W_{2n}^{⊖}| .

By (11) with q = −1, (T_{n}^{⊖}) = W(−a, −b; p, −1) = (−W_{n}^{⊖}), and k = n, we get

⟦W^{⊖}⟧(b, −a)_{4n−1} = gcd(W_{2n−1}^{⊖} − T_{2n+1}^{⊖}, W_{2n}^{⊖} + T_{2n}^{⊖})
= gcd(pW_{2n}^{⊖} + 2W_{2n−1}^{⊖}, 0) = |pW_{2n}^{⊖} + 2W_{2n−1}^{⊖}| ,
⟦W^{⊖}⟧(b, −a)_{4n+1} = gcd(W_{2n+1}^{⊖} − T_{2n+1}^{⊖}, W_{2n+2}^{⊖} + T_{2n}^{⊖})
= gcd(2W_{2n+1}^{⊖}, pW_{2n+1}^{⊖}) = gcd(2, p) |W_{2n+1}^{⊖}| .

Example 20 ([1, Thm. 3]). Let (F_{n}) = U(1, −1) be the Fibonacci numbers, and let (L_{n}) = V(1, −1) be the Lucas numbers. We see that e(F) + e(S) = 0 where (S_{n}) = W(1, 1; 1, −1). By Theorem 2 and (17), we have

⟦F ⟧(1, 1)_{2n−1} = ⟦F ⟧(0, 1)_{2n−2} = \begin{cases}F_{2m−1}, & if n = 2m; \\ L_{2m}, & if n = 2m + 1. \end{cases}

6 Examples

There are some results for some well-known sequences of numbers, such as the results of shifted Fibonacci numbers provided by Chen [1], Dudley and Tucker [3], Rahn and Kreh [8], the results of shifted Pell numbers provided by Koken and Arslan [7], and the results of shifted balancing numbers provided by Ray and Pradhan [9]. We list those gcds and their periods ω_{even} and ω_{odd} for the even and odd part respectively below if they are bounded. (That is, for any integer n, ⟦W ⟧(s, t)_{n} = ⟦W ⟧(s, t)_{n+2ω}.)

⟦W ⟧(s, t)_{n}  p q e(W) e(S) ω_{odd} ω_{even} references
⟦F ⟧(1, −1)_{n}  1 −1 −1 −1  3  - [3]
⟦F ⟧(±1, ±1)_{n} 1 −1 −1  1  -  3 [3] and [1, Thm. 3, 5]
⟦F ⟧(±2, ±2)_{n} 1 −1 −1  4  4  10 [1, Thm. 4, 6]
⟦F ⟧(±3, ±3)_{n} 1 −1 −1  9  6  30 [8, Thm. 1, 2]
⟦L⟧(1, 1)_{n}  1 −1  5  1 12  3 [1, Thm. 7]
⟦P ⟧(±2, ∓1)_{n} 2 −1 −1 −1  1  - [7, Thm. 1, 4]
⟦P ⟧(±1, ∓2)_{n} 2 −1 −1 −7  2  4 [7, Thm. 1, 4]
⟦Q⟧(±6, ∓2)_{n} 2 −1  8  8  1  - [7, Thm. 7, 9]
⟦Q⟧(±2, ∓6)_{n} 2 −1  8 56  4  2 [7, Thm. 7, 9]
⟦B⟧(±1, ±6)_{n} 6 1 −1 −1  -  - [9, Thm. 3.1, 3.3]
⟦B⟧(±2, ±12)_{n} 6 1 −1 −4  2  1 [9, Thm. 3.2, 3.4]
⟦C⟧(1, 3)_{n}  6 1  8  8  -  - [9, Thm. 3.5]

Table 2: Some known results for ⟦W ⟧(s, t)_{n}.

In the following, we show some examples using our results. In the first example, we present the process in detail.

Example 21. We let (F_{n}) denote the Fibonacci numbers, and let (L_{n}) denote the Lucas numbers. For any integer n,

⟦L⟧(2, 1)_{n} = \begin{cases}5F_{n/2}, & if n ≡ 2 (mod 4); \\ L_{n/2}, & if n ≡ 0 (mod 4); \\ 2, & if n ≡ 3 (mod 6); \\ 1, & otherwise. \end{cases} ⟦L⟧(−2, −1)_{n} = \begin{cases}L_{n/2}, & if n ≡ 2 (mod 4); \\ 5F_{n/2}, & if n ≡ 0 (mod 4); \\ 2, & if n ≡ 3 (mod 6); \\ 1, & otherwise. \end{cases}

Proof. Since (S_{n}) = ±W(2, 1; 1, −1) = (±L_{n}), by Corollary 4 with e(L) = e(S) = 5, we get ⟦L⟧(±2, ±1)_{2n−1} divides e(L) + e(S) = 10 ≠ 0. Thus, by Theorem 7, since L_{12} ≡ 2, L_{13} ≡ 1 (mod 10), we can choose the period ω = 12.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ L_{n} & 2 & 1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 & 76 & 123 & 199 & 322 & 521 \\ L_{n} mod 10 & 2 & 1 & 3 & 4 & 7 & 1 & 8 & 9 & 7 & 6 & 3 & 9 & 2 & 1 \end{matrix}

Then we get the values of (⟦L⟧(±2, ±1)_{n}) for all odd n while they are bounded.

\begin{matrix}n & 1 & 3 & 5 & 7 & 9 & 11 & 13 \\ ⟦L⟧(2, 1)_{n} & 1 & 2 & 1 & 1 & 2 & 1 & 1 \\ ⟦L⟧(−2, −1)_{n} & 1 & 2 & 1 & 1 & 2 & 1 & 1 \end{matrix}

On the other hand, e(L) − e(S) = 0. By Proposition 18, (⟦L⟧(±2, ±1)_{2n}) is unbounded, and

⟦L⟧(2, 1)_{2n} = \begin{cases}gcd(5, 0)F_{n}, & if n odd; \\ gcd(2, 1)L_{n}, & if n even. \end{cases} ⟦L⟧(−2, −1)_{2n} = \begin{cases}gcd(2, 1)L_{n}, & if n odd; \\ gcd(5, 0)F_{n}, & if n even. \end{cases}

Thus, we get the values of (⟦L⟧(±2, ±1)_{n}) for all even n while they are unbounded.

\begin{matrix}n & 0 & 2 & 4 & 6 & 8 & 10 & 12 \\ ⟦L⟧(2, 1)_{n} & 2 & 5 & 3 & 10 & 7 & 25 & 18 \\ ⟦L⟧(−2, −1)_{n} & 0 & 1 & 5 & 4 & 15 & 11 & 40 \end{matrix}  \begin{matrix}n & 0 & 2 & 4 & 6 & 8 & 10 & 12 \\ 5F_{n/2} & 0 & 5 & 5 & 10 & 15 & 25 & 40 \\ L_{n/2} & 2 & 1 & 3 & 4 & 7 & 11 & 18 \end{matrix}

We can use Theorem 7 and Proposition 19 to get the values of (⟦L⟧(∓1, ±2)_{n}) for both bounded and unbounded parts. However, we can also use Theorem 2 to get the values since L_{−1} = −1, for example, (in fact [5, Eq. (2.16)], V_{−n} = q^{−n}V_{n})

⟦L⟧(−1, 2)_{n} = ⟦L⟧(2, 1)_{n+1}, ⟦L⟧(1, −2)_{n} = ⟦L⟧(−2, −1)_{n+1}.

We let (P_{n}) denote the Pell numbers defined by (P_{n}) = U(2, −1) = W(0, 1; 2, −1), and let (Q_{n}) denote the Pell-Lucas numbers defined by (Q_{n}) = V(2, −1) = W(2, 2; 2, −1).

Example 22 ([7, Thm. 1, 4]). For any integer n,

⟦P ⟧(0, 1)_{n} = \begin{cases}2P_{n/2}, & if n ≡ 2 (mod 4); \\ Q_{n/2}, & if n ≡ 0 (mod 4); \\ 1, & otherwise. \end{cases} ⟦P ⟧(0, −1)_{n} = \begin{cases}Q_{n/2}, & if n ≡ 2 (mod 4); \\ 2P_{n/2}, & if n ≡ 0 (mod 4); \\ 1, & otherwise. \end{cases}

Proof. Since (S_{n}) = ±W(0, 1; 2, −1) = (±P_{n}), by Corollary 4 with e(P) = e(S) = −1, we get ⟦P ⟧(0, ±1)_{2n−1} divides e(P)+e(S) = 2. Thus, by Theorem 7, since P_{2} ≡ 0, P_{3} ≡ 1 (mod 2), we choose the period ω = 2. Then we can get the values of (⟦P ⟧(0, ±1)_{n}) for all odd n while they are bounded.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 \\ P_{n} mod 2 & 0 & 1 & 0 & 1 & 0 & 1 \\ ⟦P ⟧(0, 1)_{n} & & 1 & & 1 & & 1 \\ ⟦P ⟧(0, −1)_{n} & & 1 & & 1 & & 1 \end{matrix}  \begin{matrix}n & 0 & 2 & 4 & 6 & 8 \\ ⟦P ⟧(0, 1)_{n} & 2 & 2 & 6 & 10 & 34 \\ ⟦P ⟧(0, −1)_{n} & 0 & 2 & 4 & 14 & 24 \\ 2P_{n/2} & 0 & 2 & 4 & 10 & 24 \\ Q_{n/2} & 2 & 2 & 6 & 14 & 34 \end{matrix}

And by Proposition 18, we get the values of the unbounded part of (⟦P ⟧(0, ±1)_{n}).

We can use Theorem 2 to get the values of ⟦P ⟧(±1, 0)_{n} since P_{−1} = 1, for example, (in fact [5, Eq. (2.17)], U_{−n} = −q^{−n}U_{n})

⟦P ⟧(1, 0)_{n} = ⟦P ⟧(0, 1)_{n+1}, ⟦P ⟧(−1, 0)_{n} = ⟦P ⟧(0, −1)_{n+1}.

Example 23. For any integer n,

⟦P ⟧(1, 1)_{n} = \begin{cases}3, & if n ≡ 2 (mod 8); \\ 1, & otherwise. \end{cases}  ⟦P ⟧(−1, −1)_{n} = \begin{cases}3, & if n ≡ 6 (mod 8); \\ 1, & otherwise. \end{cases}

Proof. Since (S_{n}) = ±W(1, 1; 2, −1), by Corollary 4 with e(P) = −1 and e(S) = 2, we get ⟦P ⟧(±1, ±1)_{2n−1} divides e(P) + e(S) = 1 and ⟦P ⟧(±1, ±1)_{2n} divides e(P) − e(S) = 3, so that ⟦P ⟧(±1, ±1)_{n} divides 3. Thus, by Theorem 7, since P_{8} ≡ 0, P_{9} ≡ 1 (mod 3), we choose the period ω = 8. Then we can get the results.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ P_{n} mod 3 & 0 & 1 & 2 & 2 & 0 & 2 & 1 & 1 & 0 & 1 \\ ⟦P ⟧(1, 1)_{n} & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ ⟦P ⟧(−1, −1)_{n} & 1 & 1 & 1 & 1 & 1 & 1 & 3 & 1 & 1 & 1 \end{matrix}

Example 24. For any integer n,

⟦Q⟧(1, 1)_{n} = \begin{cases}5, & if n ≡ 3 (mod 12); \\ 3, & if n ≡ 0 (mod 8); \\ 1, & otherwise. \end{cases} ⟦Q⟧(−1, −1)_{n} = \begin{cases}5, & if n ≡ 9 (mod 12); \\ 3, & if n ≡ 4 (mod 8); \\ 1, & otherwise. \end{cases}

Proof. Since (S_{n}) = ±W(1, 1; 2, −1), by Corollary 4 with e(Q) = 8 and e(S) = 2, we get ⟦Q⟧(±1, ±1)_{2n−1} divides e(Q) + e(S) = 10 and ⟦Q⟧(±1, ±1)_{2n} divides e(Q) − e(S) = 6, so that ⟦Q⟧(±1, ±1)_{n} divides 30. Thus, by Theorem 7, since Q_{24} ≡ 2, Q_{25} ≡ 2 (mod 30), we choose the period ω = 24. Then we can get the results.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ Q_{n} mod 30 & 2 & 2 & 6 & 14 & 4 & 22 & 18 & 28 & 14 & 26 & 6 & 8 \\ ⟦Q⟧(1, 1)_{n} & 3 & 1 & 1 & 5 & 1 & 1 & 1 & 1 & 3 & 1 & 1 & 1 \\ ⟦Q⟧(−1, −1)_{n} & 1 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 5 & 1 & 1 \\ n & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ Q_{n} mod 30 & 22 & 22 & 6 & 4 & 14 & 2 & 18 & 8 & 4 & 16 & 6 & 28 \\ ⟦Q⟧(1, 1)_{n} & 1 & 1 & 1 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ ⟦Q⟧(−1, −1)_{n} & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 3 & 5 & 1 & 1 \end{matrix} 24 25 2 2 3 1 1 1

Example 25 ([7, Thm. 7, 9]). For any integer n,

⟦Q⟧(2, 2)_{n} = \begin{cases}8P_{n/2}, & if n ≡ 2 (mod 4); \\ 2Q_{n/2}, & if n ≡ 0 (mod 4); \\ 4, & otherwise. \end{cases} ⟦Q⟧(−2, −2)_{n} = \begin{cases}2Q_{n/2}, & if n ≡ 2 (mod 4); \\ 8P_{n/2}, & if n ≡ 0 (mod 4); \\ 4, & otherwise. \end{cases}

Proof. Since (S_{n}) = ±W(2, 2; 2, −1) = (±Q_{n}), By Corollary 4 with e(Q) = e(S) = 8, we get ⟦Q⟧(±2, ±2)_{2n−1} divides e(Q) + e(S) = 16. Thus, by Theorem 7, since Q_{4} ≡ 2, Q_{5} ≡ 2 (mod 16), we choose the period ω = 4. Then we can get the values of (⟦Q⟧(±2, ±2)_{n}) for all odd n while they are bounded.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 \\ Q_{n} mod 16 & 2 & 2 & 6 & 14 & 2 & 2 \\ ⟦Q⟧(2, 2)_{n} & & 4 & & 4 & & 4 \\ ⟦Q⟧(−2, −2)_{n} & & 4 & & 4 & & 4 \end{matrix}  \begin{matrix}n & 0 & 2 & 4 & 6 & 8 \\ ⟦Q⟧(2, 2)_{n} & 4 & 8 & 12 & 40 & 68 \\ ⟦Q⟧(−2, −2)_{n} & 0 & 4 & 16 & 28 & 96 \\ 8P_{n/2} & 0 & 8 & 16 & 40 & 96 \\ Q_{n/2} & 4 & 4 & 12 & 28 & 68 \end{matrix}

And by Proposition 18, we get the values of the unbounded part of (⟦Q⟧(±2, ±2)_{n}).

We can use Theorem 2 to get the values of ⟦Q⟧(∓2, ±2)_{n} since Q_{−1} = −2, for example,

⟦Q⟧(−2, 2)_{n} = ⟦Q⟧(2, 2)_{n+1}, ⟦Q⟧(2, −2)_{n} = ⟦Q⟧(−2, −2)_{n+1}.

References

[1] K.-W. Chen, Greatest common divisors in shifted Fibonacci sequences, J. Integer Sequences 14 (2011), Article 11.4.7.

[2] J. H. Conway, The Sensual (Quadratic) Form, Mathematical Association of America, 1997.

[3] U. Dudley and B. Tucker, Greatest common divisors in altered Fibonacci sequences, Fibonacci Quart. 9 (1971), 89–91.

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

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

[6] E. Kiliç and P. Stănică, Factorizations and representations of binary polynomial recurrences by matrix methods, Rocky Mountain J. Math. 41 (2011), 1247–1264.

[7] F. Koken and S. Arslan, GCD properties of the altered Pell and Pell Lucas numbers, IOSR J. Math. 14 (5) (2018), 82–89.

[8] A. Rahn and M. Kreh, Greatest common divisors of shifted Fibonacci sequences revisited, J. Integer Sequences 21 (2018), Article 18.6.7.

[9] P. K. Ray and S. S. Pradhan, Greatest common divisors of shifted balancing numbers, Bol. Soc. Parana. Mat. 35 (3) (2017), 273–283.

[10] J. Spilker, The GCD of the shifted Fibonacci sequence. In J. Sander, J. Steuding, and R. Steuding, eds., From Arithmetic to Zeta-Functions, Springer, 2016, pp. 473–483.

[11] B. Thongkam and N. Sailadda, The greatest common divisors of generalized Fibonacci and generalized Pell numbers, Notes Number Theory Discrete Math. 24 (1) (2018), 97–102.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11A05, 11B83. Keywords: greatest common divisor, Horadam sequence, recurrence sequence.

(Concerned with sequences \underline{A000045}, \underline{A000032}, \underline{A000129}, \underline{A002203}, \underline{A001110}, and \underline{A001541}.) Received July 1 2019; revised version received March 12 2020; April 3 2020. Published in Journal of Integer Sequences, June 8 2020. Return to Journal of Integer Sequences home page.