Lihat sumber Barisan Fibonacci

{{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&nbsp;... both Gopala (before 1135&nbsp;AD) and Hemachandra (c.&nbsp;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)&nbsp;...}}</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}}.&nbsp;450&nbsp;SM–200&nbsp;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.&nbsp;100&nbsp;SM–c.&nbsp;350&nbsp;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.&nbsp;700 SM), yang telah hilang, tapi ada sebagai kutipan oleh Gopala (ca.&nbsp;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.&nbsp;1150) juga memiliki pengetahuan tentang barisan,<ref name="GlobalScience2" /> dalam tulisannya "jumlah dari sebelumnya dan yang sebelumnya lagi menjadi banyaknya&nbsp;... ''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>

=== Eropa ===
[[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&nbsp;−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&nbsp;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&nbsp;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&nbsp;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:Fibonacci Numbers|Tabel 500 bilangan Fibonacci pertama]]

== 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 Menghitung bilangan Fibonacci pada Mesin Turing] {{Webarchive|url=https://web.archive.org/web/20050206192956/http://semillon.wpi.edu/~aofa/AofA/msg00012.html |date=2005-02-06 }}
* [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 Deret Fibonacci] {{Webarchive|url=https://web.archive.org/web/20050122054810/http://goldennumber.net/fibonser.htm |date=2005-01-22 }}
* [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]]