Matdis — Bab Tambahan
Barisan, Deret & Rekurensi
Pola bilangan, notasi sigma, relasi rekurensi, fungsi pembangkit, dan penerapannya dalam analisis algoritma.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 6. — Rosen, Discrete Mathematics, 8th ed., Ch. 2, 8. — Knuth, The Art of Computer Programming, Vol. 1, Ch. 1.2.
Mengapa Barisan & Rekurensi?
Analogi: bunga majemuk di bank. Saldo bulan ini = saldo bulan lalu × (1 + bunga). Anda tidak perlu tahu rumus tertutupnya untuk menghitung bulan depan — cukup tahu aturan melangkah dari satu suku ke suku berikutnya. Itulah relasi rekurensi.
Hampir semua algoritma dapat dianalisis dengan cara yang sama. Merge sort memenuhi T(n) = 2T(n/2) + n, pencarian biner memenuhi T(n) = T(n/2) + 1, dan pemanggilan rekursif apa pun menghasilkan rekurensi yang bisa diselesaikan jadi rumus tertutup.
Bab ini mengajarkan dua arah: dari pola ke rumus (menebak lalu membuktikan dengan induksi), dan dari rekurensi ke rumus tertutup (persamaan karakteristik dan fungsi pembangkit).
1. Barisan Aritmetika
Definisi
Barisan aritmetika: setiap suku = suku sebelumnya + beda tetap d.
Suku ke-n: aₙ = a₁ + (n-1)d
Jumlah n suku: Sₙ = n(a₁ + aₙ)/2 = n(2a₁ + (n-1)d)/2
# Contoh: 2, 5, 8, 11, 14, ... (a₁=2, d=3)
# a₁₀ = 2 + 9×3 = 29, S₁₀ = 10(2+29)/2 = 155
Analogi: Tabungan Tetap
Menabung Rp 100rb per bulan = barisan aritmetika. Setelah n bulan: tabungan = a₁ + (n-1)×100rb. Deret = total uang yang ditabung. Konsep yang sama digunakan dalam analisis biaya linear algorithms dan loop dengan iterasi tetap.
Demo Barisan Aritmetika
Barisan: 2, 5, 8, 11, 14, 17, 20, 23, ...
Suku ke-10
a10 = 29
Jumlah 10 suku
S10 = 155
Visualisasi: Barisan sebagai Batang
2. Barisan & Deret Geometri
Definisi
Barisan geometri: setiap suku = suku sebelumnya × rasio tetap r.
Suku ke-n: aₙ = a₁ · r^(n-1)
Jumlah n suku (r≠1): Sₙ = a₁(rⁿ−1)/(r−1)
Deret tak hingga (|r|<1): S∞ = a₁/(1−r)
# Brute-force 256-bit key: 2²⁵⁶ operasi (barisan geometri r=2)
Demo Barisan Geometri
Barisan: 1.00, 2.00, 4.00, 8.00, 16.00, 32.00, ...
Suku ke-8
a8 = 128.0000
Jumlah 8 suku
S8 = 255.0000
3. Notasi Sigma dan Identitas Penjumlahan
Identitas Penjumlahan Penting:
4. Relasi Rekurensi
Definisi (Relasi Rekurensi)
Relasi rekurensi mendefinisikan suku ke-n berdasarkan satu atau lebih suku sebelumnya, beserta kondisi awal (initial conditions).
Linear homogen: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ
Linear non-homogen: aₙ = c₁aₙ₋₁ + ... + cₖaₙ₋ₖ + F(n)
Divide-and-conquer: T(n) = aT(n/b) + f(n) — diselesaikan dengan Master Theorem.
Demo Rekurensi Linear Homogen: aₙ = α·aₙ₋₁ + β·aₙ₋₂
aₙ = 1·aₙ₋₁ + 1·aₙ₋₂, a₀=0, a₁=1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
α=1, β=1, a₀=0, a₁=1 → Fibonacci! α=1, β=-1 → oscillating. α=2, β=0 → powers of 2.
5. Barisan Fibonacci dan Golden Ratio
Barisan Fibonacci
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Tumbuh eksponensial seperti φⁿ/√5 di mana φ = (1+√5)/2 ≈ 1.618 (golden ratio).
Formula Binet: F(n) = (φⁿ - ψⁿ)/√5, ψ = (1-√5)/2
Matrix form: [F(n+1), F(n); F(n), F(n-1)] = [[1,1],[1,0]]ⁿ
# Matrix exponentiation: F(n) dalam O(log n)!
Eksplorasi: Barisan Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
F(12) = 144
Rasio F(n)/F(n-1) = 1.617978 → φ ≈ 1.618034
6. Solusi Rekurensi Linear Homogen
Metode Persamaan Karakteristik
Untuk rekurensi aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, cari akar persamaan karakteristik r² = c₁r + c₂:
Persamaan karakteristik: r² - c₁r - c₂ = 0
Akar berbeda (r₁ ≠ r₂): aₙ = A·r₁ⁿ + B·r₂ⁿ
Akar kembar (r₁ = r₂ = r): aₙ = (A + Bn)·rⁿ
Akar kompleks (r = ρe^(iθ)): aₙ = ρⁿ(A cos(nθ) + B sin(nθ))
# A, B ditentukan dari initial conditions
Contoh: Fibonacci
aₙ = aₙ₋₁ + aₙ₋₂. Persamaan karakteristik: r² - r - 1 = 0.
Akar: r = (1 ± √5)/2. Jadi r₁ = φ = (1+√5)/2, r₂ = ψ = (1-√5)/2.
aₙ = A·φⁿ + B·ψⁿ. Initial: a₀=0, a₁=1.
a₀ = A + B = 0 → B = -A
a₁ = Aφ + Bψ = A(φ - ψ) = A√5 = 1 → A = 1/√5.
F(n) = (φⁿ - ψⁿ)/√5 — Formula Binet. ✓
7. Fungsi Pembangkit (Generating Functions)
Definisi
Fungsi pembangkit dari barisan {a₀, a₁, a₂, ...} adalah deret pangkat formal:
G(x) = a₀ + a₁x + a₂x² + a₃x³ + ... = Σₙ aₙxⁿ
Kegunaan: mengubah masalah rekurensi (beda) menjadi masalah aljabar (persamaan fungsi), kemudian ekstrak koefisien untuk mendapatkan solusi closed-form.
Contoh penting:
1/(1-x) = 1 + x + x² + x³ + ... (|x|<1)
1/(1-x)² = 1 + 2x + 3x² + 4x³ + ... (OGF untuk {n+1})
Fibonacci: G(x) = x/(1-x-x²) → koefisien xⁿ = F(n)
8. LFSR: Rekurensi Linear atas GF(2)
LFSR (Linear Feedback Shift Register)
LFSR adalah rekurensi linear atas GF(2): bₙ = c₁bₙ₋₁ ⊕ c₂bₙ₋₂ ⊕ ... ⊕ cₖbₙ₋ₖ. Menghasilkan barisan pseudo-random biner dengan periode sangat panjang.
Maximal-length LFSR (m-sequence): periode 2ᵏ−1 untuk LFSR dengan k bit, menggunakan primitive polynomial.
Linear complexity: jumlah minimum bit yang diperlukan untuk memulihkan seluruh LFSR sequence (Berlekamp-Massey algorithm).
Sifat penting — deterministik: keluarannya tampak acak, tetapi sepenuhnya ditentukan oleh state awal. Algoritma Berlekamp-Massey bahkan dapat memulihkan seluruh aturan rekurensi hanya dari 2k bit keluaran. Karena itu LFSR cocok sebagai pembangkit bilangan acak semu untuk simulasi dan pengujian, tetapi tidak untuk keperluan yang menuntut ketidakterdugaan.
Penerapan nyata: pembangkitan pola uji pada rangkaian digital (BIST), kode penyebar pada komunikasi CDMA, dan penghitung cepat pada FPGA — karena LFSR jauh lebih hemat gerbang daripada pencacah biner biasa.
Demo LFSR (state 4-bit, tap [0,3])
State awal: [1, 0, 1, 1], bₙ = b₀ ⊕ b₃
Output (16 bit):
Pola terlihat pseudo-random tapi deterministik — dapat dipecahkan dengan Berlekamp-Massey dari 8 bit output.
Rekurensi di Balik Algoritma Sehari-hari
Divide and Conquer: Setiap algoritma yang membelah masalah menghasilkan rekurensi. Merge sort: T(n)=2T(n/2)+n ⇒ Θ(n log n). Pencarian biner: T(n)=T(n/2)+1 ⇒ Θ(log n). Perkalian Karatsuba: T(n)=3T(n/2)+n ⇒ Θ(n^1,585), lebih cepat dari perkalian sekolah O(n²).
Pemrograman Dinamis: Rekurensi Fibonacci F(n)=F(n−1)+F(n−2) jika dihitung naif memakan waktu eksponensial karena subsoal berulang. Dengan memoisasi turun ke O(n) — perbedaan antara program yang selesai seketika dan yang menggantung.
Fungsi Pembangkit: Mengubah barisan menjadi deret pangkat memungkinkan masalah pencacahan diselesaikan secara aljabar. Contoh: banyaknya cara menukar uang dengan pecahan tertentu adalah koefisien pada hasil kali beberapa deret geometri.
Analisis Amortisasi: Array dinamis yang menggandakan kapasitas saat penuh memenuhi rekurensi biaya penyalinan 1+2+4+…+n < 2n. Karena itu push berbiaya O(1) secara amortisasi meski sesekali mahal.
9. Contoh Soal & Pembahasan
Soal 1: Barisan Aritmetika
Barisan aritmetika: a₁=5, d=3. Tentukan a₂₀ dan S₂₀.
Soal 2: Barisan Geometri (Ledakan Eksponensial)
Sebuah algoritma brute-force memeriksa 2²⁵⁶ kemungkinan. Jika sebuah superkomputer memeriksa 2⁶⁴ kemungkinan per detik, berapa tahun waktu yang dibutuhkan?
Soal 3: Rekurensi Master Theorem
Selesaikan T(n) = 4T(n/2) + n menggunakan Master Theorem.
Soal 4: Persamaan Karakteristik
Selesaikan aₙ = 4aₙ₋₁ - 4aₙ₋₂, a₀=1, a₁=4.
Soal 5: Generating Function
Gunakan generating function untuk menemukan formula tertutup dari aₙ = aₙ₋₁ + 2 (a₀=3).
Soal 6: FFT dan Perkalian Polinom
Mengapa FFT membuat perkalian dua polinom jauh lebih cepat? Apa rekurensi yang terlibat?
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 6.
Mudah
1. Hitung 10 suku pertama deret Fibonacci: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2).
2. Tuliskan relasi rekurensi untuk jumlah bayar cicilan a(n) = 1.05·a(n-1) (bunga 5%) dengan a(0) = 10000.
3. Apa bedanya barisan aritmetika dan geometrika? Berikan satu contoh masing-masing.
4. Tentukan rumus suku ke-n dari barisan: 2, 6, 18, 54, ...
Sedang
1. Selesaikan rekurensi: a(n) = 3a(n-1) - 2a(n-2), a(0)=1, a(1)=3.
2. Tentukan fungsi pembangkit (generating function) untuk barisan: 1, 2, 4, 8, ... (2ⁿ).
3. Barisan a(n) = 5a(n-1) dengan a(0)=3. Tentukan a(10).
4. Apa hubungan antara bilangan Fibonacci dan deret geometri? Apakah Fibonacci tumbuh secara eksponensial?
Sulit
1. Selesaikan rekurensi T(n) = T(n-1) + T(n-2) + 2ⁿ (Fibonacci non-homogen). Temukan solusi khusus dan solusi umum.
2. Turunkan rumus Fibonacci closed form (Binet's formula) menggunakan nilai eigen matriks M = [[1,1],[1,0]]. Jelaskan hubungannya dengan eigenvalue decomposition.
3. LFSR dengan tap polynomial x⁴+x+1 (primitive polynomial mod 2), state awal [1,0,0,0]. Hitung periode LFSR dan jelaskan mengapa primitive polynomial menjamin periode maksimal 2ⁿ-1.
Kasus Terintegrasi (2+ Topik)
Gunakan generating function untuk menyelesaikan a(n) = 2a(n-1) + 1, a(0)=0. Temukan solusi closed-form dan verifikasi untuk n=3.
Matriks M=[[1,1],[1,0]] memiliki Mⁿ yang mengandung bilangan Fibonacci. Hitung M³ secara eksplisit dan verifikasi F(4), F(3), F(2) dari hasilnya. Jelaskan mengapa matrix exponentiation memberikan O(log n) untuk menghitung Fibonacci ke-n.
LFSR dengan koneksi polynomial x⁵+x²+1 menghasilkan m-sequence. Jelaskan: (1) mengapa output LFSR tampak acak, (2) bagaimana Berlekamp-Massey merekonstruksi LFSR dari output, (3) mengapa LFSR saja tidak aman sebagai stream cipher.