GCD of Sums of k Consecutive Fibonacci, Lucas, and Generalized Fibonacci Numbers

Dan Guyer and aBa Mbirika Department of Mathematics University of Wisconsin-Eau Claire Eau Claire, WI 54702 USA

                 guyerdm7106@uwec.edu
                   mbirika@uwec.edu

Abstract

We explore the sums of k consecutive terms in the generalized Fibonacci sequence (G_{n})_{n≥0} given by the recurrence G_{n} = G_{n−1} + G_{n−2} for all n ≥ 2 with integral initial conditions G_{0} and G_{1}. In particular, we give precise values for the greatest common divisor (GCD) of all sums of k consecutive terms of (G_{n})_{n≥0}. When G_{0} = 0 and G_{1} = 1, we yield the GCD of all sums of k consecutive Fibonacci numbers, and when G_{0} = 2 and G_{1} = 1, we yield the GCD of all sums of k consecutive Lucas numbers. Denoting the GCD of all sums of k consecutive generalized Fibonacci numbers by the symbol G_{G_{0},G_{1}}(k), we give two tantalizing characterizations for these values, one involving a simple formula in k and another involving generalized Pisano periods:

G_{G_{0},G_{1}}(k) = gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}) and
G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k},

where π_{G_{0},G_{1}}(m) denotes the generalized Pisano period of the generalized Fibonacci sequence modulo m. The fact that these vastly different-looking formulas coincide leads to some surprising and delightful new understandings of the Fibonacci and Lucas numbers.

1 Introduction

In the inaugural issue of the Fibonacci Quarterly in 1963, I. D. Ruggles proposed the following problem in the Elementary Problems section: “Show that the sum of twenty consecutive Fibonacci numbers is divisible by the 10^{th} Fibonacci number F_{10} = 55.” [13] Since the Ruggles problem, there have been numerous papers studying sums of consecutive Fibonacci numbers or Lucas numbers [9, 19, 20, 4, 3, 14]. However, with all this work on consecutive sums of Fibonacci and Lucas numbers, one related topic seems to be missing from the literature, namely that of the greatest common divisor (GCD) of sums of Fibonacci and Lucas numbers. That being said, the On-Line Encyclopedia of Integer Sequences (OEIS) does have two entries, \underline{A210209} and \underline{A229339}, which give the GCDs of the sums of k consecutive Fibonacci (respectively, Lucas) numbers [15]. But in those entries, no references are given to any existing papers in the literature providing rigorous proofs that confirm these sequences. More precisely, two references are given in the entry \underline{A210209} but they appear to have little connection to the actual sequence, and the entry \underline{A229339} contains no references at all. Our paper serves to fill this deficiency in the literature.

Motivated by the Ruggles problem, we observed the surprising fact that not only is the sum of any twenty consecutive Fibonacci numbers divisible by F_{10}, but also that F_{10} is the greatest of all the divisors of these sums. This became a main motivation for us to explore sums of any finite length of consecutive Fibonacci numbers, then for Lucas numbers, and then eventually for all possible generalized Gibonacci sequences. Appearing in the literature as early as 1901 by Tagiuri [18], the generalized Fibonacci numbers (or so-called Gibonacci numbers^{1}) are defined by the recurrence

G_{i} = G_{i−1} + G_{i−2} for all i ≥ 2

with initial conditions G_{0}, G_{1} ∈ ℤ. We examine the GCD of the sums of k consecutive Gibonacci numbers, and consequently k consecutive Fibonacci and Lucas numbers. More precisely, given k ∈ ℕ we explore the GCD of an infinite number of finite sums

∑_{i=1}^{k} G_{i} , ∑_{i=2}^{k+1} G_{i} , ∑_{i=3}^{k+2} G_{i} , …

That is, we compute the GCD of the terms in the sequence (∑_{i=0}^{k−1} G_{n+i})_{n≥1}. By a slight

abuse of notation, we write this value as gcd {(∑_{i=0}^{k−1} G_{n+i})_{n≥1}}.

1Thomas Koshy attributes Art Benjamin and Jennifer Quinn for coining this term “Gibonacci” in their 2003 book Proofs that Really Count: The Art of Combinatorial Proof [1].

Convention 1. For brevity, we use the symbols F(k), L(k), and G_{G_{0},G_{1}}(k), respectively, to denote the three values

gcd {(∑_{i=0}^{k−1} F_{n+i})_{n≥1}} , gcd {(∑_{i=0}^{k−1} L_{n+i})_{n≥1}} , and gcd {(∑_{i=0}^{k−1} G_{n+i})_{n≥1}} .

For reasons to be explained in Theorem 19 and Convention 20, it suffices to only consider Gibonacci sequences with relatively prime initial conditions G_{0} and G_{1}.

Remark 2. Observe that when G_{0} = 0 and G_{1} = 1 we have G_{G_{0},G_{1}}(k) = F(k), and when G_{0} = 2 and G_{1} = 1 we have G_{G_{0},G_{1}}(k) = L(k). Hence in the symbols F(k) and L(k), we suppress writing the initial values since those are well known in the Fibonacci and Lucas setting.

To compute G_{G_{0},G_{1}}(k), we establish two very different yet equivalent characterizations for this value. One is a simple formula in k, namely G_{G_{0},G_{1}}(k) = gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}). Another is a formula utilizing the generalized Pisano period π_{G_{0},G_{1}}(m) of the Gibonacci sequence modulo m, namely G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k}. We summarize our main results in Table 1.

k  F(k) L(k)  G_{G_{0},G_{1}}(k) Proof in this paper
k ≡ 0, 4, 8 (mod 12)  F_{k/2} 5F_{k/2} F_{k/2}^{a} or 5F_{k/2}^{b}  Theorem 32
k ≡ 2, 6, 10 (mod 12)  L_{k/2} L_{k/2}  L_{k/2}  Theorem 33
k ≡ 3, 9 (mod 12)  2  2  2^{c}  Theorem 38
k ≡ 1, 5, 7, 11 (mod 12)  1  1  1^{c}  Theorem 39

Table 1: Summary of our main results

a This value holds if and only if gcd(G_{0} + G_{2}, G_{1} + G_{3}) = 1.

b This value holds if and only if gcd(G_{0} + G_{2}, G_{1} + G_{3}) ≠ 1.
c These values hold if G_{1}^{2} − G_{0}G_{1} − G_{0}^{2} = ±1. The case when

G_{1}^{2} − G_{0}G_{1} − G_{0}^{2} ≠ ±1 is addressed in Section 6

The paper is broken down as follows. In Section 2, we give a brief overview of necessary definitions and identities; in particular, we prove a few known results whose proofs seem to be missing in the literature. In Section 3, we provide proofs of our two characterizations for G_{G_{0},G_{1}}(k). In Sections 4 and 5, we prove our main results for the values G_{G_{0},G_{1}}(k) when k is even and odd, respectively. In Section 6, we explore three tantalizing applications of our G_{G_{0},G_{1}}(k) characterizations. Finally, in Section 7, we provide five open questions motivated by results in this paper.

2 Definitions and preliminary identities

Many results in this section are well known, and we provide references to where a proof of each result can be found. Some other lesser “well-known” results have no proofs in the literature as far as we have exhaustively searched, and for those results we do provide our own proofs. We use the convention of denoting these well-known results as propositions.

Definition 3. The generalized Fibonacci sequence (G_{n})_{n≥0} is defined by the recurrence relation

G_{n} = G_{n−1} + G_{n−2}

for all n ≥ 2 and with arbitrary initial conditions G_{0}, G_{1} ∈ ℤ. The Fibonacci sequence (F_{n})_{n≥0} is recovered when G_{0} = 0 and G_{1} = 1, and the Lucas sequence (L_{n})_{n≥0} is recovered when G_{0} = 2 and G_{1} = 1. For brevity, we use the term Gibonacci sequence to refer to any generalized Fibonacci sequence.

The following closed form expression for the Fibonacci sequence in Proposition 4 was derived and first published by Jacques Binet in 1843, but it was known at least a century earlier by Abraham de Moivre in 1718. We include this proposition and the related Proposition 5 that follows it because we use them to prove Identities (6), (7), and (8) in Lemma 9. In these two propositions, we set α := \frac{1+\sqrt{5}}{2} and β := \frac{1−\sqrt{5}}{2}.

Proposition 4. For n ∈ ℤ, the Fibonacci number F_{n} has the closed form

F_{n} = \frac{α^{n} − β^{n}}{α − β} .

Proposition 5. For n ∈ ℤ, the Lucas number L_{n} has the closed form

L_{n} = α^{n} + β^{n}.

Proposition 6. The following five identities hold:

L_{n} = F_{n+1} + F_{n−1}  for all n ∈ ℤ;  (1)
F_{2n} = F_{n}L_{n}  for all n ∈ ℤ;  (2)
G_{m+n} = F_{m−1}G_{n} + F_{m}G_{n+1}  for all m, n ≥ 1;  (3)
G_{i} = G_{0}F_{i−1} + G_{1}F_{i}  for all i ≥ 1;  (4)
∑_{i=1}^{n} G_{i} = G_{n+2} − G_{2}  for all n ≥ 1.  (5)

Proof. Identities (1), (2), (3), and (5), respectively, are proven by Vajda in his Identities (6), (13), (8), and (33), respectively [21, pp. 24,25,38]. Identity (4) follows from Identity (3) if we set m := i and n := 0.

Proposition 7. (Generalized Cassini’s Identity) For all n ≥ 0, the following equality holds: G_{n+1}G_{n−1} − G_{n}^{2} = (−1)^{n} · D_{G_{0},G_{1}}, where D_{G_{0},G_{1}} = G_{1}^{2} − G_{0}G_{1} − G_{0}^{2}.

Proof. A generalization of this well-known identity is stated in Rabinowitz [12, Theorem 8].

Though many encyclopedic resources such as Vajda [21] and Koshy [11] give nice closed forms for F_{j−1} + F_{j+1} and L_{j−1} + L_{j+1}, the literature surprisingly lacks a closed form for G_{j−1} + G_{j+1}. We fill this gap in the literature with Lemma 8 below, and this lemma along with the three identities in Lemma 9 helps us prove the four Gibonacci propositions to follow in Subsection 2.1.

Lemma 8. For all j ≥ 1, the following identity holds:

G_{j−1} + G_{j+1} = G_{0}L_{j−1} + G_{1}L_{j}.

Proof. Let j ≥ 1 be given. Observe the sequence of equalities

G_{j−1} + G_{j+1} = (G_{0}F_{j−2} + G_{1}F_{j−1}) + (G_{0}F_{j} + G_{1}F_{j+1}) (by Proposition 6, Identity (4))
= G_{0}(F_{j−2} + F_{j}) + G_{1}(F_{j−1} + F_{j+1})
= G_{0}L_{j−1} + G_{1}L_{j}.  (by Proposition 6, Identity (1))

Hence the identity holds for all j ≥ 1.

To prove the propositions in Subsection 2.1, we also utilize three identities given in Lemma 9. Identities (6) and (7) of this lemma can be found in Koshy [11, Identities 70 and 71, p. 90], but he provides no proofs. It turns out that these two identities were originally stated in 1971 (though unfortunately again without proofs) in Dudley and Tucker [6]. The related Identity (8), in the form we provide and utilize in Subsection 2.1, does not appear to be in the literature. Due to the lack of proofs for any of these identities in the literature, for completion we prove these three identities in Lemma 9 by proving a single identity in which these three identities hold as a consequence (see Remark 10).

Lemma 9. For all j ≥ 0, the following three identities hold:

F_{4j+1} − 1 = F_{2j}L_{2j+1}  (6)
F_{4j+3} − 1 = F_{2j+2}L_{2j+1}  (7)
F_{4j+4} − 1 = F_{2j+3}L_{2j+1}.  (8)

Proof. Utilizing the closed forms for F_{n} and L_{n} in Propositions 4 and 5, for r, j ∈ ℤ we have the sequence of equalities

F_{2j+r}L_{2j+1} = \frac{α^{2j+r} − β^{2j+r}}{α − β} · (α^{2j+1} + β^{2j+1})

= \frac{α^{4j+r+1} − β^{4j+r+1} + α^{2j+r}β^{2j+1} − α^{2j+1}β^{2j+r}}{α − β}

= \frac{α^{4j+r+1} − β^{4j+r+1}}{α − β} + \frac{(αβ)^{2j+1} (α^{r−1} − β^{r−1})}{α − β}

= F_{4j+r+1} + (−1)^{2j+1} · \frac{α^{r−1} − β^{r−1}}{α − β}  (since αβ = −1)

= F_{4j+r+1} − F_{r−1}.

If we set r := 0, then we have F_{2j+0}L_{2j+1} = F_{4j+0+1} − F_{0−1} so Identity (6) holds since F_{−1} = 1. And if we set r := 2, then we have F_{2j+2}L_{2j+1} = F_{4j+2+1} − F_{2−1} so Identity (7) holds since F_{1} = 1. Lastly if we set r := 3, then we have F_{2j+3}L_{2j+1} = F_{4j+3+1} − F_{3−1} so Identity (8) holds since F_{2} = 1.

Remark 10. In proving Lemma 9, we actually proved the much stronger result that an infinite family of identities of the following form holds:

F_{4j+r+1} − F_{r−1} = F_{2j+r}L_{2j+1},

for all r, j ∈ ℤ. This follows since the closed formulas for F_{n} and L_{n}, given in Propositions 4 and 5, work for all integer values of n.

2.1 Four Gibonacci propositions

The following four Gibonacci identities (along with our characterizations for the values G_{G_{0},G_{1}}(k) given in Subsections 3.1 and 3.2 to follow) are used in the proofs of our main results in Sections 4 and 5:

G_{4j+1} − G_{1} = F_{2j}(G_{2j} + G_{2j+2})  (Proposition 11)
G_{4j+2} − G_{2} = F_{2j}(G_{2j+1} + G_{2j+3})  (Proposition 12)
G_{4j+3} − G_{1} = L_{2j+1}G_{2j+2}  (Proposition 13)
G_{4j+4} − G_{2} = L_{2j+1}G_{2j+3}  (Proposition 14).

These identities are stated in Koshy but without proof [11, p. 214], so for completeness we provide proofs for each proposition.

Proposition 11. For all j ≥ 0, the following identity holds:

G_{4j+1} − G_{1} = F_{2j}(G_{2j} + G_{2j+2}).

Proof. Let j ≥ 0 be given. Observe the sequence of equalities

F_{2j}(G_{2j} + G_{2j+2}) = F_{2j}(G_{0}L_{2j} + G_{1}L_{2j+1})  (by Lemma 8)
= G_{0} · F_{2j}L_{2j} + G_{1} · F_{2j}L_{2j+1}
= G_{0}F_{4j} + G_{1} · F_{2j}L_{2j+1}  (by Proposition 6, Identity (2))
= G_{0}F_{4j} + G_{1}(F_{4j+1} − 1)  (by Lemma 9, Identity (6))
= (G_{0}F_{4j} + G_{1}F_{4j+1}) − G_{1}
= G_{4j+1} − G_{1},  (by Proposition 6, Identity (4))

as desired. Hence G_{4j+1} − G_{1} = F_{2j}(G_{2j} + G_{2j+2}) for all j ≥ 0. Proposition 12. For all j ≥ 0, the following identity holds:

G_{4j+2} − G_{2} = F_{2j}(G_{2j+1} + G_{2j+3}).

Proof. Let j ≥ 0 be given. Observe the sequence of equalities

F_{2j}(G_{2j+1} + G_{2j+3}) = F_{2j}(G_{0}L_{2j+1} + G_{1}L_{2j+2})  (by Lemma 8)
= G_{0} · F_{2j}L_{2j+1} + G_{1} · F_{2j}L_{2j+2}
= G_{0} · F_{2j}L_{2j+1} + G_{1} · F_{2j}(L_{2j} + L_{2j+1})
= (G_{0} · F_{2j}L_{2j+1} + G_{1} · F_{2j}L_{2j+1}) + G_{1} · F_{2j}L_{2j}
= (G_{0} + G_{1}) · F_{2j}L_{2j+1} + G_{1} · F_{2j}L_{2j}
= G_{2} · F_{2j}L_{2j+1} + G_{1} · F_{2j}L_{2j}
= G_{2} · (F_{4j+1} − 1) + G_{1} · F_{2j}L_{2j}  (by Lemma 9, Identity (6))
= G_{2} · (F_{4j+1} − 1) + G_{1}F_{4j}  (by Proposition 6, Identity (2))
= (G_{1}F_{4j} + G_{2}F_{4j+1}) − G_{2}
= G_{4j+2} − G_{2},

where the last equality holds since for all i ≥ 1, the value G_{i} can be written in the following form G_{i} = G_{1}F_{i−2} + G_{2}F_{i−1} by Identity (3) of Proposition 6, if we set m := i − 1 and n := 1. Hence F_{4j+2} − G_{2} = F_{2j}(G_{2j+1} + G_{2j+3}) for all j ≥ 0. Proposition 13. For all j ≥ 0, the following identity holds:

G_{4j+3} − G_{1} = L_{2j+1}G_{2j+2}.

Proof. Let j ≥ 0 be given. Observe the sequence of equalities

G_{4j+3} − G_{1} = (G_{0}F_{4j+2} + G_{1}F_{4j+3}) − G_{1}  (by Proposition 6, Identity (4))
= G_{0}F_{4j+2} + G_{1}(F_{4j+3} − 1)
= G_{0}F_{4j+2} + G_{1}(F_{2j+2}L_{2j+1})  (by Lemma 9, Identity (7))
= G_{0}(F_{2j+1}L_{2j+1}) + G_{1}(F_{2j+2}L_{2j+1}) (by Proposition 6, Identity (2))
= L_{2j+1}(G_{0}G_{2j+1} + G_{1}F_{2j+2})
= L_{2j+1}G_{2j+2},  (by Proposition 6, Identity (4))

as desired. Hence G_{4j+3} − G_{1} = L_{2j+1}G_{2j+2} for all j ≥ 0.

Proposition 14. For all j ≥ 0, the following identity holds:

G_{4j+4} − G_{2} = L_{2j+1}G_{2j+3}.

Proof. Let j ≥ 0 be given. Observe the sequence of equalities

G_{4j+4} − G_{2} = (G_{0}F_{4j+3} + G_{1}F_{4j+4}) − G_{2}  (by Proposition 6, Identity (4))
= (G_{0}F_{4j+3} + G_{1}F_{4j+4}) − (G_{0} + G_{1})
= G_{0}(F_{4j+3} − 1) + G_{1}(F_{4j+4} − 1)
= G_{0}(F_{2j+2}L_{2j+1}) + G_{1}(F_{4j+4} − 1)  (by Lemma 9, Identity (7))
= G_{0}(F_{2j+2}L_{2j+1}) + G_{1}(F_{2j+3}L_{2j+1})  (by Lemma 9, Identity (8))
= L_{2j+1}(G_{0}F_{2j+2} + G_{1}F_{2j+3})
= L_{2j+1}G_{2j+3},  (by Proposition 6, Identity (4))

as desired. Hence G_{4j+4} − G_{2} = L_{2j+1}G_{2j+3} for all j ≥ 0.

3 Two equivalent formulas used to compute G_{G_{0},G_{1}}(k)

The first two major results of this paper are given in this section. We provide two seemingly different, yet equivalent, formulas that compute the value G_{G_{0},G_{1}}(k), the GCD of the sums of k consecutive Gibonacci numbers. These two different characterizations not only help prove our main results in Sections 4 and 5, but also lead to some tantalizing applications in Section 6.

3.1 A simple GCD characterization

In this subection, we give our first of two characterizations for the value G_{G_{0},G_{1}}(k). Moreover, we establish why it suffices to consider only the Gibonacci sequences with relatively prime initial conditions, since the value G_{G_{0},G_{1}}(k) for a sequence with non-relatively prime initial values G_{0} and G_{1} turns out to be a multiple of the value G_{G′_{0},G′_{1}}(k) of a related sequence with relatively prime initial values G′_{0} and G′_{1}.

Theorem 15. The largest integer that divides every sum of k consecutive Gibonacci numbers is gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}). That is, G_{G_{0},G_{1}}(k) = gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}).

Proof. Fix n ∈ ℕ and consider the arbitrary sum G_{n} +G_{n+1} +⋯+G_{n+(k−1)} of k consecutive Gibonacci numbers. Then we have the sequence of equalities

∑_{i=0}^{k−1} G_{n+i} = ∑_{i=1}^{n+(k−1)} G_{i} − ∑_{i=1}^{n−1} G_{i}
= (G_{(n+k−1)+2} − G_{2}) − (G_{(n−1)+2} − G_{2})  (by Proposition 6, Identity (5))
= G_{n+k+1} − G_{n+1}
= G_{(k+1)+n} − G_{n+1}
= F_{n−1}G_{k+1} + F_{n}G_{k+2} − G_{n+1}  (by Proposition 6, Identity (3))
= F_{n−1}G_{k+1} + F_{n}G_{k+2} − F_{n}G_{2} − F_{n−1}G_{1} (by Proposition 6, Identity (3))
= F_{n−1}G_{k+1} − F_{n−1}G_{1} + F_{n}G_{k+2} − F_{n}G_{2}
= F_{n−1}(G_{k+1} − G_{1}) + F_{n}(G_{k+2} − G_{2}).

Hence our sequence of finite sums of k consecutive Gibonacci numbers can be written as

(∑_{i=0}^{k−1} G_{n+i})_{n≥1} = (F_{n−1}(G_{k+1} − G_{1}) + F_{n}(G_{k+2} − G_{2}))_{n≥1}.  (9)

Set q := gcd(G_{k+1} −G_{1}, G_{k+2} −G_{2}). We will show that q ≤ G_{G_{0},G_{1}}(k) and that G_{G_{0},G_{1}}(k) ≤ q, and hence G_{G_{0},G_{1}}(k) = q follows. Since q divides both G_{k+1} − G_{1} and G_{k+2} − G_{2}, then q divides every term in our sequence, and therefore q ≤ G_{G_{0},G_{1}}(k), as desired. Next we establish that G_{G_{0},G_{1}}(k) ≤ q. Observe that the GCD of every term in our sequence is at most the GCD of the first two terms. Consider the GCD of the first two terms. We have the sequence of inequalities and equalities

G_{G_{0},G_{1}}(k) ≤ gcd (F_{0}(G_{k+1} − G_{1}) + F_{1}(G_{k+2} − G_{2}) , F_{1}(G_{k+1} − G_{1}) + F_{2}(G_{k+2} − G_{2}))
= gcd (G_{k+2} − G_{2} , G_{k+1} − G_{1} + G_{k+2} − G_{2})
= gcd (G_{k+2} − G_{2} , G_{k+1} − G_{1})
= q,

where the second equality holds by the property gcd(a, b+a) = gcd(a, b). Thus G_{G_{0},G_{1}}(k) ≤ q, as desired. We conclude that G_{G_{0},G_{1}}(k) = gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}).

Corollary 16. The largest integer to divide every sum of k consecutive Fibonacci numbers is precisely gcd(F_{k+1} − F_{1}, F_{k+2} − F_{2}). That is, F(k) = gcd(F_{k+1} − 1, F_{k+2} − 1).

Corollary 17. The largest integer to divide every sum of k consecutive Lucas numbers is precisely gcd(L_{k+1} − L_{1}, L_{k+2} − L_{2}). That is, L(k) = gcd(L_{k+1} − 1, L_{k+2} − 3).

After proving the following two results, Lemma 18 and Theorem 19, we will conclude that it is sufficient to explore only the Gibonacci sequences which have relatively prime initial values.

Lemma 18. For all n ∈ ℤ, the values gcd(G_{n+1}, G_{n+2}) and gcd(G_{n}, G_{n+1}) coincide. In particular, gcd(G_{0}, G_{1}) = gcd(G_{n}, G_{n+1}) holds for all n ∈ ℤ

Proof. Observe the following sequence of equalities.

gcd(G_{n+1}, G_{n+2}) = gcd(G_{n+1}, G_{n+1} + G_{n})
= gcd(G_{n+1}, G_{n}).

Hence gcd(G_{0}, G_{1}) = gcd(G_{n}, G_{n+1}) as desired for all n ∈ ℤ.

Theorem 19. Fix G_{0}, G_{1} ∈ ℤ and set d := gcd(G_{0}, G_{1}). Then the GCD of every sum of k consecutive Gibonacci numbers in the sequence (G_{n})_{n≥0} is d times the GCD of every sum of k consecutive Gibonacci numbers in the new sequence {G′_{n}}_{n=0}^{∞} generated by the relatively prime initial conditions G′_{0} = \frac{G_{0}}{d} and G′_{1} = \frac{G_{1}}{d}. In particular, we have the following:

G_{G_{0},G_{1}}(k) = d · G_{G′_{0},G′_{1}}(k).

Proof. Set d := gcd(G_{0}, G_{1}). By Lemma 18, we have gcd(G_{k+1}, G_{k+2}) = gcd(G_{0}, G_{1}) = d for all k ∈ ℤ. By Theorem 15, the largest positive integer that divides every sum of k consecutive Gibonacci numbers is gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}). Moreover, since d divides G_{0} and G_{1}, then d divides every term in the sequence (G_{n})_{n≥0}. In particular, \frac{G_{k+1}−G_{1}}{d} and \frac{G_{k+2}−G_{2}}{d} are integers. Observe the sequence of equalities

gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}) = gcd (d · \frac{G_{k+1} − G_{1}}{d} , d · \frac{G_{k+2} − G_{2}}{d} )

= d · gcd (\frac{G_{k+1} − G_{1}}{d} , \frac{G_{k+2} − G_{2}}{d} ) .

Notice that by Theorem 15, the value gcd (\frac{G_{k+1}−G_{1}}{d} , \frac{G_{k+2}−G_{2}}{d} ) is the GCD of the sum of k

consecutive Gibonacci in the new sequence \{G′_{n}\}_{n=0}^{∞} generated by the initial values G′_{0} = \frac{G_{0}}{d} and G′_{1} = \frac{G_{1}}{d}. Clearly G′_{0} and G′_{1} are relatively prime. In particular, we have

G_{G_{0},G_{1}}(k) = d · G_{G′_{0},G′_{1}}(k),

as desired.

Convention 20. In order to give a complete classification of the GCD of every sum of k consecutive Gibonacci numbers, as a consequence of Theorem 19, we need only to consider Gibonacci sequences with relatively prime initial values.

3.2 A generalized Pisano period characterization

As in the setting of the Fibonacci and Lucas sequences modulo m, it is well known that the Gibonacci sequence modulo m is also periodic. Hence it makes sense to consider the period π_{G_{0},G_{1}}(m) of this sequence given in the following definition.

Definition 21. Let m ≥ 2. The generalized Pisano period, π_{G_{0},G_{1}}(m), of the Gibonacci sequence (G_{n})_{n≥0} is the smallest positive integer r such that

G_{r} ≡ G_{0} (mod m) and G_{r+1} ≡ G_{1} (mod m).

In the Fibonacci (respectively, Lucas) setting we denote this period by π_{F} (m) (respectively, π_{L}(m)).

Lemma 22. The value m divides the sum of any π_{G_{0},G_{1}}(m) consecutive Gibonacci numbers. That is, m divides ∑_{i=1}^{π_{G_{0},G_{1}}(m)} G_{n+i} for any fixed n ∈ ℤ.

Proof. We need to prove m divides the sum of the terms in a generalized Pisano period of any Gibonacci sequence. However, by the periodicity of generalized Pisano periods, it suffices to show that m divides the sum of the terms in the particular generalized Pisano period given by (G_{1}, G_{2}, …, G_{π_{G_{0},G_{1}}(m)}). By Identity (5) of Proposition 6 we have

∑_{i=1}^{π_{G_{0},G_{1}}(m)} G_{i} = G_{π_{G_{0},G_{1}}(m)+2} − G_{2}.

However, by the definition of a generalized Pisano period, G_{π_{G_{0},G_{1}}(m)+2} ≡ G_{2} (mod m).

Hence m divides G_{π_{G_{0},G_{1}}(m)+2} − G_{2} and therefore also divides ∑_{i=1}^{π_{G_{0},G_{1}}(m)} G_{i} as desired. It follows that m divides the sum of the terms in the particular generalized Pisano period (G_{1}, G_{2}, …, G_{π_{G_{0},G_{1}}(m)}), which proves that m divides the sum of any π_{G_{0},G_{1}}(m) consecutive Gibonacci numbers.

Remark 23. It can be proven that the value π_{G_{0},G_{1}}(m) in Lemma 22 is minimal with respect to the following property: If s ∈ ℕ with s < π_{G_{0},G_{1}}(m), then m cannot divide the sum of every s consecutive Gibonacci numbers.

Theorem 24. The value π_{G_{0},G_{1}}(m) divides k if and only if m divides G_{G_{0},G_{1}}(k).

Proof. Let k ∈ ℕ be fixed. Suppose π_{G_{0},G_{1}}(m) divides k. By Lemma 22, we know that m divides the sum of any π_{G_{0},G_{1}}(m) consecutive Gibonacci numbers. Thus m divides any sum of t · π_{G_{0},G_{1}}(m) consecutive Gibonacci numbers for any t ∈ ℕ. From our assumption that π_{G_{0},G_{1}} divides k, it follows that k = t_{0} · π_{G_{0},G_{1}}(m) for some t_{0} ∈ ℕ. Hence m is a common divisor of any sum of k consecutive Gibonacci numbers, which proves that m divides the greatest common divisor G_{G_{0},G_{1}}(k) as desired.

Assume m divides G_{G_{0},G_{1}}(k). Then m divides gcd(G_{k+2} −G_{2}, G_{k+1} −G_{1}). Thus m divides G_{k+2} − G_{2} and m divides G_{k+1} − G_{1}. Hence G_{k+2} ≡ G_{2} (mod m) and G_{k+1} ≡ G_{1} (mod m). By the periodicity of the sequence (G_{n})_{n≥0} under a modulus, π_{G_{0},G_{1}}(m) divides k.

Theorem 25. For all k ≥ 1, we have G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k}.

Proof. For ease of notation, set ℓ(k) := lcm{m | π_{G_{0},G_{1}}(m) divides k}. Then it suffices to prove that G_{G_{0},G_{1}}(k) divides ℓ(k) and that ℓ(k) divides G_{G_{0},G_{1}}(k). Since both G_{G_{0},G_{1}}(k) and ℓ(k) are strictly greater than 0, we only need to show that any divisor of G_{G_{0},G_{1}}(k) is a divisor of ℓ(k), and vice versa. Let d_{0} be a divisor of G_{G_{0},G_{1}}(k). Then by Theorem 24, it follows that π_{G_{0},G_{1}}(d_{0}) divides k. Hence by definition of ℓ(k), we conclude that d_{0} divides ℓ(k) as desired. Now, suppose that d_{1} is a divisor of ℓ(k). Then by definition of ℓ(k), it must be that π_{G_{0},G_{1}}(d_{1}) divides k. Hence by Theorem 24, we conclude that d_{1} divides G_{G_{0},G_{1}}(k) as desired.

4 Main results for G_{G_{0},G_{1}}(k) when k is even

In this section, we provide our main results for the values G_{G_{0},G_{1}}(k) when k is even. There are two cases that we consider; namely, when k ≡ 0, 4, or 8 (mod 12) given in Subsection 4.1 and when k ≡ 2, 6, or 10 (mod 12) given in Subsection 4.2. From Table 1 in Section 1, we see that the second row, which corresponds to k ≡ 2, 6, 10 (mod 12), gives the same value L_{k/2} regardless if we are considering F(k), L(k), or G_{G_{0},G_{1}}(k); that is, no matter which initial values for the sequence {G_{i}}_{n=0}^{∞} are chosen, the values F(k), L(k), and G_{G_{0},G_{1}}(k) coincide. However in the first row of this table when k ≡ 0, 4, 8 (mod 12), it turns out that the value of G_{G_{0},G_{1}}(k) depends on the initial conditions G_{0} and G_{1}, and hence the values F(k), L(k), and G_{G_{0},G_{1}}(k) may differ. More precisely, for a fixed k such that k ≡ 0, 4, 8 (mod 12), we will see in the following subsection that the behavior of these latter three values depends on an easily computed parameter which we denote by δ_{G_{0},G_{1}}, defined as δ_{G_{0},G_{1}} := gcd(G_{0} + G_{2}, G_{1} + G_{3}).

4.1 The k ≡ 0, 4, 8 (mod 12) case

Lemmas 27 is used to conclude our penultimate result, Lemma 31, which essentially implies that the value of G_{G_{0},G_{1}}(k) is determined soley by the value k and the parameter δ_{G_{0},G_{1}}.

Remark 26. It is worth noting that in this subsection, only our main result, Theorem 32, involves the value k. The two lemmas have no mention of the value k, and in fact, say something quite interesting about any Gibonacci sequence (G_{n})_{n≥0}. In particular, as a consequence of Lemma 31, the value gcd(G_{0} + G_{2}, G_{1} + G_{3}), which is the parameter δ_{G_{0},G_{1}}, equals 1 or 5, and moreover the value gcd(G_{n} + G_{n+2}, G_{n+1} + G_{n+3}) equals δ_{G_{0},G_{1}} for all n ≥ 0.

Lemma 27. Fix an integer i ≥ 0. It follows that the value gcd(G_{i} + G_{i+2}, G_{i+1} + G_{i+3}) is either 1 or 5.

Proof. Suppose gcd(G_{0}, G_{1}) = 1. Let d be any divisor of gcd(G_{i} + G_{i+2}, G_{i+1} + G_{i+3}). Since d divides the sums G_{i} + G_{i+2} and G_{i+1} + G_{i+3}, we have the congruences

G_{i} + G_{i+2} ≡ 0 (mod d)  (10)
G_{i+1} + G_{i+3} ≡ 0 (mod d).  (11)

We can express the three values G_{i+2}, G_{i+1} and G_{i+3}, respectively, in terms of G_{i} as follows:

G_{i+2} ≡ −G_{i} (mod d)  (by Congruence (10))  (12)
G_{i+1} = G_{i+2} − G_{i}
≡ −G_{i} − G_{i} (mod d)  (by Congruence (12))
≡ −2G_{i} (mod d)  (13)
G_{i+3} = G_{i+2} + G_{i+1}
≡ −G_{i} − 2G_{i} (mod d)  (by Congruences (12) and (13))
≡ −3G_{i} (mod d).  (14)

Then by Congruences (11), (13), and (14), we have

0 ≡ G_{i+1} + G_{i+3} ≡ −2G_{i} − 3G_{i} = −5G_{i} (mod d),

and thus 5G_{i} ≡ 0 (mod d). Furthermore, observe that by adding Congruences (10) and (11) we get that G_{i+2} + G_{i+4} ≡ 0 (mod d). Hence d is a divisor of G_{i+1} + G_{i+3} and G_{i+2} + G_{i+4}. Therefore d divides gcd(G_{i+1} + G_{i+3}, G_{i+2} + G_{i+4}). Analogous to our previous work, we can express the three values G_{i+3}, G_{i+2} and G_{i}, respectively, in terms of G_{i+1} to find that d divides 5G_{i+1}. Since d divides both 5G_{i} and 5G_{i+1} and gcd(G_{i}, G_{i+1}) = 1, it must be that d divides 5. Thus d = 1 or d = 5.

Remark 28. It is worthy to note that both values 1 and 5 are attained in Lemma 27. For i = 0 in the Fibonacci sequence, we have gcd(F_{0} + F_{2}, F_{1} + F_{3}) = gcd(1, 2) = 1. Moreover, for i = 0 in the Lucas sequence, we have gcd(L_{0} +L_{2}, L_{1} +L_{3}) = gcd(5, 5) = 5. However, it is not yet clear that for fixed initial values G_{0} and G_{1}, the values gcd(G_{n} + G_{n+2}, G_{n+1} + G_{n+3}) will be the same for all n. However, a consequence of Lemma 31 will confirm the latter. But first we need to define what we mean for two Gibonacci sequences to be equivalent (up to shift) modulo m for some m ≥ 2.

Definition 29. Let m ≥ 2. Let G and G′ denote the Gibonacci sequences (G_{n})_{n≥0} and (G′_{n})_{n≥0}, respectively, with corresponding generalized Pisano periods π_{G_{0},G_{1}}(m) and π_{G′_{0},G′_{1}}(m). We say that G modulo m is equivalent (up to shift) to G′ modulo m if the following two conditions hold:

(i) The values π_{G_{0},G_{1}}(m) and π_{G′_{0},G′_{1}}(m) coincide.

(ii) For some r ∈ ℤ, we have G_{r+n} ≡ G′_{n} (mod m) for all n ∈ ℤ.

Remark 30. It can be shown that the value δ_{G_{0},G_{1}} equals 5 if and only if the Gibonacci sequence (G_{n})_{n≥0} modulo 5 is equivalent (up to shift) to the Lucas sequence (L_{n})_{n≥0} modulo 5.

Lemma 31. The value δ_{G_{0},G_{1}} equals 1 or 5, and we have the following:

gcd(G_{n} + G_{n+2}, G_{n+1} + G_{n+3}) = δ_{G_{0},G_{1}}

for all n ≥ 0.

Proof. Let H_{n} = G_{n} + G_{n+2}. Observe that

H_{n} + H_{n+1} = (G_{n} + G_{n+2}) + (G_{n+1} + G_{n+3})
= (G_{n} + G_{n+1}) + (G_{n+2} + G_{n+3})
= G_{n+2} + G_{n+4}
= H_{n+2}.

Thus the sequence (H_{n})_{n≥0} is itself a generalized Fibonacci sequence. By Lemma 18, we have gcd(H_{0}, H_{1}) = gcd(H_{n}, H_{n+1}) for all n ≥ 0.

We are now ready to prove the main theorem of this subsection. We utilize the parameter δ_{G_{0},G_{1}}. Recall from Remark 28 that δ_{G_{0},G_{1}} = 1 for the Fibonacci sequence, δ_{G_{0},G_{1}} = 5 for the Lucas sequence, and δ_{G_{0},G_{1}} = 1 or 5 for Gibonacci sequences.

Theorem 32. If k ≡ 0, 4, 8 (mod 12), then gcd(G_{k+1} −G_{1}, G_{k+2} −G_{2}) = δ_{G_{0},G_{1}} ·F_{k/2}, where δ_{G_{0},G_{1}} = gcd(G_{0} + G_{2}, G_{1} + G_{3}). In particular, we conclude the following:

F(k) = F_{k/2}
L(k) = 5F_{k/2}
G_{G_{0},G_{1}}(k) = δ_{G_{0},G_{1}} · F_{k/2}.

Proof. Assume k ≡ 0, 4, 8 (mod 12). Then k ≡ 0 (mod 4). Thus k = 4j for some j ∈ ℤ. Observe the sequence of equalities

gcd(G_{k+1}−G_{1}, G_{k+2} − G_{2})
= gcd(G_{4j+1} − G_{1}, G_{4j+2} − G_{2})
= gcd(F_{2j}(G_{2j} + G_{2j+2}), F_{2j}(G_{2j+1} + G_{2j+3})) (by Propositions 11 and 12)
= F_{2j} · gcd(G_{2j} + G_{2j+2}, G_{2j+1} + G_{2j+3})
= F_{k/2} · gcd(G_{2j} + G_{2j+2}, G_{2j+1} + G_{2j+3}).

Observe that from Lemma 31, we know gcd(G_{2j} + G_{2j+2}, G_{2j+1} + G_{2j+3}) = δ_{G_{0},G_{1}}. Thus gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}) = δ_{G_{0},G_{1}} · F_{k/2}. We conclude that if k ≡ 0, 4, 8 (mod 12), then F(k) = F_{k/2} and L(k) = 5F_{k/2} and G_{G_{0},G_{1}}(k) = δ_{G_{0},G_{1}} · F_{k/2}.

4.2 The k ≡ 2, 6, 10 (mod 12) case

Whereas the k ≡ 0, 4, 8 (mod 12) case in Subsection 4.1 had variability in the value G_{G_{0},G_{1}}(k) dependent on the initial values G_{0} and G_{1}, the k ≡ 2, 6, 10 (mod 12) case in this subsection is more straightforward since all values F(k), L(k), and G_{G_{0},G_{1}}(k) coincide, regardless of the initial values.

Theorem 33. If k ≡ 2, 6, 10 (mod 12), then gcd(G_{k+1} − 1, G_{k+2} − 3) = L_{k/2}. In particular, we conclude the following:

F(k) = L_{k/2}
L(k) = L_{k/2}
G_{G_{0},G_{1}}(k) = L_{k/2}.

Proof. Assume k ≡ 2, 6, 10 (mod 12). Then k ≡ 2 (mod 4). Thus k = 4j + 2 for some j ∈ ℤ. Observe the sequence of equalities

gcd(G_{k+1}−G_{1}, G_{k+2} − G_{2})
= gcd(G_{(4j+2)+1} − G_{1}, G_{(4j+2)+2} − G_{2})
= gcd(G_{4j+3} − G_{1}, G_{4j+4} − G_{2})
= gcd(L_{2j+1}G_{2j+2}, L_{2j+1}G_{2j+3})  (by Propositions 13 and 14)
= L_{2j+1} · gcd(G_{2j+2}, G_{2j+3})
= L_{2j+1}  (since gcd(G_{2j+2}, G_{2j+3}) = 1)
= L_{k/2}.

Thus gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}) = L_{k/2}. We conclude that if k ≡ 2, 6, 10 (mod 12), then we have F(k) = L(k) = G_{G_{0},G_{1}}(k) = L_{k/2}.

5 Main results for G_{G_{0},G_{1}}(k) when k is odd

The two main results in this section, Theorems 38 and 39, rely on the generalized Pisano period π_{G_{0},G_{1}}(m) being even for all m > 2. The period π_{F} (m) of the Fibonacci sequence modulo m being even for all m > 2 is well known and proven in 1960 by Wall [22], and a clever short proof was given more recently by Elsenhans and Jahnel [8]. Similarly, the period π_{L}(m) of the Lucas sequence modulo m is also even for all m > 2; however, this well-known result seems to lack a proof in the literature, though it is stated in a number of sources. A corollary to the following lemmas will not only prove that the Fibonacci and Lucas periods are even, but also provides a sufficiency condition on the initial values G_{0} and G_{1} that will give the defined G_{G_{0},G_{1}}(k) values we gave in Table 1 in this case when k is odd.

5.1 A sufficiency criterion for when π_{G_{0},G_{1}}(m) is even for all m > 2

Lemma 34. Let D_{G_{n},G_{n+1}} denote the value G_{n+1}^{2} − G_{n}G_{n+1} − G_{n}^{2}. Then the following holds:

D_{G_{n},G_{n+1}} = (−1)^{n} · D_{G_{0},G_{1}}  (15)

for all n ≥ 0. In particular, we have |D_{G_{n},G_{n+1}}| = |D_{G_{0},G_{1}}| for all n ≥ 0. Proof. We prove this by induction on n. Identity (15) clearly holds when n = 0. So suppose it holds for some k ≥ 0, and consider D_{G_{k+1},G_{k+2}}. Then we have

D_{G_{k+1},G_{k+2}} = G_{k+2}^{2} − G_{k+1}G_{k+2} − G_{k+1}^{2}
= (G_{k} + G_{k+1})^{2} − G_{k+1}(G_{k} + G_{k+1}) − G_{k+1}^{2}
= G_{k}^{2} + 2G_{k}G_{k+1} + G_{k+1}^{2} − G_{k}G_{k+1} − G_{k+1}^{2} − G_{k+1}^{2}
= −(G_{k+1}^{2} − G_{k}G_{k+1} − G_{k}^{2})
= −(−1)^{k} · D_{G_{0},G_{1}}
= (−1)^{k+1} · D_{G_{0},G_{1}},

where the fifth equality holds by the induction hypothesis. Hence Identity (15) holds for all n ≥ 0. Lemma 35. For all integers m > 2, the following congruence holds:

(−1)^{π_{G_{0},G_{1}}(m)} · D_{G_{0},G_{1}} ≡ D_{G_{0},G_{1}} (mod m).

Proof. By the generalized Cassini’s identity, given in Proposition 7, it follows that

G_{n+1}G_{n−1} − G_{n}^{2} = (−1)^{n} · D_{G_{0},G_{1}}.

Substituting π_{G_{0},G_{1}}(m) for n in the latter identity, we have

G_{π_{G_{0},G_{1}}(m)+1} · G_{π_{G_{0},G_{1}}(m)−1} − G_{π_{G_{0},G_{1}}(m)}^{2} = (−1)^{π_{G_{0},G_{1}}(m)} · D_{G_{0},G_{1}}.

Since G_{π_{G_{0},G_{1}}(m)+i} ≡ G_{i} (mod m) for all i, we get the sequence of congruences

(−1)^{π_{G_{0},G_{1}}(m)} · D_{G_{0},G_{1}} ≡ G_{1}G_{−1} − G_{0}^{2} (mod m)
≡ G_{1}(G_{1} − G_{0}) − G_{0}^{2} (mod m)
≡ D_{G_{0},G_{1}} (mod m),

and the claim holds. Corollary 36. For all m > 2, the Pisano periods of the Fibonacci and Lucas sequences are even. In the general setting, if D_{G_{0},G_{1}} = ±1 then π_{G_{0},G_{1}}(m) is even for all m > 2.

Proof. By Lemma 35, we have (−1)^{π_{G_{0},G_{1}}(m)} · D_{G_{0},G_{1}} ≡ D_{G_{0},G_{1}} (mod m) for all m > 2. We address the Fibonacci, Lucas, and Gibonacci settings in three separate cases. Case 1: If G_{0} = 0 and G_{1} = 1, then D_{G_{0},G_{1}} = 1, and we have (−1)^{π_{F} (m)} ≡ 1 (mod m), which implies that π_{F} (m) is even for all m > 2.

Case 2: If G_{0} = 2 and G_{1} = 1, then D_{G_{0},G_{1}} = −5, and we have (−1)^{π_{L}(m)}5 ≡ 5 (mod m), which implies that π_{L}(m) is even for all m > 2 when gcd(5, m) = 1. If on the other hand gcd(5, m) ≠ 1, then m = 5^{s}t for some s, t ∈ ℕ with gcd(5, t) = 1. A consequence of Theorem 2 by Wall yields π_{L}(m) = lcm (π_{L}(5^{s}), π_{L}(t)) [22]. But since π_{L}(5) divides π_{L}(5^{s}) and π_{L}(5) = 4, then 4 divides lcm (π_{L}(5^{s}), π_{L}(t)). Hence π_{L}(m) is even for all m > 2.

Case 3: In general, for any initial values G_{0} and G_{1} with D_{G_{0},G_{1}} = ±1, it follows that (−1)^{π_{G_{0},G_{1}}(m)} ≡ 1 (mod m). Hence π_{G_{0},G_{1}}(m) is even for all m > 2 when D_{G_{0},G_{1}} = ±1.

5.2 The k ≡ 3, 9 (mod 12) case

Lemma 37. If k is odd and π_{G_{0},G_{1}}(m) is even for all m > 2, then G_{G_{0},G_{1}}(k) ≤ 2.

Proof. Suppose that π_{G_{0},G_{1}}(m) is even for all m > 2 and k is odd. By Theorem 25, we have G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k}. Since π_{G_{0},G_{1}}(m) is even for all m > 2 and k is odd, π_{G_{0},G_{1}}(m) cannot divide k for all m > 2. Thus G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k} ≤ 2 as desired.

Theorem 38. If k ≡ 3, 9 (mod 12) and π_{G_{0},G_{1}}(m) is even for all m > 2, then G_{G_{0},G_{1}}(k) = 2. In particular, we conclude the following:

F(k) = 2
L(k) = 2
G_{G_{0},G_{1}}(k) = 2 if D_{G_{0},G_{1}} = ±1.

Proof. Suppose k ≡ 3, 9 (mod 12) and that π_{G_{0},G_{1}}(m) is even for all m > 2. Then we have k ≡ 0 (mod 3). Since gcd(G_{0}, G_{1}) = 1, the Gibonacci sequence modulo 2 is equivalent (up to shift) to the sequence

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

Hence π_{G_{0},G_{1}}(2) = 3. By assumption, k ≡ 0 (mod 3) and thus π_{G_{0},G_{1}}(2) divides k. Therefore by Theorem 25, we have G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k} ≥ 2. However by Lemma 37, G_{G_{0},G_{1}}(k) ≤ 2 since k is odd. We conclude that if k ≡ 3, 9 (mod 12), then we have F(k) = L(k) = 2. Also if D_{G_{0},G_{1}} = ±1, then π_{G_{0},G_{1}}(m) is even and G_{G_{0},G_{1}}(k) = 2.

5.3 The k ≡ 1, 5, 7, 11 (mod 12) case

Theorem 39. If k ≡ 1, 5, 7, 11 (mod 12) and π_{G_{0},G_{1}}(m) is even for all m > 2, then G_{G_{0},G_{1}}(k) = 1. In particular, we conclude the following:

F(k) = 1
L(k) = 1
G_{G_{0},G_{1}}(k) = 1 if D_{G_{0},G_{1}} = ±1.

Proof. Suppose k ≡ 1, 5, 7, 11 (mod 12) and that π_{G_{0},G_{1}}(m) is even for all m > 2. As in the proof of Theorem 38, we know the fact that gcd(G_{0}, G_{1}) = 1 holds implies that π_{G_{0},G_{1}}(2) = 3. However, since we have k ≢ 0 (mod 3) it cannot be that π_{G_{0},G_{1}}(2) divides the value k. Therefore by Lemma 37, it follows that G_{G_{0},G_{1}}(k) = lcm{m | π_{G_{0},G_{1}}(m) divides k} = 1 as desired. We conclude that if k ≡ 1, 5, 7, 11 (mod 12), then we have F(k) = L(k) = 1. Also if D_{G_{0},G_{1}} = ±1, then G_{G_{0},G_{1}}(k) = 1.

6 Interesting applications

The Pisano period characterization of the value G_{G_{0},G_{1}}(k) not only yields the GCD of all sums of k consecutive Gibonacci numbers, but also leads to some interesting applications. In this section, we highlight three such applications.

6.1 Restrictions on the factors of G_{G_{0},G_{1}}(k) when k is odd

While the Fibonacci and Lucas sequences satisfy the property that both π_{F} (m) and π_{L}(m) are even for all m > 2, this is not the case in general. From this, we may exhibit odd values of k for which G_{G_{0},G_{1}}(k) is greater than two. We provide an example of this below and we place restrictions on the values of m that can make π_{G_{0},G_{1}}(m) odd later in this subsection. Using the generalized Pisano period characterization of G_{G_{0},G_{1}}(k), we place restrictions on the factors of G_{G_{0},G_{1}}(k).

Example 40. In this example, we will show that π_{1,4}(m) = 5 only when m = 11. Recall that by Theorems 38 and 39, the value G_{G_{0},G_{1}}(k) is 1 or 2 if k is odd and D_{G_{0},G_{1}} = ±1, where D_{G_{0},G_{1}} was defined to be G_{1}^{2} − G_{0}G_{1} − G_{0}^{2}. Hence if D_{G_{0},G_{1}} ≠ ±1, it is interesting to consider what are the possible values of G_{G_{0},G_{1}}(k) when k is odd. We shall consider the Gibonacci sequence with initial values G_{0} = 1 and G_{1} = 4, which we will call the (1, 4)- Gibonacci sequence. Observe that in this case, we have G_{1}^{2} − G_{0}G_{1} − G_{0}^{2} = 11 ≠ ±1, and hence the value G_{1,4}(k) when k is odd is not forced to be 1 or 2, necessarily. We consider the value G_{1,4}(k) when k = 5 by computing it in two different ways. First, we write out the (1, 4)-Gibonacci sequence as follows:

1, 4, 5, 9, 14, 23, 37, 60, 97, 157, 245, 402, 647, 849, 1496, …

Consider the first four terms of the sequence (∑_{i=0}^{k−1} G_{n+i})_{n≥1} when k = 5:

(4 + 5 + 9 + 14 + 23, 5 + 9 + 14 + 23 + 37, 9 + 14 + 23 + 37 + 60, 14 + 23 + 37 + 60 + 97, …),

or equivalently, (55, 88, 143, 231, …). By inspection, one may suspect that G_{1,4}(5) is 11. This can be affirmed by our simple GCD characterization as follows:

G_{1,4}(5) = gcd(G_{7} − G_{2}, G_{6} − G_{1}) = gcd(60 − 5, 37 − 4) = gcd(55, 33) = 11.

On the other hand, by using the generalized Pisano characterization of G_{G_{0},G_{1}}(k), we know

G_{1,4}(5) = 11 = lcm{m | π_{1,4}(m) divides 5}.

By Theorem 24, since 11 divides G_{1,4}(5), it must be that π_{1,4}(11) divides 5. Clearly π_{1,4}(11) ≠ 1. Hence π_{1,4}(11) = 5 is forced. Furthermore, since 11 is prime, its only divisors are 1 and 11. Hence the only divisors of lcm{m | π_{1,4}(m) divides 5} can be 1 or 11, and again employing Theorem 24, this implies that π_{1,4}(m) does not divide 5 for all m ≠ 1, 11. Hence, we can conclude that for the particular Gibonacci sequence with initial values G_{0} = 1 and G_{1} = 4, we know that the only modulus value m that yields π_{G_{0},G_{1}}(m) = 5 is the value m = 11.

Remark 41. Observe that in the previous example the values m = 11 and D_{1,4} = 11 coincide. When examining the (1, 24)-Gibonacci sequence, which yields an odd period for m = 29, we do not have m = D_{1,24}. However, the value m = 29 divides D_{1,24} = 551.

Proposition 42 (Wall, Theorem 8). If p is prime and p ≡ 3, 7, 13, 17 (mod 20), then it follows that π_{G_{0},G_{1}}(p^{e}) = π_{F} (p^{e}).

Since π_{F} (m) is even for all m > 2, Proposition 42 yields the immediate corollary.

Corollary 43. If p is prime and p ≡ 3, 7, 13, 17 (mod 20), then π_{G_{0},G_{1}}(p) is even no matter the choice of (coprime) initial conditions.

Theorem 44. There exists no prime p ≡ 3, 7, 13, 17 (mod 20) that can be a factor of G_{G_{0},G_{1}}(k) if k is odd.

Proof. Recall that by Theorem 24, the value π_{G_{0},G_{1}}(m) divides k if and only if m divides G_{G_{0},G_{1}}(k). So if p is a prime such that p ≡ 3, 7, 13, 17 (mod 20), then by Corollary 43, we know that π_{G_{0},G_{1}}(p) is even. However, if k is odd then surely π_{G_{0},G_{1}}(p) cannot divide k. Hence no prime of the form p ≡ 3, 7, 13, 17 (mod 20) can be a factor of G_{G_{0},G_{1}}(k) if k is odd.

6.2 Largest modulus m yielding a given Pisano period value π_{F} (m)

It is well known that for a given modulus m, the corresponding Pisano period π_{F} (m) is bounded above by 6m. This problem was proposed by Freyd in 1990 and answered by Brown in 1992 [2]. Moreover, this upper bound is achieved, for instance, when m = 10 since π_{F} (10) = 60. Furthermore, since the value π_{G_{0},G_{1}}(m) divides π_{F} (m), the value 6m also serves as an upper bound on any Gibonacci sequence. Hence, this question of an upper bound for any generalized Pisano period of a given modulus m is answered. However, a different but related question can be considered.

Question 45. For a given period k and a Gibonacci sequence with initial values G_{0} and G_{1}, what is the largest modulus value m such that π_{G_{0},G_{1}}(m) = k? We answer this question in the Fibonacci setting.^{2} We invite the interested reader to explore this problem in the Lucas and Gibonacci setting.

The following example exhibits how this question may be approached in the Fibonacci and Lucas settings, in particular, from the generalized Pisano period characterization of G_{G_{0},G_{1}}(k).

Example 46. Let us attempt to compute the largest modulus value m that yields a Pisano period π_{F} (m) equal to 60. Setting k := 60 in Theorem 32, we know F(60) = F_{30} = 832 040. By Theorem 24, we know the following:

π_{F} (m) divides 60 if and only if m divides F(60).

Hence we can conclude that if π_{F} (m) = 60, then m divides 832 040. So certainly, we have 832 040 as a potential maximum value m that makes π_{F} (m) = 60, but the question that remains is “Does π_{F} (832 040) indeed equal 60?” A simple computer computation reveals that this is so. Hence the largest modulus value m that yields a Pisano period π_{F} (m) equal to 60 is m = 832 040. In Theorem 48, we will prove that in general for k ≡ 0 (mod 4) that F(k) (or equivalently F_{k/2}) is the actual largest modulus that produces a Pisano period equal to k.

Before we prove our main result, Theorem 48, we need the following known results on the periods π_{F} (m) when m is a Fibonacci or Lucas number.

Lemma 47. The following identities hold:

π_{F} (F_{i}) = \begin{cases}2i, & if i ≥ 4 and even; \\ 4i, & if i ≥ 5 and odd. \end{cases}  (16)

π_{F} (L_{i}) = \begin{cases}4i, & if i ≥ 2 and even; \\ 2i, & if i ≥ 3 and odd. \end{cases}  (17)

In particular, it follows that range(π_{F}) = {3} ∪ {n ∈ 2ℤ | n ≥ 6}.

2This question was explored in 2018 in the Fibonacci setting by Dishong and Renault from an algorithmic approach that allows a computer to calculate all values m such that π_{F} (m) = k [5]. However, we answer this question from a theoretical approach utilizing the generalized Pisano period characterization of G_{G_{0},G_{1}}(k).

Proof. Identity (16) was first proven in 1971 by Stanley [16] (and independently in 1989 by Ehrlich [7], who was apparently unaware of Stanley’s result). Identity (17) was proven in 1976 by Stanley [17]. Moreover, in that same paper Stanley states that the range of π_{F} is all even integers greater than 4 though omits the trivial result that π_{F} (2) = 3 and hence we have range(π_{F}) = {3} ∪ {n ∈ 2ℤ | n ≥ 6}, as desired.

Theorem 48. Let k ≥ 6 be an even integer, and set m_{F} := F(k). Then m_{F} is the largest modulus value yielding a Fibonacci period of k. More precisely, π_{F} (m_{F}) = k and for all m > m_{F}, we have π_{F} (m) ≠ k. In particular, we have the following:

m_{F} = \begin{cases}F_{k/2}, & if k ≡ 0 (mod 4), \\ L_{k/2}, & if k ≡ 2 (mod 4). \end{cases}

Proof. Suppose k ≥ 6 is an even integer. Then either k ≡ 0 (mod 4) or k ≡ 2 (mod 4).

Case 1: Suppose k ≡ 0 (mod 4). Set m_{F} := F(k). Then by Theorem 32, we have m_{F} = F_{k/2}. Since k ≡ 0 (mod 4) and k ≥ 6 is even, then k/2 ≥ 4 is even. Thus, Identity (16) of Lemma 47 implies that π_{F} (F_{k/2}) = k. Hence we have π_{F} (m_{F}) = k. We now show that there are no larger values m > m_{F} yielding π_{F} (m) = k. Recall that Theorem 24 implies

π_{F} (m) divides k if and only if m divides F(k).

Hence F(k) is the maximum potential modulus value m that could make π_{F} (m) = k. Since we have π_{F} (m_{F}) = k and m_{F} = F(k), then we have achieved the maximum modulus, namely F_{k/2}, yielding a period of k when k ≡ 0 (mod 4).

Case 2: Suppose k ≡ 2 (mod 4). Set m_{F} := F(k). Then by Theorem 33, we have m_{F} = L_{k/2}. Since k ≡ 2 (mod 4) and k ≥ 6 is even, then k/2 ≥ 3 is odd. Thus, Identity (17) of Lemma 47 implies that π_{F} (L_{k/2}) = k. Hence we have π_{F} (m_{F}) = k. By the exact same argument given in Case 1, we know that F(k) is the maximum potential modulus value m that could make π_{F} (m) = k. So we have achieved the maximum modulus, namely L_{k/2}, yielding a period of k when k ≡ 2 (mod 4).

6.3 Computing odd-indexed Lucas numbers using G_{G_{0},G_{1}}(k) characterizations

The fact that the formulas gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}) and lcm{m | π_{G_{0},G_{1}}(m) divides k} for G_{G_{0},G_{1}}(k) coincide leads to some surprising and delightful new understandings of the Fibonacci and Lucas numbers. One such example can be garnered from looking at the the k ≡ 2, 6, 10 (mod 12) row in Table 1. Given such a k-value, the Lucas number L_{k/2} can be computed in two new ways. One is by taking a Gibonacci sequence (G_{n})_{n≥0} with any initial relatively prime initial values G_{0} and G_{1}, then by the first G_{G_{0},G_{1}}(k) characterization, we have L_{k/2} = gcd(G_{k+1} − G_{1}, G_{k+2} − G_{2}). On the other hand, by the second G_{G_{0},G_{1}}(k) characterization, we have L_{k/2} = lcm{m | π_{G_{0},G_{1}}(m) divides k}. In this subsection, we consider the first of these two ways. We have effectively established an easily computable way to find any odd-index Lucas number using any Gibonacci sequence with relatively prime initial values.

Theorem 49. Let j be an odd positive integer, and suppose that (G_{n})_{n≥0} is a Gibonacci sequence with relatively prime initial values G_{0} and G_{1}. Then the j^{th} Lucas number L_{j} is given by G_{G_{0},G_{1}}(2j). More precisely, we have

L_{j} = gcd (G_{2j+1} − G_{1}, G_{2j+2} − G_{2}).

Proof. This follows from Theorem 33 if we set k := 2j and observe that k ≡ 2 (mod 4) since j is odd.

The latter theorem is quite surprising. It leads one to ponder if such a GCD-formulation can be discovered which yields the even-index Lucas numbers. But even more intriguing is the fact that we have our second characterization of the G_{G_{0},G_{1}}(k) formula. More precisely, the odd index Lucas number L_{j} is given by lcm{m | π_{G_{0},G_{1}}(m) divides 2j}. Admittedly, computing the Lucas number L_{j} using this LCM formulation is not as easily done as it is using Theorem 49, due to the fact that the periods π_{G_{0},G_{1}}(m) are not easily computed. In the open questions section, we ask a question regarding this formulation.

7 Open questions

There are many avenues for further research motivated from the work in this present paper. The following open problems arose from the consideration of our G_{G_{0},G_{1}}(k) characterizations and other questions related to our research.

Question 50. By examining our two equivalent definitions of G_{G_{0},G_{1}}(k), we observe that when k ≡ 2 (mod 4) it follows that L_{k/2} = lcm{m | π_{G_{0},G_{1}}(m) divides k} for every possible choice of G_{0} and G_{1}. Is there an intuitive reason why this must be true?

Question 51. Theorem 44 establishes that no prime p ≡ 3, 7, 13, 17 (mod 20) can be a factor of G_{G_{0},G_{1}}(k) if k is odd. Which primes of the form p ≡ 1, 9, 11, 19 (mod 20) can be factors of G_{G_{0},G_{1}}(k) when k is odd? Can we place further restrictions on the possible factors of G_{G_{0},G_{1}}(k) when k is odd?

Question 52. Observe that for the Fibonacci and Lucas sequences we have that π_{F} (m) and π_{L}(m) are even for all m > 2. For which initial values G_{0} and G_{1}, does there exist a number N such that π_{G_{0},G_{1}}(m) is even for all m > N?

Question 53. To prove Theorem 48 for the maximum modulus value m that yields a given period k in the Fibonacci and Lucas settings, respectively, we relied heavily on Lemma 47 which gave the Fibonacci and Lucas Pisano periods for moduli of the form F_{i} and L_{i}. Can we generalize this lemma to provide conditions on initial values G_{0} and G_{1} that can help us predict the precise value of π_{G_{0},G_{1}}(G_{i}) for each i; that is, the generalized Pisano period of the sequence (G_{n})_{n≥0} modulo the Gibonacci number G_{i}?

Question 54. Can we extend our work to sums of k consecutive squares of Gibonacci numbers? That is, for a fixed k ∈ ℕ and initial values G_{0}, G_{1} ∈ ℤ, what is the value of

G_{G_{0},G_{1}}^{2}(k), which we define to be gcd {(∑_{i=0}^{k−1} G_{n+i}^{2})_{n≥1}}? In the Fibonacci setting, small

computational data leads to the following conjectural values of F^{2}(k), which are the values G_{G_{0},G_{1}}^{2}(k) when G_{0} = 0 and G_{1} = 1:

\begin{matrix}k & F^{2}(k) \\ 0 & 0 = F_{0}L_{0} \\ 4 & 1 · 3 = F_{2}L_{2} \\ 8 & 3 · 7 = F_{4}L_{4} \\ 12 & 2^{4} · 3^{2} = F_{6}L_{6} \\ 16 & 3 · 7 · 47 = F_{8}L_{8} \\ 20 & 3 · 5 · 11 · 41 = F_{10}L_{10} \end{matrix}  \begin{matrix}k & F^{2}(k) \\ 1 & 1 \\ 5 & 1 \\ 9 & 2 \\ 13 & 1 \\ 17 & 1 \\ 21 & 2 \end{matrix}  \begin{matrix}k & F^{2}(k) \\ 2 & 1 = F_{1}L_{1} \\ 6 & 2^{3} = F_{3}L_{3} \\ 10 & 5 · 11 = F_{5}L_{5} \\ 14 & 13 · 29 = F_{7}L_{7} \\ 18 & 2^{3} · 17 · 19 = F_{9}L_{9} \\ 22 & 89 · 199 = F_{11}L_{11} \end{matrix}  \begin{matrix}k & F^{2}(k) \\ 3 & 2 \\ 7 & 1 \\ 11 & 1 \\ 15 & 2 \\ 19 & 1 \\ 23 & 1 \end{matrix}

The four tables above partition the possible k-values into residue classes modulo 4. Observe that in the third table, namely when k ≡ 2 (mod 4), we highlight in red the fact that F^{2}(k) values factor into two distinct primes, namely F_{k/2} and L_{k/2}. However it is well known that F_{n}L_{n} = F_{2n}. Hence, for these aforementioned k-values, we conjecture that F^{2}(k) = F_{k}. Looking closer at the conjectural F^{2}(k) value when k = 18, observe that F_{9} = 2 · 17 and L_{9} = 2^{2} · 19, and their product is indeed the conjectured F^{2}(k) value 2^{3} · 17 · 19. This occurs also for all the values in the table above for k ≡ 0 (mod 4), so the phenomena of F^{2}(k) = F_{k} does seems to hold for all even k values.

Further computational evidence does support the conjecture that F^{2}(k) = F_{k} for all even k values. We feel this is simply too beautiful a result to not be true. Of course, the ultimate goal would be to prove this result and extend it to the Lucas setting to find L^{2}(k) and more generally G_{G_{0},G_{1}}^{2}(k) for any Gibonacci sequence.

8 Acknowledgments

We thank the University of Wisconsin-Eau Claire’s mathematics department where much of this research was conducted. We also thank Julianna Tymoczko for her advice that helped improve the exposition in this paper. Additionally, we thank Marc Renault for helpful correspondences over email. We are also grateful for the program Mathematica, which helped us produce much of the raw data leading to many of our conjectures that eventually became main results in this paper. Lastly, we greatly appreciate the thorough reading given by the anonymous referee who helped us streamline some of our proofs with clearer and more succinct arguments.

References

[1] A. Benjamin and J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[2] K. S. Brown, Problems and Solutions: Solutions: E3410 (Proposed by P. Freyd), Amer. Math. Monthly 99 (1992), 278–279.

[3] Z. Čerin, On factors of sums of consecutive Fibonacci and Lucas numbers, Ann. Math. Inform. 41 (2013), 19–25.

[4] B. Demirtürk, Fibonacci and Lucas sums by matrix methods, Int. Math. Forum 5 (2010), 99–107.

[5] A. Dishong and M. Renault, The Fibonacci sequence under a modulus: computing all moduli that produce a given period, Involve 11 (2018), 769–774.

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

[7] A. Ehrlich, On the periods of the Fibonacci sequence modulo m, Fibonacci Quart. 27 (1989), 11–13.

[8] A.-S. Elsenhans and J. Jahnel, The Fibonacci sequence modulo p^{2} – an investigation by computer for p < 10^{14}, preprint, 2010. Available at https://arxiv.org/abs/1006.

0824.

[9] M. Iyer, Sums involving Fibonacci numbers, Fibonacci Quart. 7 (1969), 92–98.

[10] N. Khaochim and P. Pongsriiam, The general case on the order of appearance of product of consecutive Lucas numbers, Acta Math. Univ. Comenian. (N.S.) 87 (2018), 277–289.

[11] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.

[12] S. Rabinowitz, Algorithmic Manipulation of Second-Order Linear Recurrences, Fibonacci Quart. 37 (1991), 162–177.

[13] I. D. Ruggles, Elementary problem B-1, Fibonacci Quart. 1 (1963), 73.

[14] D. Shtefan and I. Dobrovolska, The sums of the consecutive Fibonacci numbers, Fibonacci Quart. 56 (2018), 229–236.

[15] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

at https://oeis.org.

[16] T. E. Stanley, A note on the sequence of Fibonacci numbers, Math. Mag. 44 (1971), 19–22.

[17] T. E. Stanley, Some remarks on the periodicity of the sequence of Fibonacci numbers, Fibonacci Quart. 14 (1976), 52–54.

[18] A. Tagiuri, Di alcune successioni ricorrenti a termini interi e positivi, Periodico di Matematica 16 (1901), 1–12.

[19] A. Tekcan, B. Gezer, and O. Bizim, Some relations on Lucas numbers and their sums, Adv. Stud. Contemp. Math. (Kyungshang) 15 (2007), 195–211.

[20] A. Tekcan, A. Özkoç, B. Gezer, and O. Bizim, Some relations involving the sums of Fibonacci numbers, Proc. Jangjeon Math. Soc. 11 (2008), 1–12.

[21] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section, Ellis Horwood Limited, 1989.

[22] D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525–532.

2010 Mathematics Subject Classification: Primary 11B39, Secondary 11A05, 11B50. Keywords: Fibonacci sequence, Lucas sequence, greatest common divisor, Pisano period.

(Concerned with sequences \underline{A210209} and \underline{A229339}.)

Received May 25 2021; revised version received November 3 2021. Published in Journal of Integer Sequences, November 3 2021.

Return to Journal of Integer Sequences home page.