INDUKSI MATEMATIKA (Matematika Diskret)

Induksi Matematika digunakan untuk mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu. Suatu teknik yang dikembangkan untuk membuktikan pernyataan. Perhatikan kasus berikut:
“Beberapa orang Amerika mengusulkan agar pemerintah menghentikan pengeluaran koin 1 sen (1¢), karena selain nilainya terlalu kecil, harga-harga barang yang sama atau lebih dari 4 ¢ dapat dibayar dengan koin 2 ¢ atau 5 ¢ (tanpa memerlukan koin 1 ¢)”

Secara formal dapat dikatakan:
“Untuk setiap bilangan bulat n≥4, n sen dapat diperoleh dengan koin 2¢ dan 5¢”


Perhatikan tabel berikut:




Baris ke-k dalam tabel tersebut adalah untuk mendapatkan (k+3) ¢ dengan menggunakan koin 2 ¢ dan 5 ¢.

Untuk melanjutkan pembuatan tabel berikutnya haruslah dibuat aturan bagaimana mengisi baris ke-(k+1), dengan menggunakan pola baris ke-k.

Ada 2 kemungkinan:
1. Ada koin 5 ¢ yang digunakan untuk menyusun
atau
2. Semua koinnya adalah 2 ¢

Jika ada 5 ¢ yang digunakan untuk menyusun k-koin, maka untuk menyusun (k+1) koin:

- gantilah koin 5 ¢ dengan 3 buah koin 2 ¢, sehingga jumlah seluruhnya (k+1) koin.
atau
- gantilah 2 buah koin 2 ¢ yang nilainya 4 ¢, dengan 5 ¢, sehingga seluruhnya (k+1) koin

Dari contoh tersebut:

Tunjukkan bahwa P(4) benar
dengan kata lain: 4 ¢ dapat disusun dengan koin 2 ¢ dan 5 ¢

Tunjukkan kebenaran P(k+1) bisa didapatkan dengan diketahuinya kebenaran P(k)

dengan kata lain:

misalkan k ¢ dapat disusun dengan koin 2 ¢ dan 5 ¢, maka ditunjukkan bagaimana (k+1) ¢ didapatkan dari koin 2 ¢ dan 5 ¢

Disimpulkan:
Misalkan P(n) adalah pernyataan yang yang didefinisikan dalam bilangan bulat n dan a adalah bilangan bulat tetap, maka:
P(a) benar
Jika P(k) benar, maka P(k+1) benar, untuk k ≥ a

Sehingga: P(n) benar untuk semua n ≥ a
Langkah 1 disebut Basis
Langkah 2 disebut Langkah Induksi

Contoh Kasus:
Buktikan bahwa: