Relasi Rekurensi & Persamaan Karakteristik

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. Hubungan inilah yang kita sebut sebagai relasi rekurensi.

1. Barisan Fibonacci dan Pemodelan Rekursif

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$

Contoh (Masalah Pengubinan (Tiling 2 x n))

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

2. Rekurensi Linier Homogen dengan Koefisien Konstan

Sebuah relasi rekurensi linier homogen berorde $k$ memiliki bentuk umum:

$a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}$

di mana $c_{i}$ adalah konstanta dan $c_{k} \neq = 0$ .

Persamaan Karakteristik

Substitusi $a_{n} = r^{n}$ ke dalam relasi rekurensi menghasilkan persamaan karakteristik:

$r^{k} - c_{1} r^{k - 1} - c_{2} r^{k - 2} - \dots - c_{k} = 0$

Teorema (Solusi Akar Berbeda (Orde 2))

Jika persamaan karakteristik $r^{2} - c_{1} r - c_{2} = 0$ memiliki dua akar real berbeda $r_{1}$ dan $r_{2}$ , maka solusi umum dari relasi rekurensi adalah:

$a_{n} = α r_{1}^{n} + β r_{2}^{n}$

Nilai konstanta $α$ dan $β$ ditentukan menggunakan nilai awal (syarat batas) $a_{0}$ dan $a_{1}$ .

Teorema (Solusi Akar Kembar (Orde 2))

Jika persamaan karakteristik memiliki akar kembar $r_{1} = r_{2} = r$ , maka solusi umumnya adalah:

$a_{n} = (α + β n) r^{n}$

Contoh Soal & Pembahasan

Contoh (Formula Binet untuk Fibonacci)

Tentukan rumus eksplisit untuk barisan Fibonacci yang didefinisikan oleh $F_{n} = F_{n - 1} + F_{n - 2}$ dengan $F_{0} = 0$ dan $F_{1} = 1$ .

Contoh (Akar Kembar)

Selesaikan relasi rekurensi $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ dengan $a_{0} = 1$ dan $a_{1} = 6$ .

Latihan Soal

✏️ Latihan Soal 1 (Rekurensi Akar Berbeda)

Selesaikan relasi rekurensi $a_{n} = a_{n - 1} + 2 a_{n - 2}$ dengan $a_{0} = 2$ dan $a_{1} = 7$ .

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Persamaan karakteristik: $r^{2} - r - 2 = 0 ⟹ (r - 2) (r + 1) = 0 ⟹ r_{1} = 2, r_{2} = - 1$ . Solusi umum: $a_{n} = α 2^{n} + β (- 1)^{n}$ .

$a_{0} = 2 ⟹ α + β = 2$ .
$a_{1} = 7 ⟹ 2 α - β = 7$ . Penjumlahan: $3 α = 9 ⟹ α = 3$ , sehingga $β = - 1$ . Rumus eksplisit: $a_{n} = 3 \cdot 2^{n} - (- 1)^{n}$ . $■$

✏️ Latihan Soal 2 (String Biner Tanpa 11)

Berapa banyak string biner panjang 7 yang tidak memuat sub-string “11”?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Misalkan $b_{n}$ adalah banyaknya string biner panjang $n$ tanpa “11”. Rekurensi: $b_{n} = b_{n - 1} + b_{n - 2}$ dengan $b_{1} = 2$ (‘0’, ‘1’) dan $b_{2} = 3$ (‘00’, ‘01’, ‘10’).

$b_{3} = 5$
$b_{4} = 8$
$b_{5} = 13$
$b_{6} = 21$
$b_{7} = 34$ . Maka banyaknya string biner panjang 7 tanpa “11” adalah $34$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Prinsip Inklusi-Eksklusi
Sub-Topik Selanjutnya: Pengantar Teori Graf →

Relasi Rekurensi & Persamaan Karakteristik

1. Barisan Fibonacci dan Pemodelan Rekursif

2. Rekurensi Linier Homogen dengan Koefisien Konstan

Persamaan Karakteristik

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

🏆 Soal ONMIPA Terkait (1 Soal)

Materi Terkait (Linked References) (3)

Prinsip Inklusi-Eksklusi, Derangement & Fungsi Onto

Teori Graf Dasar, Graf Eulerian, Hamiltonian & Teorema Hall

Naskah Soal & Pembahasan ONMIPA PT 2025 — Seleksi Wilayah

Diskusi & Tanya Jawab

Title