5 0 599 KB
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