Induksi Matematika merupakan sebuah metode pembuktian dalam matematika. Induksi matematika digunakan untuk membuktikan pernyataan-pernyataan yang berlaku untuk bilangan-bilangan asli. Sebagai contoh, perhatikan pernyataan berikut.

Contoh

Untuk setiap bilangan asli $n$, berlaku$$1+2+3+ \ldots +n=\frac{n(n+1)}{2}$$

Untuk $n=1$, kita peroleh $1=\frac{1(1+1)}{2}$ yang bernilai benar. Untuk $n=2$, kita peroleh $1+2=\frac{2(2+1)}{2}$ yang juga bernilai benar. Kita coba untuk nilai $n$ yang lebih besar, misalnya $n=5$. Kita peroleh $1+2+3+4+5=\frac{5(5+1)}{2}$. Dapat dicek bahwa ruas kiri dan kanan berjumlah sama, yaitu 15. Namun apakah memeriksa beberapa nilai seperti ini, cukup untuk membuktikan bahwa pernyataan tersebut benar untuk semua bilangan asli $n$? Tentu tidak.

Sebelum membahas lebih lanjut mengenai induksi matematika dan contoh-contohnya, kita akan membuktikan prinsip induksi matematika. Pembuktian ini memanfaatkan Sifat Terurut Baik dari himpunan bilangan asli. Jika pembaca ingin fokus pada penggunaan Prinsip Induksi Matematika, pembaca dapat melewati pembahasan mengenai sifat ini.

Lewati

Sifat Terurut Baik dari $\mathbb{N}$

Setiap himpunan bagian tak kosong dari $\mathbb{N}$ memiliki elemen terkecil.

Berdasarkan sifat di atas, jika $S$ himpunan bagian tak kosong dari $\mathbb{N}$ maka $S$ memiliki elemen terkecil. Sebagai contoh, $S=\{3,7,11\}$ merupakan himpunan bagian dari $\mathbb{N}$. Himpunan $S$ memiliki elemen terkecil, yaitu 3. Cukup jelas, kan? Kita akan menggunakan sifat ini dalam membuktikan Prinsip Induksi Matematika.

Prinsip Induksi Matematika

Misalkan $S \subseteq \mathbb{N}$ yang memenuhi kedua sifat berikut.
  1. Bilangan $1 \in S$.
  2. Untuk setiap $k \in \mathbb{N}$, jika $k \in S$ maka $k+1 \in S$.
Maka kita punya $S=\mathbb{N}$.

Lewati Bukti

Bukti

Kita akan membuktikan prinsip induksi matematika dengan bukti kontradiksi. Andaikan $S \neq \mathbb{N}$. Maka $\mathbb{N} \backslash S$ bukan himpunan kosong dan jelas merupakan himpunan bagian dari $\mathbb{N}$. Berdasarkan Sifat Terurut Baik, $\mathbb{N} \backslash S$ mempunyai elemen terkecil, kita misalkan dengan $m$.

Berdasarkan hipotesis 1, kita tahu bahwa $1 \in S$, sehingga $1 \notin \mathbb{N} \backslash S$. Karena $m$ elemen terkecil dari $\mathbb{N} \backslash S$ dan $1 \notin \mathbb{N} \backslash S$, maka haruslah $m>1$. Namun ini berarti $m-1>0$, sehingga $m-1$ juga bilangan asli. Perhatikan bahwa $m-1< m$. Karena $m$ elemen terkecil dari $\mathbb{N} \backslash S$, maka $m-1$ bukan elemen dari $\mathbb{N} \backslash S$. Artinya, $m-1 \in S$.

Misalkan $k=m-1 \in S$. Berdasarkan hipotesis 2, jika $k \in S$ maka $k+1 \in S$. Artinya $k+1=(m-1)+1=m \in S$. Padahal sebelumnya, kita menyatakan bahwa $m$ elemen terkecil dari $\mathbb{N} \backslash S$, yang berarti $m \notin S$. Terjadi kontradiksi. Dengan demikian, pengandaian bahwa $S \neq \mathbb{N}$ tidak boleh dilakukan. Jadi, terbukti bahwa $S=\mathbb{N}$.

Bentuk Lain Prinsip Induksi Matematika

Pada awal pembahasan, kita menyatakan bahwa Induksi Matematis digunakan untuk membuktikan pernyataan mengenai bilangan asli. Nah, untuk itu kita perlu mempelajari bentuk lain dari Prinsip Induksi Matematika di atas, sebab pada prinsip di atas kita menggunakan istilah himpunan dan elemennya.

Untuk setiap $n \in \mathbb{N}$, kita misalkan $P(n)$ adalah pernyataan mengenai $n$. Sebagai contoh, $P(n)$ adalah pernyataan "$n^3+5n$ habis dibagi 6", di mana $n$ bilangan asli. Maka $P(1)$ adalah pernyataan "$1^3+5 \cdot 1$ habis dibagi 6" dan $P(7)$ adalah pernyataan "$7^3+5 \cdot 7$ habis dibagi 6". Sebagai pernyataan, tentu $P(1)$, $P(7)$, dan yang lainnya memiliki nilai kebenaran (benar atau salah, namun tidak keduanya).

Misalkan $S=\{ n \in \mathbb{N} \mid P(n) \text{ bernilai benar} \}$. Jika $P(3)$ bernilai benar maka $3 \in S$, dan jika $P(4)$ bernilai salah maka $4 \notin S$. Sebaliknya, jika $6 \in S$ maka pernyataan $P(6)$ bernilai benar. Dengan demikian, Prinsip Induksi Matematika juga dapat dinyatakan sebagai berikut.

Prinsip Induksi Matematika

Untuk setiap $n \in \mathbb{N}$, misalkan $P(n)$ adalah pernyataan mengenai $n$. Misalkan $P(n)$ memenuhi kedua sifat berikut.
  1. $P(1)$ bernilai benar.
  2. Untuk setiap $k \in \mathbb{N}$, jika $P(k)$ bernilai benar maka $P(k+1)$ bernilai benar.
Maka $P(n)$ bernilai benar untuk setiap $n \in \mathbb{N}$.

Sebelum masuk pada contoh soal, kita perlu memahami Prinsip Induksi Matematika dengan baik. Poin 1 dinamakan Langkah Dasar dan poin 2 dinamakan Langkah Induksi. Dari sini, bisa muncul pertanyaan, apakah cukup jika hanya dengan Langkah Induksi? Jawabannya, tidak. Sebab dengan mengetahui bahwa untuk setiap $k \in \mathbb{N}$ berlaku "jika $P(k)$ bernilai benar maka $P(k+1)$ bernilai benar", kita tidak dapat menarik kesimpulan apa-apa. Hanya terdapat sebuah premis (misalkan premis 1). Untuk itu, kita memerlukan premis lain (misalkan premis 2), dalam hal ini kita menggunakan premis "P(1) bernilai benar". Dan premis inilah yang dibuktikan pada Langkah Dasar. Untuk nilai $k=1$, kita peroleh

Premis 1: Jika $P(1)$ bernilai benar maka $P(2)$ bernilai benar.
Premis 2: $P(1)$ bernilai benar.

Berdasarkan Modus Ponens, kita dapat menyimpulkan bahwa $P(2)$ bernilai benar. Dengan cara yang sama, kita dapat membuktikan bahwa $P(3)$, $P(4)$, dan seterusnya juga bernilai benar. Bagaimana, sudah ada gambaran mengenai induksi matematika bukan?

Contoh 1

Buktikan bahwa, untuk setiap bilangan asli $n$, berlaku$$1+2+3+ \ldots +n=\frac{n(n+1)}{2}$$

Pembahasan

Pertama, kita misalkan $P(n)$ adalah pernyataan $1+2+3+ \ldots +n=\frac{n(n+1)}{2}$.

Langkah Dasar
Untuk $n=1$, kita punya$$P(1):1=\frac{1(1+1)}{2}$$Untuk memeriksa, kita dapat memulai dari ruas kanan.$$\frac{1(1+1)}{2}=\frac{2}{2}=1$$Diperoleh ruas kiri. Jadi, $P(1)$ bernilai benar. Berikutnya, kita lanjut pada langkah induksi.

Langkah Induksi

Kita akan membuktikan pernyataan "Jika $P(k)$ bernilai benar maka $P(k+1)$ bernilai benar". Kita dapat memulai dengan mengasumsikan $P(k)$ bernilai benar. Dengan menggunakan asumsi ini, kita membuktikan bahwa $P(k+1)$ juga bernilai benar.

Misal $k \in \mathbb{N}$. Asumsikan pernyataan $P(k)$ bernilai benar, yaitu$$P(k):1+2+3+ \ldots +k=\frac{k(k+1)}{2}$$Kita akan menunjukkan bahwa $P(k+1)$ juga bernilai benar, yaitu$$P(k+1):1+2+3+ \ldots +k+(k+1)=\frac{[k+1] \left([k+1]+1 \right)}{2}$$

Kita mulai dari ruas kiri persamaan, yang dapat ditulis seperti berikut, berdasarkan sifat asosiatif.$$1+2+3+ \ldots +k+(k+1)=(\underbrace{1+2+3+ \ldots +k}_{\text{Perhatikan Asumsi}})+(k+1)$$Berdasarkan asumsi, kita peroleh$$\begin{aligned}1+2+3+ \ldots +k+(k+1) &= \frac{k(k+1)}{2}+(k+1) \\&= (k+1) \left( \frac{k}{2}+1 \right) \\&= (k+1) \cdot \left( \frac{k+2}{2} \right) \\&= \frac{(k+1)(k+2)}{2} \\&= \frac{[k+1] \left( [k+1]+1 \right)}{2}\end{aligned}$$Nah, terbukti bahwa $P(k+1)$ bernilai benar.

Berdasarkan Prinsip Induksi Matematika, terbukti bahwa $P(n)$ bernilai benar untuk setiap bilangan asli $n$. Jadi, untuk setiap bilangan asli $n$, berlaku$$1+2+3+ \ldots +n=\frac{n(n+1)}{2}$$

Contoh 2

Buktikan bahwa $3^n+1$ habis dibagi 2, untuk setiap bilangan asli $n$.

Pembahasan

Pertama, kita misalkan $P(n)$ adalah pernyataan $3^n+1$ habis dibagi n.

Langkah Dasar
Untuk $n=1$, kita punya$$P(1):3^1+1 \text{ habis dibagi } 2$$Karena $3^1+1=4$ dan 4 habis dibagi 2, maka $P(1)$ bernilai benar.

Langkah Induksi
Misal $k \in \mathbb{N}$. Asumsikan $P(k)$ bernilai benar, yaitu$$P(k):3^k+1 \text{ habis dibagi } 2$$Kita akan menunjukkan bahwa $P(k+1)$ juga bernilai benar, yaitu$$P(k+1):3^{k+1}+1 \text{ habis dibagi } 2$$

Perhatikan bahwa$$3^{k+1}+1 = 3^k \cdot 3^1+1= 3\cdot 3^k +1$$Kita perlu memunculkan asumsi sebelumnya, yaitu $3^k+1$ yang habis dibagi 2. Perhatikan bahwa$$\begin{aligned}3^{k+1}+1 &= 3\cdot 3^k +1 \\&= (2+1) \cdot 3^k +1 \\&= (2 \cdot 3^k + 3^k)+1 \\&= 2 \cdot 3^k + \underbrace{(3^k+1)}_{\text{Perhatikan Asumsi}}\end{aligned}$$

Berdasarkan asumsi, $3^k+1$ habis dibagi 2, artinya terdapat suatu bilangan bulat $m$ sehingga $3^k+1=2 \cdot m$. Akibatnya$$\begin{aligned}3^{k+1}+1 &= 2 \cdot 3^k + 2 \cdot m \\&= 2(3^k+m)\end{aligned}$$Karena 2 merupakan faktor dari $2(3^k+m)=3^{k+1}+1$, maka jelas bahwa $3^{k+1}+1$ habis dibagi 2. Dengan demikian, $P(k+1)$ bernilai benar.

Berdasarkan Prinsip Induksi Matematika, terbukti bahwa $P(n)$ bernilai benar untuk setiap bilangan asli $n$. Jadi, $3^n+1$ habis dibagi 2, untuk setiap bilangan asli $n$.

Pada beberapa kasus, pernyataan $P(n)$ bernilai salah untuk beberapa nilai, namun bernilai benar untuk setiap $n \geq n_0$, untuk suatu bilangan asli $n_0$. Sebagai contoh, perhatikan pernyataan "$P(n):2^n>2n+1$". Pernyataan $P(n)$ bernilai salah untuk nilai $n=1$ dan $n=2$. Namun bernilai benar untuk $n=3$ dan $n=4$. Lebih lanjut, $P(n)$ bernilai benar untuk setiap $n \geq 3$. Untuk membuktikan pernyataan semacam ini, kita dapat menggunakan bentuk lain dari Prinsip Induksi Matematika berikut.

Prinsip Induksi Matematika

Misalkan $n_0 \in \mathbb{N}$ dan $P(n)$ adalah pernyataan yang berlaku untuk setiap $n \geq n_0$. Misalkan $P(n)$ memenuhi kedua sifat berikut.
  1. $P(n_0)$ bernilai benar.
  2. Untuk setiap $k \in \mathbb{N}$, jika $P(k)$ bernilai benar maka $P(k+1)$ bernilai benar.
Maka $P(n)$ bernilai benar untuk setiap $n \geq n_0$.

Prinsip Induksi Matematika di atas nampak mirip dengan bentuk sebelumnya, bukan? Perbedaannya hanya terletak pada langkah dasar. Pada langkah dasar, baik bentuk pertama maupun kedua, kita memeriksa apakah pernyataan $P(a)$ bernilai benar, di mana $a$ merupakan bilangan asli terkecil pada batasan nilai $n$ yang diberikan. Pada bentuk pertama, tidak dinyatakan batasan nilai $n$. Hal ini berarti $n \geq 1$, sehingga kita memeriksa pernyataan $P(1)$. Jika batasannya adalah $n \geq 3$ maka kita memeriksa pernyataan $P(3)$. Namun, bagaimana jika batasan nilai $n$ adalah $n>4$? Kita memilih nilai $n$ yang paling kecil, yaitu $n=5$, sehingga kita memeriksa pernyataan $P(5)$.

Contoh 3

Buktikan bahwa $2^n< n!$ untuk setiap $n \geq 4$, dan $n \in \mathbb{N}$.

Pembahasan

Pertama, kita misalkan $P(n)$ adalah pernyataan $2^n< n!$.

Langkah Dasar
Untuk $n=4$, kita punya $P(4):2^4< 4!$. Karena $2^4=16$ dan $4!=24$, maka $2^4< 4!$. Jadi, $P(4)$ bernilai benar.

Langkah Induksi
Misalkan $k \in \mathbb{N}$, dengan $k \geq 4$. Asumsikan $P(k)$ bernilai benar, yaitu $P(k):2^k< k!$. Kita akan menunjukkan bahwa $P(k+1)$ juga bernilai benar, yaitu $P(k):2^{k+1}< (k+1)!$.

Perhatikan bahwa$$\begin{aligned}2^{k+1} &< 2^k \cdot 2^1 \\&= 2 \cdot 2^k \\&< 2 \cdot k! &[\text{Berdasarkan Asumsi}] \\&= k!+k!\end{aligned}$$Diperoleh $2^{k+1}< k!+k!$. Diketahui $k \geq 4 >1$ atau $1 < k$, sehingga $k! < k \cdot k!$. Akibatnya$$\begin{aligned}2^{k+1} &< k!+k! \\&< k \cdot k! +k! \\&= (k+1) \cdot k! \\&= (k+1)!\end{aligned}$$Diperoleh $2^{k+1}< (k+1)!$. Dengan demikian, $P(k+1)$ bernilai benar.

Berdasarkan Prinsip Induksi Matematika, terbukti bahwa $P(n)$ bernilai benar untuk setiap $n \geq 4$, dan $n \in \mathbb{N}$. Jadi, $2^n< n!$ untuk setiap $n \geq 4$, dan $n \in \mathbb{N}$.

Contoh 4

Buktikan bahwa $2^n > n^2$ untuk setiap $n > 4$, dan $n \in \mathbb{N}$.

Pembahasan

Pertama, kita misalkan $P(n)$ adalah pernyataan $2^n > n^2$.

Langkah Dasar
Untuk $n=5$, kita punya $P(5):2^5 > 5^2$. Karena $2^5=32$ dan $5^2=25$, maka $2^5 > 5^2$. Jadi, $P(5)$ bernilai benar.

Langkah Induksi
Misalkan $k \in \mathbb{N}$, dengan $k > 4$. Asumsikan $P(k)$ bernilai benar, yaitu $P(k):2^k > k^2$. Kita akan menunjukkan bahwa $P(k+1)$ juga bernilai benar, yaitu $P(k):2^{k+1} > (k+1)^2$.

Perhatikan bahwa$$\begin{aligned}2^{k+1} &= 2^k \cdot 2^1 \\&= 2 \cdot 2^k \\&> 2 \cdot k^2 &[\text{Berdasarkan Asumsi}]\end{aligned}$$Pada bagian ini, kita memperoleh $2^{k+1}>2k^2 \quad (\ast)$.

Dalam pembuktian dengan induksi matematika, terkadang kita perlu bekerja mundur untuk memperoleh hasil yang kita inginkan. Berdasarkan proses di atas, kita memperoleh $2^{k+1}>2k^2$. Padahal yang ingin kita tuju adalah $2^{k+1}>(k+1)^2$. Ini artinya, kita perlu menunjukkan bahwa $2k^2 > (k+1)^2$. Kita akan mencoba bekerja mundur. Perhatikan bahwa$$\begin{aligned}2k^2 &> (k+1)^2 \\2k^2 &> k^2+2k+1 \\k^2-2k-1 &> 0 \\k^2-2k+1 &> 2 \\(k-1)^2 &> 2\end{aligned}$$Diperoleh $(k-1)^2 > 2$. Yang jadi pertanyaan, apakah hasil ini bernilai benar untuk setiap nilai $k$ pada soal? Jika ya, maka kita dapat memanfaatkan hasil ini untuk melanjutkan bukti di atas.

Untuk $k>4$, berlaku $(k-1)^2 > (4-1)^2 = 9 > 2$. Kita dapat menguraikan pertidaksamaan $(k-1)^2>2$ sebagai berikut.$$\begin{aligned}(k-1)^2 &> 2 \\k^2-2k+1 &> 2 \\k^2-2k-1 &> 0 \\2k^2 &> k^2+2k+1 \\2k^2 &> (k+1)^2\end{aligned}$$

Diperoleh $2k^2 > (k+1)^2$. Akibatnya, pertidaksamaan $(\ast)$ pada bagian sebelumnya menjadi $2^{k+1}>2k^2>(k+1)^2$. Dengan demikian, $P(k+1)$ bernilai benar.

Berdasarkan Prinsip Induksi Matematika, terbukti bahwa $P(n)$ bernilai benar untuk setiap $n > 4$, dan $n \in \mathbb{N}$. Jadi, $2^n > n^2$ untuk setiap $n > 4$, dan $n \in \mathbb{N}$.

Induksi matematika yang baru saja kita pelajari disebut Induksi Matematika Lemah. Semoga penulis memiliki kesempatan untuk melanjutkan pembahasan mengenai Induksi Matematika Kuat dalam tulisan berikutnya. Semoga bermanfaat.

Referensi
Introduction to Real Analysis (Fourth Edition), by Robert G. Bartle and Donald R. Sherbert