Induksi matematika

Sebuah deskripsi tidak formal dari induksi matematika dapat diilustrasikan dengan mengacu kepada efek sekuensial dari jatuhnya domino.

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.

Demonstrasi pembuktian klaim bahwa "Jumlah dari n bilangan ganjil pertama adalah bilangan kuadrat, bukan n."

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. 1 adalah bilangan asli.
2. Terdapat satu bilang turutan yang unik dan bentuk bilangan asli pada setiap bilangan asli.
3. Bilangan turutan yang sama mustahil ditemukan pada dua bilangan asli yang berbeda.
4. 1 bukan merupakan turutan dari sebarang bilangan asli
5. 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 $1 3 5 \cdots 2n-1=n^{2}$ untuk jumlah n bilangan ganjil pertama adalah n²!

Persamaan yang perlu dibuktikan:

$S(n)=1 3 5 \cdots 2n-1=n^{2}$

Langkah pembuktian pertama:
untuk $n=1$, benar bahwa $\ S(1)=1^{2}=1$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$S(k)=1 3 5 \cdots 2k-1=k^{2}$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$S(k 1)=1 3 5 \cdots 2k-1 2(k 1)-1=(k 1)^{2}$

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa $k^{2}=1 3 5 ... 2k-1$ sesuai dengan pengandaian awal

$[1 3 5 \cdots 2k-1] 2(k 1)-1=k^{2} 2(k 1)-1$

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

$k^{2} 2(k 1)-1=(k 1)^{2}$

$\ k^{2} 2k 1=(k 1)^{2}$, ingat bahwa $(k 1)^{2}=k^{2} 2k 1$

$\ (k 1)^{2}=(k 1)^{2}$ (terbukti benar)

Kesimpulan:
Jadi, $S(n)$ benar untuk jumlah n bilangan ganjil pertama adalah n² karena memenuhi kedua langkah pembuktian

• Buktikan bahwa $1 2 3 4 5 \cdots n={\frac {n(n 1)}{2}}$ untuk setiap bilangan bulat positif adalah n!

Persamaan yang perlu dibuktikan:

$S(n)=1 2 3 4 5 \cdots n={\frac {n(n 1)}{2}}$

Langkah pembuktian pertama:
untuk $n=1$, benar bahwa $\ S(1)={\frac {1(1 1)}{2}}=1$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$S(k)=1 2 3 4 5 \cdots k={\frac {k(k 1)}{2}}$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$S(k 1)=1 2 3 4 5 \cdots k k 1={\frac {(k 1)[(k 1) 1]}{2}}$

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa ${\frac {k(k 1)}{2}}=1 2 3 4 5 \cdots k$ sesuai dengan pengandaian awal

$[1 2 3 4 5 \cdots k] k 1={\frac {k(k 1)}{2}} k 1$

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

${\frac {k(k 1)}{2}} k 1={\frac {(k 1)[(k 1) 1]}{2}}$

$(k 1)({\frac {k}{2}} 1)={\frac {(k 1)[(k 1) 1]}{2}}$

$(k 1)({\frac {k 2}{2}})={\frac {(k 1)[(k 1) 1]}{2}}$

${\frac {(k 1)[(k 1) 1]}{2}}={\frac {(k 1)[(k 1) 1]}{2}}$

${\frac {(k 1)[(k 1) 1]}{2}}={\frac {(k 1)[(k 1) 1]}{2}}$ (terbukti benar)

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

Pertidaksamaan

• Buktikan bahwa $4n<2^{n}$ untuk semua bilangan bulat positif n ≥ 5!

Persamaan yang perlu dibuktikan:

$S(n)=4n<2^{n}$

Langkah pembuktian pertama:
untuk $n=5$, benar bahwa $4(5)<2^{5}$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$S(k)=4k<2^{k}$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$S(k 1)=4(k 1)<2^{k 1}$

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

$4(k 1)=4k 4$ (karena 4 < 4k)

$=4k 4k$

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

$4k 4k<2^{k 1}$

$2(4k)<2^{k 1}$

$2(2^{k})<2^{k 1}$, ingat bahwa $a^{m}a^{n}=a^{m n}$

$2^{k 1}<2^{k 1}$ (terbukti benar)

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

Faktor (termasuk kali atau bagi)

• Buktikan bahwa salah satu faktor dari $n^{3} 3n^{2} 2n$ adalah 3 untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

$S(n)=n^{3} 3n^{2} 2n$

Langkah pembuktian pertama:
untuk $n=1$, benar bahwa $1^{3} 3(1)^{2} 2(1)=6$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$k^{3} 3k^{2} 2k$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$(k 1)^{3} 3(k 1)^{2} 2(k 1)$

sekarang tunjukkan bahwa 3 adalah faktor dari $(k 1)^{3} 3(k 1)^{2} 2(k 1)$

$(k 1)^{3} 3(k 1)^{2} 2(k 1)=k^{3} 3k^{2} 3k 1 3k^{2} 6k 3 2k 2$

$=(k^{3} 3k^{2} 2k) (3k^{2} 9k 6)$

$=(k^{3} 3k^{2} 2k) 3\cdot (k^{2} 3k 2)$

karena 3 adalah faktor dari $3\cdot (k^{2} 3k 2)$ dan 3 juga merupakan faktor $k^{3} 3k^{2} 2k$, maka 3 adalah faktor dari $(k 1)^{3} 3(k 1)^{2} 2(k 1)$. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, $S(n)$ benar untuk 3 adalah faktor $n^{3} 3n^{2} 2n$ untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

• Buktikan bahwa 3 adalah faktor $4^{n}-1$ untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

$S(n)=4^{n}-1$

Langkah pembuktian pertama:
untuk $n=1$, benar bahwa $4^{1}-1=3$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$4^{k}-1$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$4^{k 1}-1$

sekarang tunjukkan bahwa 3 adalah faktor dari $4^{k 1}-1$

$4^{k 1}-1=4^{k 1}-4^{k} 4^{k}-1$

$=4^{k}(4-1) (4^{k}-1)$

$=4^{k}\cdot 3 (4^{k}-1)$

karena 3 adalah faktor dari $4k\cdot 3$ dan 3 juga merupakan faktor $4^{k}-1$, maka 3 adalah faktor dari $4^{k 1}-1$. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, $S(n)$ benar untuk 3 adalah faktor $4^{n}-1$ untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

• Buktikan bahwa $5^{n}-1$ habis dibagi 4 untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

$S(n)=5^{n}-1$

Langkah pembuktian pertama:
untuk $n=1$, benar bahwa $5^{1}-1=4$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$5^{k}-1$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$5^{k 1}-1$

sekarang tunjukkan bahwa $5^{k 1}-1$ habis dibagi 4

$5^{k 1}-1=5^{k 1}-5^{k} 5^{k}-1$

$=5^{k}(5-1) (5^{k}-1)$

$=5^{k}\cdot 4 (5^{k}-1)$

karena $5k\cdot 4$ dan $5^{k}-1$ habis dibagi 4, maka $5^{k 1}-1$ habis dibagi 4. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, $S(n)$ benar untuk $5^{n}-1$ habis dibagi 4 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

Faktorisasi

• Buktikan bahwa x - y adalah faktor $x^{n}-y^{n}$ untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

$S(n)=x^{n}-y^{n}$

Langkah pembuktian pertama:
untuk $n=1$, benar bahwa $x^{1}-y^{1}=x-y$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$x^{k}-y^{k}$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$x^{k 1}-y^{k 1}$

sekarang tunjukkan bahwa x - y adalah faktor dari $x^{k 1}-y^{k 1}$

$x^{k 1}-y^{k 1}=x^{k 1}-x^{k}y x^{k}y-y^{k 1}$

$=x^{k}(x-y) (x^{k}-y^{k})y$

karena x - y adalah faktor dari $x^{k}\cdot (x-y)$ dan x - y juga merupakan faktor $(x^{k}-y^{k})\cdot y$, maka x - y adalah faktor dari $x^{k 1}-y^{k 1}$. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, $S(n)$ benar untuk x - y adalah faktor $x^{n}-y^{n}$ 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!

${\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} \cdots {\frac {1}{2n(n 1)}}$

Persamaan yang perlu dibuktikan:

$S(n)={\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} \cdots {\frac {1}{2n(n 1)}}$

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

$S(1)={\frac {1}{4}}={\frac {1^{2}}{2(1)(1 1)}}$

$S(2)={\frac {1}{4}} {\frac {1}{12}}={\frac {4}{12}}={\frac {2^{2}}{2(2)(2 1)}}$

$S(3)={\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}}={\frac {9}{24}}={\frac {3^{2}}{2(3)(3 1)}}$

$S(4)={\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} {\frac {1}{40}}={\frac {16}{40}}={\frac {4^{2}}{2(4)(4 1)}}$

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

$S(k)={\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} \cdots {\frac {1}{2k(k 1)}}={\frac {k^{2}}{2k(k 1)}}$, maka akan dibuktikan benar pula untuk $n=k 1$, yaitu

$S(k 1)={\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} \cdots {\frac {1}{2k(k 1)}} {\frac {1}{2(k 1)((k 1) 1)}}={\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}$

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa ${\frac {k^{2}}{2k(k 1)}}={\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} \cdots {\frac {1}{2k(k 1)}}$ sesuai dengan pengandaian awal

$[{\frac {1}{4}} {\frac {1}{12}} {\frac {1}{24}} \cdots {\frac {1}{2k(k 1)}}] {\frac {1}{2(k 1)[(k 1) 1]}}={\frac {k^{2}}{2k(k 1)}} {\frac {1}{2(k 1)[(k 1) 1]}}$

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

${\frac {k^{2}}{2k(k 1)}} {\frac {1}{2(k 1)((k 1) 1)}}={\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}$

${\frac {k^{2}}{2k(k 1)}} {\frac {1}{2(k 1)(k 2)}}={\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}$

${\frac {k^{2}(k 2) k}{2k(k 1)(k 2)}}={\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}$

${\frac {k(k^{2} 2k 1)}{2k(k 1)(k 2)}}={\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}$

${\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}={\frac {(k 1)^{2}}{2(k 1)[(k 1) 1]}}$ (terbukti benar)

Kesimpulan:
Jadi, $S(n)$ 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

1. Lolang, E., dan Tandiseru, S. R. (2017). Dasar-Dasar Matematika Diskrit dengan Pendekatan Problem Solving (PDF). Tana Toraja: UKI Toraja Press. ISBN 978-602-18328-8-2.  Pemeliharaan CS1: Banyak nama: authors list (link)
2. Utomo, D. P., dan Huda, M. (2020). Pemahaman Relasional Analisis Proses Pembuktian Menggunakan Induksi Matematika (PDF). Yogyakarta: CV. Bildung Nusantara. ISBN 978-623-7148-42-5.  Pemeliharaan CS1: Banyak nama: authors list (link)

Bacaan lanjutan

Analisis

• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (edisi ke-3rd). Addison-Wesley. ISBN 0-201-89683-4.  (Section 1.2.1: Mathematical Induction, pp. 11-21.)
• Kolmogorov, Andrey N. (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 0-486-61226-0.  (Section 1.3.8: Transfinite induction, pp. 28-29.)
• Franklin, J. (1996). Proof in Mathematics: An Introduction. Sydney: Quakers Hill Press. ISBN 1-876192-00-3.  (Ch. 8.)

Sejarah

• Acerbi, F. (2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences. 55: 57–76. doi:10.1007/s004070000020. 
• Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly. 24 (5): 199–207. 
• Cajori, Florian (1918). "Origin of the Name "Mathematical Induction"". 25 (5): 197–201. 
• "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis. XXXI: 253–265. 1994. 
• Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Induction". Archives Internationales d'Histiore des Sciences. 6: 17–37. 
• Rabinovitch, Nachum L. (1970). "Rabi Levi Ben Gershon and the Origins of Mathematical Induction". Archive for the History of Exact Science. 6: 237–248. doi:10.1007/BF00327237. 
• Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences. 9: 1–12. doi:10.1007/BF00348537. 
• Ungure, S. (1991). "Greek Mathematics and Mathematical Induction". Physis. XXVIII: 273–289. 
• Ungure, S. (1994). "Fowling after Induction". Physis. XXXI: 267–272. 
• Vacca, G. (1909). "Maurolycus, the First Discoverer of the Principle of Mathematical Induction". Bulletin of the American Mathematical Society. 16: 70–73. 
• Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis. 69 (2): 259–262. 
• Kuntarti, Sri Kurnianingsih (2007). Matematika SMA dan MA jilid 3B untuk Kelas XII Semester II Program IPA. Sulistiyono. Jakarta: Esis. ISBN 978-979-015-297-7.