Induksi Matematika adalah cara standar dalam membuktikan bahwa sebuah
pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian
dengan cara ini terdiri dari dua langkah, yaitu:
Menunjukkan bahwa pernyataan itu berlaku untuk bilangan 1.
Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n, maka pernyataan itu juga berlaku untuk bilangan n + 1.
Prinsip Induksi Sederhana
Secara formal Induksi Matematika ini bisa didefinisikan sebagai berikut.
Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n) yang bisa benar atau salah. Misalkan
Langkah 1 disebut dengan Langkah Dasar, sedangkan Langkah 2 disebut dengan Langkah Induktif.
Contoh 1
Gunakan induksi matematika untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2.
Penyelesaian:
1. Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif pertama adalah 12 = 1. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1.
Langkah induksi: Andaikan p(n) benar, yaitu pernyataan
1 + 3 + 5 + … + (2n – 1) = n2
adalah benar (hipotesis induksi) [catatlah bahwa bilangan ganjil positif ke-n adalah (2n – 1)]. Kita harus memperlihatkan bahwa p(n +1) juga benar, yaitu
1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2
juga benar. Hal ini dapat kita tunjukkan sebagai berikut:
1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)
= n2 + (2n + 1)
= n2 + 2n + 1
= (n + 1)2
Karena langkah basis dan langkah induksi keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n2.
Gunakan induksi matematika untuk membuktikan bahwa 5n – 1 dapat dibagi 4 untuk setiap n = 1, 2, …
Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n) yang bisa benar atau salah. Misalkan
P(1) benar.
Jika P(n) benar, maka P(n + 1) benar.
Sehingga P(n) benar untuk setiap bilangan asli n.Langkah 1 disebut dengan Langkah Dasar, sedangkan Langkah 2 disebut dengan Langkah Induktif.
Contoh 1
Gunakan induksi matematika untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2.
Penyelesaian:
1. Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif pertama adalah 12 = 1. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1.
Langkah induksi: Andaikan p(n) benar, yaitu pernyataan
1 + 3 + 5 + … + (2n – 1) = n2
adalah benar (hipotesis induksi) [catatlah bahwa bilangan ganjil positif ke-n adalah (2n – 1)]. Kita harus memperlihatkan bahwa p(n +1) juga benar, yaitu
1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2
juga benar. Hal ini dapat kita tunjukkan sebagai berikut:
1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)
= n2 + (2n + 1)
= n2 + 2n + 1
= (n + 1)2
Karena langkah basis dan langkah induksi keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n2.
Gunakan induksi matematika untuk membuktikan bahwa 5n – 1 dapat dibagi 4 untuk setiap n = 1, 2, …
1.Akan ditunjukkan bahwa 5n – 1 habis dibagi 4 untuk n = 1. Jelas sekali bahwa 51 – 1 = 5 – 1 = 4 habis dibagi 4.
2.Asumsikan bahwa 5n -1 habis dibagi 4 untuk n = k, yaitu 5k -1
habis dibagi 4. Akan ditunjukkan bahwa 5n – 1 juga habis dibagi 4 untuk n
= k + 1, yaitu 5k+1 – 1 habis dibagi 4.
5k+1 -1 = 5.5k – 1
= (1 + 4).5k – 1
= 5k + 4.5k – 1
= (5k – 1) + 4.5k
Berdasarkan asumsi, 5k – 1 habis dibagi 4. Sedangkan 4.5k juga habis dibagi 4. Dengan demikian 5k+1 – 1 habis dibagi 4. Karena Langkah Dasar dan Langkah Induktif terbukti, maka dapat disimpulkan bahwa 5n – 1 dapat dibagi 4 untuk setiap n = 1, 2, …
Prinsip Induksi yang Dirampatkan
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ³ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:
Untuk semua bilangan bulat tidak-negatif n, buktikan dengan induksi matematik bahwa 20 + 21 + 22 + … + 2n = 2n+1 – 1
Penyelesaian:
(i) Basis induksi. Untuk n = 0 (bilangan bulat tidak negatif pertama), kita peroleh:
20 = 20+1 – 1
Ini jelas benar, sebab 20 = 1 = 20+1 – 1
= 21 – 1
= 2 – 1
= 1
ii) Langkah induksi. Andaikan bahwa untuk semua bilangan bulat tidak-negatif n,
20 + 21 + 22 + … + 2n = 2n+1 – 1
adalah benar (hipotesis induksi). Kita harus menunjukkan bahwa
20 + 21 + 22 + … + 2n + 2n+1 = 2(n+1) + 1 – 1
juga benar. Ini kita tunjukkan sebagai berikut:
20 + 21 + 22 + … + 2n + 2n+1 = (20 + 21 + 22 + … + 2n) + 2n+1
= (2n+1 – 1) + 2n+1 (dari hipotesis induksi)
= (2n+1 + 2n+1) – 1
= (2 . 2n+1) – 1
= 2n+2 – 1
= 2(n+1) + 1 – 1
Karena langkah (i) dan (ii) keduanya telah diperlihatkan benar, maka untuk semua bilangan bulat tidak-negatif n, terbukti bahwa 20 + 21 + 22 + … + 2n = 2n+1 – 1
Induksi Kuat (Prinsip kedua dari induksi matematika)
Terdapat bentuk lain dari induksi matematika yang sering dipergunakan dalam bukti. Teknik ini dinamakan Induksi Kuat atau Prinsip kedua dari induksi matematika
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ³ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:
1. p(n0) benar, dan
2. jika p(n0 ), p(n0+1), …, p(n) benar maka p(n+1) juga benar untuk semua bilangan bulat n ³ n0,.
= (1 + 4).5k – 1
= 5k + 4.5k – 1
= (5k – 1) + 4.5k
Berdasarkan asumsi, 5k – 1 habis dibagi 4. Sedangkan 4.5k juga habis dibagi 4. Dengan demikian 5k+1 – 1 habis dibagi 4. Karena Langkah Dasar dan Langkah Induktif terbukti, maka dapat disimpulkan bahwa 5n – 1 dapat dibagi 4 untuk setiap n = 1, 2, …
Prinsip Induksi yang Dirampatkan
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ³ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:
p(n0) benar, dan
untuk semua bilangan bulat n ³ n0, jika p(n) benar maka p(n+1) juga benar.
Contoh 3Untuk semua bilangan bulat tidak-negatif n, buktikan dengan induksi matematik bahwa 20 + 21 + 22 + … + 2n = 2n+1 – 1
Penyelesaian:
(i) Basis induksi. Untuk n = 0 (bilangan bulat tidak negatif pertama), kita peroleh:
20 = 20+1 – 1
Ini jelas benar, sebab 20 = 1 = 20+1 – 1
= 21 – 1
= 2 – 1
= 1
ii) Langkah induksi. Andaikan bahwa untuk semua bilangan bulat tidak-negatif n,
20 + 21 + 22 + … + 2n = 2n+1 – 1
adalah benar (hipotesis induksi). Kita harus menunjukkan bahwa
20 + 21 + 22 + … + 2n + 2n+1 = 2(n+1) + 1 – 1
juga benar. Ini kita tunjukkan sebagai berikut:
20 + 21 + 22 + … + 2n + 2n+1 = (20 + 21 + 22 + … + 2n) + 2n+1
= (2n+1 – 1) + 2n+1 (dari hipotesis induksi)
= (2n+1 + 2n+1) – 1
= (2 . 2n+1) – 1
= 2n+2 – 1
= 2(n+1) + 1 – 1
Karena langkah (i) dan (ii) keduanya telah diperlihatkan benar, maka untuk semua bilangan bulat tidak-negatif n, terbukti bahwa 20 + 21 + 22 + … + 2n = 2n+1 – 1
Induksi Kuat (Prinsip kedua dari induksi matematika)
Terdapat bentuk lain dari induksi matematika yang sering dipergunakan dalam bukti. Teknik ini dinamakan Induksi Kuat atau Prinsip kedua dari induksi matematika
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ³ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:
1. p(n0) benar, dan
2. jika p(n0 ), p(n0+1), …, p(n) benar maka p(n+1) juga benar untuk semua bilangan bulat n ³ n0,.
Contoh 4
Bilangan bulat positif disebut prima jika dan hanya jika bilangan
bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin
membuktikan bahwa setiap bilangan bulat positif n (n ³ 2) dapat
dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
Buktikan dengan prinsip induksi kuat.
Penyelesaian:
(i)Basis induksi. Jika n = 2, maka 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.
(ii)Langkah induksi. Misalkan pernyataan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Kita perlu menunjukkan bahwa n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Ada dua kemungkinan nilai n + 1:
Jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.
Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain,
(n + 1)/ a = b atau (n + 1) = ab
yang dalam hal ini, 2 £ a £ b £ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab.
Karena langkah (i) dan (ii) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
Soal:
1. Buktikan 1 + 2 + 3 + . . . + n = ½ n (n + 1) untuk setiap n bilangan asli.
2. Buktikan bahwa semua bilangan berbentuk 7n – 2n dapat dibagi oleh 5 untuk setiap n bilangan asli.
3. Temukan kesalahan dalam pembuktian berikut. Kita ingin membuktikan bahwa an = 1 untuk semua bilangan bulat tak-negatif n bilamana a adalah bilangan riil tidak-nol.
Penyelesaian:
1. Pernyataan yang akan dibuktikan adalah
1 + 2 + 3 + . . . + n = ½ n (n + 1)
(i) Basis induksi. Dengan demikian, P(1) adalah 1 = ½ .1.(1+1), P(2) = 1 + 2 =½.2.(2+1) dan seterusnya.
(ii) Untuk membuktikan pernyataan itu, perhatikan bahwa P(1) adalah benar. Kemudian, misalkan bahwa
1 + 2 + 3 + . . . + n = ½ n (n + 1)
adalah benar, dan kita harus membuktikan bahwa P(n+1) adalah benar. Untuk ini, kita tambahkan kedua ruas pernyataan P(n) dengan (n + 1) dan diperoleh
1+ 2 + . . . + n + (n + 1) = ½ n (n+1) (n+1)
= ½ [n(n+1)+ 2(n+1)]
= ½ (n2 + 3n + 2)
= ½ (n+1)( n +2)
= ½ (n+1)[( n+1)+1]
Dari sini kita peroleh bahwa Pn+1 adalah benar. Hal ini menunjukkan bahwa pernyataan
1 + 2 + 3 + . . . + n = ½ n (n + 1)
adalah benar untuk setiap n bilangan asli.
2. Pernyataan yang akan dibuktikan adalah
P(n) : 7n - 2n dapat dibagi oleh 5
(i) P(1) adalah benar sebab 71 – 21 = 5. Selanjutnya, kita asumsikan bahwa P(n) adalah benar.
(ii) Dengan asumsi di atas kita akan menyelidiki kebenaran pernyataan P(n+1) . Untuk itu, kita perhatikan bahwa
7n+1 + 2n+1 = 7.7n – 7.2 n + 7.2n – 2.2n
= 7[7n - 2n] + 5.2n
= 7(5m) + 5. 2n m є N (asumsi P(n) benar)
= 5(7m + 2n )
Karena 7m + 2n bilangan asli, maka dari kesamaan terakhir kita dapat menyimpulkan bahwa 7n+1 +2n+1 dapat dibagi dengan 5. Dengan kata lain, pernyataan Pn+1 adalah benar. Dengan demikian, bilangan berbentuk 7n - 2n dapat dibagi oleh 5 untuk setiap n bilangan asli.
3. Temukan kesalahan dalam pembuktian berikut. Kita ingin membuktikan bahwa an = 1 untuk semua bilangan bulat tak-negatif n bilamana a adalah bilangan riil tidak-nol. Kita akan membuktikan ini dengan prinsip induksi kuat.
(i) Basis induksi. Untuk n = 0, jelas a0 = 1 adalah benar sesuai definisi a0.
(ii) Langkah induksi. Misalkan pernyataan tersebut benar untuk 0, 1, 2, …, n, yaitu a0 = 1, a1 = 1, a2 = 1, …, an = 1. Kita ingin memperlihatkan bahwa a(n+1) = 1. Untuk menunjukkan hal ini, maka
= (dari hipotesis induksi)
= 1
Kesalahan terjadi pada langkah induksi, karena untuk n = 0 kita tidak dapat menghitung
sebab nilai a–1 tidak terdapat dalam hipotesis induksi.
http://donybagus.students-blog.undip.ac.id/matematika-diskrit/
Penyelesaian:
(i)Basis induksi. Jika n = 2, maka 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.
(ii)Langkah induksi. Misalkan pernyataan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Kita perlu menunjukkan bahwa n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Ada dua kemungkinan nilai n + 1:
Jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.
Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain,
(n + 1)/ a = b atau (n + 1) = ab
yang dalam hal ini, 2 £ a £ b £ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab.
Karena langkah (i) dan (ii) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
Soal:
1. Buktikan 1 + 2 + 3 + . . . + n = ½ n (n + 1) untuk setiap n bilangan asli.
2. Buktikan bahwa semua bilangan berbentuk 7n – 2n dapat dibagi oleh 5 untuk setiap n bilangan asli.
3. Temukan kesalahan dalam pembuktian berikut. Kita ingin membuktikan bahwa an = 1 untuk semua bilangan bulat tak-negatif n bilamana a adalah bilangan riil tidak-nol.
Penyelesaian:
1. Pernyataan yang akan dibuktikan adalah
1 + 2 + 3 + . . . + n = ½ n (n + 1)
(i) Basis induksi. Dengan demikian, P(1) adalah 1 = ½ .1.(1+1), P(2) = 1 + 2 =½.2.(2+1) dan seterusnya.
(ii) Untuk membuktikan pernyataan itu, perhatikan bahwa P(1) adalah benar. Kemudian, misalkan bahwa
1 + 2 + 3 + . . . + n = ½ n (n + 1)
adalah benar, dan kita harus membuktikan bahwa P(n+1) adalah benar. Untuk ini, kita tambahkan kedua ruas pernyataan P(n) dengan (n + 1) dan diperoleh
1+ 2 + . . . + n + (n + 1) = ½ n (n+1) (n+1)
= ½ [n(n+1)+ 2(n+1)]
= ½ (n2 + 3n + 2)
= ½ (n+1)( n +2)
= ½ (n+1)[( n+1)+1]
Dari sini kita peroleh bahwa Pn+1 adalah benar. Hal ini menunjukkan bahwa pernyataan
1 + 2 + 3 + . . . + n = ½ n (n + 1)
adalah benar untuk setiap n bilangan asli.
2. Pernyataan yang akan dibuktikan adalah
P(n) : 7n - 2n dapat dibagi oleh 5
(i) P(1) adalah benar sebab 71 – 21 = 5. Selanjutnya, kita asumsikan bahwa P(n) adalah benar.
(ii) Dengan asumsi di atas kita akan menyelidiki kebenaran pernyataan P(n+1) . Untuk itu, kita perhatikan bahwa
7n+1 + 2n+1 = 7.7n – 7.2 n + 7.2n – 2.2n
= 7[7n - 2n] + 5.2n
= 7(5m) + 5. 2n m є N (asumsi P(n) benar)
= 5(7m + 2n )
Karena 7m + 2n bilangan asli, maka dari kesamaan terakhir kita dapat menyimpulkan bahwa 7n+1 +2n+1 dapat dibagi dengan 5. Dengan kata lain, pernyataan Pn+1 adalah benar. Dengan demikian, bilangan berbentuk 7n - 2n dapat dibagi oleh 5 untuk setiap n bilangan asli.
3. Temukan kesalahan dalam pembuktian berikut. Kita ingin membuktikan bahwa an = 1 untuk semua bilangan bulat tak-negatif n bilamana a adalah bilangan riil tidak-nol. Kita akan membuktikan ini dengan prinsip induksi kuat.
(i) Basis induksi. Untuk n = 0, jelas a0 = 1 adalah benar sesuai definisi a0.
(ii) Langkah induksi. Misalkan pernyataan tersebut benar untuk 0, 1, 2, …, n, yaitu a0 = 1, a1 = 1, a2 = 1, …, an = 1. Kita ingin memperlihatkan bahwa a(n+1) = 1. Untuk menunjukkan hal ini, maka
= (dari hipotesis induksi)
= 1
Kesalahan terjadi pada langkah induksi, karena untuk n = 0 kita tidak dapat menghitung
sebab nilai a–1 tidak terdapat dalam hipotesis induksi.
http://donybagus.students-blog.undip.ac.id/matematika-diskrit/
Tidak ada komentar:
Posting Komentar