Induksi matematika
Induksi matematika merupakan pembuktian deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli.
Induksi matematika terbagi 2 yaitu umum dan kuat.
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).Persamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_3, benar bahwa formula_4
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa formula_9 sesuai dengan pengandaian awal
kemudian padankan bentuk sederhana tadi dengan sebelah kanan
Kesimpulan:
Jadi, formula_15 benar untuk jumlah n bilangan ganjil pertama adalah n karena memenuhi kedua langkah pembuktianPersamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_3, benar bahwa formula_19
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa formula_24 sesuai dengan pengandaian awal
kemudian padankan bentuk sederhana tadi dengan sebelah kanan
Kesimpulan:
Jadi, formula_15 benar untuk setiap bilangan bulat positif adalah n karena memenuhi kedua langkah pembuktianPersamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_34, benar bahwa formula_35
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa formula_40 sesuai dengan pengandaian awal
kemudian padankan bentuk sederhana tadi dengan sebelah kanan
Kesimpulan:
Jadi, formula_15 benar untuk semua bilangan bulat positif n ≥ 5 karena memenuhi kedua langkah pembuktian
Persamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_3, benar bahwa formula_52
andaikan benar untuk formula_5, yaitu
sekarang tunjukkan bahwa 3 adalah faktor dari formula_56
karena 3 adalah faktor dari formula_61 dan 3 juga merupakan faktor formula_54, maka 3 adalah faktor dari formula_63. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.
Kesimpulan:
Jadi, formula_15 benar untuk 3 adalah faktor formula_49 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktianPersamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_3, benar bahwa formula_69
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang tunjukkan bahwa 3 adalah faktor dari formula_73
karena 3 adalah faktor dari formula_78 dan 3 juga merupakan faktor formula_71, maka 3 adalah faktor dari formula_73. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.
Kesimpulan:
Jadi, formula_15 benar untuk 3 adalah faktor formula_66 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktianPersamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_3, benar bahwa formula_86
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang tunjukkan bahwa formula_90 habis dibagi 4
karena formula_95 dan formula_88 habis dibagi 4, maka formula_90 habis dibagi 4. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.
Kesimpulan:
Jadi, formula_15 benar untuk formula_83 habis dibagi 4 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktianPersamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk formula_3, benar bahwa formula_103
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang tunjukkan bahwa x - y adalah faktor dari formula_107
karena x - y adalah faktor dari formula_111 dan x - y juga merupakan faktor formula_112, maka x - y adalah faktor dari formula_107. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.
Kesimpulan:
Jadi, formula_15 benar untuk x - y adalah faktor formula_100 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian
Temukan rumus untuk penjumlahan berhingga berikut kemudian buktikan rumus tersebut dengan induksi matematika!
Persamaan yang perlu dibuktikan:
Langkah pembuktian pertama:
untuk beberapa penjumlahan formula_118 dari pertama, benar bahwa
Langkah pembuktian kedua:
andaikan benar untuk formula_5, yaitu
sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa formula_127 sesuai dengan pengandaian awal
kemudian padankan bentuk sederhana tadi dengan sebelah kanan
Kesimpulan:
Jadi, formula_15 benar untuk hipotesis induksi matematika karena memenuhi kedua langkah pembuktian
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.)