PENENTUAN SOLUSI RELASI REKUREN DARI BILANGAN FIBONACCI DAN BILANGAN LUCAS DENGAN MENGGUNAKAN FUNGSI PEMBANGKIT

Prosiding Seminar Nasional Matematika dan Terapannya 2016 p-ISSN : 2550-0384; e-ISSN : 2550-0392

PENENTUAN SOLUSI RELASI REKUREN DARI BILANGAN FIBONACCI DAN BILANGAN LUCAS DENGAN MENGGUNAKAN FUNGSI PEMBANGKIT Linatus Shofiyah Universitas Jenderal Soedirman [email protected] Siti Rahmah Nurshiami Universitas Jenderal Soedirman Triyani Universitas Jenderal Soedirman

ABSTRACT. The research studied solution of recurrent relation on Fibonacci and Lucas numbers using a generating functions. As well as some relationships between these two solutions. The solutions and relationships are found using the generating functions which is a power series centering at zero. The recurrent relation solution of Fibonacci number is a multiple constant 1 5 of positive characteristics root to the power of n minus negative characteristics root to the power of n. Meanwhile the recurrent relation solution of Lucas number is the sum of positive characteristics root to the power of n and negative characteristics root to the power of n. There is a linear relationships between the Fibonacci numbers or Lucas numbers or their multiples. Fibonacci numbers are not only obtained from the sums and differences operation between elements of Fibonacci numbers, but also between elements of Fibonacci and Lucas numbers and between two Lucas numbers. Likewise vice versa holds for Lucas numbers. Keywords: recurrent relation solution, Fibonacci numbers, Lucas numbers, generating functions ABSTRAK. Pada penelitian ini dikaji mengenai penentuan solusi relasi rekuren bilangan Fibonacci dan bilangan Lucas dengan menggunakan fungsi pembangkit. Selain itu, pada penelitian ini juga ditentukan hubungan kedua bilangan tersebut yang dicari dengan menggunakan fungsi pembangkit, yaitu berupa deret pangkat tak hingga dengan pusat di nol. Solusi relasi rekuren baik untuk bilangan Fibonacci maupun Lucas berupa suku ke-n pada deret pangkat tersebut. Dari hasil penelitian diperoleh bahwa solusi relasi rekuren 1 5 dari akar karakteristik positif berpangkat n bilangan Fibonacci adalah kelipatan dikurangi akar karakteristik negatif berpangkat n. Sementara itu, solusi relasi rekuren dari bilangan Lucas adalah jumlah dari akar karakteristik positif berpangkat n dan akar karakteristik negatif berpangkat n. Terdapat hubungan linier antara bilangan Fibonacci dan bilangan Lucas. Hal ini ditunjukkan dengan diperolehnya bilangan Fibonacci yang tidak hanya dihasilkan dari penjumlahan suku-suku pada bilangan Fibonacci, melainkan

Penentuan Solusi Relasi Rekuren dari Bilangan Fibonacci

37

dapat dihasilkan dari operasi penjumlahan dan pengurangan antara bilangan Fibonacci dan Lucas ataupun antara dua bilangan Lucas. Begitu juga sebaliknya berlaku untuk bilangan Lucas.

Kata kunci: solusi relasi rekuren, bilangan Fibonacci, bilangan Lucas, fungsi pembangkit. 1. PENDAHULUAN Bilangan Fibonacci menarik untuk dipelajari karena banyak kejadian di sekitar yang mengikuti pola bilangan Fibonacci. Asal penemuan bilangan Fibonacci juga diperoleh berdasarkan kejadian sekitar, yaitu pada pengamatan hasil perkembangbiakan sepasang kelinci setelah n bulan dengan asumsi tidak ada kelinci yang mati. Jumlah pasangan kelinci dalam n bulan atau Fn membentuk suatu relasi rekuren antara jumlah tepat dua bulan sebelumnya dengan F0  0 dan F1  1 . Berdasarkan pengamatan tersebut ditemukanlah barisan

bilangan Fibonacci, yaitu 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,... . Bilangan Fibonacci selanjutnya dikembangkan oleh Edouard Lucas pada akhir abad ke-19, dengan mempelajari bilangan Fibonacci secara mendalam. Lucas mendapatkan bilangan baru yang diberi nama bilangan Lucas. Karena merupakan pengembangan dari bilangan Fibonacci, bilangan Lucas mempunyai relasi rekuren sama dengan bilangan Fibonacci. Bilangan Lucas ke- n atau Ln dihasilkan dari penjumlahan dua suku sebelumnya, yang membedakan adalah jika nilai awal pada bilangan Fibonacci adalah F0  0 dan F1  1 , maka nilai awal untuk bilangan Lucas adalah L0  2 dan L1  1 . Dengan demikian diperoleh barisan bilangan Lucas yaitu 2, 1, 3, 4, 7, 11, 18, 29, 47, 76,... . Sebuah barisan dapat dinyatakan dalam rumus eksplisit maupun dengan menggunakan relasi rekuren. Relasi rekuren merupakan barisan dari suku-suku dengan nilai suatu suku adalah fungsi dari suku-suku sebelumnya. Suatu barisan dikatakan solusi relasi rekuren dari suatu relasi rekuren jika suku-suku pada barisan tersebut memenuhi relasi rekuren. Solusi relasi rekuren merupakan rumus eksplisit yang dapat digunakan untuk menentukan suku ke- n dari suatu barisan

Purwokerto, 3 Desember 2016

38

L. Shofiyah d.k.k.

tanpa melibatkan suku-suku lain dari barisan tersebut. Karena barisan dapat dinyatakan dalam bentuk relasi rekuren dan dicari solusinya, maka barisan bilangan Fibonacci dan bilangan Lucas dapat dicari solusi relasi rekurennya. Solusi relasi rekuren dari barisan bilangan Fibonacci dan bilangan Lucas dapat dicari dengan menggunakan pendekatan iteratif, relasi rekuren linier, dan fungsi pembangkit (Rosen, 2007). Namun pada penelitian ini, solusi relasi rekuren dari barisan bilangan Fibonacci dan Lucas dicari menggunakan fungsi pembangkit, karena fungsi pembangkit dapat mengubah barisan ke dalam bentuk fungsi, dan dari fungsi yang diperoleh terdapat banyak metode untuk menyelesaikan solusinya tergantung dari bentuk fungsi tersebut. Oleh karena itu, pada penelitian ini penulis tertarik untuk mengkaji penentuan solusi relasi rekuren dari bilangan Fibonacci dan bilangan Lucas dengan menggunakan fungsi pembangkit. 2. HASIL DAN PEMBAHASAN 2.1 Solusi Relasi Rekuren Bilangan Fibonacci Korespondensi

antara

barisan bilangan Fibonacci

dengan fungsi

pembangkit diindikasikan oleh panah dua arah sebagai 

Fn   F0 , F1 , F2 , F3 ,...  F0  F1 x  F2 x 2  F3 x3  ...   Fn x n , n 0

dengan n  0 . Solusi relasi rekuren bilangan Fibonacci adalah koefisien dari x

n

pada deret pangkat tak hingga tersebut. Bilangan Fibonacci didefinisikan secara rekuren

Fn  Fn1  Fn2 , dengan Fn menyatakan suku ke- n dari bilangan

Fibonacci dengan nilai awal F0  0 dan F1  1 . Misal fungsi pembangkit dari barisan Fibonacci adalah 

g  x   F0  F1 x  F2 x 2  F3 x3  ...  Fn x n  ...   Fn x n .

(1)

n 0

2

Kalikan persamaan (1) dengan x dan x sehingga diperoleh xg  x   F0 x  F1 x 2  F2 x3  F3 x 4  ...  Fn1x n  ... .

(2)

x2 g  x   F0 x 2  F1 x3  F2 x 4  F3 x5  ...  Fn2 x n  ... .

(3)



39

Jika nilai awal F0  0 , F1  1 dan relasi rekuren Fn  Fn1  Fn2 mengakibatkan

Fn  Fn1  Fn2  0 untuk n  2 digunakan ketika persamaan (1) dikurangkan dengan persamaan (2) dan (3) , maka g  x   xg  x   x 2 g  x   F0   F1  F0  x   F2  F1  F0  x 2 

 F3  F2  F1  x3  ...   Fn  Fn1  Fn2  x n  ...,

1  x  x  g  x   x, 2

g  x 

x . 1  x  x2

(4)

Berdasarkan persamaan (4), fungsi pembangkit barisan Fibonacci berbentuk fungsi pembagian polinomial

x . Untuk menyelesaikannya 1  x  x2

digunakan metode pecahan parsial, yaitu dengan mendekomposisikan menjadi bentuk jumlahan suku suku

x  1  x  x2

A  1 5  x    2 



B  1 5  x    2 

,

x A B   , 2 1 x  x 1 x 1  x dengan nilai  

1 5 1 5 dan   . Dengan menggunakan nilai  dan 2 2

tersebut diperoleh nilai A 

1 5

dan B 

(5)

(6)



1 . Selanjutnya nilai A dan B 5

disubstitusikan ke persamaan (6) sehingga diperoleh  x 1  1 1    . 2 1 x  x 5  1   x  1   x  

(7)

Substitusi persamaan (7) ke dalam fungsi pembangkit bilangan Fibonacci pada persamaan (4) sehingga diperoleh


40

L. Shofiyah d.k.k.

x , 1  x  x2  1  1 1    , 5  1   x  1   x   1   n n  n n     x   x  , 5  n 0 n 0 

g  x 







5g  x     n   n xn , n 0





g  x  

n

n 5

n 0

x . n

(8)

Berdasarkan persamaan (1) dan (8) dapat disimpulkan bahwa 



F x   n

n 0

n



n

n 5

n 0

x

n

(9)

n

Pada persamaan (9) diperoleh koefisien dari x pada fungsi pembangkit bilangan Fibonacci yang selanjutnya disebut dengan solusi relasi rekuren bilangan Fibonacci yaitu Fn

dengan nilai  

 

n

n 5

,

(10)

1 5 1 5 ,  dan n  0 . 2 2

Nilai  dan  tersebut merupakan akar karakteristik dari bilangan Fibonacci. Akar karakteristik bilangan Fibonacci memiliki beberapa sifat yang diberikan pada proposisi berikut. Proposisi 1 Misalkan  dan  merupakan akar karakteristik dari bilangan Fibonacci dengan nilai  

1 5 1 5 dan   , maka berlaku sifat: 2 2

1)     1

3)   1

2)     5

4)     1

2 5)     1

2



41

Berdasarkan Proposisi 1, muncul beberapa akibat yang diberikan pada Akibat 1 berikut. Akibat 1 1)   1      5

 3)      1

2)   1      5

 4)       1

Dari persamaan (9) kemudian dikembangkan fungsi pembangkit untuk bilangan Fibonacci ke-(m+n) pada Proposisi 2 berikut. Proposisi 2 Misalkan

Fm n menyatakan bilangan Fibonacci ke-(m+n), maka fungsi

pembangkit untuk Fm n yaitu 

F n 0

m n

xn 

Fm  Fm1 x , 1  x  x2

dengan m adalah bilangan bulat yang ditentukan dan n  0 . Bukti: 



 Fmn x n   n 0

n 0

 mn   mn 5

xn ,



 1  m  n n m   x    n xn  ,    5  n 0 n 0 



1  m 1  1  m   ,   5   1 x   1  x  



m m m 1 m 1 1            x   ,   1   x 1   x  5  



Fm  Fm 1 x . 1  x  x2

■

Proposisi 2 dapat digunakan dengan mengambil m bilangan bulat yang ditentukan. Berikut diberikan fungsi pembangkit dari Fm n dengan mengambil kasus untuk

m  2, 1, 0, 1, 2 . Purwokerto, 3 Desember 2016

42

L. Shofiyah d.k.k. Tabel 1 Daftar fungsi pembangkit dan solusi dari Fm  n dengan m  2, 1, 0, 1, 2

No

Fm n

1

Fn 2

2

Fn 1

3

Fn

4

Fn 1

5

Fn 2

Fungsi pembangkit

Solusi



  n2 5 n 1    n 1 5 n  n 5 n 1    n 1 5 n2    n2 5

1  2 x 1  x  x2 1 x 1  x  x2 x 1  x  x2 1 1  x  x2 1 x 1  x  x2

n2

2.2 Solusi Relasi Rekuren Bilangan Lucas Bilangan Lucas merupakan pengembangan dari bilangan Fibonacci, oleh karena itu barisan bilangan Lucas juga dapat dicari solusinya dengan cara yang sama seperti pada bilangan Fibonacci. Bilangan Lucas didefinisikan secara rekuren Ln  Ln1  Ln2 . Ln menyatakan suku ke-n dari bilangan Lucas dengan nilai awal L0  2 dan L1  1 . Misal fungsi pembangkit dari barisan Lucas adalah 

g  x   L0  L1 x  L2 x 2  L3 x3  ...  Ln x n  ...   Ln x n .

(11)

n 0

2 Kalikan persamaan (11) dengan x dan x sehingga diperoleh

xg  x   L0 x  L1 x 2  L2 x3  L3 x 4  ...  Ln1 x n  ... ,

(12)

x2 g  x   L0 x 2  L1x3  L2 x 4  L3 x5  ...  Ln2 x n  ... .

(13)

Jika nilai awal L0  2 , L1  1 dan relasi rekuren Ln  Ln1  Ln2 mengakibatkan

Ln  Ln1  Ln2  0 untuk n  2 digunakan ketika persamaan (11) dikurangkan dengan persamaan (12) dan (13) , maka

g  x   xg  x   x 2 g  x   L0   L1  L0  x   L2  L1  L0  x 2 

 L3  L2  L1  x3  ...   Ln  Ln1  Ln2  x n  ...,

1  x  x  g  x   2  x, 2



g  x 

43

2 x . 1  x  x2

(14)

Berdasarkan persamaan (14), fungsi pembangkit barisan Lucas berbentuk fungsi pembagian polinomial

2 x , yang kemudian didekomposisikan 1  x  x2

menjadi bentuk jumlahan suku suku sebagai berikut.

2 x A B   , 2 1 x  x 1 x 1  x

(15)

dengan nilai  dan  yang sama dengan bilangan Fibonacci diperoleh nilai A  1 dan B  1 . Selanjutnya nilai A dan B disubstitusikan ke dalam persamaan

(15) sehingga diperoleh 2 x 1 1 .   2 1 x  x 1   x  1   x 

(16)

Substitusi persamaan (16) ke persamaan (14) sehingga diperoleh

2 x , 1  x  x2 1 1   , 1   x  1   x 

g  x 





n 0

n 0

   n x n   n x n , 





   n   n xn . n 0

(17)

Berdasarkan persamaan (11) dan (17) dapat disimpulkan bahwa 



 L x    n

n 0

n

n 0

n



  n xn .

(18)

Pada persamaan (18) diperoleh koefisien dari x

n

pada fungsi pembangkit

bilangan Lucas yang selanjutnya disebut dengan solusi relasi rekuren bilangan Lucas yaitu

Ln   n   n 


,

(19)

44

L. Shofiyah d.k.k.

dengan nilai  

1 5 1 5 ,  dan n  0 . Bilangan Fibonacci dan bilangan 2 2

Lucas memiliki nilai  dan  yang sama. Nilai  dan  tersebut merupakan akar karakteristik dari bilangan Fibonacci, sehingga  dan  juga merupakan akar karakteristik dari bilangan Lucas. Dengan demikian Proposisi 1 dan Akibat 1 juga berlaku untuk bilangan Lucas. Berdasarkan persamaan (18) diperoleh bahwa fungsi pembangkit untuk 



 L x    n

bilangan Lucas ke-n adalah

n 0

n

n



  n x n . Selanjutnya dengan

n 0

menggunakan cara yang sama seperti pada bilangan Fibonacci, dapat diperoleh fungsi pembangkit untuk bilangan Lucas ke-( m  n ) pada Proposisi 3 berikut. Proposisi 3 Misalkan Lm n menyatakan bilangan Lucas ke-(m+n), maka fungsi pembangkit untuk Lm n yaitu 

L n 0

m n

xn 

Lm  Lm1 x 1  x  x2

dengan m adalah bilangan bulat yang ditentukan dan n  0 . Proposisi 3 dapat digunakan dengan mengambil m sembarang bilangan bulat yang ditentukan. Berikut diberikan fungsi pembangkit dari Lm n dengan mengambil kasus untuk m  2, 1, 0, 1, 2 . Tabel 2 Daftar fungsi pembangkit dan solusi dari Lm n dengan m  2, 1, 0, 1, 2 No

Lm n

1

Ln 2

2

Ln 1

3

Ln

Fungsi pembangkit 3  4x 1  x  x2 1  3x 1  x  x2 2 x 1  x  x2

Solusi

 n2   n2

 n1   n1

n  n



4

Ln 1

5

Ln  2

1 2x 1  x  x2 3 x 1  x  x2

45

 n1   n1

 n2   n2

2.3 Hubungan Bilangan Fibonacci dan Bilangan Lucas Terdapat beberapa hubungan linier yang hanya melibatkan operasi penjumlahan atau pengurangan dari bilangan Fibonacci atau bilangan Lucas maupun kelipatannya seperti yang tertera pada Proposisi 4 berikut. Proposisi 4 Misalkan Fn merupakan bilangan Fibonacci ke- n dan Ln merupakan bilangan Lucas ke- n , maka hubungan bilangan Fibonacci dan bilangan Lucas sebagai berikut: 1) 5Fn  Ln1  Ln1

7) 2Fn1  Fn  Ln

2) Ln  Fn1  Fn1

8) 2Ln1  Ln  5Fn

3) Ln  Fn  2Fn1

9) 2Fn 2  3Fn  Ln

4) 5Fn  Ln  2Ln1

10) 2Ln 2  3Ln  5Fn

5) Fn 2  Fn2  Ln

11) 2Fn 2  3Fn  Ln

6) 5Fn  Ln 2  Ln2

12) 2Ln2  3Ln  5Fn

Dengan menggunakan fakta bahwa dua buah deret dikatakan sama jika dan hanya jika koefisien yang bersesuaian adalah sama, maka hubungan bilangan Fibonacci dan Lucas pada Proposisi 4 dapat dibuktikan. Sebagai contoh, akan dibuktikan bahwa Proposisi 4 point (1) benar. Berdasarkan Tabel 1 dan Tabel 2 maka fungsi pembangkit untuk Proposisi 4 point (1) adalah 5x 1  3x 1 2x .   2 2 1 x  x 1  x  x 1  x  x2

Dari persamaan (20) mengakibatkan


(20)

46

L. Shofiyah d.k.k. 





 5F   L n 0

n

n 0

n 1

x   Ln 1 x n , n

n 0



   Ln 1  Ln 1  x n . n 0

Oleh karena itu formula 5Fn  Ln1  Ln1 berlaku untuk n  0 . Berdasarkan persamaan (10) dan (9) diperoleh bahwa F n 



 n   n 1  1 1  1   n  n            1  

  n  n    1n 

n n  n 1        1      

  n  n    n 

   

 n 1    1 Fn 

dan

L n    n    n   

n



n



  n   1 Ln   1 Ln , n

n

untuk n sembarang bilangan bulat positif. Dengan menggunakan persamaan tersebut, akan ditunjukkan bahwa Proposisi 4 point (1) yaitu 5Fn  Ln1  Ln1 berlaku untuk n sembarang bilangan bulat negatif. Perhatikan bahwa,

L  n  1  L  n  1  L n 1  L n 1 ,   1

n 1

Ln 1   1

n 1

  1

n 1

Ln 1   1

n 1 2

  1

n 1

Ln 1   1

2

  1

n 1

 Ln 1  Ln 1  ,

  1

n 1

Ln 1 , Ln 1 ,

 1

n 1

Ln 1 ,

5 Fn ,

 5 F n . Jadi diperoleh bahwa 5F  n  L  n1  L  n1 . Oleh karena itu, 5Fn  Ln1  Ln1 berlaku untuk n  0 dan n berupa bilangan bulat negatif. Dengan kata lain Proposisi 4 point (1) berlaku untuk n sembarang bilangan bulat (Hansen, 1972). Dengan menggunakan cara yang sama diperoleh bahwa setiap point pada Proposisi 4 lainnya berlaku untuk n sembarang bilangan bulat.



47

3. KESIMPULAN DAN SARAN Solusi relasi rekuren dari bilangan Fibonacci ke-n dan bilangan Lucas ke-n berturut-turut yaitu Fn 



1 5 , 2

yang

n  n 5

diperoleh

dan Ln   n   n , dengan nilai   dengan

menggunakan

fungsi

1 5 dan 2

pembangkit.

Berdasarkan pembahasan mengenai hubungan bilangan Fibonacci dan bilangan Lucas, diperoleh bahwa bilangan Fibonacci ke-(m+n) dan bilangan Lucas ke-(m+n) dengan m adalah bilangan bulat yang ditentukan dan n Z mempunyai hubungan linier yang hanya melibatkan operasi penjumlahan atau pengurangan dari bilangan Fibonacci atau bilangan Lucas maupun kelipatannya. Hal ini ditunjukkan dengan diperolehnya bilangan Fibonacci yang tidak hanya dihasilkan dari penjumlahan suku-suku pada bilangan Fibonacci, melainkan dapat dihasilkan dari operasi penjumlahan dan pengurangan antara bilangan Fibonacci dan bilangan Lucas ataupun antara dua bilangan Lucas. Begitu juga sebaliknya, bilangan Lucas tidak hanya dihasilkan dari penjumlahan suku-suku pada bilangan Lucas, melainkan dapat dihasilkan dari operasi penjumlahan dan pengurangan antara bilangan Fibonacci dan bilangan Lucas ataupun antara dua bilangan Fibonacci. Pada penelitian ini telah dibahas hubungan bilangan Fibonacci dan bilangan Lucas yang hanya melibatkan operasi penjumlahan dan pengurangan. Untuk penelitian selanjutnya, disarankan untuk mengkaji hubungan bilangan Fibonacci dan bilangan Lucas yang melibatkan operasi perkalian.

DAFTAR PUSTAKA Hansen, R. T., Generating Identities for Fibonacci and Lucas Triples, The Fibonacci Quarterly, 10(6) (1972), 571-578. Rosen, K. H., Discrete Mathematics and Its Applications, 6th ed., McGraw-Hill, New York, 2007.


PENENTUAN SOLUSI RELASI REKUREN DARI BILANGAN FIBONACCI DAN BILANGAN LUCAS DENGAN MENGGUNAKAN FUNGSI PEMBANGKIT

Recommend Documents