INDUKSI MATEMATIKA

INDUKSI MATEMATIKA

Induksi matematika merupakan materi yang menjadi perluasan dari logika matematika. Logika matematika sendiri mempelajari pernyataan yang bisa bernilai benar atau salah, ekivalen atau ingkaran sebuah pernyataan, dan juga berisi penarikan kesimpulan.

Induksi matematika menjadi sebuah metode pembuktian secara deduktif yang digunakan untuk membuktikan suatu pernyataan benar atau salah. Dimana merupakan suatu proses atau aktivitas berpikir untuk menarik kesimpulan berdasarkan pada kebenaran pernyataan yang berlaku secara umum sehingga pada pernyataan khusus atau tertentu juga bisa berlaku benar. Dalam induksi matematika ini, variabel dari suatu perumusan dibuktikan sebagai anggota dari himpunan bilangan asli.

Ada tiga langkah dalam induksi matematika yang diperlukan untuk membuktikan suatu rumus atau pernyataan. Langkah-langkah tersebut adalah :

1.    Membuktikan bahwa rumus atau pernyataan tersebut benar untuk n = 1.

2.    Mengasumsikan bahwa rumus atau pernyataan tersebut benar untuk n = k.

3.    Membuktikan bahwa rumus atau pernyataan tersebut benar untuk n = k + 1.

Untuk menerapkan induksi matematika, kita harus bisa menyatakan pernyataan P (k + 1) ke dalam pernyataan P(k) yang diberikan. Untuk meyatakan persamaan P (k + 1), substitusikan kuantitas k + 1  kedalam pernyataan P(k).

METODE PEMBUKTIAN LANGSUNG DAN TIDAK LANGSUNG

A.   METODE PEMBUKTIAN LANGSUNG

Dalam kamus besar bahasa Indonesia dijelaskan bahwa bukti langsung adalah bukti sesuai fakta tanpa kesimpulan ataupun anggapan, bukti ini menjelaskan suatu fakta atau materi yang dipersoalkan; suatu bukti dapat dikatakan langsung jika didukung dengan pihak yang mempunyai pengetahuan nyata mengenai persoalan yang bersangkutan dengan menyaksikannya sendiri, contoh untuk membuktikan adanya uang suap (kickbacks), bukti langsung yang diperlukan adalah check dari pemasok. (glosarium)

Sedangkan dalam matematika bukti langsung adalah pembuktian yang berawal dari premis pada teorema kemudian menghasilkan kesimpulan.

Pertama yang harus kita ketahui adalah bahwa kebanyakan teorema berbentuk pernyataan kondisional, yakni dalam bentuk jika-maka (p→q) atau bisa dibawa ke bentuk tersebut. Untuk membuktikan pernyataan seperti ini, perhatikan table kebenaran berikut (B untuk benar dan S untuk salah).

dari tabel ini kita lihat bahwa kalau p salah, implikasi p→q akan selalu benar. Dengan kata lain, yang perlu kita lihat adalah saat p bernilai benar. Apabila kita mengasumsikan p benar lalu didapat hasil q benar, bukti kita selesai. untuk contoh selanjutnya kita akan membutuhkan definisi.

Definisi  Bilangan bulat n adalah bilangan genap jika terdapat bilangan bulat k sedemikian sehingga n=2k dan nn adalah bilangan ganjil jika terdapat bilangan bulat k sedemikian sehingga n=2k+1. Dua buah bilangan bulat dikatakan sama paritasnya jika keduanya ganjil atau keduanya genap, dan berbeda paritas jika salah satunya ganjil dan yang lain genap.

Berikutnya kita akan mencoba membuktikan sebuah proposisi.

Contoh

Dalam contoh ini kita akan mulai dari kerangka pembuktian, lalu mengisi kekosongan yang ada di antaranya. Yang akan kita buktikan adalah kuadrat dari bilangan ganjil pasti bilangan ganjil juga.
 

Proposisi Jika n adalah bilangan ganjil maka n­² adalah bilangan ganjil.
Bukti
Asumsikan n ganjil.



sehingga n² ganjil.

Bagian pertama dan terakhir sudah terisi. Sekarang tinggal mengisi bagian tengah dari buktinya (sebenernya ini bagian yang paling susah). Yang akan kita gunakan di sini adalah definisi di awal tadi dan beberapa pengoperasian yang diperlukan.

Proposisi Jika n adalah bilangan ganjil maka n² adalah bilangan ganjil.
Bukti
Asumsikan n ganjil.
Karena n ganjil, maka terdapat bilangan bulat k sedemikian sehingga n=2k+1



sehingga n² ganjil.

Sekarang yang menjadi tujuan kita adalah n² merupakan bilangan ganjil, yg kita butuhkah adalah definisi. n² ganjil jika dapat dinyatakan ke dalam bentuk sebelumnya. Jadi, sebelum baris terakhir kita tambahkan hal ini sehingga menjadi

Proposisi Jika n adalah bilangan ganjil maka n² adalah bilangan ganjil.
Bukti
Asumsikan n ganjil.
Karena n ganjil, maka terdapat bilangan bulat k sedemikian sehingga n=2k+1


maka n²=2m+1 untuk suatu bilangan bulat m
sehingga n² ganjil.

Hampir selesai. hanya sedikit lagi yang perlu di isi. Kita bisa mengisi kekosongan ini dengan melakukan penguadratan pada n agar dihasilkan n².

Proposisi Jika n adalah bilangan ganjil maka n² adalah bilangan ganjil.
Bukti
Asumsikan n ganjil.
Karena nn ganjil, maka terdapat bilangan bulat k sedemikian sehingga n=2k+1
dengan menguadratkan diperoleh

n²=(2k+1)²

=4k²+4k+1

=2(2k²+2k)+1

maka n²=2m+1 untuk suatu bilangan bulat m=2k²+2k
sehingga n² ganjil.  

Bukti selesai.

B.   Metode pembuktian tidak langsung

Bukti tidak langsung adalah bukti yang bergantung pada inferensi untuk menghubungkannya ke sebuah kesimpulan fakta, seperti sidik jari di tempat kejadian perkara. Sebaliknya, bukti langsung mendukung kebenaran dari asersi secara langsung, tanpa perlu bukti tambahan atau inferensi apapun.

Bukti tidak langsung memungkinkan lebih dari satu penjelasan. Bagian-bagian yang berbeda dari bukti tidak langsung mungkin diperlukan, sehingga masing-masing bagian saling menguatkan kesimpulan yang ditarik. Bersama-sama, bagian-bagian itu mungkin lebih kuat mendukung satu inferensi tertentu di antara yang lain. (Wikipedia bahasa Indonesia, ensiklopedia bebas)

Seperti apa pembuktian tidak langsung dalam matematika. Untuk memahaminya perhatikan ulasan berikut :

Pada pembahasan sebelumnya kita telah membuktikan salah satu proposisi, yaitu

Untuk n bilangan bulat, Jika n ganjil, maka n²  ganjil.

Tapi bagaimana dengan pernyataan sebaliknya? Yakni pernyataan

Untuk n bilangan bulat, Jika n² ganjil maka n ganjil

Kita lihat beberapa kemungkinan 3²=9 ganjil maka 3 ganjil, (−5)²=25 ganjil maka −5 ganjil, dan 7²=49 maka 7 ganjil. Sepertinya proposisi benar, akan kita coba buktikan dengan bukti langsung.

Asumsikan n² genap, maka terdapat bilangan bulat k sedemikian sehingga n²=2k+1. Sekarang kita menemui jalan buntu. Akan kita apa kan? Bagaimana caranya menunjukkan n juga ganjil? Yang kita ketahui hanyalah  kayanya tidak membawa ke mana-mana. Kita akan mencoba bukti tak langsung.

Pertama perhatikan table berikut

Perhatikan bahwa p→q dan ∼q→∼p memiliki nilai kebenaran yang sama untuk tiap kemungkinan. Jadi, ketimbang membuktikan p→q secara langsung, lebih baik kita buktikan ∼q→∼p dengan demikian, p→q juga akan terbukti.
Pembuktian ini disebut bukti dengan kontraposisi. Bukti dengan kontraposisi merupakan bukti tak langsung, yaitu bukti yang tidak mulai dari premis dari suatu teorema namun berakhir pada kesimpulan teorema tersebut.

Untuk membuktikan yang pertama tadi, cukup buktikan

Untuk bilangan asli n, jika n genap maka n² genap

Kita akan buktikan di sini

Proposisi Jika n genap maka n² genap.

Bukti Asumsikan n genap.  Maka ada bilangan bulat k sedemikian sehingga n=2k. Dengan menguadratkan diperoleh

n²=(2k)²=4k²=2(2k²)

Dengan kata lain, n²=2m untuk suatu bilangan bulat m.

Sehingga n² genap.