Page 14 - Matematika Diskrit Decision Making Based

(i) Basis Induksi

Untuk teka-teki susun gambar dengan satu potongan, tidak diperlukan langkah apa-apa
untuk memecahkan teka-teki itu.

(ii) Langkah Induksi

Misalkan pernyataan bahwa untuk teka-teki dengan n potongan (n = 1, 2, 3, …) diperlukan

sejumlah n-1 langkah untuk memecahkan teka-teki itu adalah benar (hipotesa induksi). Kita

harus membuktikan bahwa untuk n+1 potongan diperlukan n langkah.

Bagilah n+1 potongan menjadi dua blok, satu dengan n1 potongan dan satu lagi dengan n2
potongan, dan n1 + n2 = n + 1. Untuk langkah terakhir yang memecahkan teka-teki ini, dua

blok disatukan, sehingga membentuk satu blok besar. Menurut hipotesis induksi, diperlukan

n1-1 langah untuk menyatukan blok yang satu dan n2-1 langkah untuk menyatukan blok
lain. Digabungkan dengan langkah terakhir yang menyatukan kedua blok tersebut, maka

banyaknya langkah adalah:

(n1-1)+(n2-1)+1 langkah terakhir = (n1+ n2)-2+1=n+1-1=n.

Karena langkah (i) dan (ii) sudah diperlihatkan benar, maka
terbukti bahwa suatu teka-teki susun gambar denga n

potongan selalu diperlukan n-1 langkah untuk memecahkan.

Matematika Diskrit 10 Induksi Matematika
Ebook Decision Making Prinsip Induksi Kuat