INDUKSI MATEMATIKA

Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika. Induksi matematika berawal pada akhir abad ke-19 dua orang matematikawan yang mempelopori perkembangan indusksi matematika adalah R.Dedekin dan G.Peano.

A.    Proposisi Perihal Bilangan Bulat

Di dalam matematika, banyak teorema yang menyatakan bahwa p(n) benar unruk semua bilangan bulat positif n, yang dalam hal ini p(n) disebut juga fungsi proposisi. Contoh-contoh  proposisi prihal bilangan bulat yaitu:

-          Setiap bilangan bulat positif n(n≥2)  dapat dinyatakn  sebagai perkalian dari (satu atau lebih) bilangan prima.

-          Untuk semua n≥1,n3+2n  adalah kelipatan 3.

-          Untuk 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 nn-12.

Proposisi-proposisi semacam diataslah yang dapat dibuktikan dengan induksi matematika.

B.     Prinsip Induksi Sederhana

Prinsip induksi sederhana berbunyi sebagai berikut:

Misalkan p(n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk setiap bilangan bulat positif n. Untuk membuktikan proposisi ini,kita hanya perlu menunjukkan bahwa:

-          P(1) benar,dan

-          Jika p(n) benar maka p(n+1) juga benar untuk setiap n≥1.

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

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

C.    Prinsip Induksi yang Dirampatkan

Prinsip induksi sederhan dapat dirampatkan (generalized) untuk menunjukan halini sebagai berikut:

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 menunjukan bahwa:

-          p(n0)  benar,dan

-          jika p(n) benar maka p(n+1) benar untuk setiap n≥n0

Sehingga p(n) benar untuk semua bilangan bulat n≥n0.

D.    Prinsip Induksi Kuat

Versi induksi yang lebih kuat adalah seagai berikut:

Misalkan p(n) adalah peryataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n≥n0.  Untuk membuktikan ini kita hanya perlu menunjukan bahwa:

-          p( n0 ) benar, dan

-          jika p n0, p n0+1,…..,p(n) benar, maka p(n+1) juga benar untuk setiap bilangan bulat n≥n0.  

Sehingga p(n) benar untuk semua bilangan bulat n≥n0.

E.     Bentuk Induksi Secara Umum

Relasi biner “<” pada himpunan X dikatakan terurut dengan baik ( atau himpunan X dikatakan terurut dengan baik dengan “<”) bila memiliki properti berikut:

      1.            Diberikan x,y,z ∈X , jika x<y dan y<z, maka x<z.

      2.            Diberikan x,y∈X . Salah satu dari kemungkinan ini benar: x<y atau y<z atau x=z.

      3.            Jika A adalah himpunan bagian tidak kosong dari X, terdapat elemen x∈A  sedemikian sehingga x≤y  untuk semua y∈A.  Dengan kata lain, setiap himpunan bagian tidak kosong dari X mengandung “elemen terkecil”.

Himpunan bilangan riil tak-negatif tidak terurut dengan baik oleh relasi “<”. Himpunan ini mempunyai properti (i) dan (ii) tetapi tidak (iii).sebagai contoh, himpunan semua bilangan riil yang lebih besar dari 1, yaitu {x|x adalah bilangan riil dan x>1}, tidak mengandund elemen terkecil.

KOMBINATORIAL DAN PELUANG DISKRIT

Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.

A.    Percobaan

Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati

Contoh :

1.      Melempar dadu

Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6

2.      Melempar koin uang Rp 100

Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.

B.     Kaidah Dasar Menghitung

Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).

-          Kaidah Perkalian (rule of product)

Percobaan 1: p hasil

Percobaan 2: q hasil maka,

Percobaan 1 dan percobaan 2:   p ´ q hasil

-          Kaidah Penjumlahan (rule of sum)

Percobaan 1: p hasil

Percobaan 2: q hasil maka,

Percobaan 1 atau percobaan 2:  p + q hasil

C.    Perluasan Kaidah Menghitung

Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :

a.       P1 x p2 x … x pn untuk kaidah perkalian.

b.      P1 + p2 + … + pn untuk kaidah penjumlahan.

D.    Prinsip Inklusi-Eksklusi

Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.

Example :

1.      Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?

Answer :

Misalkan

A                      = himpunan byte yang dimulai dengan ‘11’,

B                      = himpunan byte yang diakhiri dengan ‘11’

A Ç B = himpunan byte yang berawal dan berakhir dengan ‘11’

maka

A È B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’

    ½A½ = 2⁶ = 64,      

    ½B½ = 2⁶ = 64,     

    ½A Ç B½ = 2⁴ = 16.

maka

     ½A È B½ = ½A½ + ½B½ – ½A Ç B½

                    = 2⁶ + 2⁶ – 16   = 64 + 64 – 16 = 112.

E.     Permutasi

Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah

N(n-1) (n-2) … (2)(1) = n!

Example :

—  Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?

Answer :

    Cara 1: (5)(4)(3)(2)(1) = 120 buah kata

    Cara 2: P(5, 5) = 5! = 120 buah kata                                                                              

—  Berapa banyak cara mengurutkan nama 25 orang mahasiswa?

Answer : P(25, 25) = 25!

            Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.

F.     Kombinasi

Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.

Example :

1.      Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.

Jumlah cara memasukkan bola ke dalam kotak :

 

           

2.      Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah

 

karena ada 3! cara memasukkan bola yang warnanya sama.

Kombinasi r elemen dari n elemen, atau  C(n, r),  adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.

Example from Interpretasi Kombinasi :

1.      C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.

Misalkan A = {1, 2, 3}

Jumlah Himpunan bagian dengan 2 elemen:

{1, 2} = {2, 1}

                        {1, 3} = {3, 1}    3   buah  atau

                        {2, 3} = {3, 2}

G.    Permutasi dan Kombinasi Bentuk Umum

Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama - indistinguishable). n₁ bola diantaranya berwarna 1, n₂ bola diantaranya berwarna 2, n_k bola diantaranya berwarna k, dan n₁ + n₂ + … + n_k = n.

Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?

Answer :

Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah   bola ke dalam n buah kotak adalah

   P(n, n) = n!.

   Dari pengaturan n buah bola itu,

-          ada n₁! cara memasukkan bola berwarna 1

-           ada n₂! cara memasukkan bola berwarna 2

-          ada n_k! cara memasukkan bola berwarna k

Permutasi n buah bola yang mana n₁ diantaranya berwarna 1, n₂ bola berwarna 2, …, n_k bola berwarna k adalah:

 

Dengan cara lain :

-          Ada C(n, n₁) cara untuk menempatkan n₁ buah bola yang berwarna 1.

-          Ada C(n – n₁, n₂) cara untuk menempatkan n₂ buah bola berwarna 2.

-          Ada C(n – n₁ – n₂, n₃) cara untuk menempatkan n3 buah bola berwarna 3.

-          Ada C(n – n₁ – n₂ – … –  n_k-1, n_k ) cara untuk menempatkan n_k buah bola berwarna k.

H.    Kombinasi dengan Pengulangan.

Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.

Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.

                                i.            Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).

                              ii.            Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)

Contoh :

Pada persamaan x1  +x2+x3+x4=12, xi  adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?

Penyelesaian:

Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:

-          Kotak 1 diisi 3 buah bola (x1=3)

-          Kotak 2 diisi 5  buah bola (x2=5)

-          Kotak  3 diisi 2 buah bola (x3=2)

-          Kotak 4 diisi 2 buah bola  (x4=2)

          sehingga,  x1 +x2+x3+x4=3+5+2+2=12

I.       Koefisien Binomial

1. x+y0=1

2. x+y1=x+y

3. x+y2=x2+2xy+y2

4. x+y3=x3+3x2y+3xy2+y3

5. x+y4=x3+4x3y+6x2y2+4xy3+y4

6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5

            Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah

·         Suku pertama xn, sedangkan suku terakhir adalah yn

·         Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.

·         Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.

Aturan di atas  dapat di simpulkan bahwa:

x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn

                  = k=0nC(n,k)xn-kyk

J.      Prinsip Sarang Merpati

Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.

Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.

example :

Misalkan terdapat banyak bola merah,bola putih,dan bola biru di dalam sebuah kotak.Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?

answer:

Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.

K.    Peluang Diskrit

Peluang diskrit mempunyai sifat sebagai berikut:

a.       0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.

b.      i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.

Contoh:

Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.

            Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:

PE=|E||S|=xi∈Ep(xi)

Konsep-konsep pada teori himpunan:

·         P A∩B=xi∈A∩Bp(xi)

·         P A∪B=xi∈A∪Bp(xi)

·         P A-B=xi∈A-Bp(xi)

·         P A⨁B=xi∈A⨁Bp(xi)

·         P(A)=1-P(A)