cara /teknik membuktikan kebenaran dari...induksi matematika merupakan teknik pembuktian yang baku...

Cara / Teknik membuktikan kebenaran darisuatu pernyataan Metode pembuktian untuk pernyataan

perihal bilangan bulat Contoh:p(n): “Jumlah bilangan bulat positif dari 1sampai n adalah n(n + 1)/2”.

Buktikan p(n) benar!

Cara / Teknik membuktikan kebenaran darisuatu pernyataan Metode pembuktian untuk pernyataan

perihal bilangan bulat Contoh:p(n): “Jumlah bilangan bulat positif dari 1sampai n adalah n(n + 1)/2”.

Buktikan p(n) benar!

Induksi matematika merupakan teknikpembuktian yang baku di dalam matematika.

Melalui induksi matematik kita dapatmengurangi langkah-langkah pembuktianbahwa semua bilangan bulat termasuk kedalam suatu himpunan kebenaran denganhanya sejumlah langkah terbatas.

Induksi matematika merupakan teknikpembuktian yang baku di dalam matematika.

Melalui induksi matematik kita dapatmengurangi langkah-langkah pembuktianbahwa semua bilangan bulat termasuk kedalam suatu himpunan kebenaran denganhanya sejumlah langkah terbatas.

Misalkan p(n) adalah pernyataan mengenaibilangan bulat positif. Kita ingin membuktikan bahwa p(n) benar

untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, kita

hanya perlu menunjukkan bahwa:1. p(n0) benar, dan2. jika p(n) benar, maka p(n + 1) juga benar,untuk setiap n 1,

Misalkan p(n) adalah pernyataan mengenaibilangan bulat positif. Kita ingin membuktikan bahwa p(n) benar

untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, kita

hanya perlu menunjukkan bahwa:1. p(n0) benar, dan2. jika p(n) benar, maka p(n + 1) juga benar,untuk setiap n 1,

Langkah 1 dinamakan basis induksi, sedangkanlangkah 2 dinamakan langkah induksi.

Langkah basis induksi berisi asumsi (andaian)yang menyatakan bahwa p(n) benar. Asumsitersebut dinamakan hipotesis induksi.

Hipotesis induksi digunakan untuk mendukunglangkah induksi.

Bila kita sudah menunjukkan kedua langkahtersebut benar maka kita sudah membuktikanbahwa p(n) benar untuk semua bilangan bulatpositif n.

Langkah 1 dinamakan basis induksi, sedangkanlangkah 2 dinamakan langkah induksi.

Langkah basis induksi berisi asumsi (andaian)yang menyatakan bahwa p(n) benar. Asumsitersebut dinamakan hipotesis induksi.

Hipotesis induksi digunakan untuk mendukunglangkah induksi.

Bila kita sudah menunjukkan kedua langkahtersebut benar maka kita sudah membuktikanbahwa p(n) benar untuk semua bilangan bulatpositif n.

Buktikan “Jumlah bilangan bulat positif dari 1sampai n adalah n(n + 1)/2” ! Buktikan “Jumlah bilangan bulat positif dari 1

sampai n adalah n(n + 1)/2” !

Langkah I : Buktikan bahwa P(1) benarP(1) = 1(1 + 1)/2 = 1 ………. Terbukti Langkah II : Buktikan bahwa jika P(n) benar,

maka P(n+1) juga benarP(n+1) = 1 + 2 + 3 + … + n + (n+1)(n+1)((n+1) +1)/2 = P(n) + (n+1)(n+1)(n+2)/2 = n(n+1)/2 + 2(n+1)/2(n+1)(n+2)/2 = (n+2)(n+1)/2 ……. Terbukti

Langkah I : Buktikan bahwa P(1) benarP(1) = 1(1 + 1)/2 = 1 ………. Terbukti Langkah II : Buktikan bahwa jika P(n) benar,

maka P(n+1) juga benarP(n+1) = 1 + 2 + 3 + … + n + (n+1)(n+1)((n+1) +1)/2 = P(n) + (n+1)(n+1)(n+2)/2 = n(n+1)/2 + 2(n+1)/2(n+1)(n+2)/2 = (n+2)(n+1)/2 ……. Terbukti

Buktikan bahwa jumlah n buah bilanganganjil positif pertama adalah n2!

Langkah 1 (Basis induksi):Untuk n = 1, jumlah satu buah bilangan ganjilpositif pertama adalah n2 = 12 = 1. Ini benarkarena jumlah satu buah bilangan ganjilpositif pertama memang 1.

Langkah 1 (Basis induksi):Untuk n = 1, jumlah satu buah bilangan ganjilpositif pertama adalah n2 = 12 = 1. Ini benarkarena jumlah satu buah bilangan ganjilpositif pertama memang 1.

Langkah 2 (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

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)= n2 + (2n + 1)= n2 + 2n + 1= (n + 1)2 ……………..Terbukti

Langkah 2 (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

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)= n2 + (2n + 1)= n2 + 2n + 1= (n + 1)2 ……………..Terbukti

Untuk tiap n ≥ 3, jumlah sudut dalam sebuahpoligon dengan n sisi adalah 180(n − 2).Buktikan pernyataan ini dengan induksimatematik.

Untuk tiap n ≥ 3, jumlah sudut dalam sebuahpoligon dengan n sisi adalah 180(n − 2).Buktikan pernyataan ini dengan induksimatematik.

11

BasisUntuk nilai n = 3, poligon akan berbentuk segitiga denganjumlah sudut 180. Jumlah sisi sebanyak 3 sehingga 180(3 −2) = 180. Jadi untuk n = 3 proposisi benar

InduksiAsumsikan bahwa jumlah sudut dalam poligon dengan n sisiyaitu 180(n − 2) adalah benar (hipotesis induksi).Kita ingin menunjukkan bahwa jumlah sudut poligon yangmemiliki n+1 sisi yaitu 180(n − 1)

BasisUntuk nilai n = 3, poligon akan berbentuk segitiga denganjumlah sudut 180. Jumlah sisi sebanyak 3 sehingga 180(3 −2) = 180. Jadi untuk n = 3 proposisi benar

InduksiAsumsikan bahwa jumlah sudut dalam poligon dengan n sisiyaitu 180(n − 2) adalah benar (hipotesis induksi).Kita ingin menunjukkan bahwa jumlah sudut poligon yangmemiliki n+1 sisi yaitu 180(n − 1)

12

Pada gambar diatas dapat ditunjukkan terdapat dua bagianyaitu segitiga P1PnPn+1) dan poligon dengan n sisiJumlah sudut dalam poligon n sisi menurut asumsi yaitu 180(n− 2) dan jumlah sudut di dalam untuk segitiga yaitu 180◦.Jadi jumlah sudut dalam dari poligon dengan n + 1 sisi yaitu180(n − 2) + 180 = 180(n − 1).

Karena basis dan langkah induksi benar, maka proposisi di atasterbukti benar.

Pada gambar diatas dapat ditunjukkan terdapat dua bagianyaitu segitiga P1PnPn+1) dan poligon dengan n sisiJumlah sudut dalam poligon n sisi menurut asumsi yaitu 180(n− 2) dan jumlah sudut di dalam untuk segitiga yaitu 180◦.Jadi jumlah sudut dalam dari poligon dengan n + 1 sisi yaitu180(n − 2) + 180 = 180(n − 1).

Karena basis dan langkah induksi benar, maka proposisi di atasterbukti benar.

13

1. Untuk semua bilangan bulat tidak-negatifn, buktikan dengan induksi matematik bahwa20 + 21 + 22 + … + 2n = 2n+1 – 1

2. BuktikanP(n) = 12 + 22 + 32 + … + n2 = n(n+1)(2n+1)/6untuk n > 1

1. Untuk semua bilangan bulat tidak-negatifn, buktikan dengan induksi matematik bahwa20 + 21 + 22 + … + 2n = 2n+1 – 1

2. BuktikanP(n) = 12 + 22 + 32 + … + n2 = n(n+1)(2n+1)/6untuk n > 1

3. Jika A1, A2, …, An masing-masing adalahhimpunan, buktikan dengan induksimatematik hukum De Morgan rampatanberikut:

3. Jika A1, A2, …, An masing-masing adalahhimpunan, buktikan dengan induksimatematik hukum De Morgan rampatanberikut:

nn AAAAAA 2121

4. Buktikan dengan induksi matematik bahwan5 – n habis dibagi 5 untuk n bilangan bulatpositif.

5. Di dalam sebuah pesta, setiap tamuberjabat tangan dengan tamu lainnya hanyasekali saja. Buktikan dengan induksimatematik bahwa jika ada n orang tamumaka jumlah jabat tangan yang terjadiadalah n(n – 1)/2.

4. Buktikan dengan induksi matematik bahwan5 – n habis dibagi 5 untuk n bilangan bulatpositif.

5. Di dalam sebuah pesta, setiap tamuberjabat tangan dengan tamu lainnya hanyasekali saja. Buktikan dengan induksimatematik bahwa jika ada n orang tamumaka jumlah jabat tangan yang terjadiadalah n(n – 1)/2.

6. Perlihatkan bahwa [(p1 p2) (p2 p3) … (pn–1 pn)] [(p1 p2 … pn–1)pn ] adalah tautologi bilamana p1, p2, …, pnadalah proposisi.

6. Perlihatkan bahwa [(p1 p2) (p2 p3) … (pn–1 pn)] [(p1 p2 … pn–1)pn ] adalah tautologi bilamana p1, p2, …, pnadalah proposisi.