Barisan Fibonacci

Dalam matematika, barisan Fibonacci adalah barisan yang setiap sukunya merupakan penjumlahan dari dua suku sebelumnya. Bilangan yang menjadi bagian dari barisan Fibonacci dikenal sebagai bilangan Fibonacci, umumnya dinotasikan sebagai $F n$ . Barisan ini umumnya dimulai dari 0 dan 1, walau beberapa penulis memulainya dari 1 dan 1, atau terkadang (seperti Fibonacci sendiri) dari 1 dan 2. Memulai dari 0 dan 1, beberapa suku pertama barisan ini adalah^[1]

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

Bilangan Fibonacci pertama kali dideskripsikan dalam matematika India setidaknya sejak tahun 200 SM, dalam karya oleh Pingala terkait menghitung banyaknya pola puisi Sanskerta yang dibentuk dari dua suku kata.^[2]^[3]^[4] Barisan ini diberi nama dengan nama matematikawan Italia Leonardo da Pisa, juga dikenal sebagai Fibonacci, yang memperkenalkannya ke dunia matematika Eropa Barat lewat bukunya Liber Abaci tahun 1202.^[5]

Bilangan Fibonacci sering muncul secara tak diduga dalam matematika, sampai ada jurnal tersendiri yang didedikasikan untuk mempelajarinya, Fibonacci Quarterly. Beberapa penerapan barisan Fibonacci diantaranya meliputi algoritma komputer teknik pencarian Fibonacci dan struktur data heap Fibonacci. Barisan Fibonacci juga muncul sebagai pola di alam, seperti percabangan di pohon, susunan daun pada batang, tunas buah nanas, pembungaan di tanaman articok, dan susunan dedaunan pohon cemara (meskipun tidak terjadi pada semua spesies).

Definisi

Spiral Fibonacci: hampiran spiral emas yang dibuat dengan menggambar busur lingkaran menghubungkan sudut persegi yang berseberanga pada pengubinan Fibonacci.

Barisan Fibonacci dapat didefinisikan oleh relasi perulangan^[6] $F_{0}=0,\quad F_{1}=1,$ dan $F_{n}=F_{n-1}+F_{n-2}$ untuk $n>1.$

Jika menggunakan beberapa definisi lama, nilai $F_{0}=0$ dihilangkan, jadi barisan dimulai dengan $F_{1}=F_{2}=1,$ dan perulangan $F_{n}=F_{n-1}+F_{n-2}$ valid untuk $n > 2$ .^[7]^[8] Dua puluh bilangan $F n$ Fibonacci pertama adalah:^[9]

F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆	F₁₇	F₁₈	F₁₉
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

Asal mula

Pengaturan lantai dengan kotak berukuran bilangan Fibonacci

Berdasarkan buku The Art of Computer Programming karya Donald E. Knuth, barisan ini pertama kali dijelaskan oleh matematikawan India, Gopala dan Hemachandra pada tahun 1150, ketika menyelidiki berbagai kemungkinan untuk memasukkan barang-barang ke dalam kantong.

Eropa

Sebuah halaman dari Liber AbaciFibonacci dari Biblioteka Nazionale di Firenze menunjukan (dalam kotak di kanan) 13 entri deret Fibonacci: indeks dari sekarang sampai XII (bulan) sebagai ordinal Latin dan angka romawi serta nomornya (pasangan kelinci) sebagai angka Hindu-Arab yang dimulai dengan 1, 2, 3, 5 dan diakhiri dengan 377.

Bilangan Fibonacci pertama kali muncul pada buku Liber Abaci (The Book of Calculation, 1202) oleh Fibonacci^[10]^[11] yang di mana digunakan untuk menghitung pertumbuhan populasi kelinci.^[12]^[13] Fibonacci mempertimbangkan pertumbuhan populasi kelinci yang ideal (secara biologis tidak realistis), berasumsi bahwa: seekor sepasang kelinci yang baru lahir diternakkan di ladang; setiap pasangan kawin pada umur satu bulan, dan pada akhir bulan kedua selalu menghasilkan sepasang kelinci lagi; dan kelinci tidak akan mati, tetapi terus berkembang biak selamanya. Fibonacci mengajukan teka-teki: berapa banyak pasangan yang akan ada dalam satu tahun?

Pada akhir di bulan pertama, mereka kawin, tapi masih ada 1 pasangan saja.
Pada akhir bulan kedua mereka menghasilkan pasangan baru, jadi ada 2 pasangan di lapangan.
Pada akhir bulan ketiga, pasangan awal menghasilkan pasangan kedua, tapi pasangan kedua hanya kawin selama sebulan, jadi totalnya ada 3 pasangan.
Pada akhir bulan keempat, pasangan asli telah menghasilkan pasangan baru lagi, dan pasangan yang lahir dua bulan lalu juga menghasilkan pasangan pertamanya, sehingga menjadi 5 pasangan.

Pada akhir bulan ke-n, jumlah pasang kelinci sama dengan jumlah pasangan dewasa (yaitu jumlah pasangan dalam bulan $n - 2$ ) ditambah jumlah dari pasangan yang hidup bulan lalu (bulan $n - 1$ ). Jumlah pada $n$ -th bulan adalah bilangan Fibonacci ke- $n$ .^[14]

Nama "Deret Fibonacci" pertama kali digunakan oleh ahli teori bilangan abad ke-19 Édouard Lucas.^[15]

Dalam populasi ideal yang terus bertambah, jumlah pasangan kelinci membentuk deret Fibonacci. Pada akhir bulan n-th, jumlah pasangannya sama dengan F_n.

Relasi terhadap rasio emas

Identifikasi

Rumus Binet memberikan bukti bahwa bilangan bulat positif $x$ adalah sebuah bilangan Fibonacci jika dan hanya jika setidaknya salah satu dari $5x^{2}+4$ atau $5x^{2}-4$ adalah persegi sempurna.^[16] Hal ini karena rumus Binet yang dapat dituliskan sebagai $F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}$ , dapat dikalikan dengan ${\sqrt {5}}\varphi ^{n}$ dan diselesaikan sebagai persamaan kuadrat di $\varphi ^{n}$ melalui rumus kuadrat: $\varphi ^{n}={\frac {F_{n}{\sqrt {5}}\pm {\sqrt {5{F_{n}}^{2}+4(-1)^{n}}}}{2}}.$ Membandingkan ini dengan $\varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2$ , itu mengikuti bahwa

5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\,.

Khususnya, sisi kiri adalah persegi sempurna.

Identitas lain

Banyak bentuk lain yang dapat diperoleh dengan menggunakan berbagai metode. Inilah beberapa di antaranya:^[17]

Identitas Cassini dan Catalan

Identitas Cassini menyatakan bahwa ${F_{n}}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}$ Identitas Catalan adalah generalisasi: ${F_{n}}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}{F_{r}}^{2}$

Identitas d'Ocagne

$F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}$ $F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}$ di mana L_n adalah bilangan ke-n dari bilangan Lucas. Yang terakhir adalah bentuk untuk penggandaan n; identitas lain dari jenis ini adalah $F_{3n}=2{F_{n}}^{3}+3F_{n}F_{n+1}F_{n-1}=5{F_{n}}^{3}+3(-1)^{n}F_{n}$ oleh bentuk Cassini. $F_{3n+1}={F_{n+1}}^{3}+3F_{n+1}{F_{n}}^{2}-{F_{n}}^{3}$ $F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}$ $F_{4n}=4F_{n}F_{n+1}\left({F_{n+1}}^{2}+2{F_{n}}^{2}\right)-3{F_{n}}^{2}\left({F_{n}}^{2}+2{F_{n+1}}^{2}\right)$ Ini dapat ditemukan secara eksperimental menggunakan lattice reduction, dan berguna dalam menyiapkan special number field sieve ke bilangan Fibonacci terfaktorisasi.

Lebih umumnya,^[17] $F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}{F_{n}}^{i}{F_{n+1}}^{k-i}.$ atau sebagai alternatif $F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c+i}{F_{n}}^{i}{F_{n-1}}^{k-i}.$ Menempatkan $k = 2$ dalam rumus ini, kita mendapatkan lagi rumus akhir dari bagian atas Bentuk Matriks.

Referensi

Catatan kaki penjelas

Kutipan

^ Sloane, N.J.A. (ed.). "Sequence A000045 (Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1)". On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Goonatilake, Susantha (1998), Toward a Global Science, Indiana University Press, hlm. 126, ISBN 978-0-253-33388-9
^ Singh, Parmanand (1985), "The So-called Fibonacci numbers in ancient and medieval India", Historia Mathematica, 12 (3): 229–44, doi:10.1016/0315-0860(85)90021-7 
^ Knuth, Donald (2006), The Art of Computer Programming, 4. Generating All Trees – History of Combinatorial Generation, Addison–Wesley, hlm. 50, ISBN 978-0-321-33570-8, it was natural to consider the set of all sequences of [L] and [S] that have exactly m beats. ... there are exactly Fm+1 of them. For example the 21 sequences when $m = 7$ are: [gives list]. In this way Indian prosodists were led to discover the Fibonacci sequence, as we have observed in Section 1.2.8 (from v.1)
^ Sigler 2002, hlm. 404–05.
^ Lucas 1891, hlm. 3.
^ Beck & Geoghegan 2010.
^ Bóna 2011, hlm. 180.
^ Sloane, N.J.A. (ed.). "Sequence A000045 (Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1)". On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Sigler 2002, hlm. 404–405.
^ "Fibonacci's Liber Abaci (Book of Calculation)", The University of Utah, 13 December 2009, diakses tanggal 28 November 2018
^ Hemenway, Priya (2005), Divine Proportion: Phi In Art, Nature, and Science, New York: Sterling, hlm. 20–21, ISBN 1-4027-3522-7
^ Knott, Ron (25 September 2016), "The Fibonacci Numbers and Golden section in Nature – 1", University of Surrey, diakses tanggal 27 November 2018
^ Knott, Ron, Fibonacci's Rabbits, University of Surrey Faculty of Engineering and Physical Sciences
^ Gardner, Martin (1996), Mathematical Circus, The Mathematical Association of America, hlm. 153, ISBN 978-0-88385-506-5, It is ironic that Leonardo, who made valuable contributions to mathematics, is remembered today mainly because a 19th-century French number theorist, Édouard Lucas... attached the name Fibonacci to a number sequence that appears in a trivial problem in Liber abaci
^ Gessel, Ira (October 1972), "Fibonacci is a Square" (PDF), The Fibonacci Quarterly, 10 (4): 417–19, diakses tanggal April 11, 2012
^ ^a ^b (Inggris) Weisstein, Eric W., "Fibonacci Number", MathWorld

Kutipan ilmiah

Ball, Keith M (2003), "8: Fibonacci's Rabbits Revisited", Strange Curves, Counting Rabbits, and Other Mathematical Explorations, Princeton, NJ: Princeton University Press, ISBN 978-0-691-11321-0 .
Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics, New York: Springer, ISBN 978-1-4419-7022-0 .
Bóna, Miklós (2011), A Walk Through Combinatorics (edisi ke-3rd), New Jersey: World Scientific, ISBN 978-981-4335-23-2 .
Borwein, Jonathan M.; Borwein, Peter B. (July 1998), Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley, hlm. 91–101, ISBN 978-0-471-31515-5
Lemmermeyer, Franz (2000), Reciprocity Laws: From Euler to Eisenstein, Springer Monographs in Mathematics, New York: Springer, ISBN 978-3-540-66957-9 .
Livio, Mario (2003) [2002], The Golden Ratio: The Story of Phi, the World's Most Astonishing Number (edisi ke-First trade paperback), New York City: Broadway Books, ISBN 0-7679-0816-3
Lucas, Édouard (1891), Théorie des nombres (dalam bahasa Prancis), 1, Paris: Gauthier-Villars .
Sigler, L. E. (2002), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Springer, ISBN 978-0-387-95419-6

Lihat pula

Pranala luar

The Golden Mean and the Physics of Aesthetics
The Golden Section: Phi Diarsipkan 2006-12-05 di Wayback Machine.
Menghitung bilangan Fibonacci pada Mesin Turing Diarsipkan 2005-02-06 di Wayback Machine.
Hemachandra's application to Sanskrit poetry Diarsipkan 2012-07-16 di Wayback Machine.
Deret Fibonacci Diarsipkan 2005-01-22 di Wayback Machine.
Representasi Bilangan Bulat menggunakan bilangan Fibonacci Diarsipkan 2007-10-30 di Wayback Machine.

[oeis-1] Sloane, N.J.A. (ed.). "Sequence A000045 (Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1)". On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[GlobalScience-2] Goonatilake, Susantha (1998), Toward a Global Science, Indiana University Press, hlm. 126, ISBN 978-0-253-33388-9

[HistoriaMathematica-3] Singh, Parmanand (1985), "The So-called Fibonacci numbers in ancient and medieval India", Historia Mathematica, 12 (3): 229–44, doi:10.1016/0315-0860(85)90021-7 

[Donald_Knuth_2006_50-4] Knuth, Donald (2006), The Art of Computer Programming, 4. Generating All Trees – History of Combinatorial Generation, Addison–Wesley, hlm. 50, ISBN 978-0-321-33570-8, it was natural to consider the set of all sequences of [L] and [S] that have exactly m beats. ... there are exactly Fm+1 of them. For example the 21 sequences when $m = 7$ are: [gives list]. In this way Indian prosodists were led to discover the Fibonacci sequence, as we have observed in Section 1.2.8 (from v.1)

[FOOTNOTESigler2002404–05-5] Sigler 2002, hlm. 404–05.

[FOOTNOTELucas18913-6] Lucas 1891, hlm. 3.

[FOOTNOTEBeckGeoghegan2010-7] Beck & Geoghegan 2010.

[FOOTNOTEBóna2011180-8] Bóna 2011, hlm. 180.

[oeis3-9] Sloane, N.J.A. (ed.). "Sequence A000045 (Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1)". On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[FOOTNOTESigler2002404–405-10] Sigler 2002, hlm. 404–405.

[11] "Fibonacci's Liber Abaci (Book of Calculation)", The University of Utah, 13 December 2009, diakses tanggal 28 November 2018

[12] Hemenway, Priya (2005), Divine Proportion: Phi In Art, Nature, and Science, New York: Sterling, hlm. 20–21, ISBN 1-4027-3522-7

[13] Knott, Ron (25 September 2016), "The Fibonacci Numbers and Golden section in Nature – 1", University of Surrey, diakses tanggal 27 November 2018

[14] Knott, Ron, Fibonacci's Rabbits, University of Surrey Faculty of Engineering and Physical Sciences

[15] Gardner, Martin (1996), Mathematical Circus, The Mathematical Association of America, hlm. 153, ISBN 978-0-88385-506-5, It is ironic that Leonardo, who made valuable contributions to mathematics, is remembered today mainly because a 19th-century French number theorist, Édouard Lucas... attached the name Fibonacci to a number sequence that appears in a trivial problem in Liber abaci

[16] Gessel, Ira (October 1972), "Fibonacci is a Square" (PDF), The Fibonacci Quarterly, 10 (4): 417–19, diakses tanggal April 11, 2012

[MathWorld-17] (Inggris) Weisstein, Eric W., "Fibonacci Number", MathWorld

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]