Kel-1 - Induksi Matematika Dan Keterbagian [PDF]

Citation preview

INDUKSI MATEMATIKA DAN KETERBAGIAN Disusun untuk Memenuhi Salah Satu Tugas Mata Kuliah Teori Bilangan Dosen Pengampu: Dr. Agus Maman Abadi, S.Si., M.Si.



Disusun oleh: Ummi Santria



16709251008



Nira Arsoetar



16709251018



PROGRAM PASCASARJANA PENDIDIKAN MATEMATIKA UNIVERSITAS NEGERI YOGYAKARTA 2017



A. INDUKSI MATEMATIKA Induksi matematika merupakan suatu teknik untuk membuktikan suatu pernyataan matematika apakah benar atau salah. Seringkali kita hanya menerima saja pernyataan atau argumen matematika, tanpa mengetahui kebenaran pernyataan tersebut. Oleh karena itu kita membutuhkan suatu metode untuk membuktikan kebenaran pernyataan matematika yang disebut induksi matematika. Khususnya pernyataan yang terkait dengan bilangan asli dan bilangan bulat positif. Induksi matematika juga merupakan suatu cara yang berguna untuk membuktikan berbagai identitas atau rumus. Prinsip induksi matematika adalah cara yang berguna untuk membuktikan kebenaran / keabsahan mengenai bilangan bulat. Pembuktian dengan induksi matematika dapat kita lakukan dengan dua langkah (Rosen: 2011) 1. Basis step menunjukkan pernyataan itu bernilai benar untuk bilangan 1 2. Induction step menunjukkan bahwa pernyataan itu benar untuk n + 1



Well-Ordering Principle (WOP) Sebagai suatu metode, induksi matematika harus dapat dibuktikan apakah valid atau tidak. Untuk itu diperkenalkan terlebih dulu dengan salah satu aksioma tentang himpunan bilangan bulat. (Burton, 2010:1) WOP. Setiap himpunan tak kosong S dari bilangan bulat non-negatif memuat paling sedikit unsur; yaitu, ada beberapa bilangan bulat a dalam S sedemikian sehingga a ≤ b, untuk b anggota S. Contoh : himpunan bilangan bulat positif genap Teorema 1.5 .(Rosen, K. H. 2011: 23) Prinsip Induksi Matematika. Suatu himpunan bilangan bulat positif yang memuat memuat



maka juga memuat bilangan bulat



dan yang bersifat bahwa jika



, maka haruslah himpunan itu merupakan



himpunan semua bilangan bulat positif. Jika:



(a) (b)



berakibat



Bukti. Misalkan S adalah himpunan bilangan bulat positif yang berisi bilangan bulat 1, dan bilangan bulat k + 1 yang bagaimanapun juga berisi k. Asumsikan (dengan pembuktian 1



kontradiksi) bahwa S bukan himpunan seluruh bilangan bulat positif. Oleh karena itu, ada beberapa bilangan bulat positif yang tidak terkandung dalam S. Karena himpunan bilangan bulat positif tidak terkandung dalam S adalah bukan himpunan kosong, ada setidaknya bilangan bulat positif k yang tidak berada di S. Dengan catatan k ≠ 1, karena 1 ada dalam S. Sekarang, karena k > 1 (karena tidak ada bilangan positif k dengan k < 1), bilangan bulat k – 1 adalah bilangan bulat positif yang lebih kecil dari k, dan pastinya juga berada dalam S. Tapi karena S berisi k – 1, maka pasti juga berisi (k – 1) + 1 = k, yang mana ini merupakan suatu kontradiksi, sebagaimana k seharusnya bilangan positif terkecil tidak berada di S. Ini menunjukkan bahwa S pasti merupakan himpunan seluruh bilangan bulat positif.



Contoh 1 Menggunakan induksi matematika untuk menunjukkan bahwa: ∑ Basis Step: ∑ Inductive Step: mengasumsikan hipotesis induksi untuk ∑



maka,



, menggunakan hipotesis induksi, kita mempunyai:



∑



∑



Karena dari langkah basis dan langkah induksi keduanya telah terbukti benar, maka pernyataan diatas benar.



Contoh 2: Buktikan



untuk setiap



Basis step: P1=1 P2=2 dan seterusnya.



2



bilangan asli



Untuk membuktikan pernyataan itu, perhatikan bahwa P1 adalah benar. Kemudian misalkan bahwa bahwa



adalah benar, selanjutnya harus dibuktikan adalah benar.



Sehingga dari kedua langkah tersebut benar. Hal ini membuktikan bahwa pernyataan diatas benar.



Prinsip Kedua Induksi Matematika Teorema 1.6. (Rosen, K. H. 2011 : 25) Prinsip Induksi Matematika Kuat Suatu himpunan bilangan bulat positif yang memuat yang bersifat, jika memuat



dan setiap bilangan bulat positif



maka juga memuat bilangan bulat



, maka



himpunan itu merupakan himpunan semua bilangan bulat positif.



Bukti. Misalkan T adalah himpunan bilangan bulat positif yang memuat 1untuk setiap bilangan bulat positif n, jika berisi 1, 2, ... n, maka juga berisi n + 1. Misalkan S adalah himpunan seluruh bilangan bulat sedemikian hingga semua bilangan bulat positif yang kurang arau sama dengan n berada dalam S. Jadi, bilangan 1 berada dalam S, dan dengan hipotesis ini, kita melihat bahwa jika n berada dalam S, maka n + 1 berada dalam S. Oleh karena itu, dengan prinsip induksi matematika, S pasti himpunan seluruh bilangn bulat positif, karena S adalah himpuan bagian dari T.



3



SOAL DAN JAWABAN



Latihan 1.3 (Rosen, K. H. 2011: 27) 1. Dengan menggunakan induksi matematika buktikan bahwa



berlaku untuk semua



n bilangan bulat. Jawaban: Untuk setiap n bilangan bulat positif. Basis step: Dengan



Maka,



Terbukti benar untuk Inductive step: Asumsikan



Dengan



Maka,



Terbukti benar untuk Sehingga, dengan



Maka,



Berdasarkan WOP (Well Ordering Principle), karena



maka



.



Karena kedua langkah dari langkah basis dan langkah induksi terbukti benar, maka pernyataan



berlaku untuk semua n bilangan bulat adalah benar.



2. Diduga sebuah rumus penjumlahan bilangan bulat genap positif n pertama. Buktikan kebenaran/keabsahannya menggunakan induksi matematika. Jawaban: Penjumlahan n bilangan bulat positif, yaitu: ∑



4



Basis step: untuk



kita mempunyai



adalah benar bahwa,



Inductive step: Sekarang asumsikan



, maka



Kemudian mempunyai



adalah benar. , maka:



∑



∑



Dengan kedua langkah tersebut, karena



maka,



. Sehingga terbukti benar pernyataan rumus penjumlahan bilangan bulat genap positif n pertama. 3. Gunakan induksi matematika untuk membuktikan bahwa, ∑



untuk setiap n bilangan bulat positif.



Jawaban: Basis step: Pembuktian untuk n = 1 kita mempunyai



adalah benar bahwa,



, yang mana nilai terkecil dari k = 1 Inductive step: Kemudian asumsikan bahwa menjadi



, maka benar. Kemudian membuktikan mempunyai



maka:



5



,



∑



∑



(



)



4. Diduga formula untuk: ∑ Dari nilai penjumlahan ini untuk n bilangan bulat terkecil. Buktikan bahwa dugaan benar dengan menggunakan induksi matematika. Jawaban: (1) Untuk n = 1 ∑ (2) Untuk n = k ∑ (3) Untuk n = k+1 ∑



=



∑



=



=



Sehingga terbukti bahwa ∑



6



5. Diduga sebuah rumus untuk An dimana A = (



). Buktikan dugaan ini dengan



menggunakan induksi matematika. Jawaban: Diduga bahwa An = ( A3 = A2A = (



) maka A = (



), A2 = (



),



) dan seterusnya. Untuk membuktikannya dengan menggunakan



induksi matematika Basis step: pertama-tama lihat langkah basis bahwa n = 1 maka, An = (



)



A=(



) benar.



Inductive step: Kemudian asumsi bahwa An = ( An+1 = An A = (



)(



)=(



) adalah benar maka,



)



Karena dua langkah tersebut terbukti benar, maka pernyataan rumus untuk An dimana A = (



) adalah benar.



6. Dengan menggunakan induksi matematika terbukti bahwa: ∑ Untuk setiap n bilangan bulat positif. Jawaban: Basis step: Dengan n = 1 ∑



Inductive step: Asumsikan ∑ Dengan n = k



7



∑



∑



∑



Sehingga, dengan n = k + 1 ∑



∑



∑



Untuk membuktikan induksi matematika adalah valid, maka berdasarkan well-order principle benar dengan k < k + 1 bahwa: benar. 7. Dengan menggunakan induksi matematika terbukti bahwa: ∑ Untuk setiap n bilangan bulat positif. Jawaban:



8



maka pernyataan diatas



Basis step: Dengan n = 1 ∑



Terbukti benar untuk n=1 Inductive step: Asumsikan∑ Dengan n = k ∑ ∑



∑



Terbukti benar untuk n=k Sehingga, dengan n = k + 1 ∑



∑



∑



9



[



]



[



]



[



]



[



]



Untuk membuktikan induksi matematika adalah valid, maka berdasarkan well-order principle benar dengan k < k + 1 bahwa:



Maka pernyataan diatas benar. 8. Gunakan induksi matematika untuk membuktikan bahwa ∑ berlaku untuk setiap n bilangan bulat positif. Jawaban: Basis step: Dengan n = 1 ∑



[



]



[ ]



Terbukti benar untuk n=1 Inductive step: Asumsikan ∑



*



+



Dengan n = k



10



∑



[



]



∑



[



]



[



]



∑



[



]



Sehingga, dengan n = k + 1 ∑



∑



[



∑



]



[



]



[



]



[



]



[



]



[



[



]



]



11



Untuk membuktikan induksi matematika adalah valid, maka berdasarkan well-order principle benar dengan k < k + 1 bahwa: [



]



[



]



9. Gunakan induksi matematika untuk membuktikan bahwa ∑ berlaku untuk setiap n bilangan bulat positif. Jawaban: Basis step: Untuk langkah basis n = 1 kita mempunyai



adalah benar. Inductive step: Kemudian asumsikan bahwa n = k, maka benar bahwa Kemudian mempunyai n = k + 1, maka: ∑



∑



10. Misalkan Hn penjumlahan ke-n dari Hn = ∑



Dengan menggunakan induksi



matematika terbukti bahwa: ∑



[



Untuk setiap n bilangan bulat positif. Jawaban: 12



]



Basis step: Dengan n = 1 ∑



[ [ [



]



] ]



Terbukti benar untuk n=1 Inductive step: Asumsikan ∑



[



]



Dengan n = k ∑



[



]



∑



[



]



[



]



∑



[



]



Sehingga, dengan n = k + 1 ∑ ∑ [



∑ ]



13



Untuk membuktikan induksi matematika adalah valid, maka berdasarkan well-order principle benar dengan n = k