Barisan Fibonacci dan Aplikasinya

Banyak masalah pencacahan yang sulit diselesaikan dengan rumus kombinasi statis, namun menjadi sangat mudah jika kita melihat bagaimana solusi untuk $n$ objek berhubungan dengan solusi untuk $n - 1$ atau $n - 2$ objek.

1. Definisi Barisan Fibonacci

Barisan Fibonacci ${F_{n}}$ didefinisikan secara rekursif sebagai berikut:

$F_{n} = F_{n - 1} + F_{n - 2}, untuk n \geq 2$

dengan nilai awal $F_{0} = 0$ dan $F_{1} = 1$ . Suku-suku pertamanya adalah $0, 1, 1, 2, 3, 5, 8, 13, 21, \dots$

2. Aplikasi Pemodelan Rekursif

Masalah Pengubinan (Tiling)

Contoh (Tiling Papan 2 x n)

Tentukan banyaknya cara untuk menutupi papan berukuran $2 \times n$ dengan menggunakan domino berukuran $2 \times 1$ .

Contoh Soal & Pembahasan

Contoh (String Biner Tanpa 11)

Berapa banyak string biner dengan panjang $n$ yang tidak mengandung dua angka ‘1’ yang berurutan?

Latihan Soal

✏️ Latihan Soal 1 (Naik Tangga)

Diberikan sebuah tangga dengan $n$ anak tangga. Seseorang dapat melangkah naik 1 atau 2 anak tangga sekaligus. Berapa banyak cara orang tersebut mencapai puncak?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Langkah terakhir bisa dari anak tangga $(n - 1)$ dengan 1 langkah, atau dari $(n - 2)$ dengan 2 langkah. Maka $s_{n} = s_{n - 1} + s_{n - 2}$ dengan $s_{1} = 1, s_{2} = 2$ . Ini mengikuti pola Fibonacci ( $s_{n} = F_{n + 1}$ ). $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Derangement dan Fungsi Onto
Sub-Topik Selanjutnya: Rekurensi Linier Homogen →

1. Definisi Barisan Fibonacci

2. Aplikasi Pemodelan Rekursif

Masalah Pengubinan (Tiling)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Aplikasi PIE: Derangement dan Fungsi Onto

Rekurensi Linier Homogen dan Persamaan Karakteristik

Diskusi & Tanya Jawab

Title