About Fibonacci : Identitas Fibonacci - part 4

بسم الله الرحمن الرحيم

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 :)

Review

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.

Sekian bahasan tentang identitas Fibonacci, mungkin juga bahasan terakhir tentang bilangan Fibonacci. Jika ada kekurangan mohon dimaklumi dan dikoreksi sebagai pelajaran berharga bagi saya. Terima kasih :)

Catatan :
Saya terinspirasi untuk membahas ini setelah melihat berbagai variasi jawaban untuk soal Codeforces yang di pos diatas. Karena saya anggap soal ini unik dan bisa disolve dengan banyak theorem dan struktur data, maka saya memutuskan menulis tentang ini.