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.

{\displaystyle 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**

41 thoughts on “Fibonacci, rumus binet dan aljabar linier

Silahkan, tinggalkan komentar

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s