Posted on

Naik Tangga dengan Fibonacci

Barisan Fibonacci adalah barisan {F_n} yang didefinisikan secara rekursif melalui

\displaystyle F_1=1,F_2=1, F_{n+2}=F_n+F_{n+1}.

Barikut adalah interpretasi barisan Fibonacci dengan menggunakan model menaiki tangga.

Diberikan {n} bilangan asli. Definisikan {F_n} sebagai banyaknya cara menaiki tangga dari level 1 ke level {n} dengan setiap langkahnya boleh menaiki satu anak tangga atau dua anak tangga sekaligus. Untuk {F_1} karena dari level 1 ke level 1 tidak ada yang perlu dilakukan, didefinisikan {F_1=1}. Berikutnya {F_2=1} karena hanya ada satu cara naik dari level 1 ke level 2, yakni dengan menaiki satu anak tangga.

Sekarang, agar bisa sampai ke level {n+2} (untuk {n\geq 1}), kita bisa naik sampai ke {n} kemudian naik 2 anak tangga atau naik sampai ke level {n+1} kemudian naik satu anak tangga. Dengan demikian kita peroleh

\displaystyle F_{n+2}=F_{n}+F_{n+1},

dan menunjukkan bahwa model menaiki tangga ini sesuai dengan definisi barisan Fibonacci.

Dengan menggunakan interpretasi menaiki tangga ini kita akan membuktikan beberapa identitas yang melibatkan barisan Fibonacci yang biasanya dilakukan dengan induksi matematika yang seringkali tidak memuaskan karena kita hanya memeriksa kesahihan identitas tersebut secara mekanis tanpa memahami apa yang sebenarnya terjadi.

Theorem 1 {F_1+F_2+\cdots+F_n=F_{n+2}-1}

Proof: Tinjau permasalahan menaiki tangga dari level 1 sampai ke level n+2. Salah satu cara melakukannya adalah dengan setiap saatnya menaiki satu anak tangga. Sekarang {F_{n+2}-1} adalah banyaknya cara menaiki tangga dari level 1 ke level {n+2} sehingga pada suatu saat pernah menaiki dua tangga.

Untuk setiap {k} dengan {1\leq k\leq n} tinjau cara menaiki tangga sehingga naik dari level {k} ke level {k+2} adalah terakhir kalinya naik dua undakan. Dari level ke {k+2} sampai ke {n+2} dilakukan dengan cara yang tunggal yakni naik 1 undakan setiap saatnya. Banyaknya cara untuk menaiki tangga seperti ini adalah jelas {F(k)}. \Box

Theorem 2 {F_1+F_3+\cdots+F_{2n-1}=F_{2n}}

Proof: Tinjau permasalahan naik tangga dari level 1 ke level {2n}. Misalkan {k} adalah level ganjil terakhir yang dikunjungi. Dari level {k} sampai level ke {k+1} naik satu undakan dan dari sana sampai ke level {2n} setiap saat selalu naik dua undakan. \Box

Theorem 3 {F_nF_{n+1}=F_1^2+\cdots +F_n^2}.

Proof: A menaiki tangga dari level 1 ke level {n} dan {B} naik dari level 1 ke level {n+1}. Banyaknya cara keduanya bisal melakukan hal yang demikian adalah {F_nF_{n+1}}. Misalkan {k} adalah level tertinggi yang dikunjungi oleh keduanya. Dari level {k} si A naik {a} undakan sedangkan si {B} naik {b} undakan dengan {a,b\in\{1,2\}}. Berdasarkan definisi {k} haruslah {a\neq b} (jika sama maka {A} dan {B} mengunjungi level {k+a=k+b}). Setelah itu untuk memastikan keduanya tidak pernah mengunjungi level yang sama maka mereka harus selalu naik 2 undakan. Nilai {a} dan {b} juga ditentukan secara tunggal dari syarat bahwa dengan langkah {a,2,2,\ldots,2} si {A} harus sampai ke level {n}.

Berarti dari level 1 sampai dengan level {k} si {A} dan {B} masing-masing mempunyai {F_k} cara dan sisanya dari level {k} ke level {n} dan dari level {k} ke level {n+1} ditentukan secara tunggal. \Box

Theorem 4 {F_n=F_kF_{n+1-k}+F_{k-1}F_{n-k}}.

Proof: Naik dari level 1 ke level {n} bisa dengan mengunjung level {k} terlebih dulu bisa juga tidak. Jika melalui level {k} banyaknya cara untuk melakukan hal tersebut adalah {F_kF_{n+1-k}}. Jika tidak melalui {k} maka haruslah sampai ke level {k-1} terlebih dahulu, kemudian naik dua undakan ke level {k+1} kemudian dari sana bebas melakukan apapun untuk sampai di level {n}. Banyaknya cara melakukan hal ini adalah {F_{k-1}F_{n-k}}. \Box