Modul perkuliahan

Induksi Matematika

Induksi matematika merupakan suatu metode yang penting dalam pembuktian dan sering digunakan dalam berbagai buku. Induksi matematika merupakan suatu metode yang digunakan untuk membangun kevalidan pernyataan yang diberikan dalam istilah-istilah bilangan asli (N). Walaupun kegunaannya agak dibatasi dalam konteks yang agak khusus, namun keberadaannya merupakan suatu alat yang sangat diperlukan dalam cabang-cabang matematika.

Dianggap bahwa kita sudah mengenal bilangan asli N = { 1,2,3, ... }, baik operasi biasa pada penjumlahan dan perkalian dan arti dari suatu bilangan asli yang satu lebih kecil dari yang lain. Juga dianggap kita sudah mengenal dengan sifat-sifat dasar dari bilangan asli berikut ini:

Sifat terurut baik dari N menyatakan bahwa setiap subset tidak kosong dari N mempunyai unsur terkecil. Sifat yang lebih mendetail dari sifat terurut baik bilangan asli adalah sebagai berikut:

Teorema 1.1

Jika S adalah subset dari N dan jika S , maka terdapat suatu m S sedemikian sehingga m k, untuk setiap k S.

Prinsip Induksi Matematika

Misal S subset dari N, maka berlaku sifat-sifat:

1. 
   1 S
   
2. 
   jika k S, maka (k+1) S, dan S = N
   

Bukti:

Anggaplah berlaku sebaliknya S N. Maka himpunan N – S tidak kosong dan selanjutnya dengan sifat terurut dengan baik ia akan memuat suatu unsur terkecil. Misal m adalah unsur terkecil dari N-S. Karena 1 S, maka menurut hipotesis (1), kita tahu bahwa m 1. Selanjutnya untuk m > 1 mengakibatkan bahwa m – 1 juga merupakan bilangan asli, Karena m – 1 < m dan karena m adalah unsur terkecil dari N sedemikian sehingga m S, ia mestilah merupakan kasus bahwa m-1 S.

Selanjutnya kita gunakan hipotesis (2) untuk unsur ke ke k = m – 1 dan menyimpulkan bahwa k+1 = (m-1) + 1 = m S. Kesimpulan ini bertentangan dengan pernyataan bahwa m S. Karena m diperoleh dengan mengasumsikan bahwa N-S tidak kosong, hal ini juga bertentangan dengan kesimpulan bahwa N-S kosong. Dengan demikian kita telah menunjukkan bawa S = N.

Bentuk lain dari prinsip Induksi Matematika dinyatakan sebagai berikut:

Untuk setiap n N, misalkan P(n) merupakan suatu pernyataan tentang n, anggaplah bahwa:

1. 
   P(1) benar
   
2. 
   P(k) benar maka P(k+1) benar,
   

Maka P(n) adalah benar untuk setiap n N.

Contoh

Untuk setiap n N, buktikan rumus penjumlahan berikut dengan induksi matematika.

1. 
   1 + 2 + 3 + 4 + 5 + ..... + n =
   

Jawab

Untuk n = 1 1 = , sehingga 1 S,

Andaikan untuk n = k diasumsikan bahwa k S, sehingga

1 + 2 + 3 + 4 + 5 + ..... k =

Selanjutnya akan dibuktikan bahwa untuk n = k + 1 benar, maka

1 + 2 + 3 + 4 + 5 + ..... + k + (k+1) =

, karena n = k+1, maka:

Karena rumus ini terpenuhi untuk n = k+1, kita menyimpulkan bahwa k+1 S. Jadi dari Induksi matematika terpenuhi. Oleh karena itu dengan prinsip induksi matematika kita menyimpulkan bahwa S = N dan rumus tersebut adalah benar untuk semua n N.

• 1.3 Prinsip Urutan

Prinsip adalah aturan atau sifat yang digunakan sebagai dasar atau landasan dalam uraian yang berkaitan dengan bukti sesuatu. Prinsip dapat diambil dari definisi, aksioma, atau dalil-dalil yang “dimunculkan” kembali untuk digunakan pada bagian lain suatu konsep yang memerlukan. Diantara prinsip dalam matematika adalah prinsip urutan (Well Ordering Principle).

Prinsip urutan berkaitan dengan kepositipan dan ketaksamaan antara bilangan-bilangan real. Sebagaimana halnya dalam Struktur Aljabar dari sistem bilangan real. Cara yang dapat dilakukan untuk melakukan sifat urutan adalah mengidentifikasi suatu subset khusus dari R dengan menggunakan gagasan “kepositipan”.

1. Definisi 1.1

Misal P subset R dan P . Untuk selanjutnya P disebut bilangan real positip kuat, maka berlaku sifat-sifat berikut ini:

1. 
   Jika a,b P, maka (a+b) P
   
2. 
   Jika a,b P, maka (a.b) P
   
3. 
   Jika a R, maka tepat dari salah satu yang berikut dipenuhi
   

a P, a = 0, -a P

Dua sifat yang pertama menjamin kesesuaian dari urutan dengan operasi penjumlahan dan perkalian secara berurutan. Sifat (3) biasanya disebut sifat trikotomi karena membagi R menjadi 3 jenis unsur yang berbeda. Dinyatakan bahwa himpunan {-a: a P} dari bilangan real negatip tidak mempunyai unsur persekutuan dengan P, dan selanjutnya himpunan R merupakan gabungan dari tiga himpunan yang saling asing.

Definisi 1.2

1. 
   Jika a P, kita mengatakan bahwa a adalah suatu bilangan real positip kuat (strictly positip) dan dituliskan dengan a > 0, Jika a P {0}, maka a disebut bilangan real tidak negatip dan dituliskan dalam bentuk a 0.
   
2. 
   Jika -a P, kita mengatakan bahwa a adalah suatu bilangan real negatip kuat (strictly negatip) dan dituliskan dalam bentuk a < 0, Jika -a P {0}, maka a disebut bilangan real tidak positip dan dituliskan dalam bentuk a 0.
   
3. 
   Jika a, b R dan jika a – b P maka dituliskan dalam bentuk a > b atau b < a.
   
4. 
   Jika a,b R dan jika a – b P {0}, maka a b atau b a
   

Untuk kesepakatan bersama kita akan menuliskan a < b < c yang berarti a < b dan b < c

Demikian juga jika a b dan b c maka a b c. demikian seterusnya.

Berikut ini beberapa teorema yang berkaitan dengan prinsip keterurutan

Teorema 1.2

Misalkan a,b,c R

Jika a > b dan b > c maka a > c

Tepat dari salah satu pernyataan berikut ini dipenuhi

a > b, a = b , a < b

Jika a b dan b a maka a = b

Bukti

1. 
   a > b maka menurut definisi a – b > 0 atau a – b P
   

b > c maka menurut definisi b – c > 0 atau b – c P

Karena a – b P dan b – c P maka menurut definisi diperoleh

(a-b) + (b-c) P.

Sehingga a – c P atau a > c

1. 
   Dengan sifat trikotomi dalam definisi, maka tepat salah satu dari yang berikut mungkin terjadi
   

a – b > 0, atau a-b = 0, atau –(a-b) = 0 sehingga

a > b atau a = b atau a < b.

Jika a b, maka a – b 0, sehingga dari bukti (b) kita dapatkan a – b P atau b-a P yakni a > b atau b > a. Dalam kasus lainnya salah satu dari hipotesisi tersebut kontradiksi. Jadi haruslah a = b.

Teorema 1.3

Jika a R dan a 0, maka a² > 0

1 > 0

Jika n N, maka n > 0

Bukti

1. 
   Dengan sifat trikotomi jika a 0, maka a P atau –a P. Jika a P maka dengan definisi kita mempunyai a² = a, untuk a P. Dengan cara yang sama Jika -a P maka dengan definisi sebelumnya diperoleh bentuk (-a)² = (-a)(-a) P. Dari teorema sebelumnya berakibat bahwa:
   

(-a)(-a) = ((-1)a)((-1)a) = (-1)(-1)a² = a². Akibatnya bahwa a² P. Jadi kita simpulkan bahwa jika a 0, maka a² > 0.

1. 
   Karena 1 = (1)², menurut bukti di atas akan menyebabkan bahwa
   

1 > 0.

1. 
   Kita dapat menggunakan induksi matematika untuk membuktikan pernyataan ini.
   

Pernyataan tersebut benar untuk n = 1 yakni 1 > 0. Selanjutnya kita anggap benar untuk n = k, dengan k bilangan asli.

Karena 1 > 0 dan 1 P, maka k + 1 P, sehingga pernyataan di atas benar adanya dengan menggunakan definisi sebelumnya.

2.