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\ne \mathrm{\varnothing }$, maka terdapat elemen $m\in S$ sedemikian hingga $m\le 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\ne \mathbb{N}$, maka himpunan $\mathbb{N}\mathrm{\setminus }S$ tidak kosong, dan selanjutnya dengan Teorema , $\mathbb{N}\mathrm{\setminus }S$ memuat elemen terkecil. Misalkan $m$ adalah elemen terkecil dari $\mathbb{N}\mathrm{\setminus }S$. Berdasarkan hipotesis (1), $1\in S$, maka $m\ne 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