Matdis — Bab 3
Induksi Matematika
Teknik pembuktian universal untuk pernyataan tentang bilangan asli — digunakan dalam verifikasi keamanan protokol kriptografi dan analisis algoritma rekursif.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 3. — Rosen, Discrete Mathematics, 8th ed., Ch. 5.
Mengapa Induksi Matematika?
Analogi: tangga tak berujung. Untuk yakin bisa mencapai semua anak tangga, cukup dua hal — (1) Anda bisa menginjak anak tangga pertama, dan (2) dari anak tangga mana pun Anda selalu bisa melangkah ke berikutnya. Itulah basis dan langkah induksi.
Induksi adalah cara membuktikan pernyataan untuk tak hingga banyak kasus hanya dengan dua langkah berhingga. Di informatika ia dipakai membuktikan kebenaran algoritma rekursif, menurunkan rumus penjumlahan, dan membuktikan sifat struktur data seperti pohon (induksi struktural).
Analogi: Domino Effect
Induksi seperti barisan domino tak terhingga. Langkah basis = menjatuhkan domino pertama. Langkah induktif = membuktikan bahwa setiap domino yang jatuh pasti akan menjatuhkan domino berikutnya. Dua langkah ini cukup untuk membuktikan SEMUA domino akan jatuh — tanpa mengecek satu per satu.
1. Prinsip Induksi Matematika Sederhana
Prinsip Induksi (Rinaldi Munir, Bab 3)
Untuk membuktikan P(n) benar untuk semua n ≥ n₀:
- Basis (Base Case): Tunjukkan P(n₀) benar.
- Hipotesis Induktif: Asumsikan P(k) benar untuk suatu k ≥ n₀.
- Langkah Induktif: Tunjukkan bahwa P(k) benar → P(k+1) benar.
- Kesimpulan: P(n) benar untuk semua n ≥ n₀.
[(P(n₀)) ∧ (∀k ≥ n₀: P(k) → P(k+1))] → ∀n ≥ n₀: P(n)
Demo: Rumus Deret Σᵢ₌₁ⁿ i = n(n+1)/2
Penjumlahan Langsung
15
Formula n(n+1)/2
5×6/2 = 15
Selalu sama ✓ — inilah yang dibuktikan induksi secara formal untuk semua n.
Visualisasi SMIL: Rantai Induksi
Basis → P(1) benar. Setiap P(k) → P(k+1) menjamin seluruh rantai.
2. Induksi Kuat (Strong Induction)
Prinsip Induksi Kuat
Dalam langkah induktif, boleh mengasumsikan P(j) benar untuk semua j dengan n₀ ≤ j ≤ k (bukan hanya k):
Basis: P(n₀) benar
Induktif: [∀j: n₀ ≤ j ≤ k → P(j)] → P(k+1)
Lebih kuat dari induksi biasa, berguna untuk rekursi yang tidak hanya bergantung P(k).
Contoh: Fibonacci dengan Induksi Kuat
Tunjukkan bahwa F(n) < 2ⁿ untuk semua n ≥ 1.
Basis: F(1) = 1 < 2¹ = 2 ✓. F(2) = 1 < 2² = 4 ✓.
Hipotesis Kuat: Asumsikan F(j) < 2ʲ untuk semua 1 ≤ j ≤ k.
Langkah: F(k+1) = F(k) + F(k-1) < 2ᵏ + 2ᵏ⁻¹ < 2ᵏ + 2ᵏ = 2·2ᵏ = 2ᵏ⁺¹. ✓
3. Bukti Rumus Deret
Dua Rumus Deret Fundamental
Rumus 1: Deret Aritmetika
Σᵢ₌₁ⁿ i = n(n+1)/2
Basis: n=1: 1 = 1(2)/2 = 1 ✓
Induktif: Σᵢ₌₁ᵏ⁺¹ i = k(k+1)/2 + (k+1)
= (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✓
Rumus 2: Deret Kuadrat
Σᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6
Basis: n=1: 1 = 1·2·3/6 = 1 ✓
Induktif: Tambahkan (k+1)² ke kedua sisi, sederhanakan. ✓
Rumus 3: Deret Geometri
Σᵢ₌₀ⁿ rⁱ = (rⁿ⁺¹−1)/(r−1) untuk r≠1
Basis: n=0: r⁰ = 1 = (r−1)/(r−1) = 1 ✓
Induktif: Σᵢ₌₀ᵏ⁺¹ = (rᵏ⁺¹−1)/(r−1) + rᵏ⁺¹ = (rᵏ⁺²−1)/(r−1) ✓
Rumus 4: Deret Pangkat 2
Σᵢ₌₀ⁿ 2ⁱ = 2ⁿ⁺¹ − 1
Basis: n=0: 1 = 2¹−1 = 1 ✓
Induktif: 2ᵏ⁺¹−1 + 2ᵏ⁺¹ = 2·2ᵏ⁺¹−1 = 2ᵏ⁺²−1 ✓
4. Bukti Pertidaksamaan
Contoh: Buktikan 2ⁿ > n untuk semua n ≥ 1
Basis: n=1: 2¹ = 2 > 1 ✓
Hipotesis Induktif: Asumsikan 2ᵏ > k untuk suatu k ≥ 1.
Langkah Induktif: Perlu tunjukkan 2ᵏ⁺¹ > k+1.
2ᵏ⁺¹ = 2·2ᵏ > 2k (hipotesis induktif)
2k = k + k ≥ k + 1 (karena k ≥ 1)
Jadi 2ᵏ⁺¹ > k + 1 ✓
Dengan induksi, 2ⁿ > n untuk semua n ≥ 1. □
5. Bukti Keterbagian
Demo: n³ − n dapat dibagi 6
n³ − n = 4³ − 4 = 60
60 / 6 = 10 → Habis dibagi 6 ✓
Bukti Formal dengan Induksi:
Basis: n=1: 1−1=0, 0 dibagi 6 ✓.
Hipotesis: Asumsikan 6 | (k³−k).
Langkah: (k+1)³ − (k+1) = k³+3k²+3k+1−k−1 = (k³−k)+3k(k+1).
Karena 6|(k³−k) dan 6|3k(k+1) (karena k(k+1) selalu genap), maka 6|(k+1)³−(k+1). □
6. Induksi Struktural
Definisi
Induksi tidak hanya untuk bilangan — bisa untuk struktur rekursif (pohon, string, ekspresi, program):
- Basis: Tunjukkan P benar untuk objek dasar (atom/terminal).
- Induktif: Jika P benar untuk sub-struktur, tunjukkan P benar untuk struktur yang lebih besar.
Aplikasi: Membuktikan correctness compiler, parser, dan interpreter. Membuktikan sifat rekursi dalam kriptografi (e.g., semua operasi pada Merkle tree menghasilkan hash yang valid).
Visualisasi SMIL: Pohon Rekursi Berkembang
7. Kesalahan Umum dalam Induksi
Fallacy: "Semua kuda berwarna sama"
Basis: 1 kuda — jelas berwarna sama.
Induktif: Asumsikan dalam setiap grup k kuda, semua berwarna sama.
Untuk k+1 kuda: {1,...,k} sama warna dan {2,...,k+1} sama warna. Jadi semua sama?
SALAH! Langkah k=1→k=2 gagal: {1} dan {2} tidak memiliki overlap!
Pelajaran: Hati-hati dengan kasus tepi (edge cases) di langkah induktif. Selalu verifikasi k=1 secara eksplisit.
8. Aplikasi: Induksi dalam Kebenaran Algoritma
Induksi = Alat Pembuktian Program
Induction on Key Length: Bukti bahwa Σi=1 to n bit kunci bersifat independen — menggunakan induksi pada jumlah bit. Dasar untuk membuktikan uniform key distribution.
Hash Function Chains: Merkle-Damgård construction: jika kompresi function H collision-resistant, maka dengan induksi pada jumlah blok, full hash function juga collision-resistant.
Structural Induction in EasyCrypt: Tool formal proof untuk kriptografi menggunakan induksi struktural pada ekspresi dan program untuk memverifikasi keamanan implementasi secara otomatis.
9. Contoh Soal & Pembahasan
Soal 1: Rumus Deret
Buktikan dengan induksi: 1 + 2 + ... + n = n(n+1)/2.
Soal 2: Pertidaksamaan
Buktikan n! > 2ⁿ untuk semua n ≥ 4.
Soal 3: Keterbagian
Buktikan 7 | (8ⁿ − 1) untuk semua n ≥ 1.
Soal 4: Induksi Kuat
Setiap n ≥ 2 dapat difaktorkan sebagai produk bilangan prima. Buktikan dengan induksi kuat.
Soal 5: Deret Geometri
Buktikan: Σᵢ₌₀ⁿ 2ⁱ = 2ⁿ⁺¹ − 1 untuk semua n ≥ 0.
Soal 6: Teorema Fermat Kecil
Buktikan bahwa untuk p prima dan p ∤ a, maka aᵖ ≡ a (mod p) — Teorema Fermat Kecil (dengan induksi).
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 3.
Mudah
1. Buktikan dengan induksi: 1+2+3+…+n = n(n+1)/2 untuk n≥1.
2. Buktikan: 2ⁿ > n untuk semua n ≥ 1.
3. Berapa langkah induksi diperlukan untuk membuktikan pernyataan tentang n≥5? Jelaskan basis induksinya.
4. Tentukan P(k+1) jika P(k): k² + k adalah genap.
Sedang
1. Buktikan dengan induksi kuat: Setiap bilangan bulat n ≥ 2 merupakan bilangan prima atau hasil kali bilangan-bilangan prima.
2. Buktikan: Σᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6.
3. Gunakan induksi untuk membuktikan: Jumlah n bilangan pertama barisan geometri a, ar, ar², … = a(rⁿ-1)/(r-1) untuk r≠1.
4. Buktikan dengan induksi: n! > 2ⁿ untuk n ≥ 4.
Sulit
1. Gunakan induksi struktural untuk membuktikan: Untuk setiap pohon biner dengan n simpul internal, jumlah simpul daun = n + 1.
2. Buktikan: Rekurensi T(n) = T(n-1) + n dengan T(1)=1 memiliki solusi T(n) = n(n+1)/2. Gunakan induksi dan verifikasi.
3. Gunakan induksi kuat untuk membuktikan: Setiap n ≥ 2 memiliki faktor prima terkecil p ≤ √n atau n sendiri adalah prima.
Kasus Terintegrasi (2+ Topik)
Definisikan rekurensi pohon: L(daun)=0, L(T)=1+max(L(Tₗ), L(Tᵣ)). Buktikan dengan induksi struktural: L(T) ≤ n-1 di mana n = jumlah simpul T.
Buktikan dengan induksi: FFT berorde n (dengan n = 2ᵏ) memerlukan tepat n·log₂(n)/2 operasi perkalian. Bandingkan dengan perkalian polinom cara naif.
Gunakan induksi kuat untuk membuktikan: Ada tak-hingga banyak bilangan prima. (Buktikan bahwa untuk setiap himpunan terhingga prima {p₁,…,pₙ}, ada prima lain di luar himpunan.)