Matematika Diskret

Matematika Diskrit

1. Induksi Matematika

• Induksi matematika adalah :

·         Metode pembuktian untuk proposisi perihal bilangan bulat

• Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika
• Induksi matematika dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbata

Jumlah bilangan bulat positif dari 1 sampai n adalah n(n+1)/2

Bukti :

Misalkan n = 6 à p(6) adalah “Jumlah bilangan bulat positif dari 1 sampai 6 adalah 6(6+1)/2” terlihat bahwa :

                1 + 2 + 3 + 4 + 5 + 6 = 21 è 6(7)/2 = 21

Sehingga proposisi (pernyataan) tersebut benar

Jumlah n buah bilangan ganjil positif pertama adalah n².

Bukti

Misalkan n = 6 buah (n = 1,2,3,4,5,6) maka :

·         n = 1 à 1 = 1      è (1)² = 1

·         n = 2 à 1+3 = 4 è (2)² = 4

·         n = 3 à 1+3+5 = 9            è (3)² = 9

·         n = 4 à 1+3+5+7 = 16     è (4)² = 16

·         n = 5 à 1+3+5+7+9 = 25                è (5)² = 25

·         n = 6 à 1+3+5+7+9+11 = 36 è (6)² = 36

Sehingga proposisi (pernyataan) tersebut benar

• Setiap bilangan bulat positif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima
• Untuk semua n ³ 1, n³ + 2n adalah kelipatan 3
• Untuk membayar biaya pos sebesar n sen dolar (n ³ 8) selalu dapat digunakan hanya perangko 3 sen dan 5 sen dolar
• Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali. Jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah n(n – 1)/2
• Banyaknya himpunan bagian yang dapat dibentuk dari sebuah himpunan yang beranggotakan n elemen adalah 2ⁿ.

A.      Prinsip Induksi Sederhana

Misalkan p(n) adalah proposisi bilangan bulat positif dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat positif n. Maka langkah-langkahnya adalah sebagai berikut :

n  p(n) benar

n  Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ 1

Sehingga p(n) benar untuk semua bilangan bulat positif n

Contoh :
Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n(n+1)/2 melalui induksi matematika
: 1+2+3+…+n+(n+1) = (1+2+3+…+n)+(n+1)

                                = [n(n+1)/2]+(n+1)

                                = [(n²+n)/2]+(n+1)

                                = [(n²+n)/2]+[(2n+2)/2]

                                = (n²+3n+2)/2

                                = (n+1)(n+2)/2

                                = (n+1)[(n+1)+1]/2

Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ³ 1, 1+2+3+…+n = n(n+1)/2 .