Induksi

Definisi

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 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

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

F Digunakan untuk memperlihatkan bahwa pernyataan benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil

F Buat implikasi untuk fungsi berikutnya benar untuk setiap bilangan bulat positif

Langkah induksi

F Berisi asumsi (andaian) yang menyatakan bahwa p(n) benar.

F Asumsi tersebut dinamakan hipotesis induksi.

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

Contoh :

Gunakan induksi matematika untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n².

Basis induksi

p(1) benar à jumlah 1 buah bilangan ganjil positif pertama adalah 1² = 1

Langkah induksi

Misalkan p(n) benar à asumsi bahwa :

            1+3+5+…+(2n-1) = n²

Adalah benar (hipotesis induksi)

Perlihatkan bahwa p(n+1) juga benar, yaitu :

            1+3+5+…+(2n-1)+(2n+1) = (n+ 1)²

Hal ini dapat ditunjukkan sebagai berikut :

            1+3+5+…+(2n-1)+(2n+1) = [1+3+5+…+(2n-1)]+(2n+1)

                        = n² + (2n+1)

                        = n² + 2n + 1

                        = (n+ 1)²

Langkah (i) dan (ii) dibuktikan benar, maka untuk jumlah n buah bilangan ganjil positif pertama adalah n².

Prinsip Induksi yang Dirampatkan

Prinsip induksi sederhana dapat dirampatkan (generalized)

Misalkan p(n) adalah pernyataan perihal bilangan bulat n ³ n₀. Untuk membuktikannya perlu menunjukkan bahwa :

1.      p(n₀) benar

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

            sehingga p(n) benar untuk semua bilangan bulat n ³ n₀

Contoh soal

Buktikan dengan induksi matematika bahwa 3ⁿ < n! untuk n bilangan bulat positif yang lebih besar dari 6

Jawab :

Misalkan p(n) adalah proposisi bahwa 3ⁿ < n! untuk n bilangan bulat positif yang lebih besar dari 6

Basis induksi

p(7) benar à 3⁷ < 7! « 2187 < 5040

Langkah induksi

Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3ⁿ < n! adalah benar. Perlihatkan juga bahwa p(n+1) juga benar, yaitu 3ⁿ⁺¹ < (n+1)!

Hal ini dapat ditunjukkan sbb :

             3ⁿ⁺¹ < (n+1)!

             3 . 3ⁿ < (n+1) . n!

             3ⁿ . 3 / (n+1) < n!

Menurut hipotesis induksi, 3ⁿ < n!, sedangkan untuk n > 6, nilai 3/(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3ⁿ . 3/(n+1) < n! jelas benar

Langkah (i) dan (ii) dibuktikan benar, maka terbukti bahwa 3ⁿ < n! untuk n bilangan bulat positif lebih besar dari 6.

Prinsip Induksi Kuat

Prinsip induksi yang lebih kuat adalah sbb :

1.      p(n₀) benar

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

            sehingga p(n) benar untuk semua bilangan bulat n ³ n₀

Versi induksi yang lebih kuat mirip dengan induksi sederhana, perbedaannya adalah pada langkah (ii) :

F hipotesis induksi yang lebih kuat

bahwa semua pernyataan p(1), p(2), …, p(n) adalah benar

F Hipotesis induksi sederhana

bahwa p(n) benar

Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak.

Contoh soal :

Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Buktikan dengan induksi matematika (prinsip induksi kuat) bahwa setiap bilangan bulat positif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

Jawab :

Misalkan p(n) adalah proposisi setiap bilangan bulat positif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima

Basis induksi

p(2) benar à 2 sendiri adalah bilangan prima dan 2 dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri

Langkah induksi

Misalkan p(n) benar, asumsikan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima (hipotesis induksi). Perlihatkan juga bahwa p(n+1) benar, yaitu n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima.

Hal ini dapat ditunjukkan sbb :

Jika n + 1 bilangan prima à perkalian satu atau lebih bilangan prima

Jika n + 1 bukan bilangan prima à terdapaat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa

                                    (n+1)/a = b atau (n+1) = ab

            dimana 2 £ a £ b £ n.

Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

Ini berarti bahwa n+1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n+1 = ab

Langkah (i) dan (ii) dibuktikan benar, maka terbukti bahwa setiap bilangan bulat positif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

Bentuk Induksi Secara Umum

Membuat bentuk umum metode induksi sehingga dapat diterapkan tidak hanya untuk pembuktian proposisi yang menyangkut himpunan bilangan bulat positif tetapi juga pembuktian yang menyangkut himpunan obyek yang lebih umum.

Syaratnya himpunan obyek tersebut harus mempunyai :

1.      Keterurutan

2.      Elemen terkecil

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

3.      Diberikan x, y, z Î X, jika x < y dan y < z maka x < z

4.      Diberikan x, y Î X. Salah satu dari kemungkinan ini benar : x < y atau y < x atau x = y

5.      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”

Misalkan X terurut baik oleh “<“ dan p(x) adalah pernyataan perihal elemen x dari X. Pembuktian bahwa p(x) benar untuk semua x Î X. Untuk pembuktiannya hanya perlu menunjukkan bahwa :

p(x₀) benar, yang dalam hal ini x₀ adalah elemen terkecil di dalam X

Jika p(y) benar untuk y < x, maka p(x) juga benar untuk setiap x > x₀ di dalam X Sehingga p(x) benar untuk semua x Î X

Soal :

Tinjau barisan bilangan yang didefinisikan sbb :

                               0               jika m = 0 dan n = 0

S_m,n =      S_{m-1, n} + 1     jika n = 0

                          S_{m, n-1} + 1       jika n ¹ 0

 Sebagai contoh :

S_0,0 = 0                        S_1,0 = S_0,0 + 1 = 0 + 1 = 1

S_0,1 = S_0,0 + 1 = 1        S_1,1 = S_1,0 + 1 = 1 + 1 = 2

S_2,0 = S_1,0 + 1 = 2        S_2,1 = S_2,0 + 1 = 2 + 1 = 3,…

Buktikan dengan induksi matematik bahwa untuk pasangan tidak negatif m dan n, S_m,n = m+n

Jawab  :

Basis induksi

(0,0) elemen terkecil di dalam X, maka S_m,n = 0 + 0 = 0

Langkah induksi

Buktikan semua (m,n) > (0,0) di dalam X bahwa jika S_m’,n’ = m’ + n’ benar untuk semua (m’,n’) < (m,n) maka S_m,n = m+n juga benar.

Andaikan bahwa S_m’,n’ = m’ + n’ benar untuk semua (m’,n’) à hipotesis induksi

Tunjukkan juga bahwa S_m,n =m + n baik untuk n = 0 atau n ¹ 0.

Kasus 1 :

Jika n = 0 maka dari definisi S_m,n = S_m-1,n +1

Karena (m-1, n) < (m, n) maka dari hipotesis induksi

             S_m-1,n = (m-1) + n sehingga S_m,n = S_m-1,n +1 = (m-1)+n+1=m+n

Kasus 2 :

Jika n ¹ 0 maka dari definisi S_m,n = S_m,n-1 +1

Karena (m, n-1) < (m, n) maka dari hipotesis induksi

             S_m,n-1 = m + (n-1) sehingga S_m,n = S_m,n-1 +1 = m+(n-1)+1=m+n

Langkah (i) dan (ii) sudah dibuktikan benar, maka terbukti bahwa untuk pasangan tidak negatif m dan n, S_m,n = m+n

Read more

Relasi

RELASI

Definisi Relasi adalah himpunan bagian antara  A(domain) dan B (kodomain) atau  relasi yang memasangkan setiap elemen yang ada pada himpunan  A secara tunggal, dengan elemen yang  pada B.

Macam penyajian relasi :

Penyajian Relasi dengan Diagram Panah

  Misalkan A = {3,4,5} dan B = {2,4}.

  Jika kita definisikan relasi R dari A ke B dengan aturan :   (a, b) ∈ R jika a faktor prima dari b maka relasi tersebut dapat digambarkan dengan diagram panah berikut ini :

Penyajian relasi dengan diagram cartesius

Diagram Kartesius menggunakan pasangan koordinat horisontal-vertikal. Setiap titik mewakili ada tidaknya hubungan A dan B, contoh :

Penyajian Relasi berupa Pasangan Terurut

     Contoh relasi pada diagram panah dapat

             dinyatakan dalam

             bentuk pasangan terurut, yaitu :

             R = {(3, 2), (4, 2), (5, 2), (5, 4)}

      

Penyajian Relasi dengan Tabel

Kolom pertama tabel menyatakan daerah asal,

sedangkan kolom kedua menyatakan daerah

hasil

Penyajian Relasi dengan Matriks

     
       Relasi antara A = {a₁, a₂, …, a_m} dan B = {b₁, b₂, …, b_n}

           

Jenis-jenis Relasi

Relasi Invers

Misalkan R merupakan  relasi dari himpunan A ke himpunan B. Invers dari R yang dinyatakan dengan  adalah relasi dari B ke A yang mengandung semua pasangan terurut yang bila dipertukarkan masih termasuk dalam R. Ditulis dalam notasi himpunan sbb ;

R-1= {(b,a) : (a,b)R}

contoh:
A = {1,2,3}           B = {x,y}
R = {(1,x), (1,y), (3,x)} relasi dari A ke B
R-1= {(x,1), (y,1), (x,3)} relasi invers dari B ke A

Relasi Refleksif

Misalkan R = (A, A, P(x,y)) suatu relasi.

R disebut relasi refleksif, jika setiap A berlaku (a,a)R.

Dengan kata lain, R disebut relasi refleksif jika setiap anggota dalam A berelasi dengan dirinya sendiri

Contoh Relasi Refleksif

Diketahui A = {1, 2, 3, 4} dan

R = {(1,1), (2,3), (3,3), (4,2), (4,4)}

Apakah R relasi refleksif ?

R bukan relasi refleksif, sebab (2,2) tidak termasuk dalam R.

Jika (2,2) termasuk dalam R, yaitu R1= {(1,1), (2,2), (2,3), (3,3), (4,2), (4,4)} maka R1merupakan relasi refleksif.

Relasi Simetrik

Misalkan R = (A, B, P(x,y)) suatu relasi.

R disebut relasi simetrik, jika setiap (a,b)R berlaku (b,a)R.

Dengan kata lain, R disebut relasi simetrik jika a R b berakibat b R a.

Contoh Relasi Simetrik

perhatikan satu per satu. Setiap kali kamu menemukan pasangan, misalnya (a, b), maka cari apakah (b, a) juga ada. Kalau ternyata tidak ada, pasti relasi itu tidak simetrik.

Apakah relasi dalam {1, 2, 3, 4} berikut simetrik?

pembahasan

{(1, 2), (2, 3), (4, 2), (3, 2), (2,4), (1, 1), (3, 3), (2, 1)}

Relasi tersebut simetrik. Mari kita periksa satu per satu.

 kita menemukan (1, 2). Berarti (2, 1) juga harus ada. Ternyata benar.

{(1, 2), (2, 3), (4, 2), (3, 2), (2, 4), (1, 1), (3, 3), (2,1)}

Relasi anti Simetrik

Suatu relasi R disebut relasi anti simetrik jika (a,b)R dan (b,a)R maka a=b.

Dengan kata lain Jika a, b A, a≠b, maka (a,b)R atau (b,a)R, tetapi tidak kedua-duanya.

Contoh : Misalkan R suatu relasi dalam himpunan bilangan asli yang didefinisikan “y habis dibagi oleh x”, maka R termasuk relasi anti simetrik karena jika b habis dibagi a dan a habis dibagi b, maka a = b.

Misalkan A = {1, 2, 3} dan R1= {(1,1), (2,1), (2,2), (2,3), (3,2)}, maka R1bukan relasi anti simetrik, sebab (2,3)R1dan (3,2)R1pula.

Relasi Transitif

Misalkan R suatu relasi dalam himpunan A. R disebut relasi transitif jika berlaku ; Jika (a,b)R dan (b,c)R maka (a,c)R.

Dengan kata lain

Jika a berelasi dengan b dan b berelasi dengan c, maka a berelasi dengan c.

Contoh : Misalkan A = {a, b, c} dan R = {(a,b), (a,c), (b,a), (c,b)}, maka R bukan relasi transitif, sebab (b,a)R dan (a,c)R tetapi (b,c)R.

Coba dilengkapi agar R menjadi relasi transitif

R = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c)}

Relasi Equivalen

Suatu relasi R dalam himpunan A disebut relasi equivalen jika memenuhi ;

1.Sifat Refleksif

2.Sifat Simetrik

3.Sifat Transitif

Sekian penjelasannya, untuk  lebih paham, ada 1 soal nih.

1.      Jika A = {1, 2, 3, 4}, berikut diberikan relasi atas A:

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}

R2 = {(1, 1), (1, 2), (2, 1)}

R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2,2), (3, 3), (4, 1), (4,4)}

R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}

R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3,4), (4, 4)}

R6 = {(3, 4)}

R7 = {(1, 1)}

R8 = {(1, 1), (1, 2), (3, 4), (4, 3)}

Manakah dari kedelapan relasi di atas yang masing-masing bersifat:

refleksif, simetri, anti simetri, transitif, dan yang bukan simetri sekaligus bukan antisimetri.

Pada relasi-relasi di atas yang bersifat refleksif adalah: R3, dan R5.

R1 tidak refleksif karena (3, 3)∉R1.

Relasi yang bersifat simetri: R2, R3, dan R7. 

Relasi yang bersifat antisimetri: R4, R5, R6, dan R7.

Relasi yang bersifat transitif: R5, R6, dan R7. 

Untuk melihat R3 tidak bersifat transitif, dapat menggunakan tabel

berikut:

(a,b)   (b,c)   (a,c)         Keterangan

(1,1)   (1,2)   (1,2)        Anggota R3

(1,2)   (2,2)   (1,2)        Anggota R3

(1,4)   (4,1)   (1,1)        Anggota R3

(2,1)   (1,4)   (2,4)        Bukan anggota R3

(2,2)   (2,1)   (2,1)        Anggota R3

Untuk melihat R5 bersifat transitif, lihat tabel berikut:

R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2,2), (2,3), (2,4), (3, 3), (3, 4), (4, 4)}

(a,b)   (b,c)   (a,c)         Keterangan

(1,1)   (1,2)   (1,2)        Anggota R5

(1,2)   (2,2)   (1,2)        Anggota R5

(1,3)   (3,3)   (1,3)        Anggota R5

(1,4)   (4,1)   (1,1)        Anggota R5

(2,2)   (2,4)   (2,4)        Bukan anggota R3

(2,3)   (2,1)   (2,1)        Anggota R3

(2,4)   

(3,3)   

(3,4)   

(4,4)   

Relasi yang bukan simetri dan bukan pula antisimetri: R1, dan R8.

Read more