Prinsip Induksi Matematika Adalah Suatu Teorema

Dalam tulisan ini, saya akan membahas mengenai Teorema (Prinsip) Induksi Matematika yang akan kita singkat dengan PIM. PIM digunakan sebagai metode pembuktian rumus/formula yang berkaitan dengan himpunan bilangan asli. Ide pembuktian dengan metode induksi matematika dimulai oleh Francesco Maurolico, seorang matematikawan asal Itali yang hidup pada tahun 1494–1575. Maurolico menggunakan metode induksi matematika dengan cara yang "agak samar". Penggunaan metode pembuktian dengan induksi matematika yang pertama kali dengan cara moderen saat ini sebagai metode pembuktian yang sah, muncul dalam artikel Traite du Triangle Arithmetique yang dipublikasikan pada abad ke-17. Artikel ini ditulis oleh Blaise Pascal pada tahun 1653 yang dicetak untuk publikasi pada tahun 1665 (David Burton, The History of Mathematics: An Introduction, 2011).

Himpunan bilangan asli akan kita notasikan dengan $\mathbb{N}$, yaitu \begin{equation*} \mathbb{N} = \{ 1, 2, 3, 4, \dots, n, n+1, \dots \}. \end{equation*} Salah satu fakta penting yang dipunyai oleh $\mathbb{N}$ adalah Sifat (Teorema/Prinsip) Keterurutan dengan Baik (Well Ordering Property).

Sifat Keterurutan dengan Baik $\mathbb{N}$. Setiap himpunan bagian tak kosong dari $ \mathbb{N} $ mempunyai elemen terkecil. Dengan demikian, jika $ S \subseteq \mathbb{N} $ dan $ S \neq \emptyset $, maka terdapat $ b \in S $ sehingga $ b \leq s $ untuk setiap $ s \in S $.

Dengan berbekal sifat keterurutan dengan baik himpunan bilangan asli, kita bisa membuktikan PIM.

Teorema PIM. Misalkan $ S $ adalah himpunan bagian dari $ \mathbb{N} $ dan memenuhi:
(1) $ 1 \in S $, dan
(2) jika $ k \in S $, maka $ k+1 \in S $.
Akibatnya $ S = \mathbb{N} $.

Bukti Teorema PIM: Kita akan membuktikan secara kontradiksi. Andaikan $ S \neq \mathbb{N} $. Hal ini berarti, terdapat $ a \in \mathbb{N} $ tetapi $ a \notin S $. Dengan menamakan $ T = \mathbb{N} - S $, diperoleh $ T \neq \emptyset $. Karena $ T $ himpunan bagian tak kosong dari $ \mathbb{N} $, maka menurut Sifat Keterurutan dengan Baik $ \mathbb{N} $, terdapat $ b $ elemen terkecil dari $ T $, tepatnya, $ b \in T $ dan $ b \leq t $ untuk setiap $ t \in T $. Menurut hipotesis (1), $ 1 \in S $, yang mengakibatkan $ b > 1 $ (Lihat Alasan 1). Selanjutnya diperoleh $ b-1 \in \mathbb{N} $. Karena $ b $ elemen terkecil dari $ T $, maka $ b-1 \notin T $, yang berakibat $ b-1 \in S $ (Lihat Alasan 2). Menurut hipotesis (2), diperoleh $ b = (b-1) + 1 \in S $. Hal terakhir ini berkontradiksi dengan fakta $ b \in T $, yang berarti $ b \notin S $. Dengan demikian, haruslah $ S = \mathbb{N} $. Teorema terbukti secara kontradiksi. QED

Alasan 1. Andaikan $ b \leq 1 $. Diperoleh $ b = 1 \in S $. Di lain pihak $ b \in T = \mathbb{N} - S $, berarti $ b \notin S $. Kontradiksi. Haruslah $ b>1 $.

Alasan 2. Andaikan $ b-1 \notin S $. Karena $ b-1 \in \mathbb{N} $, maka $ b-1 \in T $. Kontradiksi dengan $ b-1 \notin T $. Haruslah $ b-1 \in S $.

Saya akan memberikan contoh bagaimana menggunakan PIM dalam penyelesaian soal-soal Olimpiade matematika. See U.