Setelah sekian lama tidak berjumpa dengan pembaca setia -kalau ada-, kali ini saya menemukan persoalan menarik tentang fibonacci. Saya tidak akan bahas persoalan sebenarnya (yang mana mungkin jauh lebih susah dari topik yang akan ditulis) tapi akan saya fokuskan ke identitas barisan Fibonacci yang lain. Selamat membaca :)
Di pos sebelumnya tentang fibonacci kita sudah dapat menyatakan fibonacci dalam matriks berpangkat, yaitu
\[ \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right) = \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array}\right)^n \]
Coba jika kita pecah menjadi dua buah matriks berpangkat
\[ \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array}\right)^n = \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array}\right)^k \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array}\right)^{n-k} \]
\[ \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right) = \left( \begin{array}{cc} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array}\right) \left( \begin{array}{cc} F_{n-k+1} & F_{n-k} \\ F_{n-k} & F_{n-k-1} \end{array}\right) \]
Perhatikan bahwa
\[ F_n = F_{k+1} F_{n-k} + F_k F_{n-k-1}\]
atau dalam bentuk lain
\[ F_{m+n} = F_{n+1} F_m + F_n F_{m-1}\]
muncul ketika kita menyamakan perkalian baris pertama dan kolom kedua. Inilah yang akan saya sebut sebagai
magic identity karena sangat
useful untuk penyelesaian parsial fibonacci.
Aplikasi pada dynamic range query
Sebagai contoh, misalkan kita pada suatu range \( [L \dots R] \) ingin menambah semua array dalam range itu dengan \(F_1\), \(F_2\), \(F_3\), dan seterusnya sampai \(F_{R-L+1}\) lalu mencari jumlah semua elemen dalam range tersebut. Dengan
bruteforce hal ini mungkin dilakukan, tapi akan sangat memakan waktu jika proses tersebut dilakukan berulang-ulang.
Maka kita hanya perlu menambah parameter update \(F_1\), \(F_2\), dan \(Sum\). Dengan ketiga parameter tersebut kita bisa menggunakan
magic identity yang telah dibuktikan di atas dengan sedikit memodifikasinya menjadi
\[ S_n = F_{k+1} S_{n-k} + F_k S_{n-k-1}\]
dengan \(k = 1\), menjadi
\[ S_n = F_2 S_{n-1} + F_1 S_{n-2} \]
untuk mengupdate \(Sum\)
yang telah di
precompute sebelumnya.
Presum dari Fibonacci \(S_n\) bisa di
precompute di awal. Sehingga update dan pencarian nilai bisa dilakukan dengan cepat.
Hal ini akan sangat terasa ketika berhadapan dengan soal
dynamic query yang menggunakan Fibonacci sebagai update query nya. Sebagai contoh, soal yang baru saja saya solve menggunakan struktur data
segment tree dan
magic identity diatas
yaitu
Codeforces Round #FF Div2 E.
Back-Fibonacci dan d'Ocagne's identity
Sejauh ini kita telah membahas bilangan Fibonacci berindeks non-negatif. Kita tidak memasukkan indeks negatif karena definisi yang dipakai adalah persamaan yang tersusun menaik
\[ F_n = F_{n-2} + F_{n-1} \]
Bagaimana jika kita ubah definisinya menjadi
\[ F_n = F_{n+2} - F_{n+1} \]
Maka, akan ada definisi untuk Fibonacci berindeks negatif kan? Lalu untuk apa kita harus mencari bilangan Fibonacci berindeks negatif?
Coba perhatikan barisan berikut
\( 0, 1, 1, 2, 3, 5, 8, 11, \dots \)
Barisan di atas tidak akan berakhir. Jika kita susun barisan mundur, juga akan didapati barisan tiada berakhir
\( \dots, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, \dots \)
Perhatikan bahwa akan didapat hubungan antara bilangan berindeks negatif dengan bilangan berindeks positifnya, yaitu
\[ F_{-n} = (-1)^{n+1} F_n \]
Pembuktiannya sederhana, bisa dengan induksi atau dengan yang lain ( coba pembaca buktikan sendiri :) ).
Lalu, setelah ini apa?
Kita akan menemukan bahwa identitas negativitas diatas bersama-sama
magic identity berpotensi menimbulkan identitas baru, yang ditemukan oleh
d'Ocagne. Coba kita turunkan persamaan ini.
Kita telah mengetahui bahwa bilangan Fibonacci dapat dinyatakan dalam jumlah dari 2 perkalian Fibonacci
\[ F_{m+n} = F_{n+1} F_m + F_n F_{m-1}\]
Jika kita asumsikan \(m < 0\), maka kita subtitusikan identitas negativitas menjadi
\begin{array}{lcl}
F_{n-m} & = & F_{n+1} F_{-m} + F_n F_{-m-1}
\\ & = & F_{n+1} (-1)^{m-1} F_m + F_n (-1)^{m+2} F_{m+1}
\\ & = & - (-1)^m F_{n+1} F_m + (-1)^m F_n F_{m+1}
\end{array}
Kalikan kedua ruas dengan \((-1)^m\) menjadi
\[ (-1)^m F_{n-m} = F_n F_{m+1} - F_{n+1} F_m \]
Inilah identitas
d'Ocagne yang tidak kalah serunya dengan
magic identity. Jika pada
segment tree kita cukup memerlukan
magic identity, maka pada
binary indexed tree(BIT) kita memerlukan identitas yang bisa mengupdate sum dengan lebih fleksibel ( Ini karena yang dilakukan BIT yaitu 'hanya' mengupdate
presum dari query. Kita akan bahas kedua struktur data ini lebih lanjut nanti ;D )
Sum of Fibonacci
Banyak problem yang mensyaratkan penjumlahan elemen-elemen Fibonacci dalam inti soalnya. Dan kadang kita tidak dapat menggunakan
precompute untuk menghitungnya entah karena terlalu banyak atau batasan memori maupun runtime yang memaksa kita menggunakan cara yang lebih canggih.
Sebenarnya percaya atau tidak penjumlahan dari elemen-elemen Fibonacci itu adalah elemen Fibonacci lain. Percaya nggak?
Kali ini akan saya buktikan sedikit tentang
Fibonacci summation yang sebenarnya sangat sederhana.
Perhatikan bahwa \( F_n = F_{n+2} - F_{n+1} \) maka jika kita jumlahkan \(F_1\) sampai \(F_n\) dengan menyubtitusikan persamaan ini, akan didapatkan
\begin{array}{lcl}
\sum_{i=1}^{n} F_i & = & F_1 + F_2 + F_3 + \dots + F_n \\ & = & (F_3 - F_2) + (F_4 - F_3) + \cdots + (F_{n+2} - F_{n+1}) \\ & = & F_{n+2} - F_2
\end{array}
Simple but cool, right?
Trik ini juga bisa diaplikasikan pada soal serupa dengan yang disebut di atas. Tanpa melakukan
precompute kita bisa menggunakan formula ini sebagai pengganti. Lumayan menghemat runtime processing.
Penutup
Sebenarnya ada banyak identitas Fibonacci yang bisa didapatkan dengan berbagai cara (yang tentunya pembuktian lengkapnya akan diserahkan pada pembaca), diantaranya :
- Catalan identity : \( F_n^2 - F_{n+r}F_{n-r} = (-1)^{n-r}F_r^2 \) ( Hint : bukti menggunakan pemangkatan matriks dan determinan )
- Cassini identity : \( F_n^2 - F_{n+1}F_{n-1} = (-1)^{n-1} \) ( Kasus khusus dari Catalan identity )
dan lain sebagainya yang mungkin terlalu banyak jika diuraikan disini.
