Induksi Matematika

Induksi matematika merupakan metode pembuktian yang penting dan akan sering digunakan di dalam matematika. Metode ini digunakan untuk membuktikan kevalidan suatu pernyataan yang berlaku untuk semua bilangan asli $\mathbb{N}$.

Teorema Sifat Terurut Baik dari $\mathbb{N}$
Setiap subset tak kosong dari $\mathbb{N}$ mempunyai elemen terkecil.

Pernyataan yang lebih detail dari sifat ini adalah sebagai berikut: Jika $S$ adalah subset dari $\mathbb{N}$ dan $S \neq \emptyset$, maka terdapat elemen $m \in S$ sedemikian hingga $m \leq k$ untuk semua $k \in S$.

Prinsip Induksi Matematika Jika $S$ adalah subset dari $\mathbb{N}$ yang memiliki sifat-sifat:
(1). $1 \in S$
(2). Jika $k \in S$, maka $k + 1 \in S$ maka S = $\mathbb{N}$.

Bukti :

Jika diandaikan $S \neq \mathbb{N}$, maka himpunan $\mathbb{N}\backslash S$ tidak kosong, dan selanjutnya dengan Teorema , $\mathbb{N}\backslash S$ memuat elemen terkecil. Misalkan $m$ adalah elemen terkecil dari $\mathbb{N}\backslash S$. Berdasarkan hipotesis (1), $1 \in S$, maka $m \neq 1$. Selanjutnya $m > 1$, sehingga $m-1$ juga bilangan asli. Karena $m-1 < m$ dan karena $m$ elemen terkecil dari $\mathbb{N}$ sedemikian hingga $m \notin S$, maka $m-1$ di dalam $S$.

Sekarang, berdasarkan hipotesis (2) untuk elemen $k = m -1$ di dalam $S$, disimpulkan $k + 1 = (m-1) + 1 = m$ di dalam $S$. Kesimpulan ini kontradiksi dengan $m$ bukan elemen di $S$. Ini berarti pengandaian salah. Yang benar $S = N$.

Prinsip induksi matematika juga sering dinyatakan dengan rumusan sebagai berikut:

Untuk setiap $n \in \mathbb{N}$, misalkan $P(n)$ pernyataan yang bergantung pada $n$. Jika
(1') $P(1)$ benar
(2') Jika $P(k)$ benar, maka $P(k + 1)$ benar, maka $P(n)$ benar untuk semua $n \in \mathbb{N}$.

Hubungan dengan versi sebelumnya dibuat dengan memisalkan $S := \{n \in \mathbb{N} : P(n)\,\,\, \text{benar}\}$.

Contoh-contoh berikut memberikan gambaran bagaimana Prinsip Induksi Matematika digunakan untuk membuktikan pernyataan-pernyataan yang bergantung pada bilangan asli.

Sumber : Bartle, Sherbert. Introduction To Real Analysis 2ed John Wiley and Sons

Baca Juga : Induksi Matematika Lanjutan