MAKALAH
INDUKSI MATEMATIKA
Dosen Pengampu : M. Syawahid, M. Pd.
OLEH
NAMA NIM
1.
ANDARI
FILNA JESIKA 160103068
2.
NUR’AINI 160103069
FAKULTAS ILMU TARBIYAH DAN KEGURUAN
JURUSAN TADRIS MATEMATIKA
UNIVERSITAS ISLAM NEGERI MATARAM
2017
KATA PENGANTAR
Puji syukur kami panjatkan kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya
sehingga kami dapat menyelesaikan makalah yang
berjudul “Induksi Matematika”, yang mana makalah ini diajukan untuk
memenuhi salah satu tugas mata kuliah Matematika Diskrit.
Adapun yang kami bahas dalam makalah ini
yaitu pengertian dari induksi matematika, prinsip – prinsip induksi matematika,
dan bentuk umum dari induksi matematika.
Kami menyadari bahwa dalam
pembuatan makalah ini masih banyak kekurangan-kekurangannya, hal ini disebabkan
keterbatasan pengetahuan, waktu, serta sumber yang kami miliki. Oleh karena itu kritik dan saran yang sifatnya membangun sangat kami harapkan untuk perbaikan penyusunan selanjutnya.
Akhirnya kami berharap semoga makalah ini dapat bermanfaat bagi kami khususnya dan bagi para pembaca pada umumnya.
Mataram, 23 Oktober 2017
DAFTAR
ISI
Ø KATA
PENGANTAR.………………………………………………...............................1
Ø DAFTAR
ISI….……………………………………………………………......................2
Ø BAB
I PENDAHULUAN
1.1 Latar
Belakang Masalah ……………….…………………………………......3
1.2 Rumusan
Masalah…………………………………………………………......3
1.3 Tujuan
Pembelajaran …………………………………………………………3
Ø BAB
II PEMBAHASAN
2.1 Pengertian Induksi Matematika………...….……….…………………………5
2.2 Prinsip – prinsip Induksi
Matematika……………………………………...….5
2.3 Bentuk Induksi Secara
Umum……………………………………………….10
Ø BAB III PENUTUP
3.1 Kesimpulan ………………………………………………………………….13
3.2 Saran ………………………………………………………………………...13
Ø DAFTAR PUSTAKA
BAB I
PENDAHULUAN
1.1 Latar Belakang Masalah
Induksi
matematika merupakan teknik pembuktian yang baku didalam matematika. Melalui
induksi matematika kita dapat mengurangi langkah pembuktian bahwa semua
bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah
langkah terbatas Di dalam matematika, sebuah proposisi atau pernyataan tidak
hanya sekedar ditulis. Kita juga juga harus mengerti apa yang menyebabkan
proposisi tersebut benar yaitu bukti (proof).
Contoh
, kita ingin menemukan rumus jumlah dari n
buah bilangan ganjil positif yang pertama. Misalnya untuk n = 1, 2, 3, 4, 5, kita mengamati jumlah n bilangan ganjil positif pertama adalah
n
= 1 => 1 = 1
n
= 2 => 1 + 3 =4
n
= 3 => 1 + 3 + 5 =9
n
= 4 => 1 + 3 + 5 +7 = 16
n
= 5 => 1 + 3 + 5 + 7 + 9 = 25
Dari
nilai-nilai penjumlahan itu kita menduga bahwa jumlah n buah bilangan ganjil positif pertama adalah n2. Kita perlu membuktikan bahwa perkiraan kita tersebut
benar jika memang itu faktanya. Bagaimana cara membuktikannya dengan induksi
matematik ?
1.2 Rumusan Masalah
1. Apa
pengertian dari Induksi Matematika ?
2. Apa
saja prinsip – prinsip Induksi Matematika dan bagaimana langkah – langkah
melakukan pembuktian serta contoh penggunaan prinsip Induksi Matematika ?
3. Bagaimana
bentuk umum dari Induksi Matematika ?
1.3 Tujuan Penulisan
1. Untuk
mengetahui definisi dari Induksi Matematika.
2. Untuk
mengetahui apa saja prinsip – prinsip dalam Induksi Matematika.
3. Dapat
membuktikan suatu pernyataan dengan menggunakan induksi matematika.
4. Dapat
mengetahui contoh penggunaan prinsip Induksi Matematika.
5. Mengetahui
bentuk umum dari Induksi Matematika.
BAB II
PEMBAHASAN
2.1 Pengertian
Induksi Matematika
Induksi Matematika merupakan pembuktian
deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi
lengkap sering dipergunakan untuk pernyataan – pernyataan yang menyangkut
bilangan asli. Induksi matematika juga dapat dikatakan sebagai metode
pembuktian untuk proposisi perihal bilangan bulat. Pembuktian cara induksi
matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua
bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan sifat itu
benar untuk n = 1 (atau S(1) adalah benar), kemudian ditunjukkan
bahwa bila sifat itu benar untuk n = k (bila S(k) benar) menyebabkan
sifat itu benar untuk n = k + 1 (atau S(k + 1) benar.
Sebuah
deskripsi tidak formal dari induksi matematika dapat diilustrasikan dengan
mengacu kepada efek sekuensial dari jatuhnya domino.
2.2 Prinsip
– prinsip Induksi Matematika
·
Prinsip
Induksi Sederhana
Prinsip induksi sederhana berbunyi sebagai berikut :
Misalkan
p(n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk
semua bilangan bulat positif n. untuk membuktikan proposisi ini, kita hanya
perlu membuktikan bahwa:
1.
P(1) benar, dan
2.
Jika p(n) benar, maka p(n+1) juga benar untuk
setiap n
1.
Sehingga
p(n) benar untuk semua bilangan bulat positif n.
Langkah 1 dinamakan basis induksi, sedangkan
langkah 2 dinamakan langkah induksi. Langkah induksi berisi asumsi (andaian)
yang menyatakn bahwa p(n) benar. Asumsi tersebut dinamakan
hipotesis induksi. Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n)
benar untuk semua bilangan bulat positif n.
Contoh :
1. Gunakan induksi matematik untuk membuktikan
bahwa jumlah n buah bilangan ganjil
positif pertama adalah n2.
Penyelesaian :
Misalkan p(n) adalah proposisi yang menyatakan
bahwa jumlah n buah bilangan ganjil
positif pertama adalah n2
i.
Basis induksi: p(1) benar, karena
jumlah satu buah bilangan ganjil positif pertama adalah 12 = 1.
ii.
Langkah
induksi: misalkan p(n) benar, yaitu asumsikan bahwa
1 + 3 + 5 + … + ( 2n – 1) = n2
adalah benar (hipotesis induksi) [catatlah
bahwa bilangan ganjil positif ke-n
adalah (2n - 1)]
Kita harus memperlihatkan bahwa p(n
+ 1) juga benar, yaitu
1
+ 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2
Hal ini dapat kita tunjukkan sebagai berikut
1
+ 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] +
(2n + 1)
= n2 + (2n + 1 )
= n2 + 2n + 1
= (n + 1)2
Karena langkah basis dan langkah induksi
keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n2.
2. Buktikan dengan induksi matematika , n
, 1 + 7
+ 13 + … + (6n – 5) = n(3n
– 2).
Penyelesaian :
Andaikan bahwa p(n) menyatakan proposisi
bahwa untuk n
1, jumlah n bilangann bulat positif pertama
adalah n(3n – 2) , yaitu 1 + 7 + 13 + … + (6n – 5) = n(3n – 2). Kita harus membuktikan kebenaran proposisi ini dengan dua langkah
induksi sebagai berikut:
(i) Basis
induksi : p(1) benar, karena untuk n
= 1 kita peroleh
1 = 1(3.1 – 2)
= 1 (1)
=1
(ii) Langkah
induksi : Misalkan p(n)
benar, yaitu mengasumsikan bahwa
1 + 7 + 13 + … + (6n – 5) = n(3n – 2)
adalah benar (hipotesis induksi). Kita harus memperlihatkan bahwa p(n
+ 1) juga benar, yaitu
1 + 7 + 13 + … + (6n – 5) + (6n + 1) = (n + 1)(3n + 1)
Untuk membuktikan ini, tunjukkan bahwa
1 + 7 + 13 + … + (6n – 5) + (6n + 1) = n(3n – 2) + (6n
+ 1)
= (3n2
– 2n) + (6n
+ 1)
= 3n2 – 2n + 6n + 1
= 3n2 + 4n + 1
= (n
+ 1)(3n + 1)
Karena langkah (i) dan (ii) telah dibuktikan
benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n
1, 1 + 7 + 13 + … + (6n – 5) = n(3n – 2).
·
Prinsip
Induksi yang Dirampatkan
Kadang-kadang kita ingin membuktikan bahwa
pernyataan p(n) benar untuk semua bilangan bulat
0, jadi
tidak hanya bilangan bulat yang dimulai dari 1 saja. Prinsip induksi sederhana
dapat dirampatkan (generalized) untuk
menunjukkan hal ini sebagai berikut :
Misalkan
p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa
p(n) benar untuk semua bilangan bulat n
n0.
Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:
1.
p(n0) benar, dan
2.
jika p(n) benar maka p(n + 1) benar untuk
setiap n
n0,
sehingga p(n) benar untuk semua bilangan bulat n
n0.
Contoh :
Untuk semua bilangan bulat-negatif n, buktikan dengan induksi matematik
bahwa 20 + 21 + 22 + … + 2n = 2n+1 – 1
Penyelesaian :
Misalkan p(n) adalah proposisi
bahwa untuk semua bilangan bulat tidak-negatif n, 20 + 21 + 22 + … + 2n =
2n+1 -1
i.
Basis induksi : p(0)
benar, karena untuk n = 0 (bilangan
bulat tidak negatif pertama), kita peroleh:
20 = 1 = 20+1
– 1
= 21 – 1
= 2 – 1
= 1
ii. Langkah
induksi: Misalkan p(n)
benar, yaitu proposisi
20 + 21 +
22 + … + 2n
= 2n+1 –
1
diasumsikan benar (hipotesis induksi). Kita
harus menunjukkan bahwa p(n + 1) juga benar, yaitu
20
+ 21 + 22 + … + 2n + 2n+1
= 2(n+1)+1 – 1
Hal ini kita tunjukkan sebagai berikut :
20
+ 21 + 22 + … + 2n + 2n+1
= (20 + 21 + 22 + … + 2n) + 2n+1
= (2n+1
– 1) + 2n+1 (dari
hipotesis induksi)
= (2n+1 + 2n+1)
– 1
= (2 . 2n+1) – 1
= 2n+2 – 1
= 2(n+1)+1 – 1
Karena langkah i dan ii keduanya telah
diperlihatkan benar, maka untuk semua bilangan bulat tidak-negatif n, terbukti bahwa 20 + 21
+ 22 + … + 2n
= 2n+1 –
1
·
Prinsip
Induksi Kuat
Kadang-kadang versi induksi yang lebih kuat
diperlukan untuk membuktikan pernyataan mengenai bilangan bulat. Versi induksi
yang lebih kuat adalah sebagai berikut:
Misalkan p(n) adalah pernyataan
perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua
bilangan bulat n
. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa :
1.
p(n0)
benar, dan
2.
jika p (n0), p (n0+1), …,
p(n) benar, maka p(n+1) juga benar untuk setiap bilangan bulat n
, sehingga p(n) benar untuk semua bilangan bulat n
.
Catatlah bahwa versi induksi yang lebih kuat
ini mirip dengan induksi sederhana, kecuali bahwa pada langkah 2 kita mengambi
hipotesis induksi yang lebih kuat bahwa semua pernyataan p(1), p(2), … p(n)
adalah benar daripada hipotesis yang menyatakan bahwa p(n) benar (pada induksi
sederhana). Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang
sama meskipun memberlakukan andaian yang lebih banyak.
Contoh :
Bilangan bulat positif disebut prima jika dan
hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri.
Kita ingin membuktikan bahwa setiap bilangan bulat positif n(n
≥2)
dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
Buktikan dengan prinsip induksi kuat.
Penyelesaian
:
Misalkan p(n) adalah proposisi bahwa setiap
bilangan positif n(n ≥2)
dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
i.
Basis
Induksi : p(2) benar, karena 2 sendiri adalah bilangan prima dan disini 2
dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya
sendiri.
ii.
Langkah
Induksi : Misalkan p(n) benar, yaitu
asumsikan bahwa bilangan 2, 3, … , n
dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima (hipotesis
induksi). Kita perlu menunjukkan bahwa p(n+1)
benar, yaitu n + 1 juga dapat
dinyatakan sebagai perkalian bilangan prima. Hal ini ditunjukkan sebagai
berikut :
Jika n + 1 sendiri
bilngan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih
bilangan prima. Jika n + 1 bukan
bilangan prima, maka terdapat bilngan bulat positif a yang membagi habis n +
1 tanpa sisa. Dengan kata lain,
(n + 1)/a = b atau (n + 1) = ab
yang dalam hal ini, 2 ≤ a ≤ b
≤ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan
prima. Ini berarti, n + 1 jelas dapat
dinyatakan sebagai perkalian bilngan prima, karena n + 1 = ab
Karena
langkah (i) dan (ii) sudah ditunjukkan benar, maka terbukti bahwa setiap
bilangan bulat positif n (n
≥
2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
2.3 Bentuk
Induksi Secara Umum
Bentuk Induksi secara umum adalah
mungkin membuat bentuk umum metode induksi sehingga ia dapat diterapkan tidak
hanya untu pembuktian proposisi yang menyangkut himpunan bilngan bulat positif,
tetapi juga pembuktian yang menyangkut himpunan obyek yang lebih umum.
Syaratnya, himpunan obyek tersebut harus mempunyai keterurutan dan mempunyai elemen
kecil.
Definisi : Relasi
biner “<“ pada himpunan X
dikatakan terurut dengan baik (atau himpunan X dikatakan terurut dengan baik dengan “<“) bila memiliki
properti berikut :
i.
Diberikan x, y, z
X, jika x < y dan y < z, maka x
< z
ii.
Diberikan x, y
X.
Salah satu dari kemungkinan ini benar : x
< y atau y < x atau x = y
iii.
Jika A adalah himpunan bagian tidak
kosong dari X, terdapat elemen x
A
sedemikian sehingga x ≤ y untuk semua y
A. Dengan kata lain, setiap himpunan bagian
tidak kosong dari X mengandung “elemen terkecil”.
Bentuk induksi secara umum dapat
dituliskan sebagai berikut :
Misalkan X terurut dengan baik oleh
“ < Ë®, dan p(x) adalah pernyataan perihal elemen x dari X. kita ingin
membuktikan bahwa p(x) benar untuk semua x
X. Untuk membuktikan ini, kita hanya perlu
menunjukkan bahwa :
1.
p(x0) benar, yang dalam
hal ini x0 adalah elemn terkecil di dalam X, dan
2.
jika p(y) benar untuk y < x, maka
p(x) juga benar untuk setiap x > x0 di dalam X,
sehingga p(x) benar untuk semua x
X
Contoh :
Tinjau barisan bilangan yang didefinisikan sebagai berikut :
0 jika m = 0 dan n = 0
Sm,n = Sm – 1 ,n +
1 jika n = 0
Sm,n – 1 + 1 jika
n ≠ 0
Sebagai contoh ,
S0,0 = 0 S1,0 = S0,0 + 1 = 0 + 1 = 1
S0,1 = S0,0 + 1 = 1 S1,1 = S1,0 + 1 = 1 + 1 = 2
S2,0 = S1,0 + 1 = 2 S2,1 = S2,0 + 1 = 2 + 1 = 3
Buktikan dengan induksi matematika bahwa untuk pasangan
tidak negative m dan n, Sm,n
= m+ n
Penyelesaian :
i.
Basis induksi : Karena (0,0)
adalah elemen terkecil di dalam X, maka S0,0 = 0 + 0 = 0. Ini benar dari definisi S0,0.
ii.
Langkah induksi : Buktikan
untuk semua (m,n) > (0,0) di dalam
X bahwa jika Sm´,n´ =
m´ + n´ benar untuk semua (m´, n´ ) < (m , n) maka Sm,n =
m + n juga benar. Andaikan bahwa Sm´,n´ = m´ + n´ benar untuk semua (m´,
n´). Ini adalah hipotesis induksi. Kita perlu menunjukkan bahwa Sm,n = m + n, baik untuk n = 0
atau n ≠ 0.
Kasus 1 : Jika n = 0 dari
definisi Sm,n = Sm – 1 ,n +1.
Karena (m – 1 , n) < (m , n), maka
dari hipotesis induksi,
Sm
– 1 ,n = (m – 1) + n sehingga Sm,n
= Sm – 1 ,n + 1 = (m
– 1) + n + 1 = m + n
Kasus 2 : Jika n ≠ 0 dari
definisi Sm,n = Sm,n – 1
+ 1. Karena (m, n – 1) < (m, n), maka dari hipotesis induksi,
Sm,n
– 1 = m + (n – 1) sehingga Sm,n = Sm,n –
1 + 1 = m + (n – 1) + 1 = m + n
Karena langkah (i) dan (ii) sudah dibuktikan benar, maka terbukti
bahwa untuk pasangan tidak negatif m
dan n, Sm,n = m + n.
BAB III
PENUTUP
3.1 Kesimpulan
Dari uraian tentang induksi matematika diatas dapat disimpulkan
bahwa Induksi Matematika merupakan pembuktian
deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi
lengkap sering dipergunakan untuk pernyataan – pernyataan yang menyangkut
bilangan asli. Induksi matematika dapat juga dikatakan sebagai suatu metode
pembuktian untuk proposisi bilangan bulat.
Beberapa prinsip yang digunakan
untuk membuktikan induksi matematika yaitu prinsip induksi sederhana, prinsip
induksi yang dirapatkan dan prinsip induksi yang kuat. Bentuk Induksi secara
umum adalah mungkin membuat bentuk umum metode induksi sehingga ia dapat
diterapkan tidak hanya untu pembuktian proposisi yang menyangkut himpunan
bilngan bulat positif, tetapi juga pembuktian yang menyangkut himpunan obyek
yang lebih umum. Syaratnya, himpunan obyek tersebut harus mempunyai keterurutan
dan mempunyai elemen kecil.
3.2
Saran
Dalam penulisan makalah ini masih
banyak kekurangan sehingga tidak sesuai dengan keinginan pembaca, untuk itu
saran sangat kami harapkan agar penulisan makalah selanjutnya kekurangan-kekurangan
tersebut dapat penulis perbaiki.
DAFTAR PUSTAKA
Munir,
Rinaldi. 2014. Matematika Diskrit.
Bandung : Informatika.
Ayres,
Frank & Philip A. Schmidt. 2004. Matematika Universitas. Jakarta :
Erlangga.
