Page 7 - TUGAS UAS MD_NURUL HUDA_212110026
P. 7
Berdasarkan hipotesis induksi untuk menyelesaikan puzzle dengan
potongan diperlukan - 1 langkah dan potongan diperlukan - 1
langkah. Ditambah dengan satu langkah terakhir untuk menyatukan dan
, maka diperoleh :
( - 1) + ( - 1) + 1 = ( + ) – 2 + 1 = (n + 1) – 1 =n
Jadi p(n +1) benar untuk semua n ≥ 1.
Kesimpulan :
Karena p(1) dan p(n + 1) benar untuk semua n ≥ 1 maka p(n) benar untuk
setiap bilangan bulat positif n. Dengan kata lain, untuk menyelesaikan
puzzle dengan n potongan diperlukan n – 1 langkah.
4
