Senin, 11 April 2016

Bermain dengan Bilangan Fibonacci : Teorema Zeckendorf

Bilangan fibonacci! Ini merupakan salah satu sequence bilangan favorit gw, yang didefinisikan sebagai $F_1 = 1; F_2 = 1; F_i = F_{i-1} + F_{i-2}, i > 2$. Nah, ada salah satu teorema yang menarik nih tentang bilangan fibonacci, yaitu teorema Zeckendorf. Kece tuh namanya, teoremanya juga kece :D .
Jadi, apasih teorema Zeckendorf itu? Teorema Zeckendorf itu menyatakan bahwa setiap bilangan bulat positif dapat dinyatakan sebagai penjumlahan dari 1 atau lebih bilangan fibonacci berbeda. Contohnya, untuk 38, kita dapat : $38 = 1 + 3 + 34$. Representasi kayak gini disebut "Zeckendorf Representation", dan nyarinya bisa pakai cara greedy (dengan ngambil dulu bilangan fibonacci terbesar yang bisa diambil, lalu sisanya pasti dapat dinyatakan sebagai representasi Zeckendorf dari bilangan itu). Keren kan! Jadi kayak building blocksnya bilangan bulat. Terus buktinya gimana? Sebenernya ada 2 cara, yaitu cara gue yang gue ga tau cukup atau enggak untuk buktiin teorema ini, sama cara induksi yang jelas valid secara matematis. Cara gue dulu deh. Sebenernya gw udah sedikit ungkit sih di atas. Jadi asumsikan kita punya bilangan $N_1$. Untuk membentuk representasi Zeckendorfnya, gue pake cara greedy dengan mengambil bilangan $F_j$, dengan $F_j$ itu bilangan fibonacci terbesar yang lebih kecil dari $N_1$. Nah kan kalau udah, sisanya $N_1 - F_j$, sebut saja $N_x$. Hal ini akan terus berlanjut sampai $N_x$ itu sebuah bilangan fibonacci. Ini juga membuktikan kalau representasinya bakal berisi bilangan-bilangan berbeda karena kita nurunin "bound"nya. Kelemahan pembuktian gue adalah sebenernya perlu dibuktiin dulu kalau cara greedy itu bisa (sebenernya gue aja tau bisa digreedy gara-gara buku CP3 :v).

Beralih ke cara induksi ya. Pertama, basis induksinya dulu. Misalkan $F_1,F_2,...F_x$ itu list bilangan fibonacci dan $n$ adalah bilangan bulat posituf. Untuk $n = 1, 2, 3$ sudah jelas benar karena mereka bilangan fibonacci. Untuk $n = 4$, ada $4 = 3 + 1$. Sekarang, asumsikan setiap bilangan $n \leq k$ mempunyai representasi Zeckendorf (hipotesis induksi). Kalau $k + 1$ merupakan bilangan fibonacci, maka kita selesai, kalau tidak, maka ada sebuah bilangan $j$ yang memenuhi $F_j < k < F_{j+1}$. Sekarang kita tinjau sebuah bilangan $a = k + 1 - F_j$. Karena $a \leq k$, maka $a$ mempunyai representasi Zeckendorf (berdasarkan hipotesis induksi). Di sisi lain, $F_j + a < F_{j+1}$ dan $F_{j+1} = F_j + F_{j-1}$. Dari situ didapat bahwa $a < F_{j-1}$, sehingga representasi Zeckendorf dari $a$ tidak mengandung $F_{j-1}$. Alhasil, $k + 1$ dapat dinyatakan sebagai representasi Zeckendorf dari $a$.

Q.E.D.

Note : Gue sendiri ngerasa "bukti" versi gue ada kemiripan dengan versi induksinya. Hanya saja, karena gue bingung bikin bentuk matematis dari "bukti" gue, jadi agak susah buktiinnya.

Tidak ada komentar:

Posting Komentar

-Mohon untuk tidak spam di komentar-