# k-Step Sum and m-Step Gap Fibonacci Sequence

Authors: Maria Adam; Nicholas Assimakis
Journal: ISRN Discrete Mathematics
 (2014)

---

## Abstract

For two given integersk, m, we introduce the k-step sumand m-step gap Fibonacci sequence by presenting a recurrence formula that generates the nth term as the sum of k successive previous terms starting the sum at the mth previous term. Known sequences, like Fibonacci, tribonacci, tetranacci, and Padovan sequences, are derived for specific values of k, m. Two limiting properties concerning the terms of the sequence are presented. The limits are related to the spectral radius of the associated {
0
,
1
}-matrix.


---

## Body

## 1. Introduction

It is well-known that the Fibonacci sequence, the Lucas sequence, the Padovan sequence, the Perrin sequence, the tribonacci sequence, and the tetranacci sequence are very prominent examples of recursive sequences, which are defined as follows.The Fibonacci numbers1,1
,
2,3
,
5,8
,
13
,
… are derived by the recurrence relation f
n
=
f
n
-
1
+
f
n
-
2, n
≥
3, with f
1
=
f
2
=
1, [1], [2, A000045].The Lucas numbers2,1
,
3,4
,
7,11,18,29
,
… are derived by the recurrence relation ℓ
n
=
ℓ
n
-
1
+
ℓ
n
-
2, n
≥
3, with ℓ
1
=
2, and ℓ
2
=
1, [1], [2, A000032].The Padovan numbers1,0
,
0,1
,
0,1
,
1,1
,
2,2
,
3,4
,
5,7
,
9,12
,
… are derived by the recurrence relation a
n
=
a
n
-
2
+
a
n
-
3, n
≥
4, with a
1
=
1, a
2
=
a
3
=
0, [2, A000931].The Perrin numbers3,0
,
2,3
,
2,5
,
5,7
,
10,12,17
,
… are derived by the recurrence relation p
n
=
p
n
-
2
+
p
n
-
3, n
≥
4, with p
1
=
3, p
2
=
0, and p
3
=
2, [2, A001608].Both Fibonacci and Lucas numbers as well as both Padovan and Perrin numbers satisfy the same recurrence relation with different initial conditions.Extending the above definitions, thek-step Fibonacci sequences are derived [3]. For k
=
3, the tribonacci numbers 1,1
,
2,4
,
7,13,24,44
,
… are derived by the recurrence relation f
n
=
f
n
-
1
+
f
n
-
2
+
f
n
-
3, n
≥
4, with f
1
=
f
2
=
1, and f
3
=
2, [3–5], [2, A000073].Fork
=
4, the tetranacci numbers 1,1
,
2,4
,
8,15,29,56
,
… are derived by the recurrence relation f
n
=
f
n
-
1
+
f
n
-
2
+
f
n
-
3
+
f
n
-
4, n
≥
5, with f
1
=
f
2
=
1, and f
3
=
2, f
4
=
4, [3], [2, A000078].In this paper, we introducek-step sum and m-step gap Fibonacci sequence, where the nth term of the sequence is the sum of the k successive previous terms starting at the mth previous term, using 1’s as initial conditions. Further the closed formula of the nth term of the sequence is given and the ratio of two successive terms tends to the spectral radius of the associated {
0,1
}-matrix.


## 2. Definition ofk-Step Sum and m-Step Gap Fibonacci Sequence

For the integersk
=
1,2
,
…, m
=
0,1
,
…, we define the k
-step sum and
m
-step gap Fibonacci sequence
(
f
n
(
k
,
m
)
)
n
=
1,2
,
…, whose nth term is given by the following recurrence relation:
(1)
f
n
=
f
n
-
m
-
1
+
f
n
-
m
-
2
+
⋯
+
f
n
-
m
-
(
k
-
1
)
+
f
n
-
m
-
k
=
∑
i
=
m
+
1
k
+
m
f
n
-
i
,
for
every
n
≥
k
+
m
+
1
,
with
(2)
f
1
=
⋯
=
f
k
+
m
=
1
.
Combining (1) and (2) notice that all the terms f
n of the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… are positive integers and f
n is the sum of k terms starting the sum at the mth previous term from f
n; thus, (1) can be written equivalently as
(3)
f
n
=
f
n
-
m
-
1
+
f
n
-
m
-
2
+
⋯
+
f
n
-
m
-
(
k
-
1
)
+
f
n
-
m
-
k
=
∑
j
=
1
k
f
n
-
m
-
j
,
for
every
n
≥
k
+
m
+
1
.Remark 1.
(i) From (2)-(3) it is evident that for k
=
1 and m
=
0,1
,
… all the terms of the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… are equal to one. Hereafter consider k
≥
2, since the case k
=
1 is trivial.
(ii) Form
=
0, (3) and (2) give the nth term f
n of the sequence (
f
n
(
k
,
0
)
)
n
=
1,2
,
…, which is formulated as
(4)
f
n
=
f
n
-
1
+
f
n
-
2
+
⋯
+
f
n
-
(
k
-
1
)
+
f
n
-
k
=
∑
i
=
1
k
f
n
-
i
,
for
every
n
≥
k
+
1
,
with initial values
(5)
f
1
=
⋯
=
f
k
=
1
.Remark 2.
The sequence(
f
n
(
k
,
m
)
)
n
=
1,2
,
… gives known sequences for various values of the steps k
,
m:(i)
fork
=
2, m
=
0, (4)-(5) give the well-known Fibonacci sequence, 1,1
,
2,3
,
5,8
,
13
,
…;
(ii)
fork
=
3, m
=
0, (4)-(5) give the tribonacci sequence, 1,1
,
1,3
,
5,9
,
17,31
,
…, [2, A000213];
(iii)
fork
=
4, m
=
0, (4)-(5) give the tetranacci sequence, 1,1
,
1,1
,
4,7
,
13,25
,
…, [2, A000288];
(iv)
fork
=
2, m
=
1, (2)-(3) give the Padovan sequence, 1,1
,
1,2
,
2,3
,
4,5
,
7,9
,
…, [2, A 000931].In the following, the Dirac delta function (orδ function) is denoted by δ
n
-
j
=
{
0
,
n
≠
j
1
,
n
=
j and the Heaviside step function (or the unit step function) u
n
-
j
=
{
0
,
n
<
j
1
,
n
≥
j.Moreover, thenth number of the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… follows immediately from (2) and (3) using the above definition of the δ function and considering that the first k
+
m negative indexed terms are equal to zero:
(6)
f
-
(
k
+
m
-
1
)
=
⋯
=
f
-
1
=
f
0
=
0
,
which is formulated in the following proposition.Proposition 3.
For the given integersk
≥
2, m
≥
0, for all n
≥
1, the nth number, f
n, of the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… is given by the following recurrence relation:
(7)
f
n
=
∑
i
=
1
k
f
n
-
m
-
i
+
∑
j
=
1
k
+
m
δ
n
-
j
-
∑
j
=
1
k
-
1
∑
i
=
1
k
-
j
δ
n
-
m
-
j
-
i
,
with initial values as in (6).In the following, we are going to demonstrate a close link between matrices and Fibonacci numbers in (3) with initial values in (2).To this end, considerk
≥
2, m
≥
1. One can write the following linear system, where (3) constitutes its first equation:
(8)
f
n
=
f
n
-
m
-
1
+
f
n
-
m
-
2
+
⋯
+
f
n
-
m
-
k
+
1
+
f
n
-
m
-
k
f
n
-
1
=
f
n
-
1
⋮
f
n
-
m
=
f
n
-
m
f
n
-
m
-
1
=
f
n
-
m
-
1
⋮
f
n
-
m
-
(
k
-
1
)
=
f
n
-
m
-
(
k
-
1
)
.
Hence, using a (
k
+
m
)
×
1 vector, the linear system in (8) can be formed as
(9)
[
f
n
f
n
-
1
⋮
f
n
-
m
f
n
-
m
-
1
⋮
f
n
-
m
-
(
k
-
2
)
f
n
-
m
-
(
k
-
1
)
]
=
[
0
0
⋯
0
1
…
1
1
1
0
…
0
0
…
0
0
0
1
0
…
0
…
0
0
0
0
1
0
…
0
0
0
0
1
0
…
⋮
⋮
⋱
⋮
⋮
⋱
0
0
0
…
…
0
1
0
]
[
f
n
-
1
f
n
-
2
⋮
f
n
-
m
f
n
-
m
-
1
⋮
f
n
-
m
-
(
k
-
1
)
f
n
-
m
-
k
]
,
whereby it is obvious that the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… can be represented by a (
k
+
m
)
×
(
k
+
m
) matrix, F
k
,
m, which is a block matrix such that
(10)
F
k
,
m
=
[
F
1
F
2
F
3
F
4
]
=
[
0
⋯
0
1
⋯
1
1
0
⋯
⋯
0
0
1
0
…
0
⋮
1
0
⋮
⋱
0
⋯
⋯
0
1
0
]
,
where the first row consists of the vector-matrices F
1, F
2; the m entries of the 1
×
m vector F
1 are equal to zero and the rest k entries of the 1
×
k vector F
2 are equal to one; the (
k
+
m
-
1
)
×
(
k
+
m
-
1
) matrix F
3 is the identity matrix and the k
+
m
-
1 entries of the (
k
+
m
-
1
)
×
1 vector F
4 are equal to zero.Working as in the above, fork
≥
2, m
=
0, and using (4) with initial values in (5), we can write the following linear system:
(11)
f
n
=
f
n
-
1
+
f
n
-
2
+
⋯
+
f
n
-
k
+
1
+
f
n
-
k
f
n
-
1
=
f
n
-
1
⋮
f
n
-
(
k
-
2
)
=
f
n
-
(
k
-
2
)
f
n
-
(
k
-
1
)
=
f
n
-
(
k
-
1
)
⟺
[
f
n
f
n
-
1
⋮
f
n
-
(
k
-
2
)
f
n
-
(
k
-
1
)
]
=
[
1
1
⋯
1
1
0
⋯
0
0
1
⋮
⋮
⋱
0
⋯
1
0
]
[
f
n
-
1
f
n
-
2
⋮
f
n
-
(
k
-
1
)
f
n
-
k
]
.
The k
×
k matrix, F
k
,
0, of the coefficients of the above system, is defined as
(12)
F
k
,
0
=
[
F
~
1
1
I
k
-
1
F
~
4
]
=
[
1
1
1
⋯
1
1
0
0
⋯
0
0
1
0
⋮
⋮
⋱
0
⋯
1
0
]
,
where the k
-
1 entries of the 1
×
(
k
-
1
) vector F
~
1 are equal to one, I
k
-
1 is the (
k
-
1
)
×
(
k
-
1
) identity matrix, and the k
-
1 entries of the (
k
-
1
)
×
1 vector F
~
4 are equal to zero.Remark 4.
(i) The well-known sequences, which are presented in Remark2, correspond to F
k
,
0 in (12) for suitable integer value of k
≥
2 and =
0;(a)
fork
=
2, the Fibonacci sequence corresponds to F
2,0
=
[
1
1
1
0
];
(b)
fork
=
3, the tribonacci sequence corresponds to F
3,0
=
[
1
1
1
1
0
0
0
1
0
];
(c)
fork
=
4, the tetranacci sequence corresponds to F
4,0
=
[
1
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
].
(ii) The Padovan sequence corresponds to the matrixF
2,1
=
[
0
1
1
1
0
0
0
1
0
] by (10) with k
=
2, m
=
1.
(iii) The matrixF
k
,
0 in (12) has been defined and the determinant of F
k
,
0 has been investigated in [6] and some results on matrices related with Fibonacci numbers and Lucas numbers have been investigated in [7] and the transpose matrix of the general Q-matrix in [8].Proposition 5.
The(
k
+
m
)th degree characteristic polynomial x
(
λ
) of F
k
,
m in (10) is given by
(13)
x
(
λ
)
=
λ
k
+
m
-
∑
i
=
0
k
-
1
λ
i
=
λ
k
+
m
-
∑
i
=
1
k
λ
i
-
1
=
λ
k
+
m
-
∑
i
=
1
k
λ
k
-
i
.Proof.
The proof of (13) is based on the induction method. For k
=
2, m
=
1, the characteristic polynomial of F
2,1
=
[
0
1
1
1
0
0
0
1
0
] is x
(
λ
)
=
λ
3
-
λ
-
1, which satisfies (13). Let m be a fixed integer and assume that the formula in (13) is true for k; that is,
(14)
x
(
λ
)
=
det
⁡
(
λ
I
k
+
m
-
F
k
,
m
)
=
λ
k
+
m
-
∑
i
=
1
k
λ
k
-
i
.
Then, det
⁡
(
λ
I
k
+
m
+
1
-
F
k
+
1
,
m
) of the (
k
+
m
+
1
)
×
(
k
+
m
+
1
) matrix λ
I
k
+
m
+
1
-
F
k
+
1
,
m can be computed by using the Laplace expansion along the (
k
+
m
+
1
)th column and the assumption of induction. Thus, we have
(15)
x
(
λ
)
=
det
⁡
(
λ
I
k
+
m
+
1
-
F
k
+
1
,
m
)
=
(
-
1
)
k
+
m
+
2
(
-
1
)
det
⁡
[
-
1
λ
0
⋯
0
0
-
1
λ
0
0
0
-
1
⋱
⋮
⋮
⋱
λ
0
0
⋯
0
-
1
]
+
(
-
1
)
2
(
k
+
m
+
1
)
λ
det
⁡
⁡
(
λ
I
k
+
m
-
F
k
,
m
)
=
(
-
1
)
k
+
m
+
3
(
-
1
)
k
+
m
+
λ
(
λ
k
+
m
-
∑
i
=
1
k
λ
k
-
i
)
=
λ
k
+
m
+
1
-
∑
i
=
1
k
λ
k
+
1
-
i
-
1
=
λ
k
+
m
+
1
-
∑
i
=
1
k
+
1
λ
k
+
1
-
i
,
hence, (13) holds for k
+
1, too. Thus the result follows by the induction method.The set of all eigenvalues ofF
k
,
m is denoted by σ
(
F
k
,
m
) and called thespectrum of F
k
,
m; the nonnegative real number ρ
(
F
k
,
m
)
=
max
⁡
{
|
λ
|
:
λ
∈
σ
(
F
k
,
m
)
} is calledspectral radius of F
k
,
m. Here, ρ
(
F
k
,
m
) is an eigenvalue of F
k
,
m, since the entries of F
k
,
m are 0 or 1, [11, Theorem 8.3
.
1]; further
(16)
1
<
ρ
(
F
k
,
m
)
<
2
,
since
(17)
min
⁡
1
≤
i
≤
k
+
m
∑
j
=
1
k
+
m
φ
i
j
<
ρ
(
F
k
,
m
)
<
max
⁡
1
≤
i
≤
k
+
m
∑
j
=
1
k
+
m
φ
i
j
,
min
⁡
1
≤
j
≤
k
+
m
∑
i
=
1
k
+
m
φ
i
j
<
ρ
(
F
k
,
m
)
<
max
⁡
1
≤
j
≤
k
+
m
∑
i
=
1
k
+
m
φ
i
j
,
where φ
i
j denotes the i
jth entry of F
k
,
m, [11, Theorem 8.1
.
22], [12, Theorem 7], and [13].Notice that ifλ
j
∈
σ
(
F
k
,
m
) is an eigenvalue of F
k
,
m, then λ
-
j
∈
σ
(
F
k
,
m
), because x
(
λ
) has real coefficients. Further, since x
(
λ
) in (13) has the constant term equal to -
1, it is evident that
(18)
det
⁡
F
k
,
m
=
(
-
1
)
k
+
m
(
-
1
)
=
(
-
1
)
k
+
m
+
1
.
Hence, F
k
,
m is a nonsingular and all the eigenvalues are nonzero.Remark 6.
Notice that, form
=
0,(i)
thekth degree characteristic polynomial x
(
λ
) of the matrix F
k
,
0 in (12) is formulated by (13), which has presented in [9, 10];
(ii)
the authors in [10] have shown bounds for ρ
(
F
k
,
0
); the lower bound is more accurate than the associated bound in (16); in particular,
(19)
2
k
-
1
k
<
ρ
(
F
k
,
0
)
<
2
,
(iii)
the determinant ofF
k
,
0 is computed by (18) and derived the same result as in [6].Example 7.
Considerk
=
2, m
=
0, and the well-known Fibonacci sequence 1,1
,
2,3
,
5,8
,
…, as in Remark 2. According to Remark 4(i), the 2
×
2 matrix
(20)
F
2,0
=
[
1
1
1
0
]
is derived by (12). It is evident that the characteristic polynomial is given by x
(
λ
)
=
λ
2
-
λ
-
1 and its roots are λ
1
=
(
1
-
5
)
/
2 and ρ
(
F
2,0
)
≡
λ
2
=
(
1
+
5
)
/
2, the well-known number as the golden ratio.Example 8.
Considerk
=
2, m
=
1. By (2)-(3) the associated sequence (
f
n
(
2,1
)
)
n
=
1,2
,
… is formed as f
1
=
f
2
=
f
3
=
1 and f
n
=
f
n
-
3
+
f
n
-
2, for all n
≥
4, which is well-known as the Padovan sequence 1,1
,
1,2
,
2,3
,
4,5
,
… (see, Remark 2). According to Remark 4(ii), the associated 3
×
3 matrix is given by
(21)
F
2,1
=
[
0
1
1
1
0
0
0
1
0
]
.
The characteristic polynomial is given by (13) as x
(
λ
)
=
λ
3
-
λ
-
1 and its spectrum σ
(
F
2,1
)
=
{
ρ
(
F
2,1
)
=
1.32472,λ
1
=
-
0.66235
+
0.56227
i
,
λ
2
=
λ
-
1
=
-
0.66235
-
0.56227
i
}.For the integersk
≥
2 and m
≥
0, it is worth noting that, since the entries of the matrix (
I
k
+
m
+
F
k
,
m
)
k
+
m
-
1 are positive integers, F
k
,
m is an irreducible matrix [11, Lemma 8.4
.
1]; it follows that the spectral radius ρ
(
F
k
,
m
) is a positive, simple (without multiplicity) eigenvalue of F
k
,
m [11, Theorem 8.4.4]. In addition, the entries of F
(
k
+
m
)
2
-
2
(
k
+
m
)
+
2 are positive integers; thus F
k
,
m is a primitive matrix [11, Corollary  8.5.9]; that is, ρ
(
F
k
,
m
) is the unique eigenvalue with maximum modulus [11, Definition 8.5.0]. Hence, in the following, we denote λ
1, λ
2, …,λ
k
+
m
-
1, ρ
(
F
k
,
m
) all the distinct eigenvalues of F
k
,
m, for which the following inequality holds:
(22)
0
<
|
λ
j
|
<
ρ
(
F
k
,
m
)
;
j
=
1,2
,
…
,
k
+
m
-
1
.
Furthermore, rewriting (7) as
(23)
f
n
-
∑
i
=
1
k
f
n
-
m
-
i
=
∑
j
=
1
k
+
m
δ
n
-
j
-
∑
i
=
1
k
-
1
δ
n
-
m
-
1
-
i
-
∑
i
=
1
k
-
2
δ
n
-
m
-
2
-
i
-
⋯
-
∑
i
=
1
2
δ
n
-
m
-
(
k
-
2
)
-
i
-
δ
n
-
k
-
m
,
the z-transform on both sides of (23) yields
(24)
F
(
z
)
=
(
z
-
1
+
⋯
+
z
-
(
k
+
m
-
1
)
+
z
-
(
k
+
m
)
-
∑
i
=
1
k
-
1
z
-
(
m
+
1
+
i
)
-
∑
i
=
1
k
-
2
z
-
(
m
+
2
+
i
)
-
⋯
-
∑
i
=
1
3
z
-
(
k
+
m
+
i
-
3
)
-
∑
i
=
1
2
z
-
(
k
+
m
+
i
-
2
)
-
z
-
(
k
+
m
)
)
×
(
1
-
z
-
(
m
+
1
)
-
z
-
(
m
+
2
)
-
⋯
-
z
-
(
k
+
m
)
)
-
1
=
(
z
-
1
+
⋯
+
z
-
(
k
+
m
-
1
)
-
∑
i
=
1
k
-
2
z
-
(
m
+
1
+
i
)
-
∑
i
=
1
k
-
3
z
-
(
m
+
2
+
i
)
-
⋯
-
∑
i
=
1
2
z
-
(
k
+
m
+
i
-
3
)
-
z
-
(
k
+
m
-
1
)
-
(
k
-
2
)
z
-
(
k
+
m
)
∑
i
=
1
k
-
2
z
-
(
m
+
1
+
i
)
)
×
(
1
-
z
-
(
m
+
1
)
-
z
-
(
m
+
2
)
-
⋯
-
z
-
(
k
+
m
)
)
-
1
=
(
z
-
1
+
⋯
+
z
-
(
k
+
m
-
1
)
-
∑
i
=
1
k
-
2
z
-
(
m
+
1
+
i
)
-
∑
i
=
1
k
-
3
z
-
(
m
+
2
+
i
)
-
⋯
-
∑
i
=
1
2
z
-
(
k
+
m
+
i
-
3
)
-
z
-
(
k
+
m
-
1
)
-
(
k
-
2
)
z
-
(
k
+
m
)
∑
i
=
1
k
-
2
z
-
(
m
+
1
+
i
)
)
×
(
1
z
k
+
m
(
z
k
+
m
-
z
k
-
1
-
z
k
-
2
-
⋯
-
z
-
1
)
)
-
1
=
(
z
-
1
+
⋯
+
z
-
(
m
+
1
)
-
∑
i
=
1
k
-
3
z
-
(
m
+
2
+
i
)
-
∑
i
=
1
k
-
4
z
-
(
m
+
3
+
i
)
-
⋯
-
∑
i
=
1
2
z
-
(
k
+
m
+
i
-
3
)
-
z
-
(
k
+
m
-
1
)
-
(
k
-
2
)
z
-
(
k
+
m
)
∑
i
=
1
k
-
3
z
-
(
m
+
2
+
i
)
)
×
(
z
-
(
k
+
m
)
x
(
z
)
)
-
1
.
From (24) it is worth noting that the poles of F
(
z
) are the eigenvalues of F
k
,
m, which are all simple (distinct) and the complex eigenvalues are conjugate; furthermore, the degrees of the polynomials of numerator and denominator of F
(
z
) coincide. Thus, the partial-fraction decomposition of (24) is given by
(25)
F
(
z
)
=
k
-
2
+
c
1
-
ρ
(
F
k
,
m
)
z
-
1
+
∑
j
=
1
k
+
m
-
1
c
j
1
-
λ
j
z
-
1
,
where c, ρ
(
F
k
,
m
) are real and the others coefficients c
j are complex or real numbers.In the following theorem, we are able to present the closed formula of the terms of the sequence(
f
n
(
k
,
m
)
)
n
=
1,2
,
…, which depends on all the eigenvalues of F
k
,
m.Theorem 9.
Letλ
1, λ
2, …, λ
k
+
m
-
1, ρ
(
F
k
,
m
) be the eigenvalues of F
k
,
m and the fixed integers k, m, with k
≥
2, m
≥
0. The nth number of the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… is given by
(26)
f
n
=
c
(
ρ
(
F
k
,
m
)
)
n
+
∑
j
=
1
k
+
m
-
1
c
j
(
λ
j
)
n
,
where c, c
j, for all j
=
1,2
,
…
,
k
+
m
-
1, are the determined coefficients of the partial-fraction decomposition in (25).Proof.
The inversez-transform on both sides of (25) for all n
=
1,2
,
… yields
(27)
f
n
=
(
k
-
2
)
δ
n
+
c
(
ρ
(
F
k
,
m
)
)
n
u
n
+
∑
j
=
1
k
+
m
-
1
c
j
(
λ
j
)
n
u
n
.
The closed formula of f
n in (26) follows from the above equation and the definitions of δ and Heaviside step functions.


## 3. Limiting Properties ofk-Step Sum and m-Step Gap Fibonacci Sequence

The spectral radius ofF
k
,
m in (10) is a characteristic quantity, which appears in (26) and for some cases of k
,
m is computed in Table 1.Table 1
The spectral radiusρ
(
F
k
,
m
) of F
k
,
m with respect to k and m.
k
=
2
k
=
3
k
=
4
k
=
5
m
=
0
1.6180
1.8393
1.9276
1.9659
m
=
1
1.3247
1.4656
1.5342
1.5701
m
=
2
1.2207
1.3247
1.3808
1.4122
m
=
3
1.1673
1.2499
1.2965
1.3247From the values in Table1 observe that the spectral radius ρ
(
F
k
,
m
)
(i)
increases ask increases and m remains constant;
(ii)
decreases asm increases and k remains constant;
(iii)
lies in the interval(
1,2
) verifying (16).Note that for k
=
3, m
=
0, the spectral radius ρ
(
F
k
,
m
) is the tribonacci constant and for k
=
4, m
=
0, the spectral radius ρ
(
F
k
,
m
) is the tetranacci constant [2].The significance ofρ
(
F
k
,
m
) is presented in the following theorem.Theorem 10.
For the fixed integersk, m, with k
≥
2, m
≥
0, the positive numbers f
n of the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… in (26) satisfy the following limit properties:
(28)
lim
⁡
n
→
∞
f
n
+
1
f
n
=
ρ
(
F
k
,
m
)
,
(29)
lim
⁡
n
→
∞
f
n
n
=
ρ
(
F
k
,
m
)
,
where ρ
(
F
k
,
m
) is the spectral radius of F
k
,
m in (10).Proof.
Consider that the polar form of the determined coefficientsc
j in (25) is denoted by c
j
=
|
c
j
|
e
i
θ
j, and the eigenvalues (except the spectral radius) λ
j
=
|
λ
j
|
e
i
ω
j, for all j
=
1,2
,
…
,
k
+
m
-
1. The substitution of c
j, λ
j from the polar forms in (26) yields
(30)
f
n
=
c
(
ρ
(
F
k
,
m
)
)
n
+
∑
j
=
1
k
+
m
-
1
|
c
j
|
e
i
θ
j
(
|
λ
j
|
e
i
ω
j
)
n
=
c
(
ρ
(
F
k
,
m
)
)
n
+
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
|
n
e
i
(
θ
j
+
n
ω
j
)
=
c
(
ρ
(
F
k
,
m
)
)
n
+
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
|
n
(
cos
⁡
(
θ
j
+
n
ω
j
)
+
i
sin
(
θ
j
+
n
ω
j
)
)
.
Using (30) and the property of the spectral radius ρ
(
F
k
,
m
)
>
0 from (22), we can write
(31)
lim
⁡
n
→
∞
f
n
+
1
f
n
=
lim
⁡
n
→
∞
(
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
+
1
(
ρ
(
F
k
,
m
)
)
n
+
1
l
l
l
l
l
l
l
l
l
l
l
l
l
l
×
(
c
+
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
+
1
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
×
(
+
i
sin
(
θ
j
+
(
n
+
1
)
ω
j
)
)
cos
⁡
(
θ
j
+
(
n
+
1
)
ω
j
)
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
+
i
sin
(
θ
j
+
(
n
+
1
)
ω
j
)
)
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
+
1
)
×
(
(
c
+
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
(
ρ
(
F
k
,
m
)
)
n
l
l
l
l
l
l
l
l
l
l
l
×
(
c
+
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
×
(
cos
⁡
⁡
(
θ
j
+
n
ω
j
)
+
i
sin
(
θ
j
+
n
ω
j
)
)
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
)
∑
j
=
1
k
+
m
-
1
|
c
j
|
|
λ
j
ρ
(
F
k
,
m
)
|
n
)
-
1
)
.
Since (
cos
⁡
(
θ
j
+
n
ω
j
)
)
n
=
1,2
,
… and (
sin
(
θ
j
+
n
ω
j
)
)
n
=
1,2
,
… are bounded sequences as well as the inequality (22) implies |
λ
j
/
ρ
(
F
k
,
m
)
|
<
1 for every j
=
1,2
,
…
,
k
+
m
-
1, it is obvious that
(32)
lim
⁡
n
→
∞
(
|
λ
j
ρ
(
F
k
,
m
)
|
n
+
1
×
(
cos
⁡
⁡
(
θ
j
+
(
n
+
1
)
ω
j
)
+
i
sin
(
θ
j
+
(
n
+
1
)
ω
j
)
)
|
λ
j
ρ
(
F
k
,
m
)
|
n
+
1
)
=
lim
⁡
n
→
∞
(
|
λ
j
ρ
(
F
k
,
m
)
|
n
cos
⁡
(
θ
j
+
n
ω
j
)
+
i
sin
(
θ
j
+
n
ω
j
)
)
=
0
.
Thus, the validity of (28) follows from (31) and (32).
Furthermore, it is well known that for a sequence(
a
n
)
n
≥
1 of nonzero complex numbers, if lim
⁡
n
→
∞
⁡
(
|
a
n
+
1
|
/
|
a
n
|
)
=
α, then lim
⁡
n
→
∞
⁡
|
a
n
|
n
=
α [14, Chapter  1], whereby it is evident that for the sequence (
f
n
(
k
,
m
)
)
n
=
1,2
,
… of the positive integers (f
n
>
0), the equality (29) follows immediately from (28).Remark 11.
Notice that for everyn
=
1,2
,
… the formulas of f
n in (26) and (30) are equivalent. Additionally, notice the following.(i)
Ifk
+
m is odd, then the characteristic polynomial in (13) has one real root, ρ
(
F
k
,
m
), and the others are complex conjugate. Thus, the complex eigenvalues λ
j and the coefficients c
j in (25) appear in r complex conjugate pairs, which are denoted by λ
1, λ
2
=
λ
-
1, λ
3, λ
4
=
λ
-
3, …, λ
r
-
1, λ
r
=
λ
-
r
-
1 and c
1, c
2
=
c
-
1, c
3, c
4
=
c
-
3, …, c
r
-
1, c
r
=
c
-
r
-
1, respectively. Then, using the complex conjugate properties, (30) follows
(33)
f
n
=
c
(
ρ
(
F
k
,
m
)
)
n
+
2
∑
i
=
1
r
|
c
i
|
|
λ
i
|
n
cos
⁡
(
θ
i
+
n
ω
i
)
,
wherer
=
(
k
+
m
-
1
)
/
2.
(ii)
Ifk
+
m is even, then the characteristic polynomial in (13) has two real roots and the others are complex conjugate. The one real root is the unique real positive root ρ
(
F
k
,
m
); it lies in the interval (
1,2
) by (16) and has maximum modulus. The other real root is negative and lies in the interval [
-
1,0
) (see in Acknowledgements). Thus, the complex eigenvalues λ
j and the coefficients c
j in (25) appear in r complex conjugate pairs and λ
j, c
j are denoted as in (i). Then, using the complex conjugate properties, (30) follows
(34)
f
n
=
c
(
ρ
(
F
k
,
m
)
)
n
+
c
k
+
m
-
1
(
λ
k
+
m
-
1
)
n
+
2
∑
i
=
1
r
|
c
i
|
|
λ
i
|
n
cos
⁡
(
θ
i
+
n
ω
i
)
,
wherer
=
(
k
+
m
-
2
)
/
2.Example 12.
Consider the Padovan sequence of the Example8. Notice that k
=
2, m
=
1 and k
+
m is odd. The eigenvalues of F
2,1 are given in Example 8, ρ
(
F
2,1
)
=
1.32472, λ
1
=
-
0.66235
+
0.56227
i
=
0.86883
(
cos
⁡
(
2.43773
)
+
i
sin
(
2.43773
)
), and λ
2
≡
λ
-
1. Since |
λ
1
|
=
0.86883, it is evident that the inequality (22) is verified. The partial-fraction decomposition as in (25) yields c
=
0.54511, c
1
=
-
0.27255
+
0.07397
i
=
0.28241
(
cos
⁡
(
2.87657
)+i
sin
(
2.87657
)
), and c
2
=
-
0.27255
-
0.07397
i
≡
c
-
1.
Thus, forn
≥
1 the nth number of the Padovan sequence is computed by (33) and given by
(35)
f
n
=
c
(
ρ
(
F
2,1
)
)
n
+
2
|
c
1
|
|
λ
1
|
n
cos
⁡
(
θ
1
+
n
ω
1
)
=
0.54511
(
1.32472
)
n
+
0.56483
(
0.86883
)
n
cos
⁡
(
2.87657
+
2.43773
n
)
.
Now, the limited properties of the Padovan sequence are derived by (28) and (29):
(36)
lim
⁡
n
→
∞
f
n
+
1
f
n
=
lim
⁡
n
→
∞
f
n
n
=
1.32472
.Example 13.
Consider the 2-step sum and 2-step gap Fibonacci sequence. Notice thatk
+
m is even. The eigenvalues of F
2,2 are ρ
(
F
2,2
)
=
1.22074, λ
1
=
-
0.24812
+
1.0339
i
=
1.06333
(
cos
⁡
(
1.80631
)+i
sin
(
1.80631
)
), λ
2
≡
λ
-
1, and λ
3
=
-
0.72449. The partial-fraction decomposition as in (25) yields c
=
0.59122, c
1
=
-
0.13687
+
0.00951
i
=
0.13720
(
cos
⁡
(
3.07219
) + i
sin
(
3.07219
)
), c
2
=
c
-
1, and c
3
=
-
0.31747. Thus, for n
≥
1 the nth number of the sequence is computed by (34) and given by
(37)
f
n
=
0.59122
(
1.22074
)
n
-
0.31747
(
-
0.72449
)
n
+
0.27441
(
1.06336
)
n
cos
⁡
(
3.07219
+
1.80631
n
)
.
Now, the limited properties of the sequence are derived by (28) and (29):
(38)
lim
⁡
n
→
∞
f
n
+
1
f
n
=
lim
⁡
n
→
∞
f
n
n
=
1.22074
.


## 4. Conclusions

Thek-step sum and m-step gap Fibonacci sequence was introduced. A recurrence formula was presented generating the nth term of the sequence as the sum of k successive previous terms starting the sum at the mth previous term. It was noticed that known sequences, like Fibonacci, tribonacci, tetranacci, and Padovan sequences, are derived for specific values of k
,
m. A closed formula of the nth term of the sequence was given. The limiting properties concerning the ratio of two successive terms as well as the nth root of the nth term of the sequence were presented. It was shown that these two limits are equal to each other and are related to the spectral radius of the associated {
0,1
}-matrix. These limits can be regarded as the k-step sum and m-step gap Fibonacci sequence constants, like the tribonacci constant and the tetranacci constant.



---

*Source: 374902-2014-04-09.xml*