Fibonacci, rumus binet dan aljabar linier

Saya yakin sudah familiar dengan bilangan Fibonacci atau disebut juga deret fibonacci. Suatu pola bilangan yang sederhana pada matematika tetapi ajaibnya pola tersebut banyak muncul di alam. Semua berawal dari 0 dan 1 lalu bilangan berikutnya merupakan hasil penhumlahan 2 bilangan sebelumnya

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

Bagaimana kita mencari bilangan ke-1000? atau ke-505? Untuk mencari bilangan ke-n dari bilangan fibonacci kita menggunakan rumus binet. Rumus tersebut berkata.

$F_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)$

Ada beberapa cara untuk membuktikan rumus tersebut, dengan rekursif, dengan induksi dll. Sahabat saya Hendry Dext telah menuliskan pembuktian rumus binet. Saya juga mau membuktikan rumus binet tetapi dengan metode yang berbeda dengan Hendry. Saya akan menggunakan aljabar linier.

Pertama-tama kita akan membentuk sistem persamaan linier dengan 2 persamaan. Kita tahu bahwa suku ke n+2 fibonacci merupakan penjumlahan dari suku ke n+1 dan suku ke n. Kita peroleh persamaan yang pertama $F_{n+2}=F_{n+1}+F_{n}$ . Selanjutnya kita butu persamaan ke-2, cukup persamaan sederhana $F_{n+1}=F_{n+1}+0$ . Kita peroleh sistem persamaan linier

$F_{n+2}=F_{n+1}+F_{n}$

$F_{n+1}=F_{n+1}+0$

Jika sistem persamaandiatas diubah ke dalam persamaan matriks, diperoleh

$\left[\begin{array}{c}F_{n+2}\\F_{n+1}\end{array}\right]=\left[\begin{array}{cc}1 & 1\\1 & 0\end{array}\right]\left[\begin{array}{c}F_{n+1}\\F_{n}\end{array}\right]$

Oya sebelumnya notasi $F_n$ merupakan suku ke-n dari fibonacci dengan $F_0=0$ dan $F_1=1$ .

Jika kita notasikan $U_{n+1}=\left[{F_{n+2}\atop F_{n+1}}\right]$ , $A=\left[\begin{array}{cc}1 & 1\\1 & 0\end{array}\right]$ dan $U_{n}=\left[{F_{n+1}\atop F_{n}}\right]$ . Kita peroleh aturan dalam fibonacci

$U_{n+1}=AU_{n}$

Nah sekarang mari kita mulai menghitung

Jadi diperoleh rumus umum

$u_n=A^nu_0$

$\left[{F_{n+1}\atop F_{n}}\right]=A^{n}\left[{1\atop 0}\right]$

Nah..sekarang pertanyaannya adalah bagaimana menghitung pangkat ke-n dari matriks $A$ secara cepat?

Cara cepatnya adalah dengan menggunakan 2 matriks spesial $S$ dan $P$ . Matriks $P$ adalah matriks diagonal yang memuat nilai-nilai eigen dari matriks $A$

$P=\left[\begin{array}{cc}\lambda_{1} & 0\\ 0 & \lambda_{2}\end{array}\right]$

Sedangkan matriks $S$ adalah matriks yang kolom-kolomnya merupakan vektor-vektor eigen dari $A$ .

$S=\left[v_{1}\, v_{2}\right]$

diperoleh

$A=SPS^{-1}$

Berdasarkan persamaan diatas, dengan mudah kita dapet menghitung $A^2$

$A^2=SPS^{-1}SPS^{-1}$

$A^2=SPIPS^{-1}$

$A^2=SP^2S^{-1}$

Karena $P$ merupakan matriks diagonal maka $P^2=\left[\begin{array}{cc}\lambda_{1}^2 & 0\\ 0 & \lambda_{2}^2\end{array}\right]$

Dengan cara sama kita mendapatkan $A^3=SP^3S^{-1}$ , dengan $P^3=\left[\begin{array}{cc}\lambda_{1}^3 & 0\\ 0 & \lambda_{2}^3\end{array}\right]$

Jadi dapat disimpulkan bahwa rumus mencari pangkat ke-n dari matriks $A$ adalah

$A^n=SP^nS^{-1}$

Nah sekarang berapa vektor eigen dan nilai eigen dari $A$ . Saya tidak akan melakukan perhitungan disini. Nilai egin dari $A$ adalah $\lambda_{1}=\frac{1+\sqrt{5}}{2}$ dan $\lambda_{1}=\frac{1-\sqrt{5}}{2}$ . Sedangkan vektor eigennya adalah $v_{1}=\left[{\lambda_{1}\atop 1}\right]$ dan $v_{2}=\left[{\lambda_{2}\atop 1}\right]$ . Silahkan kalain cek sendiri $Av_1=\lambda_{1}v_1$ dan $Av_2=\lambda_{1}v_2$ .

Kita peroleh

$S=\left[\begin{array}{cc}\lambda_{1} & \lambda_{2}\\1 & 1\end{array}\right]$

dan

$S^{-1}=\frac{1}{\lambda_{1}-\lambda_{2}}\left[\begin{array}{cc}1 & -\lambda_{2}\\-1 & \lambda_{1}\end{array}\right]$

Itu berarti kita peroleh

$u_n=A^nu_0$ .

$u_n=SP^nS^{-1}\left[{1\atop 0}\right]$

$u_{n}=SP^{n}\frac{1}{\lambda_{1}-\lambda_{2}}\left[{1\atop -1}\right]$

$u_{n}=S\frac{1}{\lambda_{1}-\lambda_{2}}\left[{\lambda_{1}^{n}\atop -\lambda_{2}^{n}}\right]$

$u_{n}=\frac{1}{\lambda_{1}-\lambda_{2}}\left[{\lambda_{1}^{n+1}-\lambda_{2}^{n+1}\atop \lambda_{1}^{n}-\lambda_{2}^{n}}\right]$

$\left[{F_{n+1}\atop F_{n}}\right]=\frac{1}{\lambda_{1}-\lambda_{2}}\left[{\lambda_{1}^{n+1}-\lambda_{2}^{n+1}\atop \lambda_{1}^{n}-\lambda_{2}^{n}}\right]$

Catetan: $\lambda_{1}-\lambda_{2}=\sqrt{5}$

Akhirnya kita dapat

$F_{n+1}=\frac{1}{\sqrt{5}}\left(\lambda_{1}^{n+1}-\lambda_{2}^{n+1}\right)$

$F_{n}=\frac{1}{\sqrt{5}}\left(\lambda_{1}^{n}-\lambda_{2}^{n}\right)$

Viola we got binet’s formula

———————————————————————————————————————————————-

**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**

About Nursatria

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika

View all posts by Nursatria →

47 Responses to Fibonacci, rumus binet dan aljabar linier

Pingback: Identitas Cassini | Blog Matematika Pak Satria
Fadly Ramadhan says:

March 20, 2016 at 09:16

itukan matriks fibonaccinya ukurannya 2×2.. untuk matriks fibonacci yang ukurannya 3×3 bagaimna ya mas?

- Aria Turns says:
  
  March 21, 2016 at 21:53
  
  mengapa harus 3×3 kalau 2×2 saja cukup
  
rismaya says:

November 24, 2015 at 12:55

Maaf mas punya referensi mengenai fibonacci ada fungsi paembangkit ? terimaksih

- Aria Turns says:
  
  November 24, 2015 at 19:22
  
  maaf gak ada
  
andi nofianto says:

September 2, 2015 at 15:55

(y)

sitimarfuah07 says:

March 3, 2014 at 13:42

Reblogged this on U-Math^^.

Silahkan, tinggalkan komentar Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

	Laili Islehatin on himpunan terbuka dan tertutup…
	Joseph Matt on Iklan Matematika oleh IBM
	fauzi on Dugaan Pólya
	fauzise on Akar dari akar dari akar …
	fauzi on Penjumlahan seluruh bilangan…