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-bilangan asli.

Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan bahwa 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).

Buktikan bahwa jumlah n bilangan ganjil pertama adalah n2.

Persamaan yang perlu dibuktikan:

S(n) = 1 + 3 + 5 +----- + 2n - 1 = n ^ 2

Langkah pembuktian pertama:
untuk \ n = 1, benar bahwa \ S(1) = 1 ^ 2 = 1

Langkah pembuktian kedua:
andaikan benar untuk n = k, yaitu

S(k) = 1 + 3 + 5 +------ + 2k - 1 = k ^ 2, maka akan dibuktikan benar pula untuk n = k + 1, yaitu

S(k + 1) = 1 + 3 + 5 + ------ + 2k - 1 + 2(k + 1) - 1 =(k + 1) ^ 2

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa k2 = 1 + 3 + 5 + ... + 2k − 1 sesuai dengan pengandaian awal

[1 + 3 + 5 + ----- + 2k - 1] + 2(k + 1) - 1 = k ^ 2 + 2(k + 1) - 1

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

\ k ^ 2 + 2k + 1 = (k + 1) ^ 2, ingat bahwa (k + 1)2 = k2 + 2k + 1
\ (k + 1) ^ 2 = (k + 1) ^ 2 (terbukti benar)

Kesimpulan:
Jadi, S(n) benar untuk semua bilangan asli karena memenuhi kedua langkah pembuktian.

Soal

4ⁿ – 1 habis dibagi 3 untuk setiap bilangan bulat positif n >= 1.

Jawab:

Langkah 1 (Basic Step)

S(1) = benar

S(n) = S(1)

n = 1

jika U = 4ⁿ – 1, maka nilai U berubah menjadi

U = 4¹ – 1

U = 3

Dari soal “habis dibagi 3” maka dari langkah 1 “benar” karena

U/3 = 3/3 = 1

Langkah 2 (Induktif Step)

S(k) = benar

S(n) = S(k)

n = k

Jadi, U = 4ⁿ – 1

U = 4^k – 1 …………………………………………………………….1

Lalu

S (k +1) = benar

S(n) = S (k + 1)

n = k + 1

maka;

U = 4ⁿ – 1

U = 4^k+1 – 1

U = 4¹ x 4^k – 1

U = 4 x 4^k – 1 …………………………………………………………..2

UJI KEBENARAN

S(k) = 4^k – 1 ………………1

S(k + 1) = 4 x 4^k – 1 ……….2

Dari kedua persamaan maka didapat nilai:

4 x 4^k - 4^k = 3 x 4^k ……………3

gabungkan persamaan 3 + 1

3 x 4^k + 4^k – 1 ………………4

maka,

UJI KEBENARAN I dengan cara menggunakan persamaan 3 yang nilainya habis dibagi 3, artinya nilai harus bernilai 1.

3 x 4^k / 3 = 1 x 4^k

jadi, uji kebenaran I benar karena hasilnya bernilai 1

UJI KEBENARAN II dengan cara menjumlahkan persamaan 3 + 1 yang hasilnya bernilai sama dengan persamaan 2

persamaan 3 + 1 :

3 x 4^k + 4^k – 1

4 x 4^k – 1

jadi, uji kebenaran II benar karena hasilnya sama dengan persamaan II

Langkah 3 (kesimpulan)

Dari semua percobaan yang dilakukan, langkah 1 sampai langkah ke -2 bernilai benar. Maka kesimpulan akhir adalah BENAR.

sumber disini