## Contemporary Mathematics and Applications
Vol. 5, No. 1, 2023, pp. 1-5.

## Tentang Rumus Induksi Matematika
M. Yusuf Syaifuddin 1,* , S. Zahidah 2 & Eridani 3
1,2,3 Departemen Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga, Indonesia
*Corresponding author : muchammad-y-s@fst.unair.ac.id
Abstract. This  paper  presents  various  forms  of  induction  formulas.  There  are  three  forms  of induction  formulas  in  this  paper  and  these  formulas  are  equivalent  each  other.  This  paper  also provides information related to evidence equivalence of these formulas by proving that all of these formulas are equivalent to the Well-Ordering Principle which applies to natural number set.
Keywords: mathematical induction, well-ordering principle.

## 1 Pendahuluan
Dalam sebuah penelitian, dibutuhkan analisa dalam menyelesaikan suatu permasalahan. Pada  dasarnya  pengembangan  pola  berpikir  manusia  dalam  menganalisa  suatu permasalahan  terdapat  dua  bentuk,  yaitu  logika  berpikir  deduktif  dan  logika  berpikir induktif. Logika berpikir deduktif biasanya didasarkan pada aturan logika yang ketat dan sebagian besar tidak dapat disangkal. Sedangkan logika berpikir induktif adalah tindakan menebak  pola  atau  aturan  atau  memprediksi  perilaku  masa  depan  berdasarkan pengalaman  masa  lalu.  Seperti  halnya  ketika  kita  mengalami  matahari  terbit  di  setiap pagi,  maka  tanpa  banyak  berpikir,  kita  akan  menyimpulkan  dengan  tanpa  keraguan matahari akan terbit esok pagi.
Salah  satu  bentuk  logika  berpikir  induktif  adalah  Induksi  Matematika.  Induksi Matematika adalah bentuk logika berpikir untuk membuktikan beberapa aturan atau pola tertentu yang biasanya tak terbatas yang bahkan keberadaannya tidak diketahui, seperti halnya yang dikatakan Herbert S. Wilf “Induksi membuat anda merasa bersalah karena mendapatkan  sesuatu  dari  ketiadaan,  dan  itu  artifisial,  namun  hal  itu  merupakan  salah satu gagasan besar dari sebuah peradaban” [1].
Terdapat banyak sekali pernyataan matematika yang menyatakan bahwa suatu sifat benar untuk semua bilangan bulat positif. Sedangkan kita tahu bahwa bilangan bulat positif itu menuju  ke  tak  hingga,  dengan  kata  lain  akan  sangat  sulit  untuk  dibuktikan  secara langsung. Sebagai contoh, pernyataan berikut ini berlaku untuk semua 𝑛 bilangan bulat positif, 𝑛! ≤ 𝑛 𝑛 , 𝑛 3 − 𝑛 habis dibagi 3 , himpunan dengan 𝑛 anggota mempunyai tepat
2 𝑛 himpunan bagian, jumlahan dari 𝑛 bilangan bulat positif pertama adalah 𝑛(𝑛+1) 2 , dan lain  sebagainya.  Oleh  karena  itu,  Induksi  Matematika  dapat  digunakan  untuk membuktikan  pernyataan-pernyataan  matematika  tersebut.  Induksi  Matematika mempunyai  dua  bagian,  yang  pertama,  membuktikan  bahwa  pernyataan  benar  untuk nilai-nilai awal bilangan bulat positif secara langsung. Sedangkan bagian kedua, dengan mengasumsikan  bahwa  pernyataan  benar  untuk  suatu  bilangan  bulat  positif,  maka tunjukkan  pernyataan  tersebut  benar  untuk  bilangan  bulat  positif  yang  lebih  besar berikutnya [2].
Terdapat  beberapa  rumus  induksi  matematika.  Dalam  naskah  ini  akan  diperkenalkan beberapa  rumus  induksi  matematika  dan  akan  dibahas  ekivalesi  dari  beberapa  rumus induksi matematika tersebut.

## 2 Induksi Matematika
Di  sini  kita  meninjau  himpunan  bilangan  alam ℕ = {1,2,3, … } sebagai  semesta pembicaraan dalam subbab ini.
Definisi 1.1 Misalkan 𝐴 ⊆ ℕ dan 𝐴 ≠ ∅ . Unsur 𝑒 ∈ 𝐴 disebut unsur terkecil 𝐴 , jika 𝑥 ≤ 𝑦 , untuk setiap 𝑦 ∈ 𝐴 .
Salah  satu  sifat  penting  dari ℕ adalah  sebagai  berikut.  Periksa  [3]  untuk  pernyataan detilnya.
Postulat 1.2 (Sifat Terurut Rapi). Sebarang subhimpunan takkosong ℕ selalu mempunyai unsur terkecil.
Kita  lihat  bahwa 1 ≤ 𝑝 ,  untuk  setiap 𝑝 ∈ ℕ ,  dan  ini  berarti  1  adalah  unsur  terkecil ℕ . Misalkan 𝔼 menyatakan himpunan bilangan genap positif, maka 2 ≤ 𝑥 , untuk setiap 𝑥 ∈ 𝔼 . Dengan demikian 2 adalah unsur terkecil 𝔼 .
Sifat Terurut Rapi ℕ akan kita gunakan untuk membuktikan teorema berikut.
Teorema  1.3 (Induksi  1).  Misalkan ∅ ≠  𝑆 ⊆ ℕ ,$  dengan 1 ∈  𝑆 .  Jika 𝑥 ∈  𝑆 , mengakibatkan 𝑥 + 1 ∈ 𝑆 , maka 𝑆 = ℕ .
Bukti. Andaikan 𝑆 ≠ ℕ ,  maka 𝑆 𝑐 ≠ ∅ .$  Karena 𝑆 𝑐 ⊆ ℕ ,  maka  dapat  dipilih 𝑦 0 ∈ 𝑆 𝑐 yang memenuhi 𝑦 0 ≤ 𝑡 , untuk setiap 𝑡 ∈ 𝑆 𝑐 . Tentu ini berarti 𝑦 0 ∈ 𝑆 𝑐 , 𝑦 0 > 1 , bertindak sebagai unsur terkecil 𝑆 𝑐 . Karena 𝑦 0 − 1 < 𝑦 0 , maka 𝑦 0 − 1 ∉ 𝑆 𝑐 , atau 𝑦 0 − 1 ∈ 𝑆 . Dari sifat 𝑆 ,  kita  tahu  bahwa 𝑦 0 = (𝑦 0 − 1) + 1 ∈ 𝑆 ,  yang  merupakan  suatu  kontradiksi. Terbukti bahwa 𝑆 = ℕ . ∎
Teorema  di  atas  merupakan  bentuk  teoritis  dari  suatu  konsep  matematika  yang  biasa disebut Induksi Matematika.

## 3 Ekivalensi Rumus Induksi
Sekarang  kita  sampai  kepada  penjelasan  utama  mengenai  hubungan  antara  Prinsip Terurut Rapi ℕ dan rumus Induksi 1.
Telah diketahui bahwa rumus Induksi 1 berhasil diperoleh dari Prinsip Terurut Rapi ℕ . Sekarang dengan diketahuinya rumus Induksi 1, akan ditunjukkan keberlakuan Prinsip Terurut Rapi ℕ .
Teorema  2.1 Misalkan  rumus  Induksi  1  berlaku  di ℕ .  Sebarang 𝐴 ⊆ ℕ dan ∅ ≠  𝐴 , mempunyai unsur terkecil.
Bukti. Ambil sebarang ∅ ≠  𝐴 ⊆ ℕ , dan andaikan 𝐴 tidak memiliki unsur terkecil. Tulis ℬ: = {𝑛 ∈ ℕ ∶ 𝑛 ∉  𝐴} .  Andaikan 1 ∉ ℬ ,  ini  berarti 1 ∈ 𝐴 .  Karena  1  unsur  terkecil ℕ , maka 1 juga unsur terkecil 𝐴 . Hal tersebut merupakan suatu kontradiksi, sehingga kita simpulkan 1 ∈ ℬ . Selanjutnya kita misalkan 𝑥 ∈ ℬ , tetapi 𝑥 + 1 ∉ ℬ . Akibatnya 𝑥 ∉ 𝐴 , tetapi 𝑥 + 1 ∈ 𝐴 , dan ini berarti 𝑥 + 1 unsur terkecil 𝐴 yang merupakan suatu kontradiksi. Sehingga kita perolah 𝑥 ∈ ℬ , berakibat 𝑥 + 1 ∈ ℬ . Menurut rumus Induksi 1, kita simpulkan bahwa ℬ = ℕ . Dengan demikian 𝑛 ∉ 𝐴 ,$ untuk setiap 𝑛 ∈ ℕ atau 𝐴 = ∅ . Kontradiksi. ∎
Teorema 2.2 Dalam himpunan bilangan alam ℕ berlaku Prinsip Terurut Rapi, jika dan hanya jika rumus Induksi 1 juga berlaku di dalamnya.
Bukti. Misalkan  dalam ℕ berlaku  Prinsip  Terurut  Rapi.  Akan  dibuktikan  keberlakuan Rumus  Induksi  1  di  dalamnya.  Misalkan  kita  punyai 1  ∈  𝑆  ⊆ ℕ ,  dan 𝑥  ∈  𝑆 ,  yang berakibat 𝑥  +  1  ∈  𝑆 . Andaikan 𝑆 ≠ ℕ . Kita pilih 𝑝  ∈ ℕ tetapi 𝑝 ∉  𝑆 .Oleh karena 𝑝 ∈ 𝑆 𝐶 ≠ ∅ , maka 𝑆 𝐶 mempunyai unsur  terkecil, sebut saja 𝑞 , dan ini mengakibatkan 𝑞 − 1 ∈ 𝑆 . Tetapi dari sifat 𝑆 , kita akan sampai kepada 𝑞 ∈ 𝑆 , dan ini adalah suatu kontradiksi. Sebaliknya, misalkan dalam ℕ berlaku Rumus Induksi 1. Akan dibuktikan keberlakuan Prinsip Terurut Rapi di dalam ℕ . Andaikan Prinsip Terurut Rapi tidak berlaku di ℕ , maka akan  diperoleh ∅ ≠ 𝐴 ⊆ ℕ ,  dengan 𝐴 tidak  mempunyai  unsur  terkecil.  Misalkan  kita definisikan
𝐵 ≔ {𝑟 ∈ ℕ: 𝑟 ∉ 𝐴}.
Oleh karena 1 ∈ 𝐵 , maka 𝐵 mempunyai unsur terkecil. Misalkan 𝑠 ∈ 𝐵 tetapi 𝑠  +  1 ∉ 𝐵 .  Kita  punyai 𝑠  +  1 ∈ 𝐴 .  Oleh  karena 𝑠 ∉ 𝐴 ,  maka 𝑠  +  1 bertindak  sebagai  unsur terkecil 𝐴 .  Kontradiksi.  Dengan  demikian  Prinsip  Terurut  Rapi  berlaku  di ℕ .  Kita simpulkan bahwa Prinsip Terurut Rapi dan Rumus Induksi 1 ekivalen. ∎

## 4 Rumus Induksi Bentuk Lain
Dengan  sedikit  modifikasi  pada  rumus  induksi  1,  maka  kita  akan  mendapatkan  rumus berikut ini,
Teorema  3.1 (Induksi  2)  Misalkan 𝑎 ∈ ℕ dan ∅ ≠  𝑆 ⊆ ℕ 𝑎 : = {a, a + 1, a + 2, … } , dengan 𝑎 ∈ 𝑆 . Jika 𝑥 ∈ 𝑆 , mengakibatkan 𝑥 + 1 ∈ 𝑆 , maka 𝑆 = ℕ 𝑎 .
Bukti. Misalkan 𝑎  ∈  ℕ dan 𝑁 𝑎 ∶=   {𝑎, 𝑎  +  1, 𝑎  +  2, 𝑎  +  3, . . . } . Misalkan 𝑎  ∈  𝑆  ⊆ 𝑁 𝑎 , dan 𝑥  ∈  𝑆 mengakibatkan 𝑥  +  1  ∈  𝑆 . Andaikan 𝑆 ≠   𝑁 𝑎 . Kita pilih 𝑞 ∈   𝑁 𝑎 dan 𝑞 ∉ 𝑆 .  Oleh karena 𝑞   ∈   𝑆 𝐶 ≠ ∅ dan 𝑆 𝐶 ⊂   𝑁 𝑎 ,  maka 𝑆 𝐶 memiliki unsur terkecil, yang kita sebut 𝑑  ∈   𝑆 𝐶 .  Karena 𝑑 unsur terkecil, maka 𝑑  −  1 ∈  𝑆 .  Tetapi sifat yang dimiliki 𝑆 akan menghasilkan 𝑑  ∈  𝑆 yang merupakan suatu kontradiksi. ∎
Untuk  keperluan  aplikasi/penggunaan  rumus  induksi,  kita  punyai  fakta  berikut  yang menyatakan ekivalensi rumus-rumus di atas.
Teorema 3.2 Dalam himpunan bilangan alam ℕ berlaku rumus Induksi 1, jika dan hanya jika rumus Induksi 2 juga berlaku di dalamnya.
Bukti. Dalam  hal 𝑎  =  1 maka  Rumus  Induksi  2  mengakibatkan  Rumus  Induksi  1. Karena Rumus Induksi 1 ekivalen dengan Prinsip Terurut Rapi, maka Rumus Induksi 2 mengakibatkan Prinsip Terurut Rapi. ∎
Untuk penjelasan terakhir, kita sampai kepada rumus induksi yang terakhir, biasa disebut rumus  Induksi  Kuat .  Prinsip  ini  dapat  dibuktikan  melalui  Prinsip  Terurut  Rapi ℕ dan dapat dituliskan dengan bentuk sebagai berikut.
Teorema  3.3 (Induksi  kuat)  Misalkan ∅ ≠  𝑆 ⊆ ℕ , 1 ∈ 𝑆 .  Jika {1,2,3, … , 𝑥} ⊂ 𝑆 , mengakibatkan 𝑥 + 1 ∈ 𝑆 , maka 𝑆 = ℕ .
Bukti. Misalkan dalam ℕ berlaku Prinsip Terurut Rapi, dan andaikan 𝑆 ≠ ℕ . Ini berarti 𝑆 𝑐 ≠ ∅ . Pilih 𝑝 ∈ 𝑆 𝑐 yang bertindak sebagai unsur terkecil 𝑆 𝑐 . Jelas bahwa 𝑝 > 1 . Oleh karena 𝑝 ∈ 𝑆 𝑐 adalah unsur terkecil 𝑆 𝑐 ,$ maka 𝑝 − 1 ∉ 𝑆 𝑐 , atau 𝑝 − 1 ∈ 𝑆 . Oleh karena 1, 𝑝 − 1 ∈ 𝑆 , maka {1,2,3, … , 𝑝 − 1} ⊂ 𝑆 . Akibatnya 𝑝 ∈ 𝑆 . Kontradiksi, dan ini berarti 𝑆 = ℕ . ∎
5 Daftar Pustaka
[1] Gunderson,  D.S.,  2011,  Handbook  of  Mathematical  Induction:  Theory  and Applications, CRC Press.
[2] Rosen,  K.H.,  2019,  Discrete  Mathematics  and  Its  Applications,  McGraw-Hill Education.
[3] Valleman, D.J., 2006, How to Prove It, Cambridge University Press.