An application of Fibonacci numbers

An application of Fibonacci numbers
in matrices
Erdal Karaduman
Fen Edebiyat Fak€ultesi Matematik B€ol€um€u, Atat€urk University, 25240 Erzurum, Turkey
Abstract
In this paper, we investigate the determinants of the matrices obtained by k
sequences of the generalized order-k Fibonacci numbers.

2002 Elsevier Inc. All rights reserved.
Keywords: Fibonacci numbers; The generalized order-k Fibonacci numbers; Fibonacci sequences;
Matrix; Determinant
In the recent years, there has been much interest in applications of Fibonacci
numbers and sequences. Karaduman and Yavuz proved that the periods of the
2-step Fibonacci recurrences in finite nilpotent groups of nilpotency class 5 and
exponent p are pkðpÞ, for 2 < p 6 2927, where p is prime and kðpÞ is the periods
of ordinary 2-step Fibonacci sequences [3]. The theory has been generalized
in [4] to the 2-step general Fibonacci sequences in finite nilpotent groups of
nilpotency class 4 and exponent p. Also, it is shown in [5] that the period of 2-
step general Fibonacci sequence is equal to the length of fundamental period of
the 2-step general recurrence constructed by two generating elements of the
group of exponent p and nilpotency class 2. CAYLEY has been used for calculations
in [5].
Lee has investigated the relationship between gðkÞ
n Fibonacci numbers and
lðkÞ
n Lucas numbers [6]. Takahashi gives a fast algorithm which is based on the
product of Lucas numbers to compute large Fibonacci numbers [7]. Fibonacci
sequences have been an interesting subject in applied mathematics. West has
E-mail address: [e-mail] (E. Karaduman).
0096-3003/$ - see front matter
2002 Elsevier Inc. All rights reserved.
doi:10.1016/S0096-3003(02)00827-5
Applied Mathematics and Computation 147 (2004) 903–908
www.elsevier.com/locate/amc
shown using transfer matrices that the number jSnð123; 3214Þj of permutations
avoiding the patterns 123 and 3214 is the Fibonacci number F2n [8].
Kalman [1] derives a number of closed-form formulas for the generalized
Fibonacci sequence by matrix methods. In [2], Er has extended the matrix
representation and showed that the sums of the generalized Fibonacci numbers
could be derived directly using this representation.
Define k sequences of the generalized order-k Fibonacci numbers as shown:
gi
n ¼ X
k
j¼1
gi
n
j; for n > 0 and 1 6 i 6 k; ð1Þ
with boundary conditions
gi
n ¼ 1; i ¼ 1
n;
0; otherwise

for 1
k 6 n 6 0;
where gi
n is the nth term of the ith sequence. When k ¼ 2, generalized order-k
Fibonacci sequence is reduced to the conventional Fibonacci sequence.
Following the approach taken by Kalman [1], a k k square matrix A can be
defined as follows:
A ¼
111 1 1
100 0 0
010 0 0
.
.
. .
.
. .
.
. .
.
. .
.
.
000 0 0
000 1 0
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
:
Then, by a property of matrix multiplication, we have
½gi
nþ1gi
n gi
n
kþ2
T ¼ A½gi
ngi
n
1 gi
n
kþ1
T
: ð2Þ
To deal with the k sequences of the generalized order-k Fibonacci series
simultaneously, a k k square matrix Gn is defined as follows [2]:
Gn ¼
g1
n g2
n gk
n
g1
n
1 g2
n
1 g2
n
1
.
.
. .
.
. .
.
.
g1
n
kþ1 g2
n
kþ1 gk
n
kþ1
2
6
6
6
4
3
7
7
7
5:
Generalizing Eq. (2), we have
Gnþ1 ¼ AGn ð3Þ
Then, by an inductive argument, one may rewrite it as
Gnþ1 ¼ An
G1: ð4Þ
904 E. Karaduman / Appl. Math. Comput. 147 (2004) 903–908
Now, it can be readily seen that, by Definition (1), G1 ¼ A; therefore, Gn ¼
An. Thus, Eqs. (3) and (4) may be rewritten as shown:
Gnþ1 ¼ GnG1 ¼ G1Gn ð5Þ
or
Gnþ1 ¼ Anþ1
:
In other words, G1 is commutative under matrix multiplication.
Theorem 1. If the Gn has the form
Gn ¼
g1
n g2
n gk
n
g1
n
1 g2
n
1 gk
n
1
.
.
. .
.
. .
.
.
g1
n
kþ1 g2
n
kþ1 gk
n
kþ1
2
6
6
6
4
3
7
7
7
5
then,
det Gn ¼ ð
1Þ
n
; if k is even
1; if k is odd

;
where, gi
n ¼ Pk
j¼1 gi
n
j, for n > 0 and 1 6 i 6 k, with boundary conditions
gi
n ¼ 1; i ¼ 1
n;
0; otherwise;


for 1
k 6 n 6 0:
Proof. Since for 8k,
G1 ¼ A ¼
111 1 1
100 0 0
010 0 0
.
.
. .
.
. .
.
. .
.
. .
.
.
000 0 0
000 1 0
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
after ðk
1Þ-step elementary rows operations G1 is reduced to the triangular
matrix form as shown:
11 1 1 1
0
1
1
1
1
0 0
1
1
1
.
.
. .
.
. .
.
. .
.
. .
.
.
00 0
1
1
00 0 0
1
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
:
E. Karaduman / Appl. Math. Comput. 147 (2004) 903–908 905
So, det G1 ¼ det A ¼ 1 ð
1Þ
k
1
. On the other hand, since Gn ¼ An we have
det Gn ¼ ðdet AÞ
n
det Gn ¼ ðð
1Þ
k
1
Þ
n
: ð6Þ
Therefore, if k is even, ðk
1Þ will be odd. So, ð
1Þ
k
1 ¼
1. Thus, from (6),
we have det Gn ¼ ð
1Þ
n
. If k is odd, ðk
1Þ will be even. So, ð
1Þ
k
1 ¼ 1 and
thus, from (6), we have det Gn ¼ 1. We are done.

Now, if we ignore the condition n > 0 in Definition (1), we can define k
sequences of the generalized order-k Fibonacci numbers as shown:
gi
n ¼ X
k
j¼1
gi
n
j; 1 6 i 6 k ð7Þ
with boundary conditions
gi
n ¼ 1; i ¼ 1
n;
0; otherwise;


for 1
k 6 n 6 0;
where gi
n is the nth term of the ith sequence. When k ¼ 2, generalized order-k
Fibonacci sequence is reduced to the conventional Fibonacci sequence with
initial data g1
0 ¼ 1, g1
1 ¼ 1.
We define k k square matrices Gn, B and C as follows:
Gn ¼
g1
n g2
n gk
n
g1
n
1 g2
n
1 gk
n
1
.
.
. .
.
. .
.
.
g1
n
kþ1 g2
n
kþ1 gk
n
kþ1
2
6
6
6
4
3
7
7
7
5;
B ¼
20 21 22 2k
2 2k
1
20 20 21 2k
3 2k
2
0 20 20 2k
4 2k
3
.
.
. .
.
. .
.
. .. . .
.
. .
.
.
000 ..
. 20 21
000 20 20
2
6
6
6
6
6
6
6
4
3
7
7
7
7
7
7
7
5
;
C ¼
000 0 1
100 0 1
010 0 1
.
.
. .
.
. .
.
. .
. . .
.
. .
.
.
000 .. . 0 1
000 1 1
2
6
6
6
6
6
6
6
4
3
7
7
7
7
7
7
7
5
:
Now, it can be readily seen that, by Definition (7), G1 ¼ B. Then, by an
inductive argument, we write
906 E. Karaduman / Appl. Math. Comput. 147 (2004) 903–908
Gnþ1 ¼ BCn
: ð8Þ
But, B is not commutative under matrix multiplication.
Theorem 2. If Gn has the form as shown:
Gn ¼
g1
n g2
n gk
n
g1
n
1 g2
n
1 gk
n
1
.
.
. .
.
. .
.
.
g1
n
kþ1 g2
n
kþ1 gk
n
kþ1
2
6
6
6
4
3
7
7
7
5
then,
det Gn ¼ 1; if k is odd
ð
1Þ
n
; if k is even

:
Proof. Since Gn ¼ G1Cn
1 ¼ BCn
1, we have
det Gn ¼ det G1 ðdet CÞ
n
1
: ð9Þ
So, after ðk
1Þ-step elementary rows operations G1 is reduced to the triangular
matrix form as shown:
20 21 22 2k
2 2k
1
0
1
2
2k
3
2k
2
0 0
1
2k
4
2k
3
.
.
. .
.
. .
.
. .
.
. .
.
.
00 0
1
20
00 0 0
1
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
Therefore, we have det G1 ¼ 1 ð
1Þ
k
1
. Simultaneously, replacing first row of
C with the other rows of C, C is reduced to the triangular matrix form as
shown:
100 0 1
010 0 1
001 0 1
.
.
. .
.
. .
.
. .
.
. .
.
.
000 1 1
000 0 1
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
:
So, we have det C ¼ ð
1Þ
k
1
. Thus, we have det Gn ¼ ð
1Þ
k
1
ðð
1Þ
k
1
Þ
n
1
,
from (9). On the other hand, if k is even then we have ð
1Þ
k
1 ¼
1, and if k is
odd then we have ð
1Þ
k
1 ¼ 1. Therefore, we have
E. Karaduman / Appl. Math. Comput. 147 (2004) 903–908 907
det Gn ¼ 1; if k is odd
ð
1Þ
n
; if k is even

:
We are done.

From Eqs. (1) and (7), we see that the condition n > 0 does not change the
determinants of Gn. But, it yields that G1 is commutative under matrix multiplication
or not. i.e. if we do not ignore the condition n > 0 then G1 is
commutative under matrix multiplication, otherwise it is not.
References
[1] D. Kalman, Generalized Fibonacci numbers by matrix methods, The Fibonacci Quarterly 20 (1)
(1982) 73–76.
[2] M.C. Er, Sums of Fibonacci numbers by matrix methods, The Fibonacci Quarterly 22 (3) (1984)
204–207.
[3] E. Karaduman, U. Yavuz, On the period Fibonacci sequences in nilpotent groups, Applied
Mathematics and Computation (AMC 7453), in press.
[4] E. Karaduman, H. Aydn, General 2-Step Fibonacci Sequences in nilpotent groups of exponent
p and nilpotency class 4, Applied Mathematics and Computation (AMC 7418), in press.
[5] H. Aydn, R. Dikici, General Fibonacci sequences in finite groups, The Fibonacci Quarterly 36
(3) (1998) 216–221.
[6] G.Y. Lee, Fibonacci k-Lucas numbers and associated bipartite graphs, Linear Algebra and its
Applications 320 (2000) 51–61.
[7] D. Takahashi, A fast algorithm for computing large Fibonacci numbers, Information
Processing Letters 75 (2000) 243–246.
[8] J. West, Generating trees and the forbidden subsequences, Discrete Mathematics 157 (1996)
363–374.
908 E. Karaduman / Appl. Math. Comput. 147 (2004) 903–908

ผลลัพธ์ (ไทย) 1:

แอพลิเคชันของเลขฟีโบนัชชีในเมทริกซ์Erdal KaradumanFen ฟาก Edebiyat €ultesi € Matematik B€ ol อุ่ม €u, Atat€ urk มหาวิทยาลัย Erzurum 25240 ตุรกีบทคัดย่อในเอกสารนี้ เราตรวจสอบดีเทอร์มิแนนต์ของเมทริกซ์ที่ได้รับลำดับของเลขฟีโบนัชชีเมจแบบทั่วไปสั่ง-k2002 Elsevier Inc. สงวนลิขสิทธิ์ทั้งหมดคำสำคัญ: เลขฟีโบนัชชี เลขฟีโบนัชชีเมจแบบทั่วไปสั่ง-k ลำดับ Fibonacciเมตริกซ์ ดีเทอร์มิแนนต์ในปีที่ผ่านมา มีมากสนใจในการใช้งานของฟีโบนัชชีตัวเลขและลำดับ Karaduman และ Yavuz พิสูจน์ที่รอบระยะเวลาของการขั้นที่ 2 เกิดฟีโบนัชชีในกลุ่มนิรพลจำกัด nilpotency คลาส 5 และยกกำลัง p เป็น pkðpÞ, 2 < p 6 2927 โดยที่ p คือ นายกและ kðpÞ คือ รอบระยะเวลาFibonacci 2-ขั้นตอนทั่วไปของลำดับ [3] ทฤษฎีการตั้งค่าทั่วไปใน [4] ลำดับ 2-ขั้นตอนทั่วไปฟีโบนัชชีในกลุ่มนิรพลจำกัดnilpotency ชั้น 4 และยกกำลัง p มันจะแสดงใน [5] ที่ระยะ 2-ขั้นตอนลำดับ Fibonacci ทั่วไปจะเท่ากับความยาวของรอบระยะเวลาพื้นฐานเกิดทั่วไปขั้นตอน 2 สร้าง ด้วยสององค์ประกอบสร้างของการกลุ่มของยกกำลัง p และ nilpotency ชั้น 2 ใช้สำหรับการคำนวณ CAYLEYใน [5]ลีได้ศึกษาความสัมพันธ์ระหว่าง gðkÞเลขฟีโบนัชชี n และlðkÞLucas n หมายเลข [6] ทะกะฮะชิให้อัลกอริทึมอย่างรวดเร็วซึ่งเป็นไปตามผลิตภัณฑ์ของ Lucas การหมายเลขการคำนวณตัวเลข Fibonacci ใหญ่ [7] ฟีโบนัชชีลำดับได้รับสนใจในคณิตศาสตร์ประยุกต์ ตะวันตกได้ที่อยู่อีเมล์: [e-mail] (E. Karaduman)0096-3003 / $ - ดูหน้าเรื่อง 2002 Elsevier อิงค์ สงวนลิขสิทธิ์ทั้งหมดdoi:10.1016 / S0096-3003 (02) 00827-5ใช้คณิตศาสตร์และการคำนวณ 147 (2004) 903-908www.elsevier.com/locate/amcแสดงโดยใช้เมทริกซ์โอนที่ jSnð123 หมายเลข 3214Þj สับหลีกเลี่ยงรูปแบบ 123 และ 3214 เป็น F2n เลขฟีโบนัชชี [8]จำนวนแบบฟอร์มปิดสูตรที่เมจแบบทั่วไปมา Kalman [1]ลำดับ fibonacci โดยวิธีเมตริกซ์ ใน [2], Er ได้ขยายเมตริกซ์แสดง และชี้ให้เห็นว่าผลรวมของเลขฟีโบนัชชีเมจแบบทั่วไปสามารถได้รับมาโดยตรงโดยใช้การแสดงนี้กำหนด k ลำดับของเลขฟีโบนัชชีเมจแบบทั่วไปสั่ง-k ดัง:gin ¼ Xkj¼1gin j สำหรับ n > 0 และ 1 6 6 k ฉัน ð1Þมีเงื่อนไขขอบเขตgin ¼ 1 ไอ¼ 1 n0 เป็นอย่างอื่นสำหรับ n k 6 1 6 0ที่จิn คือ คำที่ n ของลำดับระยะ เมื่อสั่ง-k k ¼ 2 ตั้งค่าทั่วไปลำดับ fibonacci จะลดลงเป็นลำดับ Fibonacci ธรรมดาสามารถเป็นเมทริกซ์จัตุรัส k k A ต่อวิธีการดำเนินการ โดย Kalman [1],กำหนดได้ดังนี้:เป็น¼111 1 1100 0 0010 0 0... ... ... ... ...000 0 0000 1 02666666437777775:โดยคุณสมบัติของการคูณเมทริกซ์ เรามาแล้ว½ginþ1giเอ็นจิn kþ2T ¼ A½gingin 1 gin kþ1T: ð2Þการจัดการกับลำดับที่ k ของลำดับ Fibonacci สั่ง k เมจแบบทั่วไปพร้อมกัน เมทริกซ์จัตุรัส k k Gn ถูกกำหนดเป็นดังนี้ [2]:Gn ¼g1n g2n gkng1g2 n 1g2 n 1n 1... ... ...g1n kþ1 g2n kþ1 gkn kþ12666437775:Generalizing Eq. (2), เราได้Gnþ1 ¼ AGn ð3Þโดยอาร์กิวเมนต์เชิงอุปนัย หนึ่งอาจเขียนใหม่เป็นGnþ1 ¼มีG1: ð4Þ904 E. Karaduman / คณิตศาสตร์ประยุกต์ Comput 147 (2004) 903-908ตอนนี้ ให้พร้อมเห็นว่า โดยนิยาม (1), G1 ¼ A ดังนั้น Gn ¼การ ดังนั้น Eqs (3) และ (4) พฤษภาคมจิตจะแสดง:Gnþ1 ¼ GnG1 ¼ G1Gn ð5ÞหรือGnþ1 ¼ Anþ1:ในคำอื่น ๆ G1 จะสลับภายใต้การคูณเมทริกซ์ทฤษฎีบทที่ 1 ถ้า Gn มีรูปแบบGn ¼g1n g2n gkng1g2 n 1gk n 1n 1... ... ...g1n kþ1 g2n kþ1 gkn kþ12666437775แล้ว1Þ เดช Gn ¼ðn; ถ้า k เป็นเลขคู่1 ถ้า k เป็นคี่;ที่ gin ¼คือจิ j¼1j n, n > 0 และ 1 6 6 k มีเงื่อนไขขอบเขตของฉันgin ¼ 1 ไอ¼ 1 n0 มิฉะนั้น
สำหรับ n k 6 1 6 0:หลักฐานการ เนื่องจากใน 8kG1 ¼เป็น¼111 1 1100 0 0010 0 0... ... ... ... ...000 0 0000 1 02666666437777775หลังจากขั้นตอน ðk 1Þ ประถมแถวดำเนิน G1 จะลดลงเป็นที่สามแบบฟอร์มเมตริกซ์แสดง:11 1 1 10 1 1 1 10 0 1 1 1... ... ... ... ...00 0 1 100 0 0 12666666437777775:E. Karaduman / คณิตศาสตร์ประยุกต์ Comput 147 (2004) 903-908 905อื่น ๆ เดช G1 เดช¼ A ¼ 1 ð 1Þk 1. บนมืออื่น ๆ ตั้งแต่ Gn ¼เรามีðdet Gn ¼เดช AÞnเดช 1Þ ðð Gn ¼k 1Þn: ð6Þดังนั้น ถ้า k เป็นเลขคู่ ðk 1Þ จะได้คี่ ดังนั้น ð 1Þk 1 ¼ 1 ดังนั้น จาก (6),เรามีเดช Gn ¼ð 1Þn. ถ้า k เป็นคี่ ðk 1Þ จะได้แม้แต่ ดังนั้น ð 1Þk 1 ¼ 1 และดังนั้น จาก (6), เราได้เดช Gn ¼ 1 เราจะทำ
ตอนนี้ ถ้าเราละเว้นเงื่อนไข n > 0 ในนิยาม (1), เราสามารถกำหนด kลำดับของเลขฟีโบนัชชีเมจแบบทั่วไปสั่ง-k ดัง:gin ¼ Xkj¼1gin j 1 ð7Þ i 6 k 6มีเงื่อนไขขอบเขตgin ¼ 1 ไอ¼ 1 n0 มิฉะนั้น
สำหรับ n k 6 1 6 0ที่จิn คือ คำที่ n ของลำดับระยะ เมื่อสั่ง-k k ¼ 2 ตั้งค่าทั่วไปลำดับ fibonacci จะลดลงเป็นลำดับ Fibonacci ธรรมดาด้วยข้อมูล g10 ¼ 1, g11 ¼ 1เรากำหนด k k สแควร์เมทริกซ์ Gn, B และ C เป็นดังนี้:Gn ¼g1n g2n gkng1g2 n 1gk n 1n 1... ... ...g1n kþ1 g2n kþ1 gkn kþ12666437775บี¼20 21 22 2 k k 2 2 120 20 21 2 k 3 2 k 20 20 20 2 k k 4 2 3... ... ... .. . ... ...000 .... 20 21000 20 20266666664377777775;ซี¼000 0 1100 0 1010 0 1... ... ... .. . ... ...000 ... . 0 1000 1 1266666664377777775:ตอนนี้ ให้พร้อมเห็นว่า ตามข้อกำหนด (7), G1 ¼ B. แล้ว ตามด้วยการเราเขียนอาร์กิวเมนต์เชิงอุปนัย906 E. Karaduman / คณิตศาสตร์ประยุกต์ Comput 147 (2004) 903-908Gnþ1 ¼ BCn: ð8Þแต่ ไม่สลับภายใต้การคูณเมทริกซ์ Bทฤษฎีบทที่ 2 ถ้า Gn มีรูปแบบดังที่แสดง:Gn ¼g1n g2n gkng1g2 n 1gk n 1n 1... ... ...g1n kþ1 g2n kþ1 gkn kþ12666437775แล้วเดช Gn ¼ 1 ถ้า k เป็นคี่ð 1Þn; ถ้า k เป็นเลขคู่:หลักฐานการ ตั้งแต่¼ G1Cn Gn 1 ¼ BCn 1 เรามีðdet เดช G1 Gn ¼เดช CÞn 1: ð9Þดังนั้น หลังจากขั้นตอน ðk 1Þ ประถมแถวดำเนิน G1 จะลดลงเป็นที่สามแบบฟอร์มเมตริกซ์แสดง:20 21 22 2 k k 2 2 10 1 2 2 3 2 k k 20 0 1 2 4 2 k k 3... ... ... ... ...00 0 1 2000 0 0 12666666437777775ดังนั้น เรามีเดช G1 ¼ 1 ð 1Þk 1. พร้อมกัน เปลี่ยนแถวแรกC กับแถวของ C, C จะลดลงเป็นแบบเมตริกซ์สามเหลี่ยมเป็นแสดง:100 0 1010 0 1001 0 1... ... ... ... ...000 1 1000 0 12666666437777775:ดังนั้น เรามีเดช C ¼ð 1Þk 1. ดังนั้น เรามีเดช Gn ¼ð 1Þk 1ðð 1Þk 1Þn 1,จาก (9) ในทางกลับกัน ถ้า k คือ แม้เราแล้วð 1Þk 1 ¼ 1 และ kคี่แล้วเรามีð 1Þk 1 ¼ 1 ดังนั้น เราได้E. Karaduman / คณิตศาสตร์ประยุกต์ Comput 147 (2004) 903-908 907เดช Gn ¼ 1 ถ้า k เป็นคี่ð 1Þn; ถ้า k เป็นเลขคู่:เราจะทำ
จาก Eqs (1) และ (7), เราเห็นว่า เงื่อนไข n > 0 ไม่เปลี่ยนดีเทอร์มิแนนต์ของ Gn. แต่ ก็ทำให้ว่า G1 สลับภายใต้การคูณเมทริกซ์หรือไม่ เช่นถ้าเราได้ละเว้นเงื่อนไข n > 0 แล้ว G1 เป็นภายใต้การคูณเมทริกซ์สลับ อย่างอื่นไม่การอ้างอิง[1] D. Kalman โดยวิธีเมตริกซ์ เลขฟีโบนัชชีตั้งค่าทั่วไป Fibonacci ที่ไตร 20 (1)(1982) 73-76[2] เอ็มซี Er เลขผลรวมของ Fibonacci โดยวิธีเมตริกซ์ เดอะฟีโบนัชชีไตร 22 (3) (1984)204-207[3] E. Karaduman, Yavuz สหรัฐ ในลำดับ Fibonacci รอบในนิรพลกลุ่ม ใช้คณิตศาสตร์และการคำนวณ (AMC 7453), กด[4] E. Karaduman, H. Aydn ลำดับ Fibonacci 2-ขั้นตอนทั่วไปในกลุ่มนิรพลยกp และ nilpotency คลาส 4 ใช้คณิตศาสตร์และการคำนวณ (AMC 7418), ในวารสาร[5] H. Aydn, R. Dikici ลำดับ Fibonacci ทั่วไปในกลุ่มจำกัด Fibonacci 36 รายไตรมาส(3) (1998) 216-221[6] G.Y. Lee หมายเลขฟีโบนัชชี k Lucas และเชื่อมโยงกราฟสองส่วนบริบูรณ์ พีชคณิตเชิงเส้นและโปรแกรมประยุกต์ 320 (2000) 51-61[7] D. ทะกะฮะชิ อัลกอริทึมที่รวดเร็วสำหรับการคำนวณจำนวนมาก Fibonacci ข้อมูลทั่วไป 75 (2000) 243-246[8] เจ.เวสต์ Generating ต้นไม้และ subsequences ต้องห้าม 157 คณิตศาสตร์ไม่ต่อเนื่อง (1996)363-374908 E. Karaduman / คณิตศาสตร์ประยุกต์ Comput 147 (2004) 903-908

ผลลัพธ์ (ไทย) 2:

แอพลิเคชันของตัวเลขฟีโบนักชีในการฝึกอบรมErdal Karaduman Fen Edebiyat ฟัก€ ultesi Matematik B €เฒ่า€หนอ€มึง Atat € Urk มหาวิทยาลัย 25,240 เอิร์ซ, ตุรกีบทคัดย่อในบทความนี้เราจะตรวจสอบปัจจัยของการฝึกอบรมที่ได้จากk ลำดับของ ทั่วไปเพื่อ-k ตัวเลข Fibonacci.? 2002 เอลส์อิงค์สงวนลิขสิทธิ์. คำสำคัญ: ตัวเลข Fibonacci; ทั่วไปหมายเลขลำดับฟีโบนักชี k; ลำดับฟีโบนักชี; เมทริกซ์; ปัจจัยในปีที่ผ่านมามีความสนใจมากในการใช้งานของ Fibonacci ตัวเลขและลำดับ Karaduman และ Yavuz พิสูจน์ให้เห็นว่าระยะเวลาของการซ้ำFibonacci 2 ขั้นตอนในกลุ่ม nilpotent จำกัด ของระดับ nilpotency 5 และพีสัญลักษณ์เป็นpkðpÞสำหรับ2 <p 6 2927 ที่พีเป็นสำคัญและkðpÞเป็นงวดสามัญ2 ขั้นตอนฟีโบนักชี ลำดับ [3] ทฤษฎีที่ได้รับการทั่วไปใน [4] กับ Fibonacci ทั่วไป 2 ขั้นตอนลำดับในกลุ่ม nilpotent จำกัด ของระดับnilpotency 4 p และสัญลักษณ์ นอกจากนี้ก็จะแสดงใน [5] ว่าระยะเวลาของ 2- ลำดับฟีโบนักชีทั่วไปขั้นตอนที่จะมีค่าเท่ากับความยาวของระยะเวลาที่พื้นฐานของทั้ง 2 ขั้นตอนการเกิดซ้ำทั่วไปสร้างขึ้นโดยสององค์ประกอบที่ก่อให้เกิดของกลุ่มพีสัญลักษณ์และชั้น2 nilpotency เคย์ลีได้รับการใช้สำหรับการคำนวณใน[5]. ลีได้รับการตรวจสอบความสัมพันธ์ระหว่างgðkÞ n ตัวเลข Fibonacci และlðkÞ n ตัวเลขลูคัส [6] ทากาฮาชิจะช่วยให้ขั้นตอนวิธีการอย่างรวดเร็วซึ่งจะขึ้นอยู่กับผลิตภัณฑ์ของตัวเลขลูคัสในการคำนวณตัวเลข Fibonacci ขนาดใหญ่ [7] ฟีโบนักชีลำดับได้รับเรื่องที่น่าสนใจในคณิตศาสตร์ประยุกต์ เวสต์มีที่อยู่ E-mail: [e-mail] (อี Karaduman). 0096-3003 / $ - เห็นว่าหน้า? 2002 เอลส์อิงค์สงวนลิขสิทธิ์. ดอย: 10.1016 / S0096-3003 (02) 00827-5 คณิตศาสตร์ประยุกต์และการคำนวณ 147 (2004) 903-908 www.elsevier.com/locate/amc แสดงโดยใช้การฝึกอบรมการถ่ายโอนว่าจำนวนjSnð123; 3214Þjของพีชคณิตหลีกเลี่ยงรูปแบบ 123 และ 3214 เป็นจำนวนฟีโบนักชี F2n [8]. คาลมาน [1] มาจำนวนของสูตรปิดรูปแบบสำหรับทั่วไปลำดับฟีโบนักชีโดยวิธีเมทริกซ์ ใน [2], Er ได้ขยายเมทริกซ์การแสดงและแสดงให้เห็นว่าผลรวมของตัวเลขFibonacci ทั่วไปที่. อาจจะมาโดยตรงโดยใช้การแสดงนี้กำหนดลำดับ k ของตัวเลข Fibonacci เพื่อ-k ทั่วไปที่แสดง: กูเกิn ¼ X k j¼1กูเกิล? n ญ; สำหรับ n> 0 และ 1 6 6 ฉัน k; ð1Þกับเงื่อนไขขอบเขตกูเกิn ¼ 1; ฉัน¼ 1 n; 0; อย่างอื่น? 1? k n 6 6 0; ที่กูเกิn คือพจน์ที่ n ของลำดับที่ i เมื่อ k ¼ 2 ทั่วไปเพื่อ-k. ลำดับฟีโบนักชีจะลดลงไปตามลำดับฟีโบนักชีเดิมต่อไปนี้วิธีการที่ดำเนินการโดยคาลมาน [1], เมทริกซ์ akk ตารางสามารถกำหนดดังนี้¼ 111 1 1 100 0 0 010 0 0 ............... 000 0 0 000 1 0 2 6 6 6 6 6 6 4 3 7 7 7 7 7 7 5: แล้วโดยสถานที่ของการคูณเมทริกซ์เรามี½gi nþ1gi n กูเกิn kþ2? T ¼A½giงี้1 n กูเกิล? n kþ1? T: ð2Þเพื่อจัดการกับลำดับ k ของชุดคำสั่ง k Fibonacci ทั่วไปพร้อมกันเมทริกซ์ตารางakk Gn ที่กำหนดไว้ดังต่อไปนี้ [2]: Gn ¼ g1 n g2 n gk n g1 n? 1 g2 n? 1 g2 n? 1......... g1 n? kþ1 g2 n? kþ1 gk n? kþ1 2 6 6 6 4 3 7 7 7 5: generalizing สม (2) เรามีGnþ1¼ AGN ð3Þแล้วโดยเหตุผลอุปนัยหนึ่งอาจเขียนเป็นGnþ1¼ G1: ð4Þ 904 อี Karaduman / Appl คณิตศาสตร์ คอมพิวเต 147 (2004) 903-908 ตอนนี้ก็สามารถมองเห็นได้อย่างง่ายดายว่าด้วยความละเอียด (1), G1 ¼; จึง Gn ¼ ดังนั้น EQS (3) และ (4) อาจจะเขียนใหม่ที่แสดง: Gnþ1¼ GnG1 ¼ G1Gn ð5ÞหรือGnþ1¼Anþ1: ในคำอื่น ๆ G1 คือการเปลี่ยนแปลงภายใต้การคูณเมทริกซ์. ทฤษฎีบท 1. ถ้า Gn มีรูปแบบGn ¼ g1 n g2 n gk n g1 n? 1 g2 n? 1 gk n? 1......... g1 n? kþ1 g2 n? kþ1 gk n? kþ1 2 6 6 6 4 3 7 7 7 5 แล้วdet Gn ¼ ð 1th? n; ถ้า k แม้แต่1; ถ้า k เป็นเลขคี่?; ที่กูเกิn ¼ Pk j¼1กูเกิล? n ญสำหรับ n> 0 และ 1 6 6 k ผมมีเงื่อนไขขอบเขตกูเกิn ¼ 1; ฉัน¼ 1 n; 0; อย่างอื่น? 1? k n 6 6 0: หลักฐาน ตั้งแต่ 8k, G1 ¼¼ 111 1 1 100 0 0 010 0 0............... 000 0 0 000 1 0 2 6 6 6 6 6 6 4 3 7 7 7 7 7 7 5 หลังจาก DK? 1th ขั้นตอนการดำเนินงานแถวประถม G1 จะลดลงไปที่รูปสามเหลี่ยมรูปแบบเมทริกซ์ที่แสดง: 11 1 1 1? 0 1 1 1 1? 0 0 1 1 1?........... ... 00 0 1 1? 00 0 0 1 2 6 6 6 6 6 6 4 3 7 7 7 7 7 7 5: อี Karaduman / Appl คณิตศาสตร์ คอมพิวเต 147 (2004) 903-908 905 ดังนั้นเดชอุดม G1 ¼ det ¼ 1 D? 1th k 1 ในทางกลับกันตั้งแต่ Gn ¼เรามีเดชอุดมGn ¼ðdet Ath n เดชอุดม Gn ¼ DD 1th? k 1 Þ n: ð6Þดังนั้นถ้าk เป็นแม้กระทั่ง DK? 1th จะแปลก ดังนั้น D? 1th K? 1 ¼ 1 ดังนั้นจาก (6), เรามีเดชอุดม Gn ¼ D? 1th n ถ้า k เป็นเลขคี่, DK? 1th จะยิ่ง ดังนั้น D? 1th K? 1 ¼ที่ 1 และจึงมาจาก(6) เรามีเดชอุดม Gn ¼ 1. เราจะทำ ? ตอนนี้ถ้าเราไม่สนใจสภาพ n> 0 ในการนิยาม (1) เราสามารถกำหนด k ลำดับของตัวเลขการสั่งซื้อ k Fibonacci ทั่วไปที่แสดง: กูเกิn ¼ X k j¼1กูเกิn ญ? 1 6 6 k ฉันð7Þกับเงื่อนไขขอบเขตกูเกิn ¼ 1; ฉัน¼ 1 n; 0; อย่างอื่น? 1? k n 6 6 0; ที่กูเกิn คือพจน์ที่ n ของลำดับที่ i เมื่อ k ¼ 2 ทั่วไปเพื่อ-k ลำดับฟีโบนักชีจะลดลงไปตามลำดับฟีโบนักชีธรรมดากับข้อมูลเบื้องต้น g1 0 ¼ 1, g1 1 ¼ 1. เรากำหนดตารางการฝึกอบรม kk Gn, B และ C ดังนี้Gn ¼ g1 n g2 n gk n g1 1 n g2? 1 n gk? 1 n?......... g1 n kþ1 g2? n kþ1 gk? n kþ1? 2 6 6 6 4 3 7 7 7 5; B ¼ 20 21 22 2k 2 2k 1 20 20 21 2k 3 2k 2 0 20 20 2k 4 2k? 3......... .. ...... 000 .. . 21 20 000 20 20 2 6 6 6 6 6 6 6 4 3 7 7 7 7 7 7 7 5; C ¼ 000 0 1 100 0 1 010 0 1.... ...... ...... 000 .. 1 0 000 1 1 2 6 6 6 6 6 6 6 4 3 7 7 7 7 7 7 7 5: ตอนนี้ก็สามารถมองเห็นได้อย่างง่ายดายว่าโดยนิยาม (7), G1 ¼บีแล้วโดยอาร์กิวเมนต์อุปนัยเราเขียน906 อี Karaduman / Appl คณิตศาสตร์ คอมพิวเต 147 (2004) 903-908 Gnþ1¼ BCN: ð8Þ แต่ B ไม่ได้อยู่ภายใต้การสับเปลี่ยนคูณเมทริกซ์. ทฤษฎีบท 2. ถ้า Gn มีรูปแบบเป็นที่แสดง: Gn ¼ g1 n g2 n gk n g1? 1 n g2? 1 n gk ? 1 n......... g1? n kþ1 g2? n kþ1 gk? n kþ1 2 6 6 6 4 3 7 7 7 5 แล้วdet Gn ¼ 1; ถ้า k เป็นเลขคี่ð 1th? n; ถ้า k เป็นยัง?: หลักฐาน ตั้งแต่ Gn ¼ G1Cn 1 ¼ BCN 1 เรามี? เดชอุดม Gn ¼เดชอุดม G1 ðdet CTH 1 n?: ð9Þดังนั้นหลังจาก DK? 1th ขั้นตอนแถวประถมศึกษาการดำเนินงาน G1 จะลดลงไปที่รูปสามเหลี่ยมรูปแบบเมทริกซ์ที่แสดง:? 20 21 22 2k 2 2k 1?? 0 1 2 2k 3 2k 2? 0 0 1 2k 4 2k? 3............... 00 0 1 20 00 0 0 1 2 6 6 6 6 6 6 4 3 7 7 7 7 7 7 5 ดังนั้นเราจึงมี G1 เดชอุดม¼ 1 D? 1th k 1 พร้อมกันแทนแถวแรกของC กับแถวอื่น ๆ ของ C, C จะลดลงไปในรูปแบบเมทริกซ์สามเหลี่ยมเป็นที่แสดง: 100 0 1 010 0 1 001 0 1............... 000 1 1 000 0 1 2 6 6 6 6 6 6 4 3 7 7 7 7 7 7 5: ดังนั้นเรามีเดชอุดม C ¼ð 1th? k 1 ดังนั้นเราจึงมีเดชอุดม Gn ¼ D? 1th K? 1 DD? 1th k? 1 Þ n 1, จาก (9) ในทางตรงกันข้ามถ้า k เป็นได้แล้วเราได้ D? 1th k? 1 ¼ 1 และถ้า k เป็นคี่นั้นเราได้D? 1th k? 1 ¼ 1. ดังนั้นเราจึงมีอี Karaduman / Appl คณิตศาสตร์ คอมพิวเต 147 (2004) 903-908 907 เดชอุดม Gn ¼ 1; ถ้า k เป็นเลขคี่ð 1th? n; ถ้า k เป็นยัง?: เราจะทำ ? จาก EQS (1) และ (7) เราจะเห็นว่าสภาพ n> 0 ไม่เปลี่ยนแปลงปัจจัยของGn แต่ก็มีอัตราผลตอบแทนที่ G1 คือการเปลี่ยนแปลงภายใต้การคูณเมทริกซ์หรือไม่ คือถ้าเราไม่สนใจสภาพ n> 0 แล้ว G1 คือการเปลี่ยนแปลงภายใต้การคูณเมทริกซ์มิฉะนั้นจะไม่ได้. อ้างอิง[1] D. คาลมาน, ทั่วไปตัวเลข Fibonacci โดยวิธีเมทริกซ์ที่ Fibonacci ไตรมาส 20 (1) (1982) 73 -76. [2] MC เอ้อผลรวมของตัวเลข Fibonacci โดยวิธีเมทริกซ์ที่ Fibonacci ไตรมาส 22 (3) (1984) 204-207. [3] อี Karaduman, U. Yavuz บนลำดับฟีโบนักชีในช่วงกลุ่ม nilpotent ประยุกต์คณิตศาสตร์และการคำนวณ(AMC 7453), ในการกด. [4] Karaduman อีเอช aydn ทั่วไป 2 ขั้นตอนลำดับฟีโบนักชีในกลุ่ม nilpotent ตัวแทนของพีและnilpotency ชั้น 4, คณิตศาสตร์ประยุกต์และการคำนวณ (บบส. 7418) ในการกด. [5] aydn เอชอาร์ Dikici ลำดับฟีโบนักชีในกลุ่มแน่นอนที่ Fibonacci ไตรมาส 36 (3) (1998) 216-221. [6] GY ลีฟีโบนักชีตัวเลข k-ลูคัสและฝ่ายที่เกี่ยวข้องกราฟ พีชคณิตเชิงเส้นและของแอปพลิเค320 (2000) 51-61. [7] D. ทากาฮาชิอัลกอริทึมที่รวดเร็วสำหรับการคำนวณตัวเลข Fibonacci ขนาดใหญ่ข้อมูลตัวอักษรประมวลผล75 (2000) 243-246. [8] เจเวสต์ต้นไม้สร้าง และ subsequences ต้องห้ามคณิตศาสตร์ไม่ต่อเนื่อง 157 (1996) 363-374. 908 อี Karaduman / Appl คณิตศาสตร์ คอมพิวเต 147 (2004) 903-908

ผลลัพธ์ (ไทย) 3:

ใบสมัครของตัวเลข Fibonacci ในเมทริกซ์

erdal karaduman
เฟิน edebiyat ฟากด้าน ultesi คณิตศาสตร์ B วิวด้านคือด้าน ol U ก็จ่าย urk มหาวิทยาลัย 25240 Erzurum , ตุรกี

บทคัดย่องานวิจัยนี้ศึกษาปัจจัยของเมตริกซ์ได้โดยลำดับของตัว K


2002 order-k ลำดับเลข Elsevier Inc . All Rights Reserved .
คำสำคัญ : เลขฟีโบนัชชี ;แบบทั่วไป order-k ลำดับเลข ลำดับ Fibonacci ;
เมทริกซ์ ดีเทอร์มิแนนต์
ในปีที่ผ่านมา , ได้มีความสนใจมากในการใช้ Fibonacci
ตัวเลขและลำดับ karaduman ยาวุส และพิสูจน์ได้ว่า ระยะเวลาของขั้นตอนที่ 2 เกิดขึ้นในกลุ่ม
Fibonacci องคตวิธีคลาส nilpotency 5 P
ของ PK ð P Þ , 2 < p 2927 6 ,ที่ p คือนายกรัฐมนตรีและ K ð P Þเป็นคาบ
ธรรมดา 2 ขั้นตอนลำดับ Fibonacci [ 3 ] ทฤษฎีที่ได้รับการทั่วไป
ใน [ 4 ] ถึง 2 ขั้นตอนทั่วไป Fibonacci ลำดับในกลุ่มองคตวิธี
nilpotency ระดับ 4 และเลขหน้านอกจากนี้ยังแสดงใน [ 5 ] ที่ระยะเวลา 2 -
ขั้นตอนทั่วไป Fibonacci ลำดับเท่ากับความยาวของระยะเวลา
พื้นฐานส่วนขั้นตอนที่ 2 การสร้างโดยทั่วไปสองสร้างองค์ประกอบของกลุ่มผู้สนับสนุน
p และ nilpotency คลาส 2 เคย์เลย์ได้ถูกใช้สำหรับการคำนวณ
[ 5 ] .
ลี ได้ศึกษาความสัมพันธ์ระหว่าง G ð K Þ
n ตัวเลข Fibonacci และ
L ð K Þ
n ลูคัสตัวเลข [ 6 ] ทาคาฮาชิให้ขั้นตอนวิธีการอย่างรวดเร็วซึ่งจะขึ้นอยู่กับ
ผลิตภัณฑ์ของลูคัสตัวเลข คำนวณตัวเลขขนาดใหญ่ของ Fibonacci [ 7 ] ฟีโบนัชชี
ลำดับได้เป็นหัวข้อที่น่าสนใจในคณิตศาสตร์ประยุกต์ เวสต์
อีเมล์ : [e-mail] ( เช่น karaduman )
0096-3003 / $ - ดูเรื่องหน้า
2002 Elsevier Inc . All Rights Reserved .
ดอย : 10.1016 / s0096-3003 ( 02 ) 00827-5
คณิตศาสตร์ประยุกต์และการคำนวณ 147 ( 2004 ) ส่วน– 908
www.elsevier . com / ค้นหา / AMC
แสดงการโอนคืนว่า หมายเลข jsn ð 123 ; 1 J
Þของพีชคณิตหลีกเลี่ยงรูปแบบและ 1 เป็นจำนวนฟีโบนัชชี f2n [ 8 ] .
คาลมาน [ 1 ] มาหลายสูตร ปิดแบบฟอร์มสำหรับทั่วไป
Fibonacci ลำดับโดยวิธีเมทริกซ์ ใน [ 2 ] er ได้ขยายเมทริกซ์
แทน พบว่าผลรวมของตัวเลข Fibonacci
ทั่วไปอาจจะได้โดยตรงโดยใช้
แทนนี้กำหนดลำดับของตัว K order-k ตัวเลข Fibonacci ที่แสดง :

n กี¼ x
k
J

n ¼ 1 กิ
J ; n > 0 และ 1 6 ชั้น 6 K ; ð 1 Þ
กับเงื่อนไขขอบ
กี
n ¼ 1 ; ฉัน¼ 1
N ;
0 ไม่เช่นนั้น

1
K 6 6 0 n ;
ที่กี
n คืออื่น ๆของ อ. ลําดับ เมื่อ k ¼ 2 ตัว order-k
Fibonacci ลำดับลดลง Fibonacci ลำดับปกติ ตามวิธีการถ่ายโดยคาลมาน
[ 1 ]เมทริกซ์จัตุรัส A K K สามารถ

มีดังนี้ : ¼
111 1 1 0 0

100 010 0 0
.
.
.
.
.
.
.
.
.
.
.
0
000 000 0 1 0
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
:
แล้ว โดยคุณสมบัติของการคูณเมตริกซ์ เราได้

n ½ กี þ 1gi
n
n กี
K þ 2 
t ¼½กิ

n เป็นแคะ
1 กี
n
K þ 1 
T
: ð 2 Þ
เพื่อจัดการกับ K ลำดับของตัว order-k Fibonacci ชุด
พร้อมกันK K เมทริกซ์จัตุรัส GN เป็นดังนี้ [ 2 ] :


n GN ¼ G1 G2
n
n
G1
n GK
1 G2
n
1 G2
n
1
.
.
.
.
.
.
.
G1
n
K þ 1 G2
n
K þ 1 GK
n
K þ 1
2
6
6
6
4
3
7
7
7
5
Generalizing อีคิว ( 2 ) เรามี
GN þ 1 ¼ AGN ð 3 Þ
แล้ว โดยมีปากเสียงอุปนัย , หนึ่งอาจเขียนเป็น GN þ 1 ¼เป็น

:
4 G1 ðÞ 904 . karaduman / แอปเปิ้ล คณิตศาสตร์ คอมพิวเตอร์ . 147 ( 2004 ) ส่วน– 908
ตอนนี้ก็สามารถพร้อมเห็นว่าโดยความหมาย ( 1 ) G1 ¼ ;