Nombor Fibonacci

Daripada Wikipedia, ensiklopedia bebas.
(Dilencongkan dari Bilangan Fibonacci)
Jump to navigation Jump to search
Catatan: Penggunaan templat ini adalah tidak digalakkan.
Suatu ubinan dengan segi empat yang tepinya adalah nombor Fibonaci berturut-turut pada panjangnya
Sebuah yupana (Quechua untuk "alat pengiraan") adalah sebuah kalkulator yang digunakan oleh Incas. Pengaji menganggapkan bahawa pengiraan adalah berasaskan nombor Fibonacci untuk mengurangkan bilangan biji yang diperlukan tiap sawah.[1]
Sebuah Lingkaran Fibonacci dicipta dengan melukis lengkung menyambungkan sudut berlawan segi empat dalam ubinan Fibonacci; yang ini menggunakan segi empat-segi empat pada saiz 1, 1, 2, 3, 5, 8, 13, 21 dan 34; see Golden spiral

Dalam matematik, nombor Fibonacci adalah suatu langkah nombor dinamakan sempena Leonardo of Pisa, digelar sebagai Fibonacci. Buku 1202 Liber Abaci Fibonacci memperkenalkan urutannya ke matematik Eropah Barat, walaupun urutannya telah terdahulu dijelaskan pada matematik India.[2][3]

Nombor urutan pertama adalah 0, nombor kedua adalah 1, dan setiap nombor seterusnya bersamaan dengan jumlah dua nombor yang terdahulu pada urutannya sendiri. Dalam istilah matematik, ia ditakrifkan dengan hubungan jadi semula yang berikut:

Iaitu, selepas dua nilai bermula, setiap nombor adalah jumlah dua nombor yang terdahulu. Nombor Fibonacci pertama (jujukan A000045 dalam OEIS), juga ditandakan sebagai Fn, untuk n = 0, 1, 2, … ,20 adalah:[4][5]

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Setiap nombor ke-3 urutan adalah sama rata dan lebih umumnya, setiap nombor ke-k pada urutan adalah suatu perdaraban Fk.

Urutannya lanjut ke indeks negatif n memuaskan Fn = Fn−1 + Fn−2 untuk semua integer n, dan F−n = (−1)n+1Fn:

.., −8, 5, −3, 2, −1, 1, diikuti oleh urutan di atas.

Asal Usul[sunting | sunting sumber]

Nombor Fibonacci pertama kali muncul, di bawah nama mātrāmeru (gunung irama), dalam karya ahli tatabahasa Pingala (Chandah-shāstra, Seni Prosodi, 450 or 200 BC). Prosody adalah penting dalam upacara India silam oleh kerana suatu emfasis pada keaslian utterance. Ahli matematik Indian matematik Virahanka (abad ke-6 M) menunjukkan urutan Fibonacci berpunca pada analisis meter dengan silabel panjang dan pendek. Berikutnya itu, ahli falsafah Jain Hemachandra (sekitar 1150) mendirikan suatu teks diketahui benar pada ini. Suatu komen pada karya Virahanka oleh Gopāla pada abad ke-12 juga melawat semula masalah itu dalam sesetengah perincian.

Bunyi vokal Sanskrit boleh menjadi panjang (L) atau pendek (S), dan analisis Virahanka, yang kemudian dikenali sebagai mātrā-vṛtta, ingin mengira berapa meter (mātrā) bagi panjang keseluruhan yang boleh terdiri daripada silabel ini. Jika silabel panjang adalah dua kali lebih panjang berbanding yang pendek, penyelesaian ialah:

1 mora: S (1 corak)
2 morae: SS; L (2)
3 morae: SSS, SL; LS (3)
4 morae: SSSS, SSL, SLS; LSS, LL (5)
5 morae: SSSSS, SSSL, SSLS, SLSS, SLL; LSSS, LSL, LLS (8)
6 morae: SSSSSS, SSSSL, SSSLS, SSLSS, SLSSS, LSSSS, SSLL, SLSL, SLLS, LSSL, LSLS, LLSS, LLL (13)
7 morae: SSSSSSS, SSSSSL, SSSSLS, SSSLSS, SSLSSS, SLSSSS, LSSSSS, SSSLL, SSLSL, SLSSL, LSSSL, SSLLS, SLSLS, LSSLS, SLLSS, LSLSS, LLSSS, SLLL, LSLL, LLSL, LLLS (21)

Satu corak panjang n boleh dibentuk dengan menambah S kepada corak panjang n − 1, atau L kepada corak panjang n − 2; dan pakar prosodi menunjukkan bahawa bilangan corak panjang n adalah jumlah dua nombor sebelumnya dalam urutan. Donald Knuth menyemak kerja ini dalam Art of Computer Programming sebagai rumusan bersamaan masalah bin packing item dengan panjang 1 dan 2.

Di Barat, urutan itu mula-mula dikaji oleh Leonardo dari Pisa, dikenali sebagai Fibonacci, di dalam bukunya Liber Abaci (1202)[6]. Dia menganggap pertumbuhan unggul populasi arnab (secara biologinya tidak realistik), dengan anggapan bahawa:

  • Dalam bulan "sifar", ada sepasang arnab (pasangan tambahan arnab = 0)
  • Dalam bulan pertama, pasangan pertama beranak sepasang lagi (pasangan tambahan arnab = 1)
  • Dalam bulan kedua, kedua-dua pasang arnab mempunyai sepasang lagi, dan pasangan yang pertama mati (pasangan tambahan arnab = 1)
  • Dalam bulan ketiga, pasangan kedua dan kedua-dua pasangan baru mempunyai sejumlah tiga pasangan baru, dan pasangan kedua tua mati. (pasangan tambahan arnab = 2)

Hukum ini adalah bahawa setiap pasangan arnab mempunyai 2 pasang dalam hidupnya, dan mati.

Biarkan populasi pada bulan n menjadi F(n). Pada masa ini, hanya arnab yang masih hidup pada bulan n − 2 adalah subur dan melahirkan anak, jadi F(n − 2) pasangan ditambah kepada populasi semasa F(n − 1). Oleh itu, jumlah F(n) = F(n − 1) + F(n − 2).[7]

Kaitannya dengan Nisbah Emas[sunting | sunting sumber]

Closed form expression[sunting | sunting sumber]

Like setiap sequence defined by linear recurrence, nombor Fibonacci mempunyaia closed-form solution. It has become known as Binet's formula, even though it was already known by Abraham de Moivre:

where is nisbah keemasan
(jujukan A001622 dalam OEIS)

(note, that , as can be seen from defining equation below).

Fibonacci recursion

is similar to defining equation of nisbah keemasan dalam form

which is also known as polinomial penjana of recursion.

Proof by induction[sunting | sunting sumber]

Any root of equation above satisfies and multiplying by shows:

By definition is a root of equation dan other root is . Therefore:

and

Kedua-dua and are geometric series (for n = 1, 2, 3, ...) that satisfy Fibonacci recursion. first series grows exponentially; second exponentially tends to zero, with alternating signs. Because Fibonacci recursion is linear, any linear combination of these two series will also satisfy recursion. These linear combinations form a two-dimensional linear vector space; original Jujukan Fibonacci can be found in this space.

Linear combinations of series and , with coefficients a and b, can be defined by

untuk sebarang real

All thus-defined series satisfy Fibonacci recursion

Requiring that and yields and , resulting dalam formula of Binet we started with. It has been shown that this formula satisfies Fibonacci recursion. Furthermore, an explicit check can be made:

and

establishing base cases of induction, proving that

for all

Therefore, untuk sebarang two starting values, a combination can be found such that function is exact closed formula for series.

Pengiraan melalui pembundaran[sunting | sunting sumber]

Memandangkan bagi semua , nombor adalah integer yang paling hampir dengan Oleh itu, ia boleh didapati dengan pembundaran, atau dari segi fungsi lantai:

Limit of consecutive quotients[sunting | sunting sumber]

Johannes Kepler memerhatikan bahawa nisbah consecutive nombor Fibonacci converges. He wrote that "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost”, and concluded that limit approaches nisbah keemasan .[8]

This convergence does not depend on starting values chosen, excluding 0, 0.

Proof:

It follows from explicit formula that untuk sebarang real

because and thus

Decomposition of powers of nisbah keemasan[sunting | sunting sumber]

Since nisbah keemasan satisfies equation

this expression can be used to decompose higher powers as a linear function of lower powers, which in turn can be decomposed all way down to a linear combination of and 1. resulting recurrence hubungan yield nombor Fibonacci as linear coefficients, thus closing loop:

This expression is also benar for if jujukan Fibonacci is extended to negative integers using Fibonacci rule

Bentuk matriks[sunting | sunting sumber]

A 2-dimensional system of linear difference equations that describes Jujukan Fibonacci is

or

eigenvalues of matriks A are and , and elements of eigenvectors of A, and , are dalam nisbah-nisbah and

matriks ini mempunyai determinant of −1, and thus it is a 2×2 unimodular matriks. This property can be understood in terms of pecahan berterusan representation for nisbah keemasan:

Nombor Fibonacci occur as nisbah pertembungan pecahan berterusan yang berterusan , dan matriks yang dibentuk daripada from successive convergents of any pecahan berterusan mempunyai determinant of +1 or −1.

Perwakilan matriks memberikan ungkapan tertutup nombor Fibonacci yang berikut:

Taking determinant of kedua-dua belah persamaan ini menyerlahkan identiti Cassini

Additionally, since untuk sebarang square matriks , following identities can be derived:

Untuk first one of these, there is a related identity:

Untukanother way to derive formulas see "EWD note" by Dijkstra[9].

Mengenalpasti nombor Fibonacci[sunting | sunting sumber]

question may arise sama ada sesuatu integer positif is a nombor Fibonacci. Since is closest integer to , most straightforward, brute-force test is identity

which is benar jika dan hanya sekiranya merupakan nombor Fibonacci.

Alternatively, a integer positif ialah nombor Fibonacci sekiranya dan hanya sekiranya salah satu or merupakan segi empat yang sempurna.[10]

A slightly more sophisticated test uses fact that convergents perwakilan pecahan berterusan ialah nisbah-nisbah nombor Fibonacci yang berturutan, that is inequality

(with coprime integer positif , ) is benar if and only if and are successive nombor Fibonacci. From this one derives criterion that is a nombor Fibonacci if and only if closed interval

contains a integer positif.[11]

Pengenalan[sunting | sunting sumber]

Kebanyakan pengenalan melibatkan nombor Fibonacci menarik dari hujah kombinatorik. F(n) boleh ditafsirkan sebagai bilangan cara menjumlahkan 1 dan 2 kepada n − 1, dengan kelaziman yang F(0) = 0, bermakna tiada jumlah akan menambah sehingga −1, dan F(1) = 1, bermaksud jumlah kosong akan "bertambah" untuk 0. Ini tertiba bagi perihal penghasil tambah. Sebagai contoh, 1 + 2 and 2 + 1 adalah dianggap dua jumlah yang berbeza dan dikira dua kali.

Pengenalan Pertama[sunting | sunting sumber]

Nombor Fibonacci ke-n adalah jumlah dua nombor Fibonacci sebelumnya.

Pembuktian[sunting | sunting sumber]

Kita mesti membuktikan bahawa urutan nombor yang ditakrifkan oleh tafsiran kombinatorik di atas memenuhi hubungan jadi semula yang sama dengan nombor Fibonacci (dan jadi sememangnya sama dengan nombor Fibonacci).

Set bagi cara F(n+1) untuk membuat jumlah bertertib 1 dan 2 yang berjumlah ke n boleh dibahagikan kepada dua set tak bertindih. Set pertama yang mengandungi jumlah penghasil tambah pertamanya 1; jumlah baki kepada n−1, maka F(n) menjumlah pada set pertama. Set kedua yang mengandungi jumlah penghasil tambah pertamanya 2; jumlah baki kepada n−2, maka F(n−1) menjumlah pada set kedua. Penghasil tambah pertama hanya boleh jadi 1 atau 2, supaya kedua-dua set menghabiskan set asal. Maka F(n+1) = F(n) + F(n−1).

Pengenalan Kedua[sunting | sunting sumber]

Jumlah bagi n pertama nombor Fibonacci adalah nombor Fibonacci ke-(n+2) tolak 1.

Pembuktian[sunting | sunting sumber]

Kami mengira bilangan cara menjumlahkan 1 dan 2 sehingga n + 1 supaya sekurang-kurangnya salah satu daripada penghasil tambah adalah 2.

Seperti sebelum ini, terdapat F(n + 2) cara menjumlahkan 1 dan 2 menjadi n + 1 apabila n ≥ 0. Oleh kerana hanya ada satu jumlah n + 1 yang tidak menggunakan 2, iaitu 1 + … + 1 (syarat n + 1),kita tolak 1 dari F(n + 2).

Setara, kita boleh mempertimbangkan sebutan pertama bagi 2 sebagai penghasil tambah. Jika, dalam jumlah, penghasil tambah yang pertama adalah 2, maka ada F(n) cara untuk melengkapkan pengiraan bagi n − 1. Jika penghasil tambah yang kedua ialah 2 tetapi yang pertama adalah 1, maka terdapat F(n − 1) cara untuk melengkapkan pengiraan bagi n − 2. Teruskan dengan cara ini. Kemudiannya kita mempertimbangkan penghasil tambah ke-(n + 1). Jika ia adalah 2 tetapi semua penghasil tambahn sebelumnya adalah 1, maka terdapat F(0) cara untuk melengkapkan pengiraan bagi 0. Jika suatu jumlah mengandungi 2 sebagai penghasil tambah, sebutan pertama bagi penghasil tambah itu mesti berlaku di antara posisi yang pertama dan yang ke-(n + 1). Maka F(n) + F(n − 1) + … + F(0) memberikan pengiraan yang dikehendaki.

Pengenalan Ketiga[sunting | sunting sumber]

Identiti ini mempunyai bentuk yang sedikit berbeza untuk , bergantung kepada sama ada k adalah ganjil atau genap.

[12]

Jumlah bagi nombor Fibonacci n-1 pertama, , supaya j ganjil adalah nombor Fibonacci ke-(2n).
Jumlah bagi nombor Fibonacci n pertama, , supaya j genap adalah nombor Fibonacci ke-(2n+1) tolak 1.

Pembuktian[sunting | sunting sumber]

Aruhan bagi :

Kes asas ini untuk boleh menjadi .
Aruhan bagi :

Kes asas ini untuk boleh menjadi .

Pengenalan Keempat[sunting | sunting sumber]

Pembuktian[sunting | sunting sumber]

Pengenalan ini boleh ditentukan dalam dua peringkat. Pertama, kita mengira bilangan cara menjumlahkan 1 dan 2 menjadi −1, 0, …, atau n + 1 supaya sekurang-kurangnya salah satu daripada penghasil tambah adalah 2.

Dengan pengenalan kedua kita, terdapat F(n + 2) − 1 cara menjumlahkan kepada n + 1; F(n + 1) − 1 cara menjumlahkan kepada n; …; dan, akhirnya, F(2) − 1 cara menjumlahkan kepada 1. Apabila F(1) − 1 = F(0) = 0, kita boleh menambah semua jumlah n + 1 dan menggunakan pengenalan kedua lagi untuk mendapatkan:    [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1]

= [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1] + [F(1) − 1] + F(0)
= F(n + 2) + [F(n + 1) + … + F(1) + F(0)] − (n + 2)
= F(n + 2) + [F(n + 3) − 1] − (n + 2)
= F(n + 2) + F(n + 3) − (n + 3).

Sebaliknya, kita dapati daripada pengenalan kedua bahawa terdapat

  • F(0) + F(1) + … + F(n − 1) + F(n) ways summing to n + 1;
  • F(0) + F(1) + … + F(n − 1) cara menjumlahkan kepada n;

……

  • F(0) cara menjumlahkan kepada −1.

Menambahkan semua jumlah n + 1, kita dapat melihat bahawa terdapat

  • (n + 1) F(0) + n F(1) + … + F(n) cara menjumlahkan kepada −1, 0, …, or n + 1.

Memandangkan kedua-dua kaedah pengiraan merujuk kepada nombor yang sama, kita dapat

(n + 1) F(0) + n F(1) + … + F(n) = F(n + 2) + F(n + 3) − (n + 3)

Akhir sekali, kita melengkapkan bukti dengan membuat tolakan pengenalan di atas daripada n + 1 kali pengenalan kedua.

Pengenalan Kelima[sunting | sunting sumber]

Jumlah bagi nombor Fibonacci n yang pertama dikuasa dua adalah hasil darab nombor Fibonacci ke-n dan ke-(n+1).

Pengenalan bagi n berganda[sunting | sunting sumber]

[13]

Another Identity[sunting | sunting sumber]

Another identity useful untuk mengira Fn memperoleh nilai besar n ialah

[13]

from which other identities for specific values of k, n, and c can be derived below, including

for all integers n and k. Dijkstra[9] points out that doubling identities of this type can be used to calculate Fn using O(log n) arithmetic operations. Notice that, with definition of nombor Fibonacci with negative n given dalam introduction, this formula reduces to double n formula apabila k = 0.

(From practical standpoint it should be noticed that calculation involves manipulation of numbers with length (number of digits) . Thus actual performance depends mainly upon efficiency of implemented long multiplication, and usually is or .)

Other identities[sunting | sunting sumber]

Other identities termasuk hubungan kepada nombor Lucas yang mempunyai same recursive properties but start with L0=2 and L1=1. These properties termasuk F2n=FnLn.

There are also scaling identities, which take you from Fn and Fn+1 to a variety of things of form Fan+b; sebagai contoh

oleh identiti Cassini.

These can be found experimentally using lattice pengurangan, and are useful in setting up special number field sieve to factorize a nombor Fibonacci. Such relations exist in a very general sense for numbers defined by recurrence relations, see section on multiplication formulae under Perrin numbers for details.

Siri kuasa[sunting | sunting sumber]

Fungsi generasi urutan Fibonacci adalah siri kuasa

Siri ini adalah mudah dan jawapan bentuk-tertutup menarik untuk

Jawapan ini dapat dibukti dengan menggunakan kemunculan semula Fibonacci untuk melebarkan setiap koefisi dalam jumlah infinite mentakrifkan :

Menyelesaikan persamaan for menyebabkan jawapan bentuk tertutup.

Terutamanya, buku teka-teki matematik menyatakan nilai aneh, atau lebih biasanya

untuk semua integer .

Secara bicara,

Jumlah salingan[sunting | sunting sumber]

Jumlah tidak terhingga ke atas nombor Fibonacci salingan kadang-kadang boleh dinilai dari segi fungsi theta. Sebagai contoh, kita boleh menulis jumlah setiap nombor Fibonacci salingan indeks ganjil sebagai

dan jumlah kuasa dua nombor Fibonacci salingan

Jika kita menambah 1 untuk setiap nombor Fibonacci dalam jumlah yang pertama, terdapat juga bentuk tertutup

dan ada jumlah tersarang bagi kuasa dua nombor Fibonacci lalu memberi salingan nisbah emas,

Keputusan seperti ini menjadikannya munasabah bahawa rumus tertutup untuk jumlah mendatar bagi nombor Fibonacci salingan boleh didapati, tetapi tiada yang masih diketahui. Walaupun begitu, pemalar Fibonacci salingan

telah dibuktikan tidak bernisbah oleh Richard André-Jeannin.

Nombor perdana dan kebolehbahagian[sunting | sunting sumber]

Rencana utama: Fibonacci perdana

Fibonacci perdana adalah nombor Fibonacci yang perdana (jujukan A005478 dalam OEIS). first few are:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, …

Fibonacci perdana dengan beribu-ribu digit telah ditemui, tetapi tidak diketahui sama ada ia terdapat banyak tak terhingga. Semuanya mesti mempunyai indeks utama, kecuali F4 = 3. Terdapat aturan yang sewenang-wenangnya panjang bagi nombor komposit dan dengan itu termasuk juga nombor Fibonacci komposit.

Dengan pengecualian 1, 8 dan 144 (F0 = F1, F6 dan F12) setiap nombor Fibonacci mempunyai faktor utama yang bukan faktor mana-mana nombor Fibonacci yang lebih kecil (teorem Carmichael).[14]

Tiada nombor Fibonacci lebih besar daripada F6 = 8 yang lebih besar atau kurang satu daripada nombor perdana.[15]

Sebarang tiga nombor Fibonacci berturut-turut, yang diambil dua pada satu masa, adalah secara relatifnya perdana: itu adalah,

fstb(Fn, Fn+1) = fstb(Fn, Fn+2) = 1.

Lebih umum,

fstb(Fn, Fm) = Ffstb(n, m).[16][17]

Pembahagi ganjil[sunting | sunting sumber]

Jika n adalah ganjil, semua pembahagi ganjil Fn adalah ≡ 1 (mod 4).[18][19]
Ini adalah bersamaan dengan mengatakan bahawa untuk n ganjil semua faktor perdana ganjil Fn adalah ≡ 1 (mod 4).

Contohnya,

F1 = 1, F3 = 2, F5 = 5, F7 = 13, F9 = 34 = 2×17, F11 = 89, F13 = 233, F15 = 610 = 2×5×61

Fibonacci dan Legendre[sunting | sunting sumber]

Terdapat beberapa rumus yang menarik menghubungkan nombor Fibonacci dan simbol Legendre

Jika p ialah nombor perdana, maka[20][21]

Sebagai contoh,

Juga, jika p ≠ 5 adalah nombor perdana ganjil, maka: [22]

Contoh bagi semua kes:

Kebolehbahagian dengan 11[sunting | sunting sumber]

Sebagai contoh, jadi n = 1:


F1+F2+...+F10 = 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143 = 11×13
n = 2:
F2+F3+...+F11 = 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 = 231 = 11×21
n = 3:
F3+F4+...+F12 = 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 + 144= 374 = 11×34

Malah, identitinya adalah benar bagi semua integer n, bukan hanya yang positif:

n = 0:


F0+F1+...+F9 = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88 = 11×8
n = −1:


F−1+F0+...+F8 = 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 = 55 = 11×5
n = −2:


F−2+F−1+F0+...+F7 = −1 + 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33 = 11×3

Segi tiga bersudut tegak[sunting | sunting sumber]

Starting with 5, setiap second nombor Fibonacci is length of hypotenuse of a right segi tiga with integer sides, or in other words, nombor terbesar dalam ganda tiga Pythagoras. length of longer leg of this segi tiga is equal to sum of three sides of preceding segi tiga in this series of segi tigas, and shorter leg is equal to difference between preceding bypassed nombor Fibonacci and shorter leg of preceding segi tiga.

first segi tiga in this series has sides of length 5, 4, and 3. Skipping 8, next segi tiga has sides of length 13, 12 (5 + 4 + 3), and 5 (8 − 3). Skipping 21, next segi tiga has sides of length 34, 30 (13 + 12 + 5), and 16 (21 − 5). This series continues indefinitely. segi tiga sides a, b, c can be calculated directly:

These formulas satisfy for all n, but they only represent segi tiga sides apabila .

Any four consecutive nombor Fibonacci Fn, Fn+1, Fn+2 and Fn+3 can also be used to generate a Pythagorean triple in a different way:

Contoh 1: let nombor Fibonacci be 1, 2, 3 and 5. Then:

Contoh 2: let nombor Fibonacci be 8, 13, 21 and 34. Then:

Magnitud nombor Fibonacci[sunting | sunting sumber]

Memandangkan adalah berasimptot kepada , bilangan digit dalam asas perwakilan b adalah berasimptot kepada .

Dalam asas 10, untuk setiap integer yang lebih besar daripada 1 terdapat 4 atau 5 nombor Fibonacci dengan bilangan digit itu, dalam kebanyakan kes 5.

Aplikasi[sunting | sunting sumber]

Nombor Fibonacci are important dalam run-time analysis of algoritma Euclid to determine greatest common divisor of two integers: worst case input for this algoritma is a pair of consecutive nombor Fibonacci.

Yuri Matiyasevich dapat menunjukkan bahawa nombor Fibonacci boleh ditakrifkan daripada persamaan Diophantine, which led to his original solution of Hilbert's tenth problem.

Nombor Fibonacci occur dalam sums of "shallow" diagonals in segi tiga Pascal dan segi tiga Lozanić (see "Binomial coefficient"). (They occur more obviously in segi tiga Hosoya).

Setiap integer positif boleh ditulis dalam cara khusus sebagai hasil pertambahan lebih dari satu nombor Fibonacci yang tersendiri di mana hasil pertambahan tersebut tidak termasuk sebarang daripada dua nombor Fibonacci yang berturutan. This is known as Zeckendorf's theorem, and a sum of nombor Fibonacci that satisfies these conditions is called a Zeckendorf representation.

Prinsip dan nombor Fibonacci juga digunakan dalam pasaran perniagaan di mana ia digunakan dalam algoritma, aplikasi dan strategi perdagangan. Some typical forms termasuk: Fibonacci fan, Fibonacci Arc, Fibonacci Retracement and Fibonacci Time Extension.

Nombor Fibonacci digunakan by some pseudorandom number generators.

Nombor Fibonacci digunakan in a polyphase version of merge sort algoritma in which an unsorted list is divided into two lists whose lengths correspond to sequential nombor Fibonacci - by dividing list so that two parts mempunyailengths dalam approximate proportion φ. A tape-drive implementation of polyphase merge sort was described dalam Art of Computer Programming.

nombor Fibonacci arise dalam analysis of Fibonacci heap data structure.

A one-dimensional optimization method, called Fibonacci search technique, uses nombor Fibonacci.[23]

Siri nombor Fibonacci series is used for optional lossy compression dalam IFF 8SVX audio file format used on Amiga computers. number series compands original audio wave similar to logarithmic methods e.g. hukum µ.[24][25]

In muzik, nombor Fibonacci kadangkalanya digunakan to determine tunings, and, as in visual art, to determine length or size of content or formal elements. It is commonly thought that first movement of Béla Bartók's Music for Strings, Percussion, and Celesta was structured using nombor Fibonacci.

Memandangkan faktor pertukaran unit batu kepada kilometer iaitu 1.609344 hampir dengan nisbah keemasan (denoted φ), decomposition of distance in miles into a sum of nombor Fibonacci becomes nearly kilometer sum apabila nombor Fibonacci are replaced by their successors. This method amounts to a radix 2 number register in asas nisbah keemasan φ being shifted. To convert from kilometers to miles, shift register down jujukan Fibonacci instead.[26][27][28]

Nombor Fibonacci dalam persekitaran[sunting | sunting sumber]

Sunflower head displaying florets in lingkaran of 34 and 55 around outside

Jujukan Fibonacci muncul dalam persekitaran biologi,[29] in two consecutive nombor Fibonacci, such as branching in trees, arrangement of leaves on a stem, fruitlets of a pineapple,[30] flowering of artichoke, an uncurling fern and arrangement of a pine cone.[31] In addition, numerous poorly substantiated claims of nombor Fibonacci or golden sections in nature are found in popular sources, e.g. relating to breeding of rabbits, lingkaran cengkerang, dan curve of waves[perlu rujukan]. Nombor Fibonacci juga didapati dalam family tree of honeybees. [32]

Przemyslaw Prusinkiewicz advanced idea that real instances can be in part understood as expression of certain algebraic constraints on free groups, specifically as certain Lindenmayer grammars.[33]

Suatu model corak floret dalam kepala bunga matahari diusulkan H. Vogel pada tahun 1979.[34] Model ini mempunyai bentuk:

,

where n is index number of floret and c is a constant scaling factor; florets thus lie on Fermat's spiral. divergence angle, approximately 137.51°, is golden angle, dividing circle dalam nisbah keemasan. Because this ratio is irrational, no floret mempunyai neighbor at exactly same angle from center, so florets pack efficiently. Because rational approximations to nisbah keemasan are of form F(j):F(j+1), nearest neighbors of floret number n are those at n±F(j) for some index j which depends on r, distance from center. It is often said that sunflowers and similar arrangements mempunyai 55 lingkaran dalam satu arah dan 89 dalam satu arah yang lain (or some other pair of adjacent nombor Fibonacci), but this is benar only of one range of radii, typically outermost and thus most conspicuous.[35]

  • Pada 1991, Jean-Claude Perez mengusulkan hubungan natara urutan bes DNA dalam susunan gen dengan nombor Fibonacci [36].

Konsep[sunting | sunting sumber]

Fibonacci sequence has been generalized in many ways. These termasuk:

  • Generalizing index to negative integers to produce Neganombor Fibonacci.
  • Generalizing index to real numbers using a modification of Binet's formula. [37]
  • Starting with other integers. nombor Lucas have L1 = 1, L2 = 3, and Ln = Ln−1 + Ln−2. jujukan Primefree menggunakan Fibonacci recursion with other starting points in order to generate sequences in which all numbers are composite.
  • Letting a number be a linear function (other than sum) of 2 preceding numbers. Nomber Pell mempunyai Pn = 2Pn – 1 + Pn – 2.
  • Not adding immediately preceding numbers. Padovan sequence and nombor Perrin mempunyai P(n) = P(n – 2) + P(n – 3).
  • Generating next number by adding 3 numbers (tribonacci numbers), 4 numbers (tetranacci numbers), or more.
  • Adding other objects than integers, misalnya functions or strings -- one essential example is polinomial Fibonacci.

Numbers properties[sunting | sunting sumber]

Periodicity mod n: Pisano periods[sunting | sunting sumber]

It is easily seen that if members of jujukan Fibonacci are taken mod n, resulting sequence must be periodic with period at most . lengths of periods for various n form so-called Pisano periods (jujukan A001175 dalam OEIS). Determining Pisano periods in general is an open problem,[perlu rujukan] although untuk sebarang particular n it can be solved as an instance of cycle detection.

bee ancestry code[sunting | sunting sumber]

nombor Fibonacci also appear dalam description of reproduction of a population of idealized bees, according to following rules:

  • If an egg is laid by an unmated female, it hatches a male.
  • If, however, an egg was fertilized by a male, it hatches a female.

Thus, a male bee will always have one parent manakala a female bee will have two.

If one traces ancestry of any male bee (1 bee), he has 1 female parent (1 bee). This female had 2 parents, a male and a female (2 bees). female had two parents, a male and a female, and male had one female (3 bees). Those two females each had two parents, and male had one (5 bees). This sequence of numbers of parents is jujukan Fibonacci.[38]

This is an idealization that does not describe actual bee ancestries. In reality, some ancestors of a particular bee will always be sisters or brothers, thus breaking lineage of distinct parents.

Lain-lain[sunting | sunting sumber]

Pada tahun 1963, John H. E. Cohn membuktikan segi empat dalam nombor Fibonacci adalah 0, 1, dan 144.[39]

Pada tahun 1990, Jean-claude Perez menerbitkan karya kukuh berkenaan lengkung dunia dan sensitiviti nombor Fibonacci[40][41]

Lihat pula[sunting | sunting sumber]

Rujukan[sunting | sunting sumber]

  1. ^ http://www.quipus.it/english/Andean%20Calculators.pdf
  2. ^ Parmanand Singh. "Acharya Hemachandra and the (so called) Fibonacci Numbers". Math. Ed. Siwan, 20(1):28-30, 1986. ISSN 0047-6269]
  3. ^ Parmanand Singh,"The So-called Fibonacci numbers in ancient and medieval India." Historia Mathematica 12(3), 229–44, 1985.
  4. ^ Mengikut konvensyen moden, urutannya bermula dengan F0=0. Liber Abaci memulakan urutan dengan F1 = 1, meninggalkan permulaan 0, dan urutannya masih ditulis secara ini oleh sesetengah.
  5. ^ The website [1] has the first 300 Fn factored into primes and links to more extensive tables.
  6. ^ Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag. ISBN 0-387-95419-8.  Chapter II.12, pp. 404–405.
  7. ^ Knott, Ron. "Fibonacci's Rabbits". University of Surrey School of Electronics and Physical Sciences. 
  8. ^ Kepler, Johannes (1966). A New Year Gift: On Hexagonal Snow. Oxford University Press. m/s. 92. ISBN 0198581203.  Strena seu de Nive Sexangula (1611)
  9. ^ a b E. W. Dijkstra (1978). In honour of Fibonacci. Report EWD654
  10. ^ Posamentier, Alfred (2007). The (Fabulous) FIBONACCI Numbers. Prometheus Books. m/s. 305. ISBN 978-1-59102-475-0.  Parameter |coauthors= tidak diketahui diabaikan (guna |author=) (bantuan)
  11. ^ M. Möbius, Wie erkennt man eine Fibonacci Zahl?, Math. Semesterber. (1998) 45; 243–246
  12. ^ Vorobiev, Nikolaĭ Nikolaevich (2002). "Chapter 1". Fibonacci Numbers. Birkhäuser. m/s. pp. 5–6. ISBN 3-7643-6135-2.  Parameter |coauthors= tidak diketahui diabaikan (guna |author=) (bantuan)
  13. ^ a b Fibonacci Number - from Wolfram MathWorld
  14. ^ Ron Knott, "The Fibonacci numbers".
  15. ^ Ross Honsberger Mathematical Gems III (AMS Dolciani Mathematcal Expositions No. 9), 1985, ISBN 0-88385-318-3, p. 133.
  16. ^ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
  17. ^ Su, Francis E., et al. "Fibonacci GCD's, please.", Mudd Math Fun Facts.
  18. ^ Lemmermeyer, ex. 2.27 p. 73
  19. ^ The website [2] has the first 300 Fibonacci numbers factored into primes.
  20. ^ Paulo Ribenboim (1996), The New Book of Prime Number Records, New York: Springer, ISBN 0-387-94457-5, p. 64
  21. ^ Franz Lemmermeyer (2000), Reciprocity Laws, New York: Springer, ISBN 3-540-66957-4, ex 2.25-2.28, pp. 73-74
  22. ^ Lemmermeyer, ex. 2.38, pp. 73-74
  23. ^ M. Avriel and D.J. Wilde (1966). "Optimality of the Symmetric Fibonacci Search Technique". Fibonacci Quarterly (3): 265–269. 
  24. ^ Amiga ROM Kernel Reference Manual, Addison-Wesley 1991
  25. ^ IFF - MultimediaWiki
  26. ^ An Application of the Fibonacci Number Representation
  27. ^ A Practical Use of the Sequence
  28. ^ Zeckendorf representation
  29. ^ S. Douady and Y. Couder (1996). "Phyllotaxis as a Dynamical Self Organizing Process" (PDF). Journal of Theoretical Biology. 178 (178): 255–274. doi:10.1006/jtbi.1996.0026. 
  30. ^ Jones, Judy (2006). "Science". An Incomplete Education. Ballantine Books. m/s. 544. ISBN 978-0-7394-7582-9.  Parameter |coauthors= tidak diketahui diabaikan (guna |author=) (bantuan)
  31. ^ A. Brousseau (1969). "Fibonacci Statistics in Conifers". Fibonacci Quarterly (7): 525–532. 
  32. ^ Computer Science for Fun - cs4fn: Marks for the da Vinci Code: B
  33. ^ Prusinkiewicz, Przemyslaw (1989). Lindenmayer Systems, Fractals, and Plants (Lecture Notes in Biomathematics). Springer-Verlag. ISBN 0-387-97092-4.  Parameter |coauthors= tidak diketahui diabaikan (guna |author=) (bantuan)
  34. ^ Vogel, H (1979), "A better way to construct the sunflower head", Mathematical Biosciences, 44 (44): 179–189, doi:10.1016/0025-5564(79)90080-4 
  35. ^ Prusinkiewicz, Przemyslaw (1990). [[The Algorithmic Beauty of Plants]]. Springer-Verlag. m/s. 101–107. ISBN 978-0387972978.  Parameter |coauthors= tidak diketahui diabaikan (guna |author=) (bantuan); Konflik URL–wikilink (bantuan)
  36. ^ J.C. Perez (1991), "Chaos DNA and Neuro-computers: A Golden Link", in Speculations in Science and Technology vol. 14 no. 4, ISSN 0155-7785
  37. ^ Pravin Chandra and Eric W. Weisstein, Fibonacci Number di MathWorld.
  38. ^ The Fibonacci Numbers and the Ancestry of Bees
  39. ^ J H E Cohn (1964). "Square Fibonacci Numbers Etc". Fibonacci Quarterly. 2. m/s. 109–113. 
  40. ^ IEEE Integers neural network systems (INNS) using resonance propertiesof a Fibonacciapos;s chaotic `golden neuronapos 1990
  41. ^ Golden ratio and numbers in DNA 2008

Pautan luar[sunting | sunting sumber]