Induksi matematika (mathematical induction) adalah metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli. Akan tetapi sebelum membahas mengenai induksi matematika, kita akan membahas suatu prinsip yang digunakan untuk membuktikan induksi matematika, yaitu prinsip terurut rapi (well-ordering principle) dari bilangan asli. Seperti kita ketahui, himpunan bilangan asli adalah himpunan yang memiliki anggota 1, 2, 3, … yang dapat dituliskan sebagai berikut.
Himpunan Bilangan Asli
Setelah mengingat mengenai himpunan bilangan asli, sekarang perhatikan prinsip terurut rapi dari bilangan asli berikut.
Prinsip Terurut Rapi Bilangan Asli
Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.
Secara lebih formal, prinsip tersebut menyatakan bahwa untuk setiap himpunan tidak kosong V yang merupakan himpunan bagian dari N, maka ada v0 anggota V sedemikian sehingga v0 ≤ v untuk setiap v anggota V.
Berdasarkan prinsip terurut rapi di atas, kita akan menurunkan prinsip induksi matematika yang dinyatakan dalam bentuk himpunan bagian N.
Prinsip Induksi Matematika
Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Sebelum membuktikan prinsip induksi matematika di atas secara formal, kita akan mencoba memahaminya dengan menggunakan efek domino seperti berikut.
Efek Domino
Pada gambar (a) di atas kita melihat sebaris 4 domino pertama yang ditata rapi dengan jarak antara masing-masing domino yang berdekatan kurang dari tinggi domino. Sehingga, jika kita mendorong domino nomor k ke kanan, maka domino tersebut akan merebahkan domino nomor (k + 1). Proses ini ditunjukkan oleh gambar (b). Kita tentu akan berpikir bahwa apabila proses ini berlanjut, maka domino nomor (k + 1) tersebut juga akan merebahkan domino di sebelah kanannya, yaitu domino nomor (k + 2), dan seterusnya. Bagian (c) menggambarkan bahwa dorongan terhadap domino pertama merupakan analogi dari bilangan 1 menjadi anggota himpunan S. Hal ini merupakan langkah dasar dari proses efek domino. Selanjutnya, jika k anggota S akan menyebabkan (k + 1) anggota S, akan memberikan langkah induktif dan melanjutkan proses perebahan domino. Sehingga, pada akhirnya kita akan melihat bahwa semua domino akan rebah. Atau dengan kata lain, domino yang memiliki nomor urut semua bilangan asli akan rebah. Hal ini merupakan analogi dari S = N. Bagaimana dengan bukti formal dari prinsip induksi matematika?
Bukti Andaikan S ≠ N. Maka himpunan N – S bukan merupakan himpunan kosong, sehingga berdasarkan prinsip terurut rapi, himpunan tersebut memiliki anggota terkecil m. Karena 1 anggota S (berdasarkan hipotesis 1), maka m > 1. Tetapi hal ini akan mengakibatkan bahwa m – 1 juga merupakan bilangan asli. Karena m – 1 < m dan m adalah anggota terkecil dari N – S, maka m – 1 anggota S.
Sekarang kita akan menggunakan hipotesis 2 bahwa k = m – 1 merupakan anggota S, maka k + 1 = (m – 1) + 1 = m juga anggota S. Akan tetapi pernyataan ini akan kontradiksi bahwa m bukan anggota S. Sehingga N – S adalah himpunan kosong atau dengan kata lain N = S.
Selain diformulasikan seperti di atas, Prinsip Induksi Matematika juga dapat dinyatakan sebagai berikut.
Untuk setiap n anggota N, misalkan P(n) merupakan suatu pernyataan tentang n. Apabila:
P(1) benar.
Untuk setiap k anggota N, jika P(k) benar, maka P(k + 1) benar.
Maka P(n) benar untuk setiap n anggota N.
Hubungan Prinsip Induksi Matematika tersebut dengan sebelumnya adalah dengan memisalkan S = {n anggota N | P(n) adalah benar}. Sehingga kondisi 1 dan 2 pada Prinsip Induksi Matematika di awal secara berturut-turut berkorespondensi dengan kondisi 1 dan 2 pada Prinsip Induksi Matematika terakhir. Selain itu, kesimpulan S = N juga berkorespondensi dengan kesimpulan P(n) benar untuk setiap n anggota N.
Asumsi bahwa “jika P(k) benar” dinamakan hipotesis induksi. Untuk membangun hipostesis 2, kita tidak perlu menghiraukan kebenaran dari P(k), tetapi yang perlu kita hiraukan adalah validitas dari “jika P(k), maka P(k + 1)”. Misalkan, jika kita akan menguji pernyataan P(n): “n = n + 5”, maka secara logis kondisi (2) adalah benar, dengan menambahkan 1 pada kedua sisi P(k) untuk mendapatkan P(k + 1). Akan tetapi, karena pernyataan P(1): “1 = 6” adalah salah, kita tidak dapat menggunakan Induksi Matematika untuk menyimpulkan bahwa n = n + 5 untuk setiap n anggota N.
Pada beberapa kasus, kadang P(n) bernilai salah untuk beberapa bilangan asli tertentu tetapi bernilai benar untuk n ≥ n0. Prinsip Induksi Matematika dapat dimodifikasi untuk mengatasi kasus seperti itu.
Prinsip Induksi Matematika (versi kedua)
Himpunan Bilangan Asli
Setelah mengingat mengenai himpunan bilangan asli, sekarang perhatikan prinsip terurut rapi dari bilangan asli berikut.
Prinsip Terurut Rapi Bilangan Asli
Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.
Secara lebih formal, prinsip tersebut menyatakan bahwa untuk setiap himpunan tidak kosong V yang merupakan himpunan bagian dari N, maka ada v0 anggota V sedemikian sehingga v0 ≤ v untuk setiap v anggota V.
Berdasarkan prinsip terurut rapi di atas, kita akan menurunkan prinsip induksi matematika yang dinyatakan dalam bentuk himpunan bagian N.
Prinsip Induksi Matematika
Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Sebelum membuktikan prinsip induksi matematika di atas secara formal, kita akan mencoba memahaminya dengan menggunakan efek domino seperti berikut.
Efek Domino
Pada gambar (a) di atas kita melihat sebaris 4 domino pertama yang ditata rapi dengan jarak antara masing-masing domino yang berdekatan kurang dari tinggi domino. Sehingga, jika kita mendorong domino nomor k ke kanan, maka domino tersebut akan merebahkan domino nomor (k + 1). Proses ini ditunjukkan oleh gambar (b). Kita tentu akan berpikir bahwa apabila proses ini berlanjut, maka domino nomor (k + 1) tersebut juga akan merebahkan domino di sebelah kanannya, yaitu domino nomor (k + 2), dan seterusnya. Bagian (c) menggambarkan bahwa dorongan terhadap domino pertama merupakan analogi dari bilangan 1 menjadi anggota himpunan S. Hal ini merupakan langkah dasar dari proses efek domino. Selanjutnya, jika k anggota S akan menyebabkan (k + 1) anggota S, akan memberikan langkah induktif dan melanjutkan proses perebahan domino. Sehingga, pada akhirnya kita akan melihat bahwa semua domino akan rebah. Atau dengan kata lain, domino yang memiliki nomor urut semua bilangan asli akan rebah. Hal ini merupakan analogi dari S = N. Bagaimana dengan bukti formal dari prinsip induksi matematika?
Bukti Andaikan S ≠ N. Maka himpunan N – S bukan merupakan himpunan kosong, sehingga berdasarkan prinsip terurut rapi, himpunan tersebut memiliki anggota terkecil m. Karena 1 anggota S (berdasarkan hipotesis 1), maka m > 1. Tetapi hal ini akan mengakibatkan bahwa m – 1 juga merupakan bilangan asli. Karena m – 1 < m dan m adalah anggota terkecil dari N – S, maka m – 1 anggota S.
Sekarang kita akan menggunakan hipotesis 2 bahwa k = m – 1 merupakan anggota S, maka k + 1 = (m – 1) + 1 = m juga anggota S. Akan tetapi pernyataan ini akan kontradiksi bahwa m bukan anggota S. Sehingga N – S adalah himpunan kosong atau dengan kata lain N = S.
Selain diformulasikan seperti di atas, Prinsip Induksi Matematika juga dapat dinyatakan sebagai berikut.
Untuk setiap n anggota N, misalkan P(n) merupakan suatu pernyataan tentang n. Apabila:
P(1) benar.
Untuk setiap k anggota N, jika P(k) benar, maka P(k + 1) benar.
Maka P(n) benar untuk setiap n anggota N.
Hubungan Prinsip Induksi Matematika tersebut dengan sebelumnya adalah dengan memisalkan S = {n anggota N | P(n) adalah benar}. Sehingga kondisi 1 dan 2 pada Prinsip Induksi Matematika di awal secara berturut-turut berkorespondensi dengan kondisi 1 dan 2 pada Prinsip Induksi Matematika terakhir. Selain itu, kesimpulan S = N juga berkorespondensi dengan kesimpulan P(n) benar untuk setiap n anggota N.
Asumsi bahwa “jika P(k) benar” dinamakan hipotesis induksi. Untuk membangun hipostesis 2, kita tidak perlu menghiraukan kebenaran dari P(k), tetapi yang perlu kita hiraukan adalah validitas dari “jika P(k), maka P(k + 1)”. Misalkan, jika kita akan menguji pernyataan P(n): “n = n + 5”, maka secara logis kondisi (2) adalah benar, dengan menambahkan 1 pada kedua sisi P(k) untuk mendapatkan P(k + 1). Akan tetapi, karena pernyataan P(1): “1 = 6” adalah salah, kita tidak dapat menggunakan Induksi Matematika untuk menyimpulkan bahwa n = n + 5 untuk setiap n anggota N.
Pada beberapa kasus, kadang P(n) bernilai salah untuk beberapa bilangan asli tertentu tetapi bernilai benar untuk n ≥ n0. Prinsip Induksi Matematika dapat dimodifikasi untuk mengatasi kasus seperti itu.
Prinsip Induksi Matematika (versi kedua)
Misalkan n0 anggota N dan misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n0. Apabila:
(1) Pernyataan P(n0) benar;
(2) Untuk setiap k ≥ n0, jika P(k) benar mengakibatkan P(k + 1) benar.
Maka P(n) benar untuk semua n ≥ n0.
Semoga bermanfaat !!!
Maka P(n) benar untuk semua n ≥ n0.
Semoga bermanfaat !!!
Posting Komentar