Senin, 20 Mei 2013

Prinsip Induksi matematis

1.      PRINSIP INDUKSI MATEMATIS
Induksi matematis adalah suatu metode pembuktian suatu sifat mengenai bilangan asli berlaku untuk setiap bilangan asli. Bukti yang berdasarkan asas induksi matematis disebut pembuktian secara induksi matematis  atau bukti dengan induksi lengkap
Aksioma 1.1 Sifat Terurut Rapi (Well-Ordering Property of N)
Setiap himpunan bagian dari N  yang tidak kosong memiliki suatu elemen terkecil
Prinsip Induksi Matematis (PIM)
Aksioma 1.2:
Apabila S adalah himpunan bagian dari N yang memiliki dua sifat:
(1)     1Î S
(2)     Untuk setiap kÎN, jika kÎS maka k + 1ÎS
maka S himpunan semua bilangan asli (S = N)
Aksioma 1.2 dapat  diterjemahkan ke dalam model soal-soal membuktikan sebagai berikut:
(1)     P(1) benar
(2)     Untuk setiap kÎN, jika P(k) benar maka P(k+1) benar
Maka P(n) benar untuk setiap nÎN.
Urutan PIM
(1)     Landasan Dasar P(1) benar
(2)     Hipotesis Induksi P(k) benar
Buktikan P(k + 1) benar
Contoh 1:
Untuk setiap nÎN, buktikan
Bukti
Misal P(n) = 12 + 22 + 32 + ¼ + n2.
(1)     Landasan Dasar: P(1) = 12. Karena  , maka P(1) benar
(2)     Hipotesis Induksi : asumsikan P(k) benar, yakni :
Akan dibuktikan P(k + 1) benar
Jadi terbukti , sehingga P(k+1) benar.
Maka menurut PIM, P(n) benar untuk setiap nÎN.
Aksioma 1.3 (Prinsip Induksi Matematika Versi kedua)
Misal n0ÎN dan P(n) suatu pernyataan untuk setiap bilangan asli n³n0, berlaku:
(1)     P(n0) benar
(2)     Untuk setiap k³n0, jika P(k) benar maka P(k + 1) benar.
Maka P(n) benar untuk setiap n³n0.

Contoh 2:
Diketahui a, bÎR. Buktikan ab adalah faktor dari an – bn untuk setiap nÎN.
Bukti
Bukti
Misal P(n) = an – bn.
(1)     Landasan Dasar: P(1) = ab. karena ab merupakan faktor dari P(1) = ab, maka P(1) benar
(2)     Hipotesis Induksi : asumsikan P(k) benar, yakni : ab adalah faktor dari ak – bk.
Akan dibuktikan P(k + 1) benar
Secara jelas ab faktor bk(ab) dan  berdasarkan Hipotesis Induksi ab adalah faktor dari    ak – bk, maka ab adalah faktor dari a(ak– bk). Jadi terbukti ab adalah faktor dari ak – bk, sehinggga P(k + 1) benar
Maka menurut PIM, P(n) benar untuk setiap nÎN.
Aksioma 1.3 (Prinsip Induksi Matematika Versi kedua)
Misal n0ÎN dan P(n) suatu pernyataan untuk setiap bilangan asli n³n0, berlaku:
(3)     P(n0) benar
(4)     Untuk setiap k³n0, jika P(k) benar maka P(k + 1) benar.
Maka P(n) benar untuk setiap n³n0.

Contoh 3:
Buktikan 2n > 2n + 1 untuk setiap n ³ 3, nÎN.
Bukti
(1)     Landasan Dasar: n = 3, 23 = 8 > 7 = 2×3+1. Karena 23 > 2×3+1 maka n = 3 benar
(2)     Hipotesis Induksi : asumsikan n = k  benar, yakni 2k > 2k + 1 untuk setiap k ³ 3
Akan dibuktikan  n = k + 1 benar
2k + 1 = 2×2k > 2(2k + 1) = 4k + 2 = 2k + (2k + 2) > 1 + (2k + 2) = 2(k + 1) + 1
 Jadi terbukti 2k + 1 > 2(k + 1) + 1, sehingga n = k + 1 benar
Maka menurut PIM, P(n) benar untuk setiap n ³ 3, nÎN.

Aksioma 1.3 Prinsip Induksi Versi Lebih Kuat
Misal S Í N, dimana:
(1)     1Î S
(2)     Untuk setiap kÎN, jika {1, 2, 3,¼ k}ÍS maka {1, 2, 3,¼ k, k + 1}ÍS
Maka S = N.

AKSIOMA MEDAN
Himpunan yang dilengkapi dengan satu atau beberapa operasi (yang terdefenisi pada himpunan itu) disebut sistem matematis. Sistem matematis dengan dua operasi yang memiliki sejumlah sifat tertentu disebut field atau medan.Kelompok sifat yang menentukan bahwa suatu sistem matematis merupakan medan disebut aksioma medan. Operasi yang pelaksanaannya harus dikenakan pada pasangan anggota dari suatu himpunan disebut operasi biner.
Diberikan dua buah bilangan real x dan y, kita dapat menambahkan atau mengalikan keduanya untuk memperoleh dua buah bilangan real baru x + y dan x ´ y (x.y atau cukup ditulis xy). Penambahan dan perkalian bilangan-bilangan real memiliki sifat-sifat yang dikenal dengan sifat-sifat  medan.
Sifat-sifat Aljabar R
(A1)      Hukum Komutatif Penjumlahan. a + b = b + a,  " a, b Î R.
(A2)      Hukum Asosiatif Penjumlahan.(a + b) + c  = a +(b + c),   " a, b, c Î R.
(A3)    Eksistensi Bilangan Nol (Unsur Identitas Penjumlahan). Terdapat 0ÎR yang memenuhi a + 0 = 0 + a = a,  " a Î R.
(A4)      Eksistensi Unsur Negatif (Invers Penjumlahan). Untuk setiap a Î R  terdapat −a Î R  sedemikian sehingga a +( −a) = ( −a) + a = 0.
(M1)     Hukum Komutatif Perkalian. a×b = b×a,  " a, b Î R.
(M2)     Hukum Asosiatif Perkalian. (a×b)×c  = a×(b×c),   " a, b, c Î R.
(M3)   Eksistensi Bilangan Unit 1 (Unsur Identitas Perkalian). Terdapat 1ÎR dan 1 berlainan dengan 0 sedemikian sehingga a×1 = 1×a = a,  " a Î R.
(M4)     Eksistensi Unsur Balikan (Invers Perkalian). Untuk setiap a Î R dan a ≠ 0 terdapat R  sedemikian sehingga .
(D)       Hukum Distribusi atas Penjumlahan. a×(b + c)  = a×b + a×c dan (b + c)×a  = b×a + c×a,    " a, b, c Î R.

Teorema 2.1.1.
(a)       Jika z, a Î R dengan z + a = a, maka z = 0.
(b)      Jika u dan b ≠ 0 elemen R dengan u×b = b, maka u = 1.
(c)       Jika a Î R, maka a×0 = 0.

Bukti
(a)    z = z + 0                           (sifat A3)
  = z + (a + (−a))              (sifat A4)
  = (z + a)+ (−a)               (sifat A2)
  = a + (−a)                      (Hipotesis)
  = 0                                 (sifat A3)

(b)   u = u×1                              (sifat M3)
  = u×                      (sifat M4)
  =                     (sifat M2)
  =                            (Hipotesis)
  = 1                                 (sifat M4)

(c)    a×0 = a×0 + 0                     (sifat A3)
      = a×0 + (a + (−a))       (sifat A4)
      = (a×0 + a) + (−a)       (sifat A2)
      = (a×0 + a×1) + (−a)     (sifat M3)
      = (a×(0 + 1)) + (−a)     (sifat D)
      = (a×1) + (−a)              (sifat A3)
      = a + (−a)                   (sifat M3)
      = 0                              (sifat A3)
Dengan demikian teorema 2.1.1 terbukti

Teorema 2.1.2. Jika a Î R, maka
(a)       (−1)×a = −a
(b)      –(−a) = a.
(c)       (−1)×(−1) = 1

Bukti
(a)       (−1)×a = (−1)×a + 0                       (sifat A3)
      = (−1)×a + (a + (−a))          (sifat A4)
      = ((−1)×a + a) + (−a)          (sifat A2)
      = ((−1)×a + 1×a) + (−a)       (sifat M3)
      =  ((−1) + 1)×a) + (−a)       (sifat D)
      = 0×a + (−a)                       (sifat A4)
     = a×0 + (−a)                        (sifat A1)
     = 0 + (−a)                           (Teorema 2.1.1(c))
     = −a                                    (sifat A3)
(b)      –(−a) = –(−a) + 0                         (sifat A3)
     = –(−a) + (−a + a)              (sifat A4)
     = (–(−a) + (−a)) + a           (sifat A2)
     = 0 + a                                (sifat A4)
     = a                                      (sifat A3)

Selanjutnya, diberikan dua sifat penting dari operasi perkalian, yaitu sifat ketunggalan elemen inversnya dan bahwa perkalian dua bilangan itu hasilnya nol apabila salah satu faktornya adalah nol atau dua-duanya 0.

Teorema 2.1.3.
(a)    Jika a + b = 0, maka b = −a.
(b)   Jika a ≠ 0 dan b elemen R sedemikian sehingga a×b = 1, maka
(c)    Jika a×b = 0, maka a = 0 atau b = 0.
Bukti
(a)          b = 0 + b
= (−a + a) + b
= −a + (a + b)
= −a + 0
=   a
Misalkan b1 dan b2  elemen R  yang memenuhi a + b1 = 0 dan a + b2 = 0 akan dibuktikan b1 = b2.
a + b1 = 0, maka b1 = −a dan a + b2 = 0, maka b2 = −a. karena b1 = −a dan b2 = −a, maka b1 = b2.
(b)         Pembuktian untuk yang bagian (b)  mirip dengan bagian (a) tetapi dengan menggunakan sifat-sifat perkalian
(c)           
Teorema-teorema di atas menjelaskan beberapa sifat aljabar sederhana dari system bilangan riil. Beberapa akibat dari teorema-teorema tersebut diberikan sebagai latihan.

Operasi pengurangan (substraction) didefinisikan dengan ab = a + (–b) untuk a, b Î R.
 Operasi pembagian (division) didefinisikan dengan  untuk a, b Î R dan b ≠ 0.
a×b adalah lambang dari a ´ b. Untuk selanjutnya a×b cukup ditulis ab dan 1a = a.
Penulisan a2 untuk aa, a3 untuk (a2)a, dan secara umum an+1 untuk (an)a untuk n Î n. lebih lanjut a1 lambang untuk a; jika a ≠ 0, maka dapat ditulis a0 = 1; a−1 lambang dari ; dan  an lambang dari .

Bilangan Rasional dan Irrasional
n dan z adalah himpunan bagian dari  r. elemen r yang dapat dinotasikan dalam bentuk  dimana   a, b Î Z dan b¹0 disebut bilangan rasional (rational numbers). Himpunan semua bilangan rasional dilambangkan dengan  q.
Teorema 2.1.4
Jumlah dari dua bilangan rasional adalah bilangan rasional.
Bukti
Misalkan x adalah bilangan rasional yang dinotasikan , dengan p, q Î z dan q ¹ 0,
 dan y adalah bilangan rasional yang dinotasikan dengan m, n Î z dan n ¹ 0. Maka
Karena p, q, m, n Î z maka np, mq, Î z sehingga np + mq Î z. Karena  n, q Î z, n ¹ 0 dan q ¹ 0, maka nq Î z dan nq ¹ 0 sehingga menurut definisi bilangan rasional   adalah bilangan rasional. Ini berarti hasil dari x + y adalah bilangan rasional. Jadi teorema terbukti

Teorema 2.1.5
Hasil kali dua bilangan rasional adalah bilangan rasional.
Bukti
Misalkan x adalah bilangan rasional yang dinotasikan , dengan p, q Î z dan q ¹ 0,
 dan y adalah bilangan rasional yang dinotasikan dengan m, n Î z dan n ¹ 0. Maka
Karena p, q, m, n Î z, n ¹ 0 dan q ¹ 0, maka pm, qn Î z dan qn ¹ 0, sehingga menurut definisi bilangan rasional   adalah bilangan rasional. Ini berarti hasil dari x×y adalah bilangan rasional. Jadi teorema terbukti

Tetapi pada kenyataannya tidak semua elemen r merupakan elemen q  contohnya  tidak dapat dituliskan dalam bentuk . elemen r yang bukan merupakan elemen q disebut bilangan tak rasional atau sering disebut bilangan irrasional (irrational numbers). Jadi bilangan irrasional adalah bilangan yang tak rasional atau bilangan yang tidak dapat dituliskan sebagai hasil bagi dua buah bilangan bulat.

Teorema 2.1.6. Tidak ada elemen r Î q sedemikian sehingga r2 = 2.
Bukti
Andaikan r Î q sedemikian sehingga r2 = 2. Karena r Î q, maka r dapat dinotasikan dalam bentuk  dengan p, q Î z  dan q ≠ 0 tidak mempunyai faktor persekutuan selain 1, sehingga diperoleh
Karena 2q2 genap maka p2 genap. Akibatnya p genap (sebab jika p ganjil dan andaikan p = 2k – 1 untuk k Π n, maka p2 = (2k – 1)2 = 4k2 – 4k + 1 = 2(2k2 – 2k) + 1 yang berarti p2 ganjil. Jadi p haruslah genap). Karena p2 = 2q2 dan p genap maka q ganjil (sebab jika q genap, maka faktor persekutuan dari p dan q bukan 1. Jadi q haruslah ganjil). Sehingga diperoleh,
          p2 = 2q2 Û (2k)2 = 2 q2
                        Û 4k2 = 2q2
                        Û 2k2 = q2
Karena q2 = 2k2,  maka q2 genap. Akibatnya q genap. Hal ini kontradiksi bahwa q ganjil. Jadi pengandaian salah, haruslah Tidak ada elemen r Î q sedemikian sehingga r2 = 2.

Tidak ada komentar:

Posting Komentar