Kombinatorika

Penerapan Fungsi Pembangkit pada Barisan Fibonacci

Posted by Arini Soesatyo Putri on

Pada tanggal 23 November kemarin, kita memperingati hari Fibonacci. Mungkin Anda tidak sadar bahwa hari kemarin, tanggal 11-23, membentuk lima suku pertama barisan Fibonacci, yakni 0,1,1,2,3. Untuk memperingati hari Fibonacci, maka saya akan menuliskan artikel yang berkaitan dengan barisan Fibonacci. Dalam hal ini, kita akan melihat penerapan dari fungsi pembangkit untuk menentukan rumus eksplisit dari barisan Fibonacci.

Hari Fibonacci.PNG

Seperti yang kita ketahui, barisan Fibonacci didefinisikan secara rekursif sebagai

F_{0}=0, F_{1}=1, F_{n}=F_{n-1}+F_{n-2}, untuk n\geq 2

Kita dapat mulai menyusun fungsi pembangkit dari barisan Fibonacci sebagai deret pangkat yang memiliki koefisien-koefisien barisan Fibonacci, yakni

F(x)=\sum_{n=0}^{\infty}F_{n}x^{n}

Karena F_{n}=F_{n-1}+F_{n-2} untuk setiap n\geq 2, maka dapat dituliskan

F(x)=x+\sum_{n=2}^{\infty}(F_{n-1}+F_{n-2})x^{n}=x+\sum_{n=2}^{\infty}F_{n-1}x^{n}+\sum_{n=2}^{\infty}F_{n-2}x^{n}

Selanjutnya karena masing-masing jumlah pada ruas kanan dapat dituliskan sebagai

\sum_{n=2}^{\infty}F_{n-1}x^{n}=x\sum_{n=2}^{\infty}F_{n-1}x^{n-1}=x\sum_{n=1}^{\infty}F_{n}x^{n}=xF(x)

dan

\sum_{n=2}^{\infty} F_{n-2}x^{n}=x^{2}\sum_{n=2}^{\infty}F_{n-2}x^{n-2}=x^{2}\sum_{n=0}^{\infty}F_{n}x^{n}=x^{2}F(x)

Jadi kita peroleh

F(x)=x+xF(x)+x^{2}F(x)

F(x)=\frac{x}{1-x-x^{2}}

di mana F(x) merupakan fungsi pembangkit dari barisan Fibonacci. Perjuangan kita belum selesai sampai di sini, sebab tujuan kita adalah untuk menentukan deret pangkat lain dari F(x). Untuk mencarinya, pandang penyebut dari F(x), yakni 1-x-x^{2}=-(x+\phi)(x+\psi) yang memiliki akar-akar -\phi dan -\psi, dengan

\phi =\frac{1+\sqrt{5}}{2}     dan     \psi =\frac{1-\sqrt{5}}{2}

Jadi dapat dituliskan

F(x)=-\frac{x}{(x+\phi)(x+\psi)}

Nah, dengan menggunakan dekomposisi pecahan parsial, bentuk di atas dapat dijabarkan kembali menjadi

F(x)=\frac{1}{\sqrt{5}}\frac{\psi}{x+\psi}-\frac{1}{\sqrt{5}}\frac{\phi}{x+\phi}=\frac{1}{\sqrt{5}}(\frac{\psi}{x+\psi}-\frac{\phi}{x+\phi})

Sekarang kita ingin merepresentasikan bentuk yang ada di dalam kurung pada persamaan di atas ke dalam suatu deret pangkat. Bagaimana caranya? Karena baik \frac{\psi}{x+\psi} maupun \frac{\phi}{x+\phi} keduanya menyerupai jumlah deret geometri, yakni

\sum_{n=0}x^{n}=\frac{1}{1-x}    dengan |x|<1

Maka dapat dituliskan

\frac{\psi}{x+\psi}=\frac{1}{1+\frac{x}{\psi}}=\frac{1}{1-\phi x}=\sum_{n=0}^{\infty}\phi^{n}x^{n}

(Perhatikan bahwa kita memiliki hubungan \phi=-1/\psi). Dengan cara yang serupa diperoleh

\frac{\phi}{x+\phi}=\sum_{n=0}^{\infty}\psi^{n}x^{n}

Jadi kita dapatkan deret pangkat dari fungsi pembangkit F(x) sebagai

F(x)=\frac{1}{\sqrt{5}}(\frac{\psi}{x+\psi}-\frac{\phi}{x+\phi})=\sum_{n=0}^{\infty} \frac{1}{\sqrt{5}}(\phi^{n}-\psi^{n})x^{n}

Karena di awal telah diketahui bahwa F(x)=\sum_{n=0}^{\infty}F_{n}x^{n}, maka dengan menyamakan koefisien dari x^{n} didapat

F_{n}=\frac{1}{\sqrt{5}}(\phi^{n}-\psi^{n})

Substitusikan kembali nilai \phi dan \psi untuk memperoleh

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

Voila! Rumus eksplisit dari barisan Fibonacci pun berhasil kita dapatkan. Dengan mensubstitusikan nilai n=0,1,2,3,\dots, ke dalam rumus F_{n} di atas, maka akan kita peroleh barisan

0,1,1,2,3,5,\dots

seperti yang diharapkan.

Selamat Hari Fibonacci!

Sumber Gambar

Fibonacci Day [https://id.pinterest.com/pin/157414949459912097/]

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Gravatar
Logo WordPress.com

You are commenting using your WordPress.com account. ( Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. ( Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. ( Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. ( Logout /  Ubah )

Batal

Connecting to %s