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 . 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
: 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. Barisan ini diberi nama dengan nama matematikawan Italia Leonardo da Pisa, juga dikenal sebagai Fibonacci, yang memperkenalkannya ke dunia matematika Eropa Barat lewat bukunya **' tahun 1202.

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==


Barisan Fibonacci dapat didefinisikan oleh [[relasi perulangan]] <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 . Dua puluh bilangan  Fibonacci pertama adalah:
:

== Asal mula ==

=== India ===


Barisan Fibonacci muncul dalam [[matematika India]], dalam hubungannya dengan [[Chanda|ilmu irama Veda]]. 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>

Pemahaman terkait barisan Fibonacci disampaikan pertama kali setidaknya oleh [[Pingala]] (.&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> [[Bharata Muni]] juga menuliskan pemahamannya terkait barisan Fibonacci dalam ''[[Natya Shastra]]'' (ca.&nbsp;100&nbsp;SM–c.&nbsp;350&nbsp;SM). 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). [[Hemachandra]] (ca.&nbsp;1150) juga memiliki pengetahuan tentang barisan, dalam tulisannya "jumlah dari sebelumnya dan yang sebelumnya lagi menjadi banyaknya&nbsp;... ''mātrā-vṛtta'' selanjutnya."

=== Eropa ===

Bilangan Fibonacci pertama kali muncul pada buku **' (*The Book of Calculation*, 1202) oleh Fibonacci, yang digunakan untuk menghitung pertumbuhan populasi kelinci. 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?

* 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 ) ditambah jumlah dari pasangan yang hidup bulan lalu (bulan ).  Jumlah pasangan bulan ke- adalah bilangan Fibonacci ke-.

Nama "barisan Fibonacci" pertama kali digunakan oleh ahli teori bilangan abad ke-19 Édouard Lucas.
## Hubungan dengan rasio emas

### Rumus eksplisit
Sama seperti barisan lainnya yang didefinisikan sebagai relasi perulangan dengan koefisien konstan, bilangan Fibonacci memiliki ekspresi bentuk-tertutup. 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:
F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5},
dengan
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\ldots
dikenal dengan sebutan rasio emas, dan \psi adalah konjugatnya:
\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\ldots.
Karena \psi = -\varphi^{-1}, rumus tersebut juga dapat dituliskan sebagai
F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt 5} = \frac{\varphi^n - (-\varphi)^{-n}}{2\varphi - 1}.
Untuk melihat hubungan antara barisan Fibonacci dengan kedua konstanta tersebut, perhatikan bahwa \varphi dan \psi keduanya merupakan solusi dari persamaan x^2 = x + 1 dan (sebagai akibatnya) x^n = x^{n-1} + x^{n-2}. Ini mengartikan perpangkatan dari  \varphi dan \psi  memenuhi relasi perulangan Fibonacci; dengan kata lain,\begin{align}
\varphi^n &= \varphi^{n-1} + \varphi^{n-2}, \\[3mu]
\psi^n &= \psi^{n-1} + \psi^{n-2}.
\end{align}Dari hasil tersebut, semua barisan yang didefinisikan sebagaiU_n=a \varphi^n + b \psi^njuga memenuhi relasi perulangan yang sama, karena\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}Jika nilai a dan b dipilih sedemikian sehingga U_0 = 0 dan U_1 = 1, maka barisan U_n yang terbentuk pastilah barisan Fibonacci. Pemilihan ini sama saja dengan mengharuskan a dan b memenuhi sistem persamaan:
\begin{align} a + b &= U_0 = 0 \\ \varphi a + \psi b &= U_1 = 1\end{align}
yang memiliki solusi
a = \frac{1}{\varphi-\psi} = \frac{1}{\sqrt 5},\quad  b = -a,
sama seperti rumus Binet.

Untuk sebarang nilai awal U_0 dan U_1, rumus Binet yang lebih umum adalah: U_n = a\varphi^n + b\psi^n dengan\begin{align}
a&=\frac{U_1-U_0\psi}{\sqrt 5}, \\[3mu]
b&=\frac{U_0\varphi-U_1}{\sqrt 5}.
\end{align}

### Perhitungan dengan pembulatan
Karena suku \left|\frac{\psi^{n}}{\sqrt 5}\right| pada rumus Binet selalu kurang dari \tfrac{1}{2} untuk n\geq0 , bilangan F_n menjadi bilangan bulat terdekat dengan  \frac{\varphi^n}{\sqrt 5} . Akibatnya, bilangan Fibonacci juga dapat dihasilkan dengan membulatkan:F_n=\left\lfloor\frac{\varphi^n}{\sqrt 5}\right\rceil,\ n \geq 0.Faktanya, galat pembulatan akan mengecil dengan cepat seiring membesarnya n, menjadi kurang dari 0,1 untuk n\geq 4, dan kurang dari 0,01 untuk n\geq 8. Rumus ini juga mudah diinvers untuk mendapatkan indeks dari bilangan Fibonacci F:n(F) = \left\lfloor  \log_\varphi \sqrt{5}F\right\rceil,\ F \geq 1.Jika diubah agar melakukan pembulatan ke bawah, rumus akan menghasilkan indeks bilangan Fibonacci terbesar yang tidak lebih dari F.

### Identifikasi
Rumus Binet memberikan bukti bahwa bilangan bulat positif x merupakan bilangan Fibonacci jika dan hanya jika setidaknya salah satu dari  5x^2+4 atau 5x^2-4 merupakan kuadrat sempurna. Hal ini dapat terlihat mengalikan rumus Binet, yang dituliskan sebagai F_n = (\varphi^n - (-1)^n \varphi^{-n}) / \sqrt{5}, dengan \sqrt{5} \varphi^n lalu diselesaikan sebagai persamaan kuadrat dalam \varphi^n menggunakan rumus kuadratik, menghasilkan:\varphi^n = \frac{F_n\sqrt{5} \pm \sqrt{5{F_n}^2 + 4(-1)^n}}{2}.Membandingkan bentuk ini dengan \varphi^n = F_n \varphi + F_{n-1} = (F_n\sqrt{5} + F_n + 2 F_{n-1})/2 didapatkan5{F_n}^2 + 4(-1)^n = (F_n + 2F_{n-1})^2\,.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 F_n dapat dianggap sebagai banyaknya (mungkin kosong) barisan berisi angka 1 dan 2 dengan jumlah total n-1. Hal ini dapat dipilih sebagai definisi dari F_n, dengan konvensi F_0 = 0 yang mengartikan tidak ada barisan macam itu dengan total&nbsp;−1, dan F_1 = 1 yang mengartikan ada satu barisan -- yakni barisan dengan panjang 0 -- dengan total 0. Menggunakan notasi |{...}| untuk menyatakan kardinalitas dari himpunan, berikut beberapa bilangan Fibonacci pertama:

: F_0 = 0 = |\{\}|
: F_1 = 1 = |\{()\}|
: F_2 = 1 = |\{(1)\}|
: F_3 = 2 = |\{(1,1),(2)\}|
: F_4 = 3 = |\{(1,1,1),(1,2),(2,1)\}|
: F_5 = 5 = |\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|

Dalam sudut pandang ini, hubungan perulangan F_n = F_{n-1} + F_{n-2} dapat dianggap sebagai memisahkan barisan-barisan penyusun F_n menjadi dua himpunan tidak-beririsan, yang masing-masing dimulai dari angka 1 atau 2:F_n = |\{(1,...),(1,...),...\}| + |\{(2,...),(2,...),...\}|Mengabaikan suku pertama, jumlah total setiap suku barisan pada kedua himpunan tersebut masing-masing adalah n-2 dan n-3. Nilai ini adalah kardinalitas dari F_{n-1} dan F_{n-2}, menunjukkan bahwa memang F_n = F_{n-1} + F_{n-2}.

Dengan cara yang mirip, dapat ditunjukkan bahwa jumlah dari n bilangan Fibonacci pertama sama dengan bilangan Fibonacci ke-(n+2) dikurang&nbsp;1. Secara matematis:\sum_{i=1}^n F_i = F_{n+2} - 1Identitas ini dapat dilihat sebagai memisahkan setiap barisan dengan total n+1 berdasarkan letak angka 2 pertamanya. Hal ini akan menghasilkan himpunan-himpunan berisi barisan yang dimulai dengan suku (2,...), (1,2,...), ...,  sampai dua himpunan terakhir \{(1,1,...,1,2)\} dan \{(1,1,...,1)\} yang masing-masing memiliki kardinalitas 1. Menggunakan logika yang sama seperti sebelumnya, dengan menghitung kardinalitas setiap himpunan yang dihasilkan kita dapatkanF_{n+2} = F_n + F_{n-1} + ... + |\{(1,1,...,1,2)\}| + |\{(1,1,...,1)\}|dengan dua himpunan terakhir memiliki nilai F_1 = 1. Hubungan ini dapat ditulis sebagai F_{n+2} = \sum_{i=1}^n F_n + 1, yang sama dengan identitas tersebut.

Argumen yang mirip, kali ini dengan memisahkan barisan berdasarkan letak angka&nbsp;1 pertamanya, menghasilkan dua identitas baru:\sum_{i=0}^{n-1} F_{2 i+1} = F_{2 n} dan\sum_{i=1}^{n} F_{2 i} = F_{2 n+1}-1.Dalam bentuk kalimat, jumlah dari n-1 bilangan Fibonacci berindeks-ganjil pertama adalah bilangan Fibonacci ke-2n, dan jumlah dari n bilangan Fibonacci berindeks-genap pertama adalah bilangan Fibonacci ke-(2n+1) dikurang&nbsp;1.

Trik yang berbeda dapat digunakan untuk membuktikan\sum_{i=1}^n F_i^2 = F_n F_{n+1}atau secara kalimat, jumlah dari kuadrat n bilangan Fibonacci pertama sama dengan hasil perkalian bilangan Fibonnaci ke-n dan ke-(n+1). Untuk melihat hubungan ini, mulai dengan membuat persegi panjang berukuran F_n \times F_{n+1} dan bagi menjadi persegi-persegi dengan panjang sisi F_n, F_{n-1}, ..., F_1; identitas terbukti dengan membandingkan luas keduanya.

## Identitas lain
Banyak hubungan lainnya terkait bilangan Fibonacci yang dapat diperoleh dari berbagai metode. Beberapa di antaranya meliputi:

### Identitas Cassini dan Catalan

Identitas Cassini menyatakan bahwa{F_n}^2 - F_{n+1}F_{n-1} = (-1)^{n-1}Identitas Catalan memperumum identitas tersebut menjadi:{F_n}^2 - F_{n+r}F_{n-r} = (-1)^{n-r}{F_r}^2

### Identitas d'Ocagne
Identitas ini menyatakan bahwaF_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}F_{2 n} = {F_{n+1}}^2 - {F_{n-1}}^2 = F_n \left (F_{n+1}+F_{n-1} \right ) = F_nL_ndengan L_n adalah bilangan Lucas ke-*n*. Identitas kedua di atas menunjukkan persamaan untuk menggandakan indeks n.Identitas lainnya jenis ini adalahF_{3 n} = 2{F_n}^3 + 3 F_n F_{n+1} F_{n-1} = 5{F_n}^3 + 3 (-1)^n F_nyang didapatkan dari identitas Cassini. Secara lebih umum berlaku,F_{k n+c} = \sum_{i=0}^k {k\choose i} F_{c-i} {F_n}^i {F_{n+1}}^{k-i}.atau juga dapat dituliskan sebagaiF_{k n+c} = \sum_{i=0}^k {k\choose i} F_{c+i} {F_n}^i {F_{n-1}}^{k-i}.

## Referensi

### Catatan kaki penjelas

### Kutipan

### Kutipan ilmiah

* .
* .
* .
* 
* .
* 
* .
* 

## Lihat pula
* Program bilangan Fibonacci
* 

## Pranala luar
* The Golden Mean and the Physics of Aesthetics
* The Golden Section: Phi 
* Menghitung bilangan Fibonacci pada Mesin Turing 
* Hemachandra's application to Sanskrit poetry 
* Deret Fibonacci 
* Representasi Bilangan Bulat menggunakan bilangan Fibonacci