INDUKSI MATEMATIKA


BAB I
PENDAHULUAN
A.  Latar Belakang
Apakah suatu formula untuk jumlah dari n bilangan bulat positif ganjil pertama? Jumlah dari n bilangan bulat ganjil positif pertama untuk n = 1, 2, 3, 4, 5 adalah
1 = 1,
1 + 3 = 4,
1 + 3 + 5 = 9,
1 + 3 + 5 + 7 = 16,
1 + 3 + 5 + 7 + 9 = 25.
Dari nilai-nilai ini layak untuk membawa jumlah dari n bilangan bulat ganjil positif pertama adalah n2. Kita perlu suatu metode untuk membuktikan bahwa perkiraan itu benar.
Induksi matematis adalah suatu teknik pembuktian penting secara ekstrem dapat digunakan untuk membuktikan pernyataan tegas tipe ini. Seperti yang kita lihat dalam bagian ini dan dalam bab berikutnya, induksi matematis digunakan secara ekstensif untuk membuktikan hasil tentang berbagai objek diskret luas. Misalnya, induksi matematis digunakan untuk membuktikan hasil tentang kompleksitas algoritma, pembetulan tipe program komputer tertentu, teorema tentang graf dan pohon, dan juga suatu range luas dari identitas dan pertidaksamaan.
Dalam bagian ini kita akan menggambarkan bagaimana induksi matematis dapat digunakan dan mengapa induksi matematis merupakan suatu teknik pembuktian valid. Ini secara ekstrim penting dengan mencatat bahwa induksi matematis hanya dapat digunakan untuk membuktikan hasil yang diperoleh suatu cara lain. Ini bukan merupakan alat untuk menemukan formula atau teorema.
B.  Rumusan Masalah
1.      Pengenalan Induksi Matematika
2.      Tahapan induksi matematika dan contoh-contohnya.



BAB II
PEMBAHASAN
A.      Pengenalan Induksi Matematika
Induksi matematika ditemukan pertama kali oleh seorang metematikawan asal prancis yang bernama Blaise Pascal (1623-1662). Induksi matematika merupakan teknik yang dikembangkan untuk membuktikan pernyataan dan merupakan pembuktian deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli.
Pengertian lain yaitu suatu cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya.

B.       Tahapan Induksi Matematika

Ø  Basis Step             : Tunjukkan bahwa S(1) benar
Ø  Inductive Step      : Asumsikan S(k) benar, Akan dibuktikan  S(k) ® S(k+1) benar
Ø  Conclusion            : S(n) adalah benar untuk setiap n bilangan integer   Positif
Langkah-langkah pembuktian :
  1. Pembuktian rumus atau teorema untuk suatu nilai bilangan bulat positif n, biasanya nilai yang terkecil .
  2. Bukti bahwa jika rumus atau teorema yang dimaksud adalah benar untuk n=k, dimana k adalah suatu bilanganbulat positif, maka rumus tersebut juga benar untuk n=k+1.
  3. Kesimpulan bahwa rumus yang dimaksud adalah benar untuk semua nilai n yang lebih besar daripada bilangan bulat yang telah dibuktikan kebenaranya dilangkah pertama.

Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli
pertama, yaitu 1+2+:::+n, adalah sama dengan       .Untuk membuktikan
bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah-langkah
yang dilakukan adalah sebagai berikut:
1.      Cara Biasa / Basis
Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas sekali bahwa jumlah 1 bilangan asli pertama adalah  = 1. Jadi pernyataan tersebut adalah benar untuk n = 1.
Untuk n =1, Ruas kiri                 = 1
Sedangkan Ruas kanan               =   = 1
Kerena ruas kiri = ruas kanan, maka persamaan benar untuk n=1.
2.      Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka
pernyataan tersebut juga benar untuk n = k+1.
3.      Dengan induksi matematika dapat disimpulkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n
C.       Contoh-Contoh Soal
Contoh 1:
Gunakan induksi matematika untuk membuktikan bahwa 5n− 1 dapat dibagi 4 untuk setiap n = 1, 2,....
1.           Akan ditunjukkan bahwa 5n − 1 habis dibagi 4 untuk n = 1
 51− 1 = 5− 1 = 4 è habis dibagi 4.
2.      Asumsikan bahwa 5n− 1 habis dibagi 4 untuk n = k, juga untuk n= k+ 1,
(5)k+1− 1 = 5.5k− 1
= (1 + 4).5k− 1
= 5k +4.5k−1
= (5k− 1) + 4.5k
(n=1) = (51-1)+4.51 = (5-1)+4.5 = 4+20 =24 è kelipatan 4 èbernilai 6
(n=2) = (52-1)+4.52 = (25-1)+4.25= 24+100=124 è bernilai 31

Contoh 2:
Gunakan induksi matematika untuk membuktikan bahwa n3+2n adalah kelipatan 3, untuk semua bilangan asli
1.      Akan ditunjukkan bahwa n3+2n  adalah kelipatan 3 untuk n = 1.
13+2.1=1+2=3 è kelipatan 3 è bernilai 1
2.      Asumsikan bahwa n3+2n adalah kelipatan 3 untuk n = k  juga untuk n= k+ 1
n3 +2n = (k+1)3+2(k+1)
= (k3+3k2+3k+1)+ 2k+2
= k3+3k2+5k+3
(n=1) = 13+3.12+5.1+3 = 12 è adalah kelipatan 3 è bernilai 4
(n=2)= 23+3.22+5.2+3 = 8+12+10+3 = 33 è kelipatan 3 è 10
Contoh 3 :
Gunakan induksi matematis untuk membuktikan bahwa n3 – n dapat dibagi dengan 3 apabila n adalah suatu bilangan bulat positif.
Solusi: Untuk mengonstruksi bukti, misalkan P(n) menyatakan proposisi: “n3 – n dapat dibagi dengan oleh 3.”
Langkah Dasar: P(1) benar, karena 13 – 1 = 0 dapat dibagi dengan 3.
Langkah Induktif: Asumsikan bahwa P(n) benar; yaitu, n3 – n dapat dibagi dengan 3. Kita harus menunjukkan bahwa (n + 1)3 – (n + 1) dapat dibagi dengan 3. Ingat bahwa
(n + 1)3 – (n + 1) = (n3 + 3n2 + 3n + 1) – (n + 1)
= (n3 – n) + 3(n2 + n).
Karena kedua suku dalam jumlah ini dapat dibagi dengan 3 (pertama dengan asumsi dari langkah induktif, dan kedua karena jumlah itu merupakan 3 kali suatu bilangan bulat), selanjutnya (n + 1)3 – (n + 1) juga dapat dibagi dengan 3. Ini melengkapi langkah induktif. Sehingga, dengan prinsip induksi matematis, n3 – n dapat dibagi oleh 3 apabila n adalah suatu bilangan bulat positif.


Contoh 4 :
Buktikan 1+3+5+...+(2n-1)= n2
1.      Rumusnya benar untuk n=1 karena 1=12
2.      Asumsikan bahwa rumus tersebut benar untuk n=k ; yaitu kita misalkan bahwa
1+3+5 +...+(2k-1)=k2
maka rumus tersebut benar untuk n=k+1 (Catatan bahwa bilangan bulat positif ganjil ke-n adalah (2k – 1), karena bilangan bulat ini diperoleh dengan menambahkan 2 suatu total dari k – 1 kali dengan 1.); yaitu bahwa
1+3+5+...+(2k-1)+(2k+1)=(k+1)2
Dengan menambahkan (2k+1) pada kedua ruas, Sehingga mengasumsikan bahwa P(k) benar, ini mengikuti
1+3 + 5 +…+(2k – 1) + (2k + 1) = 1 + 3 +…+ (2k – 1) + (2k + 1)
=  k2 + (2k + 1)
=  k2 + 2k + 1
=  (k + 1)2.
Ini menunjukkan bahwa P(n + 1) mengikuti dari P(n). Catatan bahwa kita menggunakan hipotesis induktif P(n) dalam kesamaan kedua dengan menempatkan kembali jumlah dari n bilangan bulat positif ganjil pertama dengan n2.
Karena P(1) benar dan implikasi P(n) P(n +1) benar untuk semua bilangan bulat positif n, prinsip induksi matematis menunjukkan bahwa P(n) benar untuk semua bilangan bulat positif n.
Contoh 5 :
Gunakan induksi matematis untuk menunjukkan bahwa
1 + 2 + 22 + … + 2n = 2n + 1 – 1
untuk semua bilangan bulat nonnegatif n. Solusi: Misalkan P(n) adalah proposisi bahwa formula ini tepat untuk bilangan bulat n.
Langkah Dasar: P(0) benar karena 20 = 1 = 21 – 1.
Langkah Induktif: Asumsikan bahwa P(n) benar. Untuk menyelesaikan langkah induktif dengan menggunakan asumsi ini, harus ditunjukkan bahwa P(n + 1) benar, yaitu,
1 + 2 + 22 + … + 2n + 2n +1 = 2(n + 1)+1 – 1 = 2n + 2 – 1.
Dengan menggunakan hipotesis induktif P(n), diperoleh
1 + 2 + 22 + … + 2n + 2n +1 = (1 + 2 + 22 + … + 2n) + 2n +1
= (2n + 1 – 1) + 2n + 1
= 2. 2n + 1 – 1
= 2n + 2 – 1.
Langkah induktif terakhir ini, yang melengkapi bukti itu.
Contoh  6:
Gunakan induksi matematis untuk membuktikan pertidaksamaan n < 2n untuk semua bilangan bulat positif n.
Solusi: Misalkan P(n) adalah proposisi “n < 2n”.
Langkah Dasar: P(1) benar, karena 1< 21 = 2.
Langkah Induktif: Asumsikan bahwa P(n) benar untuk bilangan bulat positif n. Yakni, asumsikan bahwa k < 2k. Kita perlu menunjukkan bahwa P(k + 1) benar. Yakni, kita perlu untuk menunjukkan bahwa k +1< 2k + 1. Dengan menambahkan 1 untuk kedua sisi dari k < 2k, dan kemudian mencatat bahwa 1< 2k, memberikan
k + 1< 2k + 1≤ 2k + 2k = 2k + 1
Kita telah menunjukkan bahwa P(k +1) benar, yaitu, k + 1< 2k + 1, didasarkan pada asumsi bahwa P(n) benar. Langkah induktif lengkap.
Jadi, dengan prinsip induksi matematis, telah ditunjukkan bahwa k<2k benar untuk semua bilangan bulat positif.
Contoh 7 :
Gunakan induksi matematika untuk membuktikan bahwa
n!≥ 2n−1
untuk setiap n= 1,2,....
1.         Akan ditunjukkan bahwa n!≥ 2n−1  benar untuk n = 1. Jelas sekali
bahwa  1!  21−1
 1   20
 1  1

2.         Asumsikan bahwa n! ≥ 2n−1 adalah benar untuk n=k. Akan ditunjukkan bahwa n!≥ 2n−1 juga benar untuk n=k + 1, yaitu (k + 1) ≥ 2(k+1)−1.
(k+1)!  = (k+1)(k!)
≥(k + 1)(2k−1)
 ( 2k-1)(2k-1)
≥2.2k−1
= 21+(k−1)
= 2(k+1)−1
Terbukti bahwa (k+1) ≥ 2(k+1)−1.
Karena Langkah Dasar dan Langkah  Induktif terbukti, maka dapat disimpulkan bahwa
n!≥ 2n−1
untuk setiap n = 1, 2,....
Contoh 8:
Buktikan n2  2n +1 untuk  3
Karena 32 = 9  2(3) +1=7, maka formula tersebut benar untuk n=3
Asumsikan n2 2n+1 maka:
(n+1)2=n2+2n+1 2n+1+2n+1=2n+2+2n 2n+2+1=2(n+1)+1
Sehingga formula tersebut benar untuk n+1. Menurut prinsip P induksi, formula tersebut berlaku untuk n 3
Contoh 9:
Buktikan 2n  n2 untuk n 4
Karena 24=16=42, maka  formula tersebut benar n=4. Asumsikan 2n  n2 dan juga n2  2n+1 di dapat:
2n+1 = 2(2n) 2(n2) = n2 +n2  n2 +2n +1=(n+1)2
                 Formula tersebut benar untuk n+1. Menurut prinsip induksi, formula tersebut bermakna untuk n 4.

BAB III
PENUTUP
Induksi matematis digunakan untuk membuktikan hasil tentang kompleksitas algoritma, pembetulan tipe program komputer tertentu, teorema tentang graf dan pohon, dan juga suatu range luas dari identitas dan pertidaksamaan.
Induksi Matematika juga merupakan suatu teknik yang dikembangkan untuk membuktikan pernyataan tertentu berlaku untuk setiap bilangan asli. Selain itu Induksi Matematika juga digunakan untuk mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu.
Dalam penyelesaian contoh-contoh soal induksi matematika, dapat diselesaikan dengan 3 cara, yaitu, persamaan, pertidaksamaan, dan pernyataan.

DAFTAR PUSTAKA
R. Johsonbaugh.1997.Matematika Diskrit. PT Prenhallindo:Jakarta
Ayres Frank, Schmidt Philp. 2004 edisi ke 3. Teori dan soal-soal Matematika Universitas . Erlangga: jakarta
Lipschutz seymour, Lars Lipson Marc. 2001. Slemba Tektika: Jakarta
http://www.google.co.id/search?q=persamaan+dan+pertidaksamaan+induksi+matematika&hl=id&client=firefox-a&rls=org.mozilla:id:official&prmd=imvnsb&ei=Oa_LTpWtEI33mAXo4PGoDQ&start=20&sa=N&biw=1366&bih=634
http://elnicovengeance.wordpress.com/2011/07/02/induksi-matematika/
http://mazterchez.blogspot.com/2010/03/induksi-matematika.html
http://www.scribd.com/doc/12692356/Prinsip-Induksi-Matematika

Komentar

Posting Komentar