Induksi Matematika

Pada tulisan ini saya ingin sedikit mengenalkan tentang salah satu metode pembuktian pada matematika yaitu induksi matematika. Metode pembuktian ini dapat diterapkan juga dalam bidang informatika, salah satu contohnya ialah untuk membuktikan kebenaran dari suatu algoritma.

1. Introduction

Himpunan bilangan asli $$\mathbb{N} = \{1, 2, 3, \cdots \}$$ memiliki dua operasi, penjumlahan dan perkalian, serta memiliki hubungan keterurutan. Himpunan bilangan asli memiliki banyak properti dasar yang berlaku. Pada tulisan ini, salah satu sifat dasar yang akan digunakan ialah Well Ordering Principle.

1.1 (Well Ordering Principle of $\mathbb{N}$) Setiap himpunan bagian tak kosong dari $\mathbb{N}$ memiliki anggota terkecil.

Lebih jelasnya, jika $S$ ialah himpunan bagian dari $\mathbb{N}$ dan $S$ bukan himpunan kosong maka terdapat $m \in S$ sehingga $m \leq k$ untuk setiap $k \in S$.

2. Induksi Matematika

2.1 Prinsip Induksi Matematika

Induksi matematika merupakan salah satu metode pembuktian yang sangat sering digunakan untuk membuktikan kebenaran dari sebuah proposisi yang berkaitan dengan bilangan asli.

2.1.1 (Induksi Matematika) Misalkan $S$ himpunan bagian dari $\mathbb{N}$ yang memiliki kedua sifat berikut

1. $1 \in S$

      2. Untuk setiap $k \in \mathbb{N}$, jika $k \in S$ maka $k+1 \in S$
Maka $S = \mathbb{N}$

Bukti Asumsikan yang terjadi ialah $S \neq \mathbb{N}$, hal ini berarti himpunan $\mathbb{N}\setminus S$ merupakan himpunan tak kosong. Berdasarkan Well Ordering Principle himpunan $\mathbb{N} \setminus S$ memiliki anggota terkecil $m$. Karena $1 \in S$, maka $m > 1$ yang berarti $m - 1$ merupakan bilangan asli. Karena $m - 1 < m$ dan $m$ merupakan anggota terkecil dari himpunan $\mathbb{N} \setminus S$, dapat disimpulkan $m - 1 \in S$. Berikutnya dapat dilihat dari sifat kedua, dengan mengambil $k = m$ diperoleh $k + 1 = (m - 1) + 1 = m$ merupakan anggota dari $S$. Hal ini kontradiksi dengan fakta bahwa $m \notin S$. Jadi asumsi awal salah, yang berarti terbukti bahwa haruslah $S = \mathbb{N}$.

$\blacksquare$

Definisikan $P(n)$ merupakan sebuah pernyataan dengan $n\in\mathbb{N}$ sehingga $P(n)$ dapat bernilai benar untuk beberapa nilai $n$ dan salah untuk beberapa lainnya. Sebagai contoh, jika $P(n)$ merupakan sebuah pernyataan "$n^2 = n$", artinya $P(1)$ benar dan $P(n)$ salah untuk semua $n > 1, n\in\mathbb{N}$. Dalam metode pembuktian, Induksi matematika juga dapat dirumuskan sebagai berikut.

2.1.2 (Induksi Matematika) Untuk setiap $n \in \mathbb{N}$, misalkan $P(n)$ merupakan sebuah pernyataan tentang $n$. Jika berlaku 

      1'. $P(1)$ benar 

      2'. Untuk setiap $k \in \mathbb{N}$, jika $P(k)$ benar, maka $P(k+1)$ benar.

Maka $P(n)$ benar untuk semua $n \in \mathbb{N}$.

Hubungan antara prinsip Induksi Matematika 2.1.1 dengan 2.1.2 dapat dijelaskan dengan memisalkan $S := \{ n \in \mathbb{N} : P(n) \ \text{benar} \}$.

2.2 Langkah - Langkah Pembuktian

Dalam menggunakan Induksi Matematika terdapat dua langkah yang perlu dikerjakan. Langkah pertama disebut basis induksi dan langkah kedua disebut langkah induksi. Langkah induksi berisi andaian (asumsi) yang menyatakan bahwa $P(n)$ benar. Asumsi tersebut dinamakan hipotesis induksi. Dengan menunjukan basis induksi dan langkah induksi, maka sudah terbukti bahwa $P(n)$ benar untuk semua bilangan bulat postitf $n$. Perhatikan contoh berikut

(Contoh) Buktikan bahwa jumlah $n$ bilangan bulat positif pertama adalah $\frac{n(n + 1)}{2}$.

(Solusi) Misalkan $P(n)$ menyatakan proposisi bahwa jumlah $n$ bilangan bulat pertama adalah $\frac{n(n + 1)}{2}$, yaitu $1 + 2  + 3 + \cdots + n = \frac{n(n + 1)}{2}$.

Basis Induksi : Buktikan $P(1)$ benar, karena untuk $n = 1$ diperoleh

$$\begin{aligned} 1 &= \frac{1(1 + 1)}{2} \\ &= \frac{2}{2} \\ &= 1 \end{aligned}$$

Langkah Induksi : Misalkan berlaku bahwa $P(k)$ benar yaitu mengasumsikan bahwa $$1 + 2 + 3 + \cdots k = \frac{k(k + 1)}{2}$$ adalah benar (hipotesis induksi). Harus diperlihatkan bahwa $P(k + 1)$ juga benar yaitu $$1 + 2 + 3 + \cdots k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$$ Perhatikan bahwa $$\begin{aligned}1 + 2 + 3 + \cdots k + (k + 1) &= (1 + 2 + 3 + \cdots + k) + (k + 1) \\ &= \frac{k(k + 1)}{2} + (k + 1) \\ &= \frac{k^2 + k}{2} + (k + 1) \\ &= \frac{k^2 + 3k + 2}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{aligned}$$ Karena basis induksi dan langkah induksi telah dibuktikan benar, maka untuk semua bilangan bulat positif $n$, terbukti bahwa $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

$\blacksquare$

2.3 Jenis - Jenis Induksi

2.3.1 Induksi Matematika yang Dirampatkan

Misalkan $P(n)$ adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa $P(n)$ benar untuk semua bilangan bulat $n \geq n_0$. Untuk membuktikan hal tersebut, kita hanya perlu menunjukan bahwa : 

1. $P(n_0)$ benar 

2. Jika $P(k)$ benar maka $P(k + 1)$ juga benar, untuk setiap bilangan bulat $k \geq n_0$

(Contoh) Buktikan bahwa ketaksamaan berikut benar untuk bilangan bulat $n \geq 3$ $$2^n > 2n + 1$$

(Solusi) Basis Induksi : Untuk $n = 3$ berlaku $2^3 > 2 \times 3 + 1$ karena $8 > 7$

Langkah Induksi : Asumsikan pernyataan $2^k > 2k + 1$ benar. Dengan mengalikan 2 kepada kedua ruas maka diperoleh $$2^{k+1} > 2(2k+1) = 4k + 2 = 2k + (2k+2) > 2k + 3 = 2(k+1) + 1$$ karena $2k + 2 > 3$ untuk setiap $k \geq 3$. Artinya basis induksi dan langkah induksi terbukti benar. Jadi benar bahwa ketaksamaan $2^n > 2n + 1$ untuk semua bilangan bulat $n \geq 3$

$\blacksquare$

2.3.2 Induksi Kuat

Misalkan $P(n)$ adalah pernyataan perihal bilangan bulat. Kita ingin membuktikan bahwa $P(n)$ benar untuk semua bilangan bulat $n \geq n_0$. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa :

1. $P(n_0)$ benar, dan 

2, Jika $P(n_0)$, $P(n_0 + 1)$, $\cdots$, $P(k)$ benar maka $P(k+1)$ juga benar untuk setiap bilangan bulat $k \geq n_0$

(Contoh) Bilangan bulat postif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif $n$ $(n \geq 2)$ dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

(Solusi) Basis Induksi : Untuk $n = 2$, maka 2 sendiri adalah bilangan prima dan 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

Langkah Induksi : Misalkan pernyataan pada soal benar bahwa bilangan $2, 3, \cdots, k$ dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Perlu ditunjukkan bahwa $k + 1$ juga dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima. Ada dua kemungkinan yang dapat terjadi yaitu

(a) Jika $k + 1$ merupakan bilangan prima, maka jelas $k+1$ dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

(b) Jika $k + 1$ bukan bilangan prima, maka terdapat bilangan bulat positif $a$ dan $b$ dengan $2 \leq a \leq b \leq k$ sehingga $k + 1 = ab$. Menurut hipotesis induksi, $a$ dan $b$ dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Hal ini menandakan bahwa $k+1$ dapat dinyatakan sebagai perkalian bilangan prima karena $k+1 = ab$.

Karena basis induksi dan langkah iduksi sudah ditunjukkan benar maka terbukti bahwa setiap bilangan bulat positif $n$ $(n \geq 2)$ dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

$\blacksquare$

Selain kedua jenis diatas, masih terdapat banyak jenis - jenis induksi yang bisa digunakan dalam membuktikan kebenaran sebuah pernyataan perihal bilangan bulat.

3. Aplikasi Induksi Matematika untuk Membuktikan Kebenaran Program

function Exp (a : integer, m : integer)
{Fungsi untuk menghitung $a^m$}
Deklarasi
        $k,r$ : integer

Algoritma
        $r$ $\leftarrow$ $1$
        $k$ $\leftarrow$ $m$
        while ($k > 0$)
                $r$ $\leftarrow$ $r*a$
                $k$ $\leftarrow$ $k-1$
        end
        return r

Algoritma di atas dapat dibuktikan benar dengan induksi matematika, yaitu di akhir algoritma fungsi mengembalikan nilai $a^m$.  Misalkan $r_n$ dan $k_n$ adalah nilai dari $r$ dan $k$ berturut - turut setelah melewati loop while sebanyak $n$ kali ($n \geq 0$). Misalkan $P(n)$ adalah proposisi : $r_n \times k_n = a^m$, $n \geq 0$. Akan ditunjukkan bahwa $P(n)$ benar dengan induksi matematika.

Basis induksi : Untuk $n = 0$, maka $r_0 = 1$ dan $k_0 = m$. Maka $P(0)$ benar sebab $$r_0 \times a^{k_0} = a^m \Leftrightarrow  1 \times a^m = a^m$$

Langkah induksi : Asumsikan $P(n)$ benar untuk $n \geq 0$, yaitu setelah melewati while loop $n$ kali, yaitu $r_n \times a^{k_n} = a^m$. Kita harus menunjukan bahwa $P(n+1)$ benar, yaitu $r_{n+1} \times a^{k_{n+1}} = a^m$ Perhatikan bahwa $$r_{n+1} = r_n \times a$$ $$k_{n+1} = k_n - 1$$ maka $$\begin{aligned} r_{n+1} \times a^{k_{n+1}} &= (r_n \times a) \times a^{k_n - 1} \\ &= r_n \times a^{k_n} \\ &= a^m \end{aligned}$$ Jadi $P(n+1)$ benar.

Karena kedua langkah telah ditunjukkan benar maka $P(n)$ benar untuk setiap $n \geq 0$. Algoritma fungsi diatas mengembalikan nilai dari $r_n$ disaat $k_n = 0$, yang berarti $r_n \times 1 = a^m$, dengan kata lain algoritma fungsi diatas mengembalikan nilai $a^m$.

$\blacksquare$

Referensi :

1. Introduction to Real Analysis (Fourth Edition) - Robert G. Bartle & Donald R. Sherbert
2. Slide Mata Kuliah Matematika Diskret ITB - Induksi Matematik - Rinaldi Munir