Induksi matematika

Induksi matematika merupakan salah satu kegiatan penalaran deduktif yang berkaitan dengan pembuktian matematika. Dalam matematika, induksi matematika merupakan sebuah dasar aksioma bagi beberapa teorema yang melibatkan bilangan asli. Pembuktian suatu pernyataan matematis dengan induksi matematika dilakukan pada objek matematika yang bersifat diskrit, misalnya teori bilangan, teori graf, dan kombinatorika. Matematikawan menggunakan induksi matematika untuk menjelaskan pernyataan matematika yang telah diketahui kebenarannya. 

Prinsip induksi matematis dapat dijelaskan secara umum dalam dua tahap yaitu langkah awal atau asumsi induktif dan langkah induksi dasar. Penggunaan induksi matematika utamanya dilakukan pada tiga jenis masalah matematika yaitu seri umum, habis dibagi dan ketidaksetaraan. Kemampuan pembuktian induksi matematika secara benar ditentukan oleh tingkat pemahaman konsep. Setiap prosedur induksi matematika yang digunakan pada suatu konsep matematika dapat ditentukan melalui pemahaman relasional.

Sejarah penggunaan 
Teorema matematika didasarkan pada sekumpulan aksioma dan definisi. Pembuktian semua jenis teorema dilakukan dengan menggunakan aksioma dan definisi, atau menggunakan teorema-teorema yang telah terbukti kebenarannya. Teorema dalam matematika tidak didasarkan kepada hasil-hasil eksperimen yang tidak dapat dibuktikan kebenarannya. Matematika tidak dapat menerima argumentasi bahwa suatu pernyataan matematis adalah benar hanya dengan eksperimen-eksperimen dan observasi-observasi. Pierre de Fermat (1601- 1665) membuktikan bahwa pada konjektur Fermat, persamaan tidak akan menghasilkan bilangan bulat berbentuk positif pada sebarang bilangan bulat yang bernilai lebih dari 2. Para matematikawan memerlukan waktu lebih dari tiga abad untuk menemukan pembuktian konjektur Fermat. Pada tahun 1994, konjektur Fermat dibuktikan oleh matematikawan berkebangsaan Inggris yaitu Andrew Wiles.

Sejarah penggunaan induksi matematika dijelaskan oleh Bussey dalam artikel yang ditulisnya pada tahun 1917. Dalam artikel tersebut dijelaskan bahwa proses induksi matematika telah digunakan untuk pertama kali oleh D. Franciscus Maurolycus (1494- 1575). Maurolycus adalah matewatikawan berkebangsaan Italia dan kenalan dari Blaise Pascal (1623-1662). Penggunaan induksi matematika dilakukan oleh Maurolycus dalam bukunya yang terbit pada tahun 1575. Maurolycus menggunakan induksi matematika untuk membuktikan bahwa bilangan-bilangan ganjil terbentuk dengan cara berturut-turut menambahkan 2 terhadap bilangan ganjil pertama, yaitu 1. Pembuktikan lain yang diperolehnya dengan induksi yaitu jumlah n bilangan ganjil pertama adalah kuadrat n. Pembuktian matematika yang dilakukan oleh Pascal maupun Maurolycus tidak pernah menggunakan istilah induksi. Istilah induksi digunakan pertama kalinya pada tahun 1956 oleh John Wallis. Dalam bukunya yang berjudul Arithmetica Infinitorum, Wallis menggunakan isitlah per modum inductionis. Pada tahun 1838, Augustus de Morgan (1806-1871) memperkenalkan istilah induksi matematika ke publik melalui artikel induction yang ditulisnya untuk jurnal Penny Cyclopedia.

Pada tahun 1889, Giuseppe Peano (1858-1932) merumuskan prinsip induksi matematika ke dalam lima aksioma. Di dalam kelima aksioma ini, disajikan definisi lengkap tentang bilangan asli. Kelima aksioma tersebut adalah:

 1 adalah bilangan asli. 
 Terdapat satu bilang turutan yang unik dan bentuk bilangan asli pada setiap bilangan asli. 
 Bilangan turutan yang sama mustahil ditemukan pada dua bilangan asli yang berbeda.
 1 bukan merupakan turutan dari sebarang bilangan asli
 Sifat yang dimiliki oleh 1 dan turutan semua bilangan asli, pasti dimiliki juga oleh semua bilangan asli.

Proposisi 
Dalam pembuktian tidak langsung, induksi matematika melibatkan dua proposisi, yaitu basis induksi dan hipotesis induksi. Pembuktian dilakukan dalam tiga langkah yaitu langkah basis, hipotesis induksi, dan langkah induksi.

Matematika umum 
Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan bahwa sifat itu benar untuk n = 1 (atau S(1) adalah benar), kemudian ditunjukkan bahwa bila sifat itu benar untuk n = k (bila S(k) benar) menyebabkan sifat itu benar untuk n = k + 1 (atau S(k + 1) benar).

Bilangan (termasuk jumlah deret)
 Buktikan bahwa  untuk jumlah n bilangan ganjil pertama adalah n2!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa  sesuai dengan pengandaian awal

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

, ingat bahwa 
 (terbukti benar)

Kesimpulan:
Jadi,  benar untuk jumlah n bilangan ganjil pertama adalah n2 karena memenuhi kedua langkah pembuktian

 Buktikan bahwa  untuk setiap bilangan bulat positif adalah n!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa  sesuai dengan pengandaian awal

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

 (terbukti benar)

Kesimpulan:
Jadi,  benar untuk setiap bilangan bulat positif adalah n karena memenuhi kedua langkah pembuktian

Pertidaksamaan
 Buktikan bahwa  untuk semua bilangan bulat positif n ≥ 5!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa  sesuai dengan pengandaian awal
 (karena 4 < 4k)

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

, ingat bahwa 
 (terbukti benar)

Kesimpulan:
Jadi,  benar untuk semua bilangan bulat positif n ≥ 5 karena memenuhi kedua langkah pembuktian

Faktor (termasuk kali atau bagi)

 Buktikan bahwa salah satu faktor dari  adalah 3 untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang tunjukkan bahwa 3 adalah faktor dari 

karena 3 adalah faktor dari  dan 3 juga merupakan faktor , maka 3 adalah faktor dari . Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi,  benar untuk 3 adalah faktor  untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

 Buktikan bahwa 3 adalah faktor  untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang tunjukkan bahwa 3 adalah faktor dari 

karena 3 adalah faktor dari  dan 3 juga merupakan faktor , maka 3 adalah faktor dari . Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi,  benar untuk 3 adalah faktor  untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

 Buktikan bahwa  habis dibagi 4 untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang tunjukkan bahwa  habis dibagi 4

karena  dan  habis dibagi 4, maka  habis dibagi 4. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi,  benar untuk  habis dibagi 4 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

Faktorisasi
 Buktikan bahwa x - y adalah faktor  untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang tunjukkan bahwa x - y adalah faktor dari 

karena x - y adalah faktor dari  dan x - y juga merupakan faktor , maka x - y adalah faktor dari . Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi,  benar untuk x - y adalah faktor  untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

Barisan
Temukan hasil rumus untuk penjumlahan berhingga berikut kemudian buktikan hasil rumus tersebut dengan induksi matematika!

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk beberapa penjumlahan  dari pertama, benar bahwa

Langkah pembuktian kedua:
andaikan benar untuk , yaitu
, maka akan dibuktikan benar pula untuk , yaitu

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa  sesuai dengan pengandaian awal

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

 (terbukti benar)

Kesimpulan:
Jadi,  benar untuk hipotesis induksi matematika karena memenuhi kedua langkah pembuktian

Matematika kuat 
Misalkan S(n) adalah pernyataan yang didefinisikan untuk bilangan bulat n, dan misalkan a dan b adalah bilangan bulat sedemikian sehingga a ≤ b. Jika dua pernyataan berikut bernilai benar,

S(a), S(a + 1), ..., dan S(b) semuanya bernilai benar. (langkah dasar)
Untuk sebarang bilangan bulat k ≥ b, jika S(i) benar untuk semua bilangan bulat i mulai a sampai k, maka S(k + 1) benar. (langkah induksi)

Maka untuk semua bilangan bulat n ≥ a, S(n) benar. (Asumsi bahwa S(i) benar untuk semua bilangan bulat i mulai dari a sampai k disebut sebagai hipotesis induksi. Cara lain untuk menyatakan hipotesis induksi adalah dengan menyatakan bahwa S(a), S(a + 1), ..., S(k) semuanya bernilai benar.)

 A. Bilangan (termasuk jumlah deret)

 B. Barisan

 C. Teori

Penerapan

Penalaran pada matematika formal 
Induksi matematika digunakan untuk mengatasi kelemahan dari penalaran induktif. Penggunaan induksi matematika dapat memberikan kesimpulan yang berlaku umum. Sebaliknya,  penalaran induktif yang dilakukan melalui pengalaman dan pengamatan, tidak menjamin adanya kesimpulan yang berlaku secara umum. Kesimpulan yang berlaku secara umum di dalam matematika formal hanya dapat diperoleh melalui induksi matematika.

Referensi 
 Daftar pustaka 

 

 Bacaan lanjutan 

 Analisis 
  (Section 1.2.1: Mathematical Induction, pp. 11-21.)
  (Section 1.3.8: Transfinite induction, pp. 28-29.)
  (Ch. 8.)

 Sejarah 
 
 
 
 
 
 
 
 
 
 
 
 

Logika matematika
Induksi matematis