# On Types of Distance Fibonacci Numbers Generated by Number Decompositions

Authors: Anetta Szynal-Liana; Andrzej Włoch; Iwona Włoch
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We introduce new types of distance Fibonacci numbers which are closely related with number decompositions. Using special decompositions of the numbern we give a sequence of identities for them. Moreover, we give matrix generators for distance Fibonacci numbers and their direct formulas.


---

## Body

## 1. Introduction

Thenth Fibonacci numbers F
n are defined by recurrence relation F
n
=
F
n
-
1
+
F
n
-
2, n
≥
2 with the initial conditions F
0
=
F
1
=
1. There are many generalizations of the Fibonacci numbers F
n with respect to one or more parameters; see for example [1–3]. In [1] the distance Fibonacci numbers F
d
(
1
)
(
k
,
n
) were introduced and studied. We recall this definition.Letk
≥
2, n
≥
0 be integers. The distance Fibonacci numbers of the first kind F
d
(
1
)
(
k
,
n
) are defined recursively in the following way:
(1)
F
d
(
1
)
(
k
,
n
)
=
F
d
(
1
)
(
k
,
n
-
k
+
1
)
+
F
d
(
1
)
(
k
,
n
-
k
)
for
n
≥
k
,
and F
d
(
1
)
(
k
,
n
)
=
1 for n
=
0
,
…
,
k
-
1.We will call the numbersF
d
(
1
)
(
k
,
n
) the distance Fibonacci numbers of the first kind. The number F
d
(
1
)
(
k
,
n
) is closely related to the special quasi k-decomposition of the number n; see [1].In this paper we define other three types of distance Fibonacci numbers which are also related to the special number decomposition. Moreover we shall show relations between all three types of distance Fibonacci numbers. Next we study their matrix generators and direct formulas.


## 2. Distance Fibonacci NumbersF
d
(
2
)
(
k
,
n
) and F
d
(
3
)
(
k
,
n
)

In this section we introduce two kinds of distance Fibonacci numbers. Some relations between numbersF
d
(
i
)
(
k
,
n
) for i
=
1,2
,
3 will be studied.Letk
≥
2, n
≥
0 be integers. We define the nth distance Fibonacci numbers of the second kind F
d
(
2
)
(
k
,
n
) by the kth order linear recurrence relation of the form
(2)
F
d
(
2
)
(
k
,
n
)
=
F
d
(
2
)
(
k
,
n
-
k
+
1
)
+
F
d
(
2
)
(
k
,
n
-
k
)
for
n
≥
k
,
with the initial conditionsF
d
(
2
)
(
k
,
n
)
=
0
forn
=
0
,
…
,
k
-
2,
F
d
(
2
)
(
k
,
k
-
1
)
=
1,
F
d
(
2
)
(
1,1
)
=
1,
F
d
(
2
)
(
2,2
)
=
2,
F
d
(
2
)
(
k
,
k
)
=
1, for k
≥
3.Ifk
=
2, n
≥
1, then F
d
(
2
)
(
k
,
n
) gives the Fibonacci numbers F
n.Letk
≥
2, n
≥
0 be integers. We define the nth distance Fibonacci numbers of the third kind F
d
(
3
)
(
k
,
n
) by the kth order linear recurrence relation of the form
(3)
F
d
(
3
)
(
k
,
n
)
=
F
d
(
3
)
(
k
,
n
-
k
+
1
)
+
F
d
(
3
)
(
k
,
n
-
k
)
for
n
≥
2
k
-
1
,
with the initial conditionsF
d
(
3
)
(
k
,
n
)
=
1 for n
=
0
,
.
.
.
,
k
-
1,
F
d
(
3
)
(
2,2
)
=
2,
fork
≥
3  F
d
(
3
)
(
k
,
k
)
=
3
=
F
d
(
3
)
(
k
,
2
k
-
2
),
fork
+
1
≤
n
≤
2
k
-
3  F
d
(
3
)
(
k
,
n
)
=
4.Ifk
=
2, then F
d
(
3
)
(
k
,
n
) gives the classical Fibonacci numbers.Now we give an interpretation of the numbersF
d
(
1
)
(
k
,
n
), F
d
(
2
)
(
k
,
n
), and F
d
(
3
)
(
k
,
n
) with respect to special decompositions of the number n.By a decomposition of a numbern, n
≥
1, we mean an ordered number partition of it. For example for n
=
3 we have the following four decompositions: 1
+
1
+
1, 2
+
1, 1
+
2, and 3. In this paper we study special decompositions of a number n which are closely related to distance Fibonacci numbers F
d
(
i
)
(
k
,
n
), for i
=
1,2
,
3.Let1
≤
r
≤
k
-
2 be a fixed integer. A decomposition of the number n
≥
k
-
1 of the form r
+
n
1
+
n
2
+
⋯
+
n
p (resp., n
1
+
n
2
+
⋯
+
n
p
+
r) where n
i
∈
{
k
,
k
-
1
}, i
=
1
,
…
,
p is called an r
-
k-decomposition (resp., r
+
k-decomposition). We denote the number of all r
-
k-decompositions (resp., r
+
k-decompositions) by σ
-
r
(
k
,
n
) (resp., σ
+
r
(
k
,
n
)). Clearly
(4)
σ
-
r
(
k
,
n
)
=
σ
+
r
(
k
,
n
)
.A decomposition of the numbern
≥
k
-
1 of the form n
1
+
n
2
+
⋯
+
n
p, where n
i
∈
{
k
,
k
-
1
}, i
=
1
,
…
,
p, is called a k-decomposition. We denote the number of all k-decompositions by σ
0
(
k
,
n
).Let0
≤
r
0
≤
k
-
2 be a fixed integer. A decomposition of the number n
≥
k
-
1 of the form r
0
+
n
1
+
n
2
+
⋯
+
n
p (resp., n
1
+
n
2
+
⋯
+
n
p
+
r
0) where n
i
∈
{
k
,
k
-
1
}, i
=
1
,
…
,
p is called an r
0
-
k-decomposition (resp., r
0
+
k-decomposition). Consequently as the above we denote the number of all r
0
-
k-decompositions (resp., r
0
+
k-decompositions) by σ
-
r
0
(
k
,
n
) (resp., σ
+
r
0
(
k
,
n
)). Clearly for r
0
=
0 a 0
-
k-decomposition of n is a k-decomposition and for r
0
≥
1 an r
0
-
k-decomposition (resp., r
0
+
k-decompositions) is an r
-
k-decompositions (resp., r
+
k-decompositions). From the above definitions immediately follow relations between numbers σ
-
r
(
k
,
n
), σ
-
r
0
(
k
,
n
), and σ
0
(
k
,
n
) (resp., σ
+
r
(
k
,
n
), σ
+
r
0
(
k
,
n
), and σ
0
(
k
,
n
)):
(5)
σ
-
r
0
(
k
,
n
)
=
∑
r
=
1
k
-
2
‍
σ
-
r
(
k
,
n
)
+
σ
0
(
k
,
n
)
,
(6)
σ
+
r
0
(
k
,
n
)
=
∑
r
=
1
k
-
2
‍
σ
+
r
(
k
,
n
)
+
σ
0
(
k
,
n
)
,
(7)
σ
(
k
,
n
)
=
∑
j
=
-
(
k
-
2
)
k
-
2
‍
σ
j
(
k
,
n
)
.Theorem 1 (see [1]).
Letk
≥
2, n
≥
k
-
1 be integers. Then σ
+
r
0
(
k
,
n
)
=
F
d
(
1
)
(
k
,
n
).For the proof of the next theorem we will need the following lemma.Lemma 2.
Letk
≥
2, n
≥
k
-
1 be integers. Then
(8)
2
F
d
(
1
)
(
k
,
n
)
-
F
d
(
2
)
(
k
,
n
)
=
F
d
(
3
)
(
k
,
n
)
,
hhhhhhhhhhhhhhhhiiiih
f
o
r
n
≥
k
-
1
.Proof.
Ifn
=
k
-
1, then the equality immediately follows. Assume that the lemma is true for an arbitrary t
<
n and we prove it for n. Using the definitions of numbers F
d
(
1
)
(
k
,
n
) and F
d
(
2
)
(
k
,
n
) we obtain that 2
F
d
(
1
)
(
k
,
n
)
-
F
d
(
2
)
(
k
,
n
)
=
2
F
d
(
1
)
(
k
,
n
-
k
)
+
2
F
d
(
1
)
(
k
,
n
-
k
+
1
)
-
F
d
(
2
)
(
k
,
n
-
k
)
-
F
d
(
2
)
(
k
,
n
-
k
+
1
) = F
d
(
3
)
(
k
,
n
) by the induction’s hypothesis.We can write the above lemma also in the following form.Corollary 3.
Letk
≥
2, n
≥
k
-
1 be integers. Then
(9)
F
d
(
1
)
(
k
,
n
)
-
F
d
(
2
)
(
k
,
n
)
=
F
d
(
3
)
(
k
,
n
)
-
F
d
(
1
)
(
k
,
n
)
.Theorem 4.
Letk
≥
2, n
≥
1, 1
≤
r
≤
k
-
2 be integers. Then(i)
σ
-
r
0
(
k
,
n
)
=
σ
+
r
0
(
k
,
n
)
=
F
d
(
1
)
(
k
,
n
),
(ii)
σ
0
(
k
,
n
)
=
F
d
(
2
)
(
k
,
n
),
(iii)
σ
(
k
,
n
)
=
F
d
(
3
)
(
k
,
n
).Proof.
The equality (i) follows immediately by Theorem1 and (4).
We shall show thatσ
0
(
k
,
n
)
=
F
d
(
2
)
(
k
,
n
). If n
=
1,2
,
…
,
k
-
2, then there is no k-decomposition of the number n into parts k
-
1 and k. So σ
0
(
k
,
n
)
=
0
=
F
d
(
2
)
(
k
,
n
). If n
=
k
-
1
,
k, then there is a unique k-decomposition of the number n; hence σ
0
(
k
,
n
)
=
1
=
F
d
(
2
)
(
k
,
n
). Let n
≥
k
+
1. Assume that the equality holds for an arbitrary t
<
n. We shall show that σ
0
(
k
,
n
)
=
F
d
(
2
)
(
k
,
n
). Let n
=
n
1
+
n
2
+
⋯
+
n
p be a k-decomposition of the number n into parts k and k
-
1. If n
p
=
k, then n
=
n
1
+
n
2
+
…
+
n
p
-
1
+
k so n
-
k
=
n
1
+
n
2
+
⋯
+
n
p
-
1. By induction’s hypothesis there are F
d
(
2
)
(
k
,
n
-
k
)
k-decompositions in this case. If n
p
=
k
-
1 then proving analogously we obtain F
d
(
2
)
(
k
,
n
-
k
+
1
)
k-decompositions of the form n
=
n
1
+
n
2
+
⋯
+
n
p
-
1
+
k
-
1. From the above we have F
d
(
2
)
(
k
,
n
-
k
)
+
F
d
(
2
)
(
k
,
n
-
k
+
1
)
k-decompositions of the number n into parts k and k
-
1, and by the definition of F
d
(
2
)
(
k
,
n
) it follows that σ
0
(
k
,
n
)
=
F
d
(
2
)
(
k
,
n
).
Now we shall prove thatσ
(
k
,
n
)
=
F
d
(
3
)
(
k
,
n
). From the definition of σ
(
k
,
n
) we obtain that
(10)
σ
(
k
,
n
)
=
∑
j
=
-
(
k
-
2
)
k
-
2
σ
j
(
k
,
n
)
=
2
∑
r
=
1
k
-
2
σ
+
r
(
k
,
n
)
‍
+
σ
0
(
k
,
n
)
=
F
d
(
1
)
(
k
,
n
)
+
∑
r
=
1
k
-
2
σ
+
r
(
k
,
n
)
‍
+
σ
0
(
k
,
n
)
-
σ
0
(
k
,
n
)
=
2
F
d
(
1
)
(
k
,
n
)
-
F
d
(
2
)
(
k
,
n
)
,
by the statements (i) and (ii) of this theorem.
Then the statement (iii) follows immediately by Lemma2, which ends the proof.Theorem 5.
Letk
≥
2, n
≥
k
-
1 and 1
≤
r
≤
k
-
2 be integers. Then
(11)
σ
-
r
(
k
,
p
k
+
i
)
=
2
p
,
for natural p and i
=
1,2
,
…
,
k
-
(
p
+
2
).Proof.
Letp be natural and i
=
1,2
,
…
,
k
-
(
p
+
2
). The number p
k
+
i is equal to (
i
+
l
)
+
l
·
(
k
-
1
)
+
(
p
-
l
)
·
k, for l
=
0,1
,
…
,
p, and all r
-
k-decompositions of p
k
+
i have the form (
i
+
l
)
+
n
1
+
…
+
n
p. We can put k
-
1 on l positions, so we have (
p
l
) possibilities. The sum ∑
l
=
0
p
(
p
l
) is equal to 2
p which ends the proof.Now we give applications of distance Fibonacci numbers for counting of the number of other special decompositions of the numbern.Letk
≥
2, n
≥
k be integers and let σ
±
r
0
(
k
,
n
) be the numbers of all decomposition of the number n
=
n
1
+
n
2
+
⋯
+
n
p, where n
i
∈
{
k
,
k
-
1
}, for i
=
2
,
…
,
p
-
1 and n
1
,
n
p
∈
{
1
,
…
,
k
}.Theorem 6.
Letk
≥
2, n
≥
k be integers. Then
(12)
σ
±
r
0
(
k
,
n
)
=
∑
r
=
1
k
‍
F
d
(
1
)
(
k
,
n
-
r
)
.Proof.
Letn
=
n
1
+
n
2
+
⋯
+
n
p be a decomposition of the number n, where n
i
∈
{
k
,
k
-
1
}, for i
=
2
,
…
,
p
-
1 and n
1
,
n
p
∈
{
1
,
…
,
k
}. Then n
-
n
p
=
n
1
+
n
2
+
⋯
+
n
p
-
1, where n
1
+
n
2
+
⋯
+
n
p
-
1 is either a r
-
k-decomposition or a k-decomposition of the number n
-
n
p. Since n
p
∈
{
1
,
…
,
k
} by Theorem 4(i) it follows that σ
±
r
0
(
k
,
n
)
=
∑
r
=
1
k
F
d
(
1
)
(
k
,
n
-
r
), which ends the proof.Theorem 7.
Letk
≥
3, n
≥
k be integers. Then
(13)
∑
i
=
1
k
-
2
‍
∑
j
=
1
k
-
2
‍
F
d
(
2
)
(
k
,
n
-
(
i
+
j
)
)
=
∑
i
=
1
k
-
2
‍
(
F
d
(
1
)
(
k
,
n
-
i
)
-
F
d
(
2
)
(
k
,
n
-
i
)
)
,
for natural p and i
=
1,2
,
…
,
k
-
(
p
+
2
).Proof.
Letk
≥
2, n
≥
k be integers. Let n
=
n
1
+
n
2
+
⋯
+
n
p be a decomposition η of the number n, where n
i
∈
{
k
,
k
-
1
}, for i
=
2
,
…
,
p
-
1 and n
1
,
n
p
∈
{
1
,
…
,
k
-
2
}. Then the number of such decomposition is equal to the number of k-decomposition of the number n
-
(
n
1
+
n
p
). By Theorem 4(ii) we obtain that we have F
d
(
2
)
(
k
,
n
-
(
n
1
+
n
p
)
) decompositions η. Since n
1
,
n
p
∈
{
1
,
…
,
k
-
2
} it is clear that totally we have
(14)
∑
i
=
1
k
-
2
‍
∑
j
=
1
k
-
2
‍
F
d
(
2
)
(
k
,
n
-
(
i
+
j
)
)
decompositions of the number n.
On the other hand, we have that the total number of decompositionsη is equal to the number of r
-
k-decompositions of the number n
-
n
p. Since n
p
∈
{
1
,
…
,
k
-
2
} by formula (5) and Theorem 4 we obtain
(15)
∑
i
=
1
k
-
2
‍
(
F
d
(
1
)
(
k
,
n
-
i
)
-
F
d
(
2
)
(
k
,
n
-
i
)
)
.
From the above it immediately follows that
(16)
∑
i
=
1
k
-
2
∑
j
=
1
k
-
2
‍
F
d
(
2
)
(
n
-
(
i
+
j
)
)
=
∑
i
=
1
k
-
2
‍
(
F
d
(
1
)
(
k
,
n
-
i
)
-
F
d
(
2
)
(
k
,
n
-
i
)
)
,
which ends the proof.


## 3. Identities forF
d
(
1
)
(
k
,
n
), F
d
(
2
)
(
k
,
n
), and F
d
(
3
)
(
k
,
n
)

In this section we give some identities for distance Fibonacci numbers:F
d
(
i
)
(
k
,
n
), for i
=
1,2
,
3.Theorem 8.
Letk
≥
2, n
≥
k be integers. Then
(17)
∑
j
=
1
3
‍
a
j
F
d
(
j
)
(
k
,
n
)
=
∑
i
=
0
p
‍
(
p
i
)
(
∑
j
=
1
3
‍
a
j
F
d
(
j
)
(
k
,
n
-
p
k
+
i
)
)
.Proof (by induction onn).
Forn
=
k we have p
=
1 and
(18)
∑
j
=
1
3
a
j
F
d
(
j
)
(
k
,
k
)
=
∑
j
=
1
3
a
j
(
F
d
(
j
)
(
k
,
k
-
k
)
+
F
d
(
j
)
(
k
,
k
-
k
+
1
)
)
=
∑
j
=
1
3
a
j
(
F
d
(
j
)
(
k
,
0
)
+
F
d
(
j
)
(
k
,
1
)
)
=
∑
j
=
1
3
a
j
(
F
d
(
j
)
(
k
,
k
-
1
·
k
+
0
)
+
F
d
(
j
)
(
k
,
k
-
1
·
k
+
1
)
)
=
∑
i
=
0
1
(
1
i
)
∑
j
=
1
3
a
j
F
d
(
j
)
(
k
,
i
)
‍
.
Letn
>
k. Assume that (17) is true for arbitrary t
<
n and we prove it for n. Using induction’s assumption for t
=
n
-
k and t
=
n
-
k
+
1 we have
(19)
F
d
(
j
)
(
k
,
n
)
=
F
d
(
j
)
(
k
,
n
-
k
)
+
F
d
(
j
)
(
k
,
n
-
k
+
1
)
=
∑
i
=
0
p
(
p
i
)
‍
F
d
(
j
)
(
k
,
n
-
k
-
p
k
+
i
)
+
∑
i
=
0
p
(
p
i
)
‍
F
d
(
j
)
(
k
,
n
-
k
+
1
-
p
k
+
i
)
=
∑
i
=
0
p
(
p
i
)
‍
[
F
d
(
j
)
(
k
,
n
-
k
-
p
k
+
i
)
+
F
d
(
j
)
(
k
,
n
-
k
+
1
-
p
k
+
i
)
]
=
∑
i
=
0
p
(
p
i
)
‍
[
F
d
(
j
)
(
k
,
n
-
p
k
+
i
-
k
)
+
F
d
(
j
)
(
k
,
n
-
p
k
+
i
-
k
+
1
)
]
=
∑
i
=
0
p
(
p
i
)
‍
F
d
(
j
)
(
k
,
n
-
p
k
+
i
)
,
which ends the proof.Corollary 9.
Letk
≥
2, n
≥
k be integers. Then(iv)
F
d
(
1
)
(
k
,
n
)
=
∑
i
=
0
p
(
p
i
)
F
d
(
1
)
(
k
,
n
-
p
k
+
i
),
(v)
F
d
(
2
)
(
k
,
n
)
=
∑
i
=
0
p
(
p
i
)
F
d
(
2
)
(
k
,
n
-
p
k
+
i
),
(vi)
F
d
(
3
)
(
k
,
n
)
=
∑
i
=
0
p
(
p
i
)
F
d
(
3
)
(
k
,
n
-
p
k
+
i
).Proof.
(iv) This formula directly follows from Theorem8 putting a
1
=
1 and a
2
=
a
3
=
0. For (v) and (vi) analogously.Theorem 10.
Letk
≥
3, n
≥
k be integers. Then
(20)
F
d
(
1
)
(
k
,
n
)
=
∑
i
=
0
k
-
2
‍
F
d
(
2
)
(
k
,
n
-
i
)
.Proof (by induction onn).
Forn
=
k we have F
d
(
1
)
(
k
,
k
)
=
F
d
(
1
)
(
k
,
0
)
+
F
d
(
1
)
(
k
,
1
)
=
1
+
1
=
2. The right side of (20) has the form ∑
i
=
0
k
-
2
F
d
(
2
)
(
k
,
k
-
i
)
=
F
d
(
2
)
(
k
,
k
-
0
)
+
F
d
(
2
)
(
k
,
k
-
1
) + F
d
(
2
)
(
k
,
k
-
2
)
+
⋯
+
F
d
(
2
)
(
k
,
k
-
(
k
-
2
)
)
=
F
d
(
2
)
(
k
,
k
)
+
F
d
(
2
)
(
k
,
k
-
1
) + F
d
(
2
)
(
k
,
k
-
2
)
+
⋯
+
F
d
(
2
)
(
k
,
2
)
=
1
+
1
+
0
+
⋯
+
0
=
2.
Letn
>
k. Assume that (20) is true for arbitrary t
<
n and we prove it for n. Using induction’s assumption for t
=
n
-
k and t
=
n
-
k
+
1 we have
(21)
F
d
(
1
)
(
k
,
n
)
=
F
d
(
1
)
(
k
,
n
-
k
)
+
F
d
(
1
)
(
k
,
n
-
k
+
1
)
=
∑
i
=
0
k
-
2
F
d
(
2
)
(
k
,
n
-
k
-
i
)
+
∑
i
=
0
k
-
2
F
d
(
2
)
(
k
,
n
-
k
+
1
-
i
)
=
∑
i
=
0
k
-
2
[
F
d
(
2
)
(
k
,
n
-
k
-
i
)
+
F
d
(
2
)
(
k
,
n
-
k
+
1
-
i
)
]
=
∑
i
=
0
k
-
2
[
F
d
(
2
)
(
k
,
n
-
i
-
k
)
+
F
d
(
2
)
(
k
,
n
-
i
-
k
+
1
)
]
‍
=
∑
i
=
0
k
-
2
F
d
(
2
)
(
k
,
n
-
i
)
,
‍
which ends the proof.


## 4. Matrix Generators and Combinatorial Formulas forF
d
(
1
)
(
k
,
n
), F
d
(
2
)
(
k
,
n
), and F
d
(
3
)
(
k
,
n
)

Matrix methods are important in recurrence relations. In the last decades some mathematicians have studied to find miscellaneous affinities between matrices and linear recurrences. Using matrix methods different identities and algebraic representations of considered sequences can be obtained, for instance [1, 2, 4–6]. Theory of Fibonacci numbers was previously complemented by the theory of so-called the Fibonacci Q-matrix or the golden matrix. It is worth mentioning that the American mathematician V. Hoggat was one of the first mathematicians who paid the attention to the Q-matrix. For the classical Fibonacci sequence the matrix generators, named as the golden matrix, have the form Q
=
[
1
1
1
0
] and Q
n
=
[
F
n
+
1
F
n
F
n
F
n
-
1
], for n
≥
1.Golden number and golden section have many interesting applications in different areas of science (physics, chemistry, and mechanics); see for example [7, 8]. In this section we give the matrix generators for distance Fibonacci numbers F
d
(
i
)
(
k
,
n
), where i
=
1,2
,
3. The matrix generator of the distance Fibonacci numbers of the first kind F
d
(
1
)
(
k
,
n
) was introduced in [1] and in this paper we apply this method for all kinds of distance Fibonacci numbers.Letk
≥
2 be a fixed integer. Let Q
k
=
[
q
t
j
] be a square matrix of size k. For a fixed 1
≤
t
≤
k an element q
t
1 is equal to the coefficient of F
d
(
i
)
(
k
,
n
-
t
) in the recurrence formula for the distance Fibonacci numbers F
d
(
i
)
(
k
,
n
), i
=
1,2
,
3. For j
≥
2 we define q
t
j as follows:
(22)
q
t
j
=
{
1
if
j
=
t
+
1
0
otherwise
.In other words,(23)
Q
2
=
[
1
1
1
0
]
,
Q
3
=
[
0
1
0
1
0
1
1
0
0
]
,
…
,
Q
k
=
[
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋮
1
0
0
⋯
1
1
0
0
⋯
0
]
,
and the matrix Q
k is named as the distance Fibonacci matrix or the generator of the distance Fibonacci numbers F
d
(
i
)
(
k
,
n
), i
=
1,2
,
3.For a fixed1
≤
i
≤
3 we define the square matrix A
k
(
i
) of size k named as the matrix of initial conditions of the form(24)
A
k
(
i
)
=
[
F
d
(
i
)
(
k
,
2
k
-
2
+
u
(
i
)
)
F
d
(
i
)
(
k
,
2
k
-
3
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
k
-
1
+
u
(
i
)
)
F
d
(
i
)
(
k
,
2
k
-
3
+
u
(
i
)
)
F
d
(
i
)
(
k
,
2
k
-
4
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
k
-
2
+
u
(
i
)
)
⋮
⋮
⋱
⋮
F
d
(
i
)
(
k
,
k
+
u
(
i
)
)
F
d
(
i
)
(
k
,
k
-
1
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
1
+
u
(
i
)
)
F
d
(
i
)
(
k
,
k
-
1
+
u
(
i
)
)
F
d
(
i
)
(
k
,
k
-
2
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
0
+
u
(
i
)
)
]
,where
(25)
u
(
i
)
=
{
i
-
1
for
i
=
1,2
k
-
1
for
i
=
3
.Theorem 11.
Letk
≥
2, n
≥
k be integer. Then for a fixed 1
≤
i
≤
3 holds(26)
A
k
(
i
)
Q
k
n
=
[
F
d
(
i
)
(
k
,
n
+
2
k
-
2
+
u
(
i
)
)
F
d
(
i
)
(
k
,
n
+
2
k
-
3
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
n
+
k
-
1
+
u
(
i
)
)
F
d
(
i
)
(
k
,
n
+
2
k
-
3
+
u
(
i
)
)
F
d
(
i
)
(
k
,
n
+
2
k
-
4
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
n
+
k
-
2
+
u
(
i
)
)
⋮
⋮
⋱
⋮
F
d
(
i
)
(
k
,
n
+
k
+
u
(
i
)
)
F
d
(
i
)
(
k
,
n
+
k
-
1
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
n
+
1
+
u
(
i
)
)
F
d
(
i
)
(
k
,
n
+
k
-
1
+
u
(
i
)
)
F
d
(
i
)
(
k
,
n
+
k
+
u
(
i
)
)
⋯
F
d
(
i
)
(
k
,
n
+
0
+
u
(
i
)
)
]
.Since the proof is analogous as in [1] we omit it. To obtain other matrix generators apart distance Fibonacci numbers F
d
(
i
)
(
k
,
n
), i
=
1,2
,
3, we define a collection of special sequences which are given by the same kth order linear recurrence relations as F
d
(
i
)
(
k
,
n
), i
=
1,2
,
3. These sequences give auxiliary tools for other matrix generators of F
d
(
i
)
(
k
,
n
), i
=
1,2
,
3 and their explicit formulas.Letk
≥
2, n
≥
0 be integers. Let F
k
=
{
F
d
l
(
4
)
(
k
,
n
)
,
l
=
0,1
,
…
,
k
-
1
}, where {
F
d
l
(
4
)
(
k
,
n
)
} is the sequence defined as follows:
(27)
F
d
l
(
4
)
(
k
,
n
)
=
F
d
l
(
4
)
(
k
,
n
-
k
+
1
)
+
F
d
l
(
4
)
(
k
,
n
-
k
)
,
hhhhhhhhhhhhhhhhhhhhihhhhhhhhh
for
n
≥
k
,
with the initial conditions F
d
l
(
4
)
(
k
,
l
)
=
1 and F
d
l
(
4
)
(
k
,
j
)
=
0 for j
≠
l.The numberF
d
1
(
4
)
(
k
,
n
) will be also denoted shortly by F
d
(
4
)
(
k
,
n
) and named as the nth distance Fibonacci number of the fourth kind. If k
=
2 and n
≥
1, then F
d
(
4
)
(
2
,
n
)
=
F
n
-
1.By simple observation we obtain the following relations between numbersF
d
l
(
4
)
(
k
,
n
), for l
=
0,1
,
…
,
k
-
1:
(28)
F
d
0
(
4
)
(
k
,
n
)
=
F
d
(
4
)
(
k
,
n
-
k
+
1
)
,
F
d
l
(
4
)
(
k
,
n
)
=
F
d
(
4
)
(
k
,
n
-
l
+
1
)
for
2
≤
l
≤
k
-
1
.Using sequences from the collectionF
k we can generate the distance Fibonacci numbers F
d
(
i
)
(
k
,
n
), i
=
1,2
,
3:
(29)
F
d
(
1
)
(
k
,
n
)
=
∑
l
=
0
k
-
1
‍
F
d
(
1
)
(
k
,
l
)
F
d
l
(
4
)
(
k
,
n
)
=
∑
l
=
0
k
-
1
‍
F
d
l
(
4
)
(
k
,
n
)
,
F
d
(
2
)
(
k
,
n
)
=
∑
l
=
k
-
1
k
‍
F
d
(
2
)
(
k
,
l
)
F
d
l
-
1
(
4
)
(
k
,
n
-
1
)
=
∑
l
=
k
-
1
k
‍
F
d
l
-
1
(
4
)
(
k
,
n
-
1
)
for
n
≥
1
,
F
d
(
3
)
(
k
,
n
)
=
∑
l
=
0
k
-
1
‍
F
d
(
3
)
(
k
,
k
-
1
+
l
)
F
d
l
(
4
)
(
k
,
n
-
(
k
-
1
)
)
for
n
≥
k
-
1
.Theorem 12.
Letk
≥
2 be integer. Then(i)
F
d
(
1
)
(
k
,
n
)
=
∑
t
=
0
k
-
1
F
d
(
4
)
(
k
,
n
-
t
) for n
≥
k,
(ii)
F
d
(
2
)
(
k
,
n
)
=
F
d
(
4
)
(
k
,
n
-
(
k
-
2
)
)
+
F
d
(
4
)
(
k
,
n
-
(
k
-
1
)
) for n
≥
k,
(iii)
F
d
(
3
)
(
k
,
n
)
=
F
d
(
4
)
(
k
,
n
-
2
(
k
-
1
)
)
+
3
F
d
(
4
)
(
k
,
n
-
(
k
-
1
)
)
+
4
∑
t
=
2
k
-
2
F
d
(
4
)
(
k
,
n
-
(
k
-
1
)
-
t
+
1
) + 3
F
d
(
4
)
(
k
,
n
-
2
(
k
-
1
)
+
1
) for n
≥
2
k
-
1.Proof.
LetF
d
l
(
1
)
(
k
,
n
) denote a sequence defined by the same recurrence as F
d
(
1
)
(
k
,
n
) with initial conditions
(30)
F
d
l
(
1
)
(
k
,
n
)
=
{
F
d
(
1
)
(
k
,
l
)
if
n
=
l
0
if
n
≠
l
for
n
≤
k
-
1
.
Then
(31)
F
d
l
(
1
)
(
k
,
n
)
=
F
d
0
(
1
)
(
k
,
n
)
+
⋯
+
F
d
k
-
1
(
1
)
(
k
,
n
)
=
F
d
(
1
)
(
k
,
0
)
F
d
0
(
1
)
(
k
,
n
)
+
⋯
+
F
d
(
1
)
(
k
,
-
1
)
F
d
k
-
1
(
1
)
(
k
,
n
)
=
1
F
d
0
(
1
)
(
k
,
n
)
+
⋯
+
1
F
d
k
-
1
(
1
)
(
k
,
n
)
=
∑
t
=
0
k
-
1
‍
F
d
(
4
)
(
k
,
n
-
t
)
.
We prove analogously formulas (ii) and (iii).Using the above theorem we obtain a new matrix generator for distance Fibonacci numbersF
d
(
i
)
(
k
,
n
), i
=
1,2
,
3.Corollary 13.
For the distance Fibonacci numbersF
d
(
i
)
(
k
,
n
), i
=
1,2
,
3, Theorem 12 gives its matrix generator, respectively:(1)
∑
t
=
0
k
-
1
Q
k
n
-
t for n
≥
k,
(2)
Q
k
n
-
(
k
-
2
)
+
Q
k
n
-
(
k
-
1
) for n
≥
k,
(3)
Q
k
n
-
2
(
k
-
1
)
+
3
Q
k
n
-
(
k
-
1
)
+
4
∑
t
=
2
k
-
2
Q
k
n
-
(
k
-
1
)
-
t
+
1
+
Q
k
n
-
2
(
k
-
1
)
+
1 for n
≥
2
k
-
1.Theorem 14.
Letk
≥
2, n
≥
k be integer. Then
(32)
F
d
(
4
)
(
k
,
n
+
1
)
=
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
‍
(
k
1
+
k
2
k
1
)
.Proof.
We consider a digraphD
k represented by adjacency matrix Q
k auxiliary (Figure 1).
Note that matrixQ
k
n has the following form:(33)
[
F
d
(
4
)
(
k
,
n
+
1
)
F
d
(
4
)
(
k
,
n
)
⋯
F
d
(
4
)
(
k
,
n
-
(
k
-
2
)
)
F
d
(
4
)
(
k
,
n
+
2
)
F
d
(
4
)
(
k
,
n
+
1
)
⋯
F
d
(
4
)
(
k
,
n
-
(
k
-
1
)
)
⋮
⋮
⋱
⋮
F
d
(
4
)
(
k
,
n
+
(
k
-
1
)
)
F
d
(
4
)
(
k
,
n
+
(
k
-
2
)
)
⋯
F
d
(
4
)
(
k
,
n
)
F
d
(
4
)
(
k
,
n
)
F
d
(
4
)
(
k
,
n
-
1
)
⋯
F
d
(
4
)
(
k
,
n
-
(
k
-
1
)
)
]
.
It is well known thatq
i
j
∈
Q
k
n is equal to the number of all distinct paths of length n between vertices v
i and v
j in the digraph D
k.
Each pathP from v
1 to v
1 in digraph D
k has the following form: P
:
v
1
⇢
v
x
1
→
v
1
⇢
v
x
2
→
v
1
⋯
v
1
⇢
v
x
i
→
v
1 where v
1
⇢
v
x denotes the unique shortest path from v
1 to v
x in digraph D
k. Parts v
1
⇢
v
x
→
v
1 are cycles of the length x, where x is k or k
-
1. Thus the length of the path P is equal to x
1
+
x
2
+
⋯
+
x
i. There exists one-to-one correspondence between the path P and a tuple (
x
1
,
x
2
,
…
,
x
i
). If the path P has a length n, then the corresponding tuple is a decomposition of an integer n when k occurs k
1 times and k
-
1 occurs k
2 times and k
1
·
k
+
k
2
·
(
k
-
1
)
=
n. The number of such tuples is equal to the binomial coefficient (
k
1
+
k
2
k
1
). We determine analogously the number of different paths between other pairs of vertices.Figure 1
A digraphD
k.Using Theorems14 and 12 we can prove the following.Theorem 15.
Letk
≥
2 be integer. Then
(34)
F
d
(
1
)
(
k
,
n
)
=
∑
i
=
0
k
-
1
‍
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
-
i
-
1
‍
(
k
1
+
k
2
k
1
)
,
n
≥
k
,
F
d
(
2
)
(
k
,
n
)
=
∑
i
=
k
-
2
k
-
1
‍
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
-
i
-
1
‍
(
k
1
+
k
2
k
1
)
,
n
≥
k
,
F
d
(
3
)
(
k
,
n
)
=
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
-
1
-
2
(
k
-
1
)
‍
(
k
1
+
k
2
k
1
)
+
3
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
-
1
-
(
k
-
1
)
‍
(
k
1
+
k
2
k
1
)
+
4
∑
i
=
2
k
-
2
‍
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
-
i
-
(
k
-
1
)
‍
(
k
1
+
k
2
k
1
)
+
∑
k
1
,
k
2
k
1
·
k
+
k
2
·
(
k
-
1
)
=
n
-
2
(
k
-
1
)
‍
(
k
1
+
k
2
k
1
)
,
n
≥
2
k
-
1
.Tables1, 2, 3, and 4 present first words of four types of distance Fibonacci numbers F
d
(
1
)
(
k
,
n
), F
d
(
2
)
(
k
,
n
), F
d
(
3
)
(
k
,
n
), and F
d
(
4
)
(
k
,
n
).Table 1
Thenth distance Fibonacci numbers F
d
(
1
)
(
k
,
n
).
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
F
d
(
1
)
(
2
,
n
)
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
F
d
(
1
)
(
3
,
n
)
1
1
1
2
2
3
4
5
7
9
12
16
21
28
37
F
d
(
1
)
(
4
,
n
)
1
1
1
1
2
2
2
3
4
4
5
7
8
9
12
F
d
(
1
)
(
5
,
n
)
1
1
1
1
1
2
2
2
2
3
4
4
4
5
7
F
d
(
1
)
(
6
,
n
)
1
1
1
1
1
1
2
2
2
2
2
3
4
4
4
F
d
(
1
)
(
7
,
n
)
1
1
1
1
1
1
1
2
2
2
2
2
2
3
4
F
d
(
1
)
(
8
,
n
)
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2Table 2
Thenth distance Fibonacci numbers F
d
(
2
)
(
k
,
n
).
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
F
d
(
2
)
(
2
,
n
)
0
1
2
3
5
8
13
21
34
55
89
144
233
377
610
F
d
(
2
)
(
3
,
n
)
0
0
1
1
1
2
2
3
4
5
7
9
12
16
21
F
d
(
2
)
(
4
,
n
)
0
0
0
1
1
0
1
2
1
1
3
3
2
4
6
F
d
(
2
)
(
5
,
n
)
0
0
0
0
1
1
0
0
1
2
1
0
1
3
3
F
d
(
2
)
(
6
,
n
)
0
0
0
0
0
1
1
0
0
0
1
2
1
0
0
F
d
(
2
)
(
7
,
n
)
0
0
0
0
0
0
1
1
0
0
0
0
1
2
1
F
d
(
2
)
(
8
,
n
)
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1Table 3
Thenth distance Fibonacci numbers F
d
(
3
)
(
k
,
n
).
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
F
d
(
3
)
(
2
,
n
)
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
F
d
(
3
)
(
3
,
n
)
1
1
1
3
3
4
6
7
10
13
17
23
30
40
53
F
d
(
3
)
(
4
,
n
)
1
1
1
1
3
4
3
4
7
7
7
11
14
14
18
F
d
(
3
)
(
5
,
n
)
1
1
1
1
1
3
4
4
3
4
7
8
7
7
11
F
d
(
3
)
(
6
,
n
)
1
1
1
1
1
1
3
4
4
4
3
4
7
8
8
F
d
(
3
)
(
7
,
n
)
1
1
1
1
1
1
1
3
4
4
4
4
3
4
7
F
d
(
3
)
(
8
,
n
)
1
1
1
1
1
1
1
1
3
4
4
4
4
4
3Table 4
Thenth distance Fibonacci numbers F
d
(
4
)
(
k
,
n
).
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
F
d
(
4
)
(
2
,
n
)
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
F
d
(
4
)
(
3
,
n
)
0
1
0
1
1
1
2
2
3
4
5
7
9
12
16
F
d
(
4
)
(
4
,
n
)
0
1
0
0
1
1
0
1
2
1
1
3
3
2
4
F
d
(
4
)
(
5
,
n
)
0
1
0
0
0
1
1
0
0
1
2
1
0
1
3
F
d
(
4
)
(
6
,
n
)
0
1
0
0
0
0
1
1
0
0
0
1
2
1
0
F
d
(
4
)
(
7
,
n
)
0
1
0
0
0
0
0
1
1
0
0
0
0
1
2
F
d
(
4
)
(
8
,
n
)
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0



---

*Source: 491591-2014-10-23.xml*