Bermain dengan Bilangan Fibonacci : Teorema Zeckendorf

Fibonacci! Ini adalah salah satu barisan bilangan favorit saya. Definisinya sederhana, bisa ditulis secara rekursif sebagai $F_1 = F_2 = 1; F_i = F_{i-1} + F_{i-2}, i > 2$. Properti apa sih yang dimiliki barisan ini? Salah satunya dikenal sebagai teorema Zeckendorf nih. Apa sih itu?

Teorema Zeckendorf

Setiap bilangan bulat positif dapat dinyatakan sebagai jumlah dari 1 atau lebih bilangan fibonacci (representasi tersebut disebut sebagai representasi Zeckendorf)

Terus kenapa? Kok bisa begitu?

Pertama, kita perhatikan dulu contoh representasi Zeckendorf dari suatu bilangan bulat. Jika suatu bilangan yang ingin kita periksa ternyata bilangan fibonacci, kita selesai. Jika tidak? Misalkan, $56 = 1 + 55 = F_1 + F_{10}$. Kita lihat juga representasi Zeckendorf dari beberapa bilangan bulat positif pertama:
$1 = F_1$ atau $1 = F_2$
$2 = F_3$
$3 = F_4$
$4 = 3 + 1 = F_4 + F_1$
dan seterusnya...

Sekarang, dengan menggunakan induksi (kuat) akan dibuktikan bahwa teorema tersebut benar, yaitu setiap bilangan bulat positif punya representasi Zeckendorf. Misalkan $F_1, F_2, ..., F_n$ adalah barisan bilangan fibonacci dan $n \in \mathbb{Z}^+$.

Periksa basis induksi, yaitu ketika $n = 1$, kita punya $1 = F_1$. Jadi, basis induksi benar.

Asumsikan bahwa hipotesis induksi benar, yaitu setiap bilangan bulat positif $n \leq k$ punya representasi Zeckendorf. Periksa untuk $k+1$. Jika $k+1$ bilangan fibonacci, kita selesai. Andaikan bukan, pastilah $k+1$ ada di antara dua buah bilangan fibonacci berurutan, yaitu ada suatu $i \in \mathbb{Z}^+$ sehingga $F_i < k+1 < F_{i+1}$. Definisikan suatu bilangan $x = k+1-F_i$. Karena $x \leq k$, menurut hipotesis induksi $x$ punya representasi Zeckendorf. Berarti, $k+1 = a + F_i$. Perhatikan bahwa  $(F_i < k+1 < F_{i+1})\wedge(x = k+1-F_i) \implies 0 < x < F_{i-1}$ (silahkan anda periksa) sehingga representasi Zeckendorf dari $x$ pasti tidak memuat $F_{i-1}$ (apalagi $F_i$). Oleh karena itu, $k+1$ punya representasi Zeckendorf dan dengan demikian kita selesai.

Tambahan
Periksa bahwa representasi Zeckendorf dari suatu bilangan bulat positif unik, yaitu andaikan ada dua buah representasi untuk suatu bilangan bulat positif, keduanya adalah representasi yang sama.