Barisan Fibonacci: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Dedhert.Jr (bicara | kontrib) Perbaikan penulisan rumus matematika. |
Fitur saranan suntingan: 3 pranala ditambahkan. Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Suntingan seluler lanjutan Tugas pengguna baru Disarankan: tambahkan pranala |
||
| (37 revisi perantara oleh 18 pengguna tidak ditampilkan) | |||
Baris 1:
{{Short description|Barisan dengan setiap sukunya merupakan penjumlahan dari dua suku sebelumnya}}[[File:Fibonacci Squares.svg|thumb|Pengubinan dengan [[Persegi|persegi-persegi]] yang panjang sisi-sisinya adalah beberapa suku pertama barisan Fibonacci: 1, 1, 2, 3, 5, 8, 13 dan 21.]]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 {{nowrap|{{math|''F<sub>n</sub>''}}{{space|hair}}}}. 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<ref name="oeis">{{Cite OEIS|A000045|2=Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1|mode=cs2}}</ref>
: 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 [[Bahasa Sanskerta|Sanskerta]] yang dibentuk dari dua suku kata.<ref name="GlobalScience">{{Citation|title=Toward a Global Science|first=Susantha|last=Goonatilake|publisher=Indiana University Press|year=1998|page=126|isbn=978-0-253-33388-9|url=https://books.google.com/books?id=SI5ip95BbgEC&pg=PA126}}</ref><ref name="HistoriaMathematica">{{Citation|first=Parmanand|last=Singh|title=The So-called Fibonacci numbers in ancient and medieval India|journal=Historia Mathematica|volume=12|issue=3|pages=229–44|year=1985|doi=10.1016/0315-0860(85)90021-7|doi-access=free}}</ref><ref name="Donald Knuth 2006 50">{{Citation|title=The Art of Computer Programming|volume=4. Generating All Trees – History of Combinatorial Generation|first=Donald|last=Knuth|author-link=Donald Knuth|publisher=Addison–Wesley|year=2006|isbn=978-0-321-33570-8|page=50|url=https://books.google.com/books?id=56LNfE2QGtYC&q=rhythms&pg=PA50|quote=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 {{math|1=''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)}}</ref> Barisan ini diberi nama dengan nama matematikawan [[Italia]] Leonardo da Pisa, juga dikenal sebagai [[Fibonacci]], yang memperkenalkannya ke dunia matematika Eropa Barat lewat bukunya ''{{lang|la|[[Liber Abaci]]}}'' tahun 1202.{{Sfn|Sigler|2002|pp=404–05}}
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#Spiral|pola di alam]], seperti percabangan di pohon, [[Filotaksis|susunan daun pada batang]], tunas buah nanas, pembungaan di tanaman [[articok]], dan susunan dedaunan pohon cemara (meskipun tidak terjadi pada semua spesies).
==Definisi==
[[File:Fibonacci Spiral.svg|thumb|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]]{{Sfn | Lucas | 1891 | p=3}} <math display="block">F_0=0,\quad F_1= 1,</math>dan<math display="block">F_n=F_{n-1} + F_{n-2}</math>untuk <math>n>1.</math>
Jika menggunakan beberapa definisi lama, nilai <math>F_0 = 0</math> dihilangkan, jadi barisan dimulai dengan <math>F_1=F_2=1,</math> dan perulangan <math>F_n=F_{n-1} + F_{n-2}</math> valid untuk {{math|''n'' > 2}}.{{Sfn | Beck | Geoghegan | 2010}}{{Sfn | Bóna | 2011 | p=180}} Dua puluh bilangan {{math|''F<sub>n</sub>''}} Fibonacci pertama adalah:<ref name="oeis3">{{Cite OEIS|A000045|2=Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1|mode=cs2}}</ref>
:{| class="wikitable" style="text-align:right"
! ''F''<sub>0</sub>
! ''F''<sub>1</sub>
! ''F''<sub>2</sub>
! ''F''<sub>3</sub>
! ''F''<sub>4</sub>
! ''F''<sub>5</sub>
! ''F''<sub>6</sub>
! ''F''<sub>7</sub>
! ''F''<sub>8</sub>
! ''F''<sub>9</sub>
! ''F''<sub>10</sub>
! ''F''<sub>11</sub>
! ''F''<sub>12</sub>
! ''F''<sub>13</sub>
! ''F''<sub>14</sub>
! ''F''<sub>15</sub>
! ''F''<sub>16</sub>
! ''F''<sub>17</sub>
! ''F''<sub>18</sub>
! ''F''<sub>19</sub>
|-
| 0
| 1
| 1
| 2
| 3
| 5
| 8
| 13
| 21
| 34
| 55
| 89
| 144
| 233
| 377
| 610
| 987
| 1597
| 2584
| 4181
|}
== Asal mula ==
=== India ===
{{see also|Rasio emas#Sejarah}}
[[Berkas:Fibonacci_Sanskrit_prosody.svg|jmpl|Tiga belas ({{math|''F''<sub>7</sub>}}) cara menyusun suku kata panjang dan singkat dalam baris dengan panjang enam. Dari total cara itu, delapan ({{math|''F''<sub>6</sub>}}) diantaranya berakhir dengan suku kata singkat, dan lima ({{math|''F''<sub>5</sub>}}) berakhir dengan suku kata panjang.]]
Barisan Fibonacci muncul dalam [[matematika India]], dalam hubungannya dengan [[Chanda|ilmu irama Veda]].{{sfn|Livio|2003|p=197}}<ref name="HistoriaMathematica2">{{Citation|first=Parmanand|last=Singh|title=The So-called Fibonacci numbers in ancient and medieval India|journal=Historia Mathematica|volume=12|issue=3|pages=229–44|year=1985|doi=10.1016/0315-0860(85)90021-7|doi-access=free}}</ref><ref name="knuth-v1">{{Citation|title=The Art of Computer Programming|volume=1|first=Donald|last=Knuth|author-link=Donald Knuth|publisher=Addison Wesley|year=1968|isbn=978-81-7758-754-8|url=https://books.google.com/books?id=MooMkK6ERuYC&pg=PA100|page=100|quote=Before Fibonacci wrote his work, the sequence Fn had already been discussed by Indian scholars, who had long been interested in rhythmic patterns ... both Gopala (before 1135 AD) and Hemachandra (c. 1150) mentioned the numbers 1,2,3,5,8,13,21 explicitly [see P. Singh Historia Math 12 (1985) 229–44]" p. 100 (3d ed) ...}}</ref> Dalam tradisi puisi Sanskerta, ada ketertarikan dalam menyusun semua pola dengan suku kata panjang [P] dengan dua satuan durasi, berseling dengan suku kata singkat [S] dengan satu satuan durasi. Menghitung banyaknya pola berbeda dari gabungan [P] dan [S], dengan suatu total satuan durasi yang ditetapkan, menghasilkan suatu bilangan Fibonacci: banyaknya pola dengan <math>m</math> satuan durasi adalah <math>F_{m+1}.</math><ref name="Donald Knuth 2006 502">{{Citation|title=The Art of Computer Programming|volume=4. Generating All Trees – History of Combinatorial Generation|first=Donald|last=Knuth|author-link=Donald Knuth|publisher=Addison–Wesley|year=2006|isbn=978-0-321-33570-8|page=50|url=https://books.google.com/books?id=56LNfE2QGtYC&q=rhythms&pg=PA50|quote=it was natural to consider the set of all sequences of [Long] and [Short] that have exactly m beats. ... there are exactly <math>F_{m+1}</math> of them. For example the 21 sequences when <math>m=7</math> 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)}}</ref>
Pemahaman terkait barisan Fibonacci disampaikan pertama kali setidaknya oleh [[Pingala]] ({{circa}}. 450 SM–200 SM). Singh mengutip rumus misterius Pingala ''misrau cha'' ("keduanya dicampur") dan cendekiawan menafsirkan konteksnya seperti mengatakan banyaknya pola dengan <math>m</math> ketukan (<math>F_{m+1}</math>) diperoleh dengan menambahkan satu [S] ke pola <math>F_{m}</math> dan satu [P] ke pola <math>F_{m-1}.</math><ref>{{Citation|last=Agrawala|first=VS|year=1969|title=''Pāṇinikālīna Bhāratavarṣa'' (Hn.). Varanasi-I: TheChowkhamba Vidyabhawan|quote=SadgurushiShya writes that Pingala was a younger brother of Pāṇini [Agrawala 1969, lb]. There is an alternative opinion that he was a maternal uncle of Pāṇini [Vinayasagar 1965, Preface, 121]. ... Agrawala [1969, 463–76], after a careful investigation, in which he considered the views of earlier scholars, has concluded that Pāṇini lived between 480 and 410 BC}}</ref> [[Bharata Muni]] juga menuliskan pemahamannya terkait barisan Fibonacci dalam ''[[Natya Shastra]]'' (ca. 100 SM–c. 350 SM).<ref>{{citation|title=The So-called Fibonacci Numbers in Ancient and Medieval India|last=Singh|first=Parmanand|journal=[[Historia Mathematica]]|year=1985|publisher=[[Academic Press]]|volume=12|issue=3|page=232|doi=10.1016/0315-0860(85)90021-7|doi-access=free}}</ref><ref name="GlobalScience2">{{Citation|title=Toward a Global Science|first=Susantha|last=Goonatilake|publisher=Indiana University Press|year=1998|page=126|isbn=978-0-253-33388-9|url=https://books.google.com/books?id=SI5ip95BbgEC&pg=PA126}}</ref> Eksposisi paling jelas terkait barisan muncul dalam karya oleh [[Virahanka]] (ca. 700 SM), yang telah hilang, tapi ada sebagai kutipan oleh Gopala (ca. 1135).{{sfn|Livio|2003|p=197}}{{efn|"For four, variations of meters of two [and] three being mixed, five happens. For five, variations of two earlier—three [and] four, being mixed, eight is obtained. In this way, for six, [variations] of four [and] of five being mixed, thirteen happens. And like that, variations of two earlier meters being mixed, seven [[Mora (linguistics)|morae]] [is] twenty-one. In this way, the process should be followed in all mātrā-vṛttas" <ref>{{Citation|last=Velankar|first=HD|year=1962|title='Vṛttajātisamuccaya' of kavi Virahanka|publisher=Rajasthan Oriental Research Institute|location=Jodhpur|page=101}}</ref>}} [[Hemachandra]] (ca. 1150) juga memiliki pengetahuan tentang barisan,<ref name="GlobalScience2" /> dalam tulisannya "jumlah dari sebelumnya dan yang sebelumnya lagi menjadi banyaknya ... ''mātrā-vṛtta'' selanjutnya."{{sfn|Livio|2003|p=197–198}}<ref>{{citation|last1=Shah|first1=Jayant|year=1991|title=A History of Piṅgala's Combinatorics|url=https://web.northeastern.edu/shah/papers/Pingala.pdf|journal=[[Northeastern University]]|page=41|access-date=4 January 2019}}</ref>
===
[[Berkas:Liber_abbaci_magliab_f124r.jpg|jmpl|Selembar halaman dari ''{{lang|la|[[Liber Abaci]]}}'' karya [[Fibonacci]], menunjukkan (dalam kotak di sisi kanan) 13 suku pertama barisan Fibonacci: indeks bulan dalam [[angka Romawi]] (I sampai XII), dan banyaknya pasangan kelinci dalam [[Sistem bilangan Hindu-Arab|angka Hindu-Arab]] dimulai dari 1, 2, 3, 5 dan berakhir di angka 377.]]
Bilangan Fibonacci pertama kali muncul pada buku ''{{lang|la|[[Liber Abaci]]}}'' (''The Book of Calculation'', 1202) oleh [[Fibonacci]],{{Sfn|Sigler|2002|pp=404–405}}<ref>{{citation|url=https://www.math.utah.edu/~beebe/software/java/fibonacci/liber-abaci.html|title=Fibonacci's Liber Abaci (Book of Calculation)|date=13 December 2009|website=[[The University of Utah]]|access-date=28 November 2018}}</ref> yang digunakan untuk menghitung pertumbuhan populasi kelinci.<ref>{{citation|last=Hemenway|first=Priya|title=Divine Proportion: Phi In Art, Nature, and Science|year=2005|publisher=Sterling|location=New York|isbn=1-4027-3522-7|pages=20–21}}</ref><ref>{{citation|url=http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html#Rabbits|title=The Fibonacci Numbers and Golden section in Nature – 1|last=Knott|first=Ron|date=25 September 2016|website=[[University of Surrey]]|access-date=27 November 2018}}</ref> Fibonacci membahas pertumbuhan populasi kelinci yang ideal (secara biologis tidak realistis), dengan asumsi bahwa: sepasang kelinci yang baru lahir langsung diternakkan di ladang; setiap pasangan kawin pada umur satu bulan, dan pada akhir bulan kedua pasangan akan 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?
[[Berkas:Fibonacci_Rabbits.svg|jmpl|Solusi dari masalah kelinci Fibonacci: dalam populasi ideal yang terus bertambah, banyaknya pasangan kelinci membentuk barisan Fibonasi. Pada akhir bulan ke-''n'', banyaknya pasangan sama dengan ''F<sub>n.</sub>'']]
* Pada akhir di bulan pertama, satunya-satunya pasangan kelinci kawin, tapi belum melahirkan.
* Pada akhir bulan kedua mereka menghasilkan pasangan baru (jadi ada 2 pasangan di lapangan) dan hamil kembali.
* Pada akhir bulan ketiga, pasangan awal menghasilkan pasangan baru (dan hamil kembali), tapi pasangan kedua hanya kawin selama sebulan, jadi totalnya ada 3 pasangan.
* Pada akhir bulan keempat, pasangan awal telah menghasilkan pasangan baru lagi, dan pasangan yang lahir dua bulan lalu juga menghasilkan pasangan pertamanya, sehingga total ada 5 pasangan.
Pada akhir bulan ke-''n'', jumlah pasang kelinci sama dengan jumlah pasangan dewasa (yaitu jumlah pasangan di bulan {{math|''n'' – 2}}) ditambah jumlah dari pasangan yang hidup bulan lalu (bulan {{math|''n'' – 1}}). Jumlah pasangan bulan ke-{{mvar|n}} adalah bilangan Fibonacci ke-{{mvar|n}}.<ref>{{citation|last=Knott|first=Ron|title=Fibonacci's Rabbits|url=http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html#Rabbits|publisher=[[University of Surrey]] Faculty of Engineering and Physical Sciences}}</ref>
Nama "barisan Fibonacci" pertama kali digunakan oleh ahli [[teori bilangan]] abad ke-19 [[Édouard Lucas]].<ref>{{Citation|first=Martin|last=Gardner|author-link=Martin Gardner|title=Mathematical Circus|publisher=The Mathematical Association of America|year=1996|isbn=978-0-88385-506-5|quote=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|page=153}}</ref>
== Hubungan dengan rasio emas ==
{{Main|Rasio emas}}
=== Rumus eksplisit ===
Sama seperti [[barisan]] lainnya yang didefinisikan sebagai [[relasi perulangan]] dengan koefisien konstan, bilangan Fibonacci memiliki [[Ekspresi bentuk tertutup|ekspresi bentuk-tertutup]].<ref>{{cite book|author1=Sarah-Marie Belcastro|year=2018|url=https://books.google.com/books?id=xoqADwAAQBAJ|title=Discrete Mathematics with Ducks|publisher=CRC Press|isbn=978-1-351-68369-2|edition=2nd, illustrated|page=260}} [https://books.google.com/books?id=xoqADwAAQBAJ&pg=PA260 Extract of page 260]</ref> Ekspresi ini selanjutnya dikenal sebagai '''rumus Binet''''','' dinamakan dengan nama matematikawan Prancis [[Jacques Philippe Marie Binet]], walau ekspresi tersebut sudah diketahui oleh [[Abraham de Moivre]] dan [[Daniel Bernoulli]]:<ref>{{citation|last1=Beutelspacher|first1=Albrecht|last2=Petri|first2=Bernhard|contribution=Fibonacci-Zahlen|doi=10.1007/978-3-322-85165-9_6|pages=87–98|publisher=Vieweg+Teubner Verlag|title=Der Goldene Schnitt|series=Einblick in die Wissenschaft|year=1996|isbn=978-3-8154-2511-4}}</ref><math display="block">
F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5},
</math>dengan<math display="block">
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\ldots
</math>dikenal dengan sebutan [[rasio emas]], dan <math>\psi</math> adalah konjugatnya:{{Sfn|Ball|2003|p=156}}<math display="block">
\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\ldots.
</math>Karena <math>\psi = -\varphi^{-1},</math> rumus tersebut juga dapat dituliskan sebagai<math display="block">
F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt 5} = \frac{\varphi^n - (-\varphi)^{-n}}{2\varphi - 1}.
</math>Untuk melihat hubungan antara barisan Fibonacci dengan kedua konstanta tersebut,{{Sfn|Ball|2003|pp=155–156}} perhatikan bahwa <math>\varphi</math> dan <math>\psi</math> keduanya merupakan solusi dari persamaan <math display="inline">x^2 = x + 1</math> dan (sebagai akibatnya) <math>x^n = x^{n-1} + x^{n-2}.</math> Ini mengartikan perpangkatan dari <math>\varphi</math> dan <math>\psi</math> memenuhi relasi perulangan Fibonacci; dengan kata lain,<math display="block">\begin{align}
\varphi^n &= \varphi^{n-1} + \varphi^{n-2}, \\[3mu]
\psi^n &= \psi^{n-1} + \psi^{n-2}.
\end{align}</math>Dari hasil tersebut, semua barisan yang didefinisikan sebagai<math display="block">U_n=a \varphi^n + b \psi^n</math>juga memenuhi relasi perulangan yang sama, karena<math display="block">\begin{align}
U_n &= a\varphi^n + b\psi^n \\[3mu]
&= a(\varphi^{n-1} + \varphi^{n-2}) + b(\psi^{n-1} + \psi^{n-2}) \\[3mu]
&= a\varphi^{n-1} + b\psi^{n-1} + a\varphi^{n-2} + b\psi^{n-2} \\[3mu]
&= U_{n-1} + U_{n-2}.
\end{align}</math>Jika nilai <math>a</math> dan <math>b</math> dipilih sedemikian sehingga <math>U_0 = 0</math> dan <math>U_1 = 1,</math> maka barisan <math>U_n</math> yang terbentuk pastilah barisan Fibonacci. Pemilihan ini sama saja dengan mengharuskan <math>a</math> dan <math>b</math> memenuhi sistem persamaan:<math display="block">
\begin{align} a + b &= U_0 = 0 \\ \varphi a + \psi b &= U_1 = 1\end{align}
</math>yang memiliki solusi<math display="block">
a = \frac{1}{\varphi-\psi} = \frac{1}{\sqrt 5},\quad b = -a,
</math>sama seperti rumus Binet.
Untuk sebarang nilai awal <math>U_0</math> dan <math>U_1,</math> rumus Binet yang lebih umum adalah:<math display="block"> U_n = a\varphi^n + b\psi^n </math>dengan<math display="block">\begin{align}
a&=\frac{U_1-U_0\psi}{\sqrt 5}, \\[3mu]
b&=\frac{U_0\varphi-U_1}{\sqrt 5}.
\end{align}</math>
=== Perhitungan dengan pembulatan ===
Karena suku <math display="inline">\left|\frac{\psi^{n}}{\sqrt 5}\right|</math> pada rumus Binet selalu kurang dari <math>\tfrac{1}{2}</math> untuk <math>n\geq0</math> , bilangan <math>F_n</math> menjadi [[bilangan bulat]] terdekat dengan <math display="inline">\frac{\varphi^n}{\sqrt 5} </math>. Akibatnya, bilangan Fibonacci juga dapat dihasilkan dengan [[Pembulatan|membulatkan]]:<math display="block">F_n=\left\lfloor\frac{\varphi^n}{\sqrt 5}\right\rceil,\ n \geq 0.</math>Faktanya, galat pembulatan akan mengecil dengan cepat seiring membesarnya <math>n,</math> menjadi kurang dari 0,1 untuk <math>n\geq 4,</math> dan kurang dari 0,01 untuk <math>n\geq 8.</math> Rumus ini juga mudah diinvers untuk mendapatkan indeks dari bilangan Fibonacci <math>F</math>:<math display="block">n(F) = \left\lfloor \log_\varphi \sqrt{5}F\right\rceil,\ F \geq 1.</math>Jika diubah agar melakukan [[Fungsi bilangan bulat terbesar dan terkecil|pembulatan ke bawah]], rumus akan menghasilkan indeks bilangan Fibonacci terbesar yang tidak lebih dari <math>F</math>.
=== Identifikasi ===
Rumus Binet memberikan bukti bahwa bilangan bulat positif <math>x</math> merupakan bilangan Fibonacci [[jika dan hanya jika]] setidaknya salah satu dari <math>5x^2+4</math> atau <math>5x^2-4</math> merupakan [[Bilangan persegi|kuadrat sempurna]].<ref>{{Citation|title=Fibonacci is a Square|last1=Gessel|first1=Ira|journal=[[The Fibonacci Quarterly]]|volume=10|issue=4|pages=417–19|date=October 1972|url=http://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf|access-date=April 11, 2012}}</ref> Hal ini dapat terlihat mengalikan rumus Binet, yang dituliskan sebagai <math>F_n = (\varphi^n - (-1)^n \varphi^{-n}) / \sqrt{5}</math>, dengan <math>\sqrt{5} \varphi^n</math> lalu diselesaikan sebagai [[persamaan kuadrat]] dalam <math>\varphi^n</math> menggunakan [[Rumus kuadrat|rumus kuadratik]], menghasilkan:<math display="block">\varphi^n = \frac{F_n\sqrt{5} \pm \sqrt{5{F_n}^2 + 4(-1)^n}}{2}.</math>Membandingkan bentuk ini dengan <math>\varphi^n = F_n \varphi + F_{n-1} = (F_n\sqrt{5} + F_n + 2 F_{n-1})/2</math> didapatkan<math display="block">5{F_n}^2 + 4(-1)^n = (F_n + 2F_{n-1})^2\,.</math>yang menunjukkan ruas sisi kiri merupakan bilangan kuadrat sempurna.
== Identitas kombinatorial ==
=== Bukti kombinatorial ===
Banyak identitas terkait bilangan Fibonacci yang dapat dibuktikan menggunakan argumen kombinatorial, menggunakan fakta bahwa <math>F_n</math> dapat dianggap sebagai banyaknya (mungkin kosong) barisan berisi angka 1 dan 2 dengan jumlah total <math>n-1.</math> Hal ini dapat dipilih sebagai definisi dari <math>F_n</math>, dengan konvensi <math>F_0 = 0</math> yang mengartikan tidak ada barisan macam itu dengan total −1, dan <math>F_1 = 1</math> yang mengartikan ada satu barisan -- yakni barisan dengan panjang 0 -- dengan total 0. Menggunakan notasi <math>|{...}|</math> untuk menyatakan [[kardinalitas]] dari [[Himpunan (matematika)|himpunan]], berikut beberapa bilangan Fibonacci pertama:
: <math>F_0 = 0 = |\{\}|</math>
: <math>F_1 = 1 = |\{()\}|</math>
: <math>F_2 = 1 = |\{(1)\}|</math>
: <math>F_3 = 2 = |\{(1,1),(2)\}|</math>
: <math>F_4 = 3 = |\{(1,1,1),(1,2),(2,1)\}|</math>
: <math>F_5 = 5 = |\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|</math>
Dalam sudut pandang ini, hubungan perulangan <math display="inline">F_n = F_{n-1} + F_{n-2}</math> dapat dianggap sebagai memisahkan barisan-barisan penyusun <math>F_n</math> menjadi dua himpunan tidak-beririsan, yang masing-masing dimulai dari angka 1 atau 2:<math display="block">F_n = |\{(1,...),(1,...),...\}| + |\{(2,...),(2,...),...\}|</math>Mengabaikan suku pertama, jumlah total setiap suku barisan pada kedua himpunan tersebut masing-masing adalah <math>n-2</math> dan <math>n-3</math>. Nilai ini adalah kardinalitas dari <math>F_{n-1}</math> dan <math>F_{n-2}</math>, menunjukkan bahwa memang <math display="inline">F_n = F_{n-1} + F_{n-2}.</math>
Dengan cara yang mirip, dapat ditunjukkan bahwa jumlah dari <math>n</math> bilangan Fibonacci pertama sama dengan bilangan Fibonacci ke-<math>(n+2)</math> dikurang 1.{{Sfn|Lucas|1891|p=4}} Secara matematis:<math display="block">\sum_{i=1}^n F_i = F_{n+2} - 1</math>Identitas ini dapat dilihat sebagai memisahkan setiap barisan dengan total <math>n+1</math> berdasarkan letak angka 2 pertamanya. Hal ini akan menghasilkan himpunan-himpunan berisi barisan yang dimulai dengan suku <math>(2,...), (1,2,...), ..., </math> sampai dua himpunan terakhir <math>\{(1,1,...,1,2)\}</math> dan <math>\{(1,1,...,1)\}</math> yang masing-masing memiliki kardinalitas 1. Menggunakan logika yang sama seperti sebelumnya, dengan menghitung kardinalitas setiap himpunan yang dihasilkan kita dapatkan<math display="block">F_{n+2} = F_n + F_{n-1} + ... + |\{(1,1,...,1,2)\}| + |\{(1,1,...,1)\}|</math>dengan dua himpunan terakhir memiliki nilai <math>F_1 = 1</math>. Hubungan ini dapat ditulis sebagai <math display="inline">F_{n+2} = \sum_{i=1}^n F_n + 1</math>, yang sama dengan identitas tersebut.
Argumen yang mirip, kali ini dengan memisahkan barisan berdasarkan letak angka 1 pertamanya, menghasilkan dua identitas baru:<math display="block">\sum_{i=0}^{n-1} F_{2 i+1} = F_{2 n}</math> dan<math display="block">\sum_{i=1}^{n} F_{2 i} = F_{2 n+1}-1.</math>Dalam bentuk kalimat, jumlah dari <math>n-1</math> bilangan Fibonacci berindeks-ganjil pertama adalah bilangan Fibonacci ke-<math>2n</math>, dan jumlah dari <math>n</math> bilangan Fibonacci berindeks-genap pertama adalah bilangan Fibonacci ke-<math>(2n+1)</math> dikurang 1.<ref>{{Citation|title=Fibonacci Numbers|last1=Vorobiev|first1=Nikolaĭ Nikolaevich|first2=Mircea|last2=Martin|publisher=Birkhäuser|year=2002|isbn=978-3-7643-6135-8|chapter=Chapter 1|pages=5–6}}</ref>
[[Berkas:Fibonacci_Squares.svg|ka|nirbing|260x260px]]
Trik yang berbeda dapat digunakan untuk membuktikan<math display="block">\sum_{i=1}^n F_i^2 = F_n F_{n+1}</math>atau secara kalimat, jumlah dari kuadrat <math>n</math> bilangan Fibonacci pertama sama dengan hasil perkalian bilangan Fibonnaci ke-<math>n</math> dan ke-<math>(n+1).</math> Untuk melihat hubungan ini, mulai dengan membuat [[persegi panjang]] berukuran <math>F_n \times F_{n+1}</math> dan bagi menjadi persegi-persegi dengan panjang sisi <math>F_n, F_{n-1}, ..., F_1</math>; identitas terbukti dengan membandingkan luas keduanya.
== Identitas lain ==
Banyak hubungan lainnya terkait bilangan Fibonacci yang dapat diperoleh dari berbagai metode. Beberapa di antaranya meliputi:<ref name="MathWorld">{{MathWorld|urlname=FibonacciNumber|title=Fibonacci Number|mode=cs2}}</ref>
=== Identitas Cassini dan Catalan ===
{{Main|Identitas Cassini dan Catalan}}
Identitas Cassini menyatakan bahwa<math display="block">{F_n}^2 - F_{n+1}F_{n-1} = (-1)^{n-1}</math>Identitas Catalan memperumum identitas tersebut menjadi:<math display="block">{F_n}^2 - F_{n+r}F_{n-r} = (-1)^{n-r}{F_r}^2</math>
=== Identitas d'Ocagne ===
Identitas ini menyatakan bahwa<math display="block">F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}</math><math display="block">F_{2 n} = {F_{n+1}}^2 - {F_{n-1}}^2 = F_n \left (F_{n+1}+F_{n-1} \right ) = F_nL_n</math>dengan <math>L_n</math> adalah [[bilangan Lucas]] ke-''n''. Identitas kedua di atas menunjukkan persamaan untuk menggandakan indeks <math>n.</math>Identitas lainnya jenis ini adalah<math display="block">F_{3 n} = 2{F_n}^3 + 3 F_n F_{n+1} F_{n-1} = 5{F_n}^3 + 3 (-1)^n F_n</math>yang didapatkan dari identitas Cassini. Secara lebih umum berlaku,<ref name="MathWorld" /><math display="block">F_{k n+c} = \sum_{i=0}^k {k\choose i} F_{c-i} {F_n}^i {F_{n+1}}^{k-i}.</math>atau juga dapat dituliskan sebagai<math display="block">F_{k n+c} = \sum_{i=0}^k {k\choose i} F_{c+i} {F_n}^i {F_{n-1}}^{k-i}.</math>
== Referensi ==
=== Catatan kaki penjelas ===
{{Notelist}}
=== Kutipan ===
{{Reflist}}
=== Kutipan ilmiah ===
* {{Citation|title=Strange Curves, Counting Rabbits, and Other Mathematical Explorations|first=Keith M|last=Ball|publisher=[[Princeton University Press]]|place=Princeton, NJ|year=2003|chapter=8: Fibonacci's Rabbits Revisited|isbn=978-0-691-11321-0}}.
* {{Citation|title=The Art of Proof: Basic Training for Deeper Mathematics|first1=Matthias|last1=Beck|first2=Ross|last2=Geoghegan|publisher=Springer|place=New York|year=2010|isbn=978-1-4419-7022-0}}.
* {{Citation|title=A Walk Through Combinatorics|edition=3rd|first=Miklós|last=Bóna|author-link=Miklós Bóna|publisher=World Scientific|place=New Jersey|year=2011|isbn=978-981-4335-23-2}}.
* {{anchor|Borwein}}{{Citation|last1=Borwein|first1=Jonathan M.|authorlink=Jonathan Borwein|authorlink2=Peter Borwein|first2=Peter B.|last2=Borwein|title=Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity|pages=91–101|publisher=Wiley|date=July 1998|url=http://www.wiley.com/WileyCDA/WileyTitle/productCd-047131515X.html|isbn=978-0-471-31515-5}}
* {{Citation|first=Franz|last=Lemmermeyer|year=2000|title=Reciprocity Laws: From Euler to Eisenstein|series=Springer Monographs in Mathematics|place=New York|publisher=Springer|isbn=978-3-540-66957-9}}.
* {{citation|last=Livio|first=Mario|author-link=Mario Livio|title=The Golden Ratio: The Story of Phi, the World's Most Astonishing Number|url=https://books.google.com/books?id=bUARfgWRH14C|orig-year=2002|edition=First trade paperback|year=2003|publisher=[[Random House|Broadway Books]]|location=New York City|isbn=0-7679-0816-3}}
* {{Citation|title=Théorie des nombres|first=Édouard|last=Lucas|publisher=Gauthier-Villars|year=1891|volume=1|language=fr|place=Paris|url=https://archive.org/details/thoriedesnombr01lucauoft}}.
* {{Citation|first=L. E.|last=Sigler|title=Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation|series=Sources and Studies in the History of Mathematics and Physical Sciences|publisher=Springer|year=2002|isbn=978-0-387-95419-6}}
== Lihat pula ==
* [[Program bilangan Fibonacci]]
* [[Wikisource:
== Pranala luar ==
* [http://arxiv.org/abs/physics/0411195 The Golden Mean and the Physics of Aesthetics]
* [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/phi.html The Golden Section: Phi] {{Webarchive|url=https://web.archive.org/web/20061205091146/http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/phi.html |date=2006-12-05 }}
* [http://semillon.wpi.edu/~aofa/AofA/msg00012.html
* [http://www.sju.edu/~rhall/Multi/rhythm2.pdf Hemachandra's application to Sanskrit poetry] {{Webarchive|url=https://web.archive.org/web/20120716224803/http://www.sju.edu/~rhall/Multi/rhythm2.pdf |date=2012-07-16 }}
* [http://goldennumber.net/fibonser.htm
* [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrep.html Representasi Bilangan Bulat menggunakan bilangan Fibonacci] {{Webarchive|url=https://web.archive.org/web/20071030055316/http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrep.html |date=2007-10-30 }}
{{Deret (matematika)}}
[[Kategori:Bilangan]]
| |||