Barisan Fibonacci adalah barisan yang didefinisikan secara rekursif melalui
Barikut adalah interpretasi barisan Fibonacci dengan menggunakan model menaiki tangga.
Diberikan bilangan asli. Definisikan
sebagai banyaknya cara menaiki tangga dari level 1 ke level
dengan setiap langkahnya boleh menaiki satu anak tangga atau dua anak tangga sekaligus. Untuk
karena dari level 1 ke level 1 tidak ada yang perlu dilakukan, didefinisikan
. Berikutnya
karena hanya ada satu cara naik dari level 1 ke level 2, yakni dengan menaiki satu anak tangga.
Sekarang, agar bisa sampai ke level (untuk
), kita bisa naik sampai ke
kemudian naik 2 anak tangga atau naik sampai ke level
kemudian naik satu anak tangga. Dengan demikian kita peroleh
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
![]()
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 adalah banyaknya cara menaiki tangga dari level 1 ke level
sehingga pada suatu saat pernah menaiki dua tangga.
Untuk setiap dengan
tinjau cara menaiki tangga sehingga naik dari level
ke level
adalah terakhir kalinya naik dua undakan. Dari level ke
sampai ke
dilakukan dengan cara yang tunggal yakni naik 1 undakan setiap saatnya. Banyaknya cara untuk menaiki tangga seperti ini adalah jelas
.
Theorem 2
![]()
Proof: Tinjau permasalahan naik tangga dari level 1 ke level . Misalkan
adalah level ganjil terakhir yang dikunjungi. Dari level
sampai level ke
naik satu undakan dan dari sana sampai ke level
setiap saat selalu naik dua undakan.
Theorem 3
.
Proof: A menaiki tangga dari level 1 ke level dan
naik dari level 1 ke level
. Banyaknya cara keduanya bisal melakukan hal yang demikian adalah
. Misalkan
adalah level tertinggi yang dikunjungi oleh keduanya. Dari level
si A naik
undakan sedangkan si
naik
undakan dengan
. Berdasarkan definisi
haruslah
(jika sama maka
dan
mengunjungi level
). Setelah itu untuk memastikan keduanya tidak pernah mengunjungi level yang sama maka mereka harus selalu naik 2 undakan. Nilai
dan
juga ditentukan secara tunggal dari syarat bahwa dengan langkah
si
harus sampai ke level
.
Berarti dari level 1 sampai dengan level si
dan
masing-masing mempunyai
cara dan sisanya dari level
ke level
dan dari level
ke level
ditentukan secara tunggal.
Theorem 4
.
Proof: Naik dari level 1 ke level bisa dengan mengunjung level
terlebih dulu bisa juga tidak. Jika melalui level
banyaknya cara untuk melakukan hal tersebut adalah
. Jika tidak melalui
maka haruslah sampai ke level
terlebih dahulu, kemudian naik dua undakan ke level
kemudian dari sana bebas melakukan apapun untuk sampai di level
. Banyaknya cara melakukan hal ini adalah
.