Induksi matematis adalah teknik pembuktian fundamental untuk pernyataan yang berlaku pada seluruh bilangan bulat non-negatif. Dalam DSA, induksi adalah tulang punggung pembuktian kebenaran algoritma rekursif, analisis kompleksitas, dan struktur data berbasis hierarki (seperti tree). Pada Chapter ini kita akan mempelajari prinsip induksi matematis, dua variasi utamanya (lemah dan kuat), serta penerapannya pada pembuktian rumus deret dan sifat algoritma.

Prinsip Induksi Matematis #

Misalkan P(n) adalah pernyataan yang bergantung pada bilangan bulat n ≥ n₀. Untuk membuktikan P(n) benar untuk semua n ≥ n₀, kita lakukan dua langkah:

  1. Kasus Dasar (Base Case): buktikan P(n₀) benar.
  2. Langkah Induksi (Inductive Step): asumsikan P(k) benar untuk suatu k ≥ n₀ (hipotesis induksi). Gunakan hipotesis ini untuk membuktikan P(k+1) benar.

Bila kedua langkah terpenuhi, maka P(n) benar untuk semua n ≥ n₀.

Induksi Lemah vs Induksi Kuat #

Terdapat dua variasi induksi:

Induksi Lemah (Weak Induction) #

Hipotesis induksi hanya mengasumsikan P(k). Cocok untuk rekursi yang hanya memanggil T(k) dari T(k+1), misalnya faktorial.

Induksi Kuat (Strong Induction) #

Hipotesis induksi mengasumsikan P(n₀), P(n₀+1), ..., P(k) semuanya benar. Cocok untuk rekursi yang memanggil beberapa langkah sebelumnya, misalnya Fibonacci atau merge sort yang membagi masalah menjadi T(k/2) dan T(k - k/2).

Contoh 1: Penjumlahan 1 sampai n #

Buktikan bahwa 1 + 2 + ... + n = n(n+1)/2 untuk semua n ≥ 1.

Pembuktian #

Kasus Dasar (n = 1): ruas kiri = 1, ruas kanan = 1·2/2 = 1. Keduanya sama. ✓

Langkah Induksi: asumsikan 1 + 2 + ... + k = k(k+1)/2 (hipotesis induksi). Buktikan 1 + 2 + ... + (k+1) = (k+1)(k+2)/2.

text 
1 + 2 + ... + (k+1) = [1 + 2 + ... + k] + (k+1)
                    = k(k+1)/2 + (k+1)          (berdasarkan hipotesis)
                    = (k+1) [k/2 + 1]
                    = (k+1)(k+2)/2

Pembuktian selesai. ∎

Kode: Verifikasi Numerik #

cpp 
#include <iostream>

long long jumlah(int n) {
    long long total = 0;
    for (int i = 1; i <= n; ++i) total += i;
    return total;
}

long long rumus(int n) {
    return 1LL * n * (n + 1) / 2;
}

int main() {
    std::cout << "n\tjumlah(n)\trumus(n)\tsama?\n";
    for (int n : {1, 5, 10, 100, 1000, 10000}) {
        long long j = jumlah(n);
        long long r = rumus(n);
        std::cout << n << '\t' << j << '\t' << r
                  << (j == r ? "\tYA" : "\tTIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
n	jumlah(n)	rumus(n)	sama?
1	1	1	YA
5	15	15	YA
10	55	55	YA
100	5050	5050	YA
1000	500500	500500	YA
10000	50005000	50005000	YA

Bedah Kode Baris-per-Baris #

  1. Fungsi jumlah: menghitung penjumlahan secara iteratif, sebagai ground truth untuk verifikasi.
  2. Fungsi rumus: mengimplementasikan rumus Gauss n(n+1)/2 yang ingin kita buktikan. Kita pakai 1LL untuk memaksa perhitungan long long agar tidak overflow untuk n besar.
  3. Loop {1, 5, 10, 100, 1000, 10000}: menguji beberapa nilai n untuk memverifikasi kesesuaian.
  4. Output: untuk seluruh n, hasil jumlah sama dengan rumus. Verifikasi numerik ini bukan pembuktian formal, tetapi memberi keyakinan tambahan.
  5. Implikasi: walaupun pembuktian formal dengan induksi sudah cukup, verifikasi numerik membantu menangkap kesalahan ketik atau kesalahan logika yang mungkin terjadi.

Contoh 2: Jumlah Kuadrat #

Buktikan bahwa 1² + 2² + ... + n² = n(n+1)(2n+1)/6 untuk semua n ≥ 1.

Pembuktian #

Kasus Dasar (n = 1): ruas kiri = 1, ruas kanan = 1·2·3/6 = 1. Sama. ✓

Langkah Induksi: asumsikan 1² + 2² + ... + k² = k(k+1)(2k+1)/6. Buktikan 1² + ... + (k+1)² = (k+1)(k+2)(2k+3)/6.

text 
1² + ... + (k+1)² = [1² + ... + k²] + (k+1)²
                  = k(k+1)(2k+1)/6 + (k+1)²
                  = (k+1) [k(2k+1)/6 + (k+1)]
                  = (k+1) [(2k² + k + 6k + 6)/6]
                  = (k+1) [(2k² + 7k + 6)/6]
                  = (k+1)(k+2)(2k+3)/6

Faktorisasi 2k² + 7k + 6 = (k+2)(2k+3) dapat diverifikasi dengan ekspansi. ∎

Contoh 3: Banyaknya Node pada Binary Tree Penuh #

Sebuah binary tree penuh dengan kedalaman d memiliki 2^(d+1) - 1 node (dengan kedalaman root = 0). Mari kita buktikan dengan induksi pada d.

Pembuktian #

Definisi: binary tree penuh dengan kedalaman d adalah tree yang setiap node internal (non-leaf) memiliki tepat dua anak, dan semua leaf berada pada kedalaman d.

Kasus Dasar (d = 0): tree hanya berisi root. Jumlah node = 1 = 2^1 - 1. ✓

Langkah Induksi: asumsikan binary tree penuh dengan kedalaman k memiliki 2^(k+1) - 1 node. Binary tree penuh dengan kedalaman k+1 dapat dibayangkan sebagai root yang memiliki dua sub-tree penuh berkedalaman k sebagai anak kiri dan kanan. Total node:

text 
1 (root) + 2 × [jumlah node sub-tree berkedalaman k]
= 1 + 2 × (2^(k+1) - 1)
= 1 + 2^(k+2) - 2
= 2^(k+2) - 1

Ini sesuai dengan rumus 2^(d+1) - 1 untuk d = k+1. ∎

Contoh 4: Kebenaran Faktorial Rekursif #

Fungsi factorial(n) berikut menghitung n!. Mari kita buktikan kebenarannya dengan induksi.

Kode Program #

cpp 
#include <iostream>

long long factorial(int n) {
    if (n <= 1) return 1;
    return static_cast<long long>(n) * factorial(n - 1);
}

int main() {
    for (int n : {0, 1, 5, 10, 20}) {
        std::cout << "factorial(" << n << ") = " << factorial(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
factorial(0) = 1
factorial(1) = 1
factorial(5) = 120
factorial(10) = 3628800
factorial(20) = 2432902008176640000

Pembuktian Kebenaran #

Spesifikasi: factorial(n) mengembalikan n! untuk semua n ≥ 0.

Kasus Dasar (n = 0 dan n = 1): factorial(0) dan factorial(1) mengembalikan 1, yang sama dengan 0! = 1! = 1. ✓

Langkah Induksi: asumsikan factorial(k) benar, yaitu mengembalikan k!. Buktikan factorial(k+1) mengembalikan (k+1)!.

text 
factorial(k+1) = (k+1) * factorial(k)        // baris return
               = (k+1) * k!                    // hipotesis induksi
               = (k+1)!                         // definisi faktorial

Pembuktian selesai. ∎

Bedah Kode Baris-per-Baris #

  1. Baris if (n <= 1) return 1;: base case — 0! = 1 dan 1! = 1 secara definisi.
  2. Baris return static_cast<long long>(n) * factorial(n - 1);: langkah induksi — n! = n × (n-1)!. Cast ke long long menghindari overflow pada intermediate.
  3. Output factorial(20) = 2432902008176640000: nilai maksimum yang muat di long long (signed 64-bit) adalah 20!. 21! akan overflow.
  4. Implikasi: pembuktian kebenaran dengan induksi memberi jaminan bahwa factorial(n) mengembalikan n! untuk setiap n ≥ 0 (asalkan tidak overflow).

Induksi pada Struktur Rekursif #

Induksi tidak terbatas pada bilangan bulat. Kita bisa menginduksi pada:

  • Struktur tree: induksi pada kedalaman atau jumlah node.
  • String: induksi pada panjang string.
  • Graph: induksi pada jumlah simpul atau sisi.
  • List: induksi pada panjang list.

Ringkasan #

  • Induksi matematis membuktikan pernyataan P(n) untuk semua n ≥ n₀ melalui kasus dasar dan langkah induksi.
  • Induksi lemah mengasumsikan P(k); induksi kuat mengasumsikan P(n₀), ..., P(k) semuanya.
  • Contoh klasik: rumus deret 1 + 2 + ... + n = n(n+1)/2, rumus kuadrat n(n+1)(2n+1)/6, dan jumlah node binary tree penuh 2^(d+1) - 1.
  • Pembuktian kebenaran algoritma rekursif sering kali memanfaatkan induksi: base case algoritma menjadi kasus dasar, recursive case menjadi langkah induksi.
  • Structural induction adalah variasi untuk struktur rekursif seperti tree dan list.

Pada Chapter berikutnya kita akan menerapkan teknik loop invariant dan induksi untuk membuktikan kebenaran algoritma klasik seperti linear search dan insertion sort.