SOAL DAN PEMBAHASAN MATERI KOMBINAS DAN PERMUTASI

1. Berapa banyak string yang dapat dibentuk dari huruf-huruf kata “WEAKNESS” sedemikian sehingga 2    buah huruf “S” tidak terletak berdampingan?

          Penyelesaian:

2. Carilah jumlah himpunan bagian dari A = {a,b,c,d,e} bila diletakkan ke himpunan B dengan 2 elemen?

           Penyelesaian:

3. Sebuah kelompok terdiri dari 7 orang wanita dan 4 orang pria. Berapa banyak perwakilan 4 orang yang dapat dibentuk dari kelompok itu jika paling sedikit harus ada 2 orang wanita didalamnya?

           Penyelesaian:

      

INDUKSI MATEMATIKA

Induksi matematika adalah metode pembuktian untuk proposisi perihal bilangan bulat. Induksi matematika merupakan teknik pembuktian yang baku didalam matematika. Induksi metamtika dapat mengurangi lagkah-langkah pembuktian bahwa semua bilangan bulat termasuk kedalma suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.  

         Contoh:

 

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

Contoh:

Jumlah n buah bilangan ganjil positif pertama adalah n2.

Bukti:

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

nn = 1 à 1 = 1  è (1)2 = 1

nn = 2 à 1+3 = 4  è (2)2 = 4

nn = 3 à 1+3+5 = 9  è (3)2 = 9

nn = 4 à 1+3+5+7 = 16  è (4)2 = 16

nn = 5 à 1+3+5+7+9 = 25  è (5)2 = 25

nn = 6 à 1+3+5+7+9+11 = 36 è (6)2 = 36

         Sehingga proposisi (pernyataan) tersebut benar

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 :

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

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

       

          Basis Induksi:  

•         Digunakan untuk memperlihatkan bahwa pernyataan benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil
•         Buat implikasi untuk fungsi berikutnya benar untuk setiap bilangan bulat positif \

           Langkah Induksi:

•         Berisi asumsi (andaian) yang menyatakan bahwa p(n) benar.
•         Asumsi tersebut dinamakan hipotesis induksi.

           Bila kedua langkah tersebut benar maka pembuktian bahwa p(n) benar untuk semua  bilangan positif n.

 

      

          CONTOH:

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

•           Basis induksi

                    p(1) benar ➜ n = 1 diperoleh dari :

                                           

                          1 = 1(1+1)/2

                             

                              = 1(2)/2

           

                              = 2/2

                              

                              =1

•           Langkah induksi

                    Misalkan p(n) benar à asumsi bahwa :

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

                    Adalah benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar yaitu 

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

                      

                1+2+3+…+n+(n+1) = (1+2+3+…+n)+(n+1)

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

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

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

  = (n2+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