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) = 1² + 2² + 3² + ¼ + n².

(1)     Landasan Dasar: P(1) = 1². 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 n₀ÎN dan P(n) suatu pernyataan untuk setiap bilangan asli n³n₀, berlaku:

(1)     P(n₀) benar

(2)     Untuk setiap k³n₀, jika P(k) benar maka P(k + 1) benar.

Maka P(n) benar untuk setiap n³n₀.

Contoh 2:

Diketahui a, bÎR. Buktikan a – b adalah faktor dari aⁿ – bⁿ untuk setiap nÎN.

Bukti

Bukti

Misal P(n) = aⁿ – bⁿ.

(1)     Landasan Dasar: P(1) = a – b. karena a – b merupakan faktor dari P(1) = a – b, maka P(1) benar

(2)     Hipotesis Induksi : asumsikan P(k) benar, yakni : a – b adalah faktor dari a^k – b^k.

Akan dibuktikan P(k + 1) benar

Secara jelas a – b faktor b^k(a – b) dan  berdasarkan Hipotesis Induksi a – b adalah faktor dari    a^k – b^k, maka a – b adalah faktor dari a(a^k– b^k). Jadi terbukti a – b adalah faktor dari a^k – b^k, sehinggga P(k + 1) benar

Maka menurut PIM, P(n) benar untuk setiap nÎN.

Aksioma 1.3 (Prinsip Induksi Matematika Versi kedua)

Misal n₀ÎN dan P(n) suatu pernyataan untuk setiap bilangan asli n³n₀, berlaku:

(3)     P(n₀) benar

(4)     Untuk setiap k³n₀, jika P(k) benar maka P(k + 1) benar.

Maka P(n) benar untuk setiap n³n₀.

Contoh 3:

Buktikan 2ⁿ > 2n + 1 untuk setiap n ³ 3, nÎN.

Bukti

(1)     Landasan Dasar: n = 3, 2³ = 8 > 7 = 2×3+1. Karena 2³ > 2×3+1 maka n = 3 benar

(2)     Hipotesis Induksi : asumsikan n = k  benar, yakni 2^k > 2k + 1 untuk setiap k ³ 3

Akan dibuktikan  n = k + 1 benar

2^{k + 1} = 2×2^k > 2(2k + 1) = 4k + 2 = 2k + (2k + 2) > 1 + (2k + 2) = 2(k + 1) + 1

 Jadi terbukti 2^{k + 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

(A₁)      Hukum Komutatif Penjumlahan. a + b = b + a,  " a, b Î R.

(A₂)      Hukum Asosiatif Penjumlahan.(a + b) + c  = a +(b + c),   " a, b, c Î R.

(A₃)    Eksistensi Bilangan Nol (Unsur Identitas Penjumlahan). Terdapat 0ÎR yang memenuhi a + 0 = 0 + a = a,  " a Î R.

(A₄)      Eksistensi Unsur Negatif (Invers Penjumlahan). Untuk setiap a Î R  terdapat −a Î R  sedemikian sehingga a +( −a) = ( −a) + a = 0.

(M₁)     Hukum Komutatif Perkalian. a×b = b×a,  " a, b Î R.

(M₂)     Hukum Asosiatif Perkalian. (a×b)×c  = a×(b×c),   " a, b, c Î R.

(M₃)   Eksistensi Bilangan Unit 1 (Unsur Identitas Perkalian). Terdapat 1ÎR dan 1 berlainan dengan 0 sedemikian sehingga a×1 = 1×a = a,  " a Î R.

(M₄)     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 A₃)

  = z + (a + (−a))              (sifat A₄)

  = (z + a)+ (−a)               (sifat A₂)

  = a + (−a)                      (Hipotesis)

  = 0                                 (sifat A₃)

(b)   u = u×1                              (sifat M₃)

  = u×                      (sifat M₄)

  =                     (sifat M₂)

  =                            (Hipotesis)

  = 1                                 (sifat M₄)

(c)    a×0 = a×0 + 0                     (sifat A₃)

      = a×0 + (a + (−a))       (sifat A₄)

      = (a×0 + a) + (−a)       (sifat A₂)

      = (a×0 + a×1) + (−a)     (sifat M₃)

      = (a×(0 + 1)) + (−a)     (sifat D)

      = (a×1) + (−a)              (sifat A₃)

      = a + (−a)                   (sifat M₃)

      = 0                              (sifat A₃)

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 A₃)

      = (−1)×a + (a + (−a))          (sifat A₄)

      = ((−1)×a + a) + (−a)          (sifat A₂)

      = ((−1)×a + 1×a) + (−a)       (sifat M₃)

      =  ((−1) + 1)×a) + (−a)       (sifat D)

      = 0×a + (−a)                       (sifat A₄)

     = a×0 + (−a)                        (sifat A₁)

     = 0 + (−a)                           (Teorema 2.1.1(c))

     = −a                                    (sifat A₃)

(b)      –(−a) = –(−a) + 0                         (sifat A₃)

     = –(−a) + (−a + a)              (sifat A₄)

     = (–(−a) + (−a)) + a           (sifat A₂)

     = 0 + a                                (sifat A₄)

     = a                                      (sifat A₃)

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 b₁ dan b₂  elemen R  yang memenuhi a + b₁ = 0 dan a + b₂ = 0 akan dibuktikan b₁ = b₂.

a + b₁ = 0, maka b₁ = −a dan a + b₂ = 0, maka b₂ = −a. karena b₁ = −a dan b₂ = −a, maka b₁ = b₂.

(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 a – b = 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 a² untuk aa, a³ untuk (a²)a, dan secara umum aⁿ⁺¹ untuk (aⁿ)a untuk n Î n. lebih lanjut a¹ lambang untuk a; jika a ≠ 0, maka dapat ditulis a⁰ = 1; a⁻¹ lambang dari ; dan  a⁻ⁿ 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 r² = 2.

Bukti

Andaikan r Î q sedemikian sehingga r² = 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 2q² genap maka p² genap. Akibatnya p genap (sebab jika p ganjil dan andaikan p = 2k – 1 untuk k Π n, maka p² = (2k – 1)² = 4k² – 4k + 1 = 2(2k² – 2k) + 1 yang berarti p² ganjil. Jadi p haruslah genap). Karena p² = 2q² 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,

          p² = 2q² Û (2k)² = 2 q²

                        Û 4k² = 2q²

                        Û 2k² = q²

Karena q² = 2k²,  maka q² genap. Akibatnya q genap. Hal ini kontradiksi bahwa q ganjil. Jadi pengandaian salah, haruslah Tidak ada elemen r Î q sedemikian sehingga r² = 2.