Menara Hanoi adalah permainan "tiga menara". Pada menara

Teorema terbukti benar menggunakan induksi matematika dengan basis induksi pada n=1 dan langkah induksi untuk n=k+1.

Pembahasan

Untuk membuktikan teorema bahwa jumlah langkah minimum yang diperlukan untuk memindahkan n piringan dalam permainan Menara Hanoi adalah 2^n - 1 langkah menggunakan induksi matematika, kita ikuti langkah-langkah berikut:

1. Basis Induksi (n=1):
Untuk memindahkan 1 piringan dari menara A ke menara C, hanya diperlukan 1 langkah. Menggunakan rumus: 2^1 - 1 = 2 - 1 = 1 langkah. Basis induksi terpenuhi.

2. Asumsi Induksi:
Asumsikan bahwa untuk memindahkan k piringan, diperlukan paling sedikit 2^k - 1 langkah.

3. Langkah Induksi (n=k+1):
Kita perlu membuktikan bahwa untuk memindahkan k+1 piringan, diperlukan paling sedikit 2^(k+1) - 1 langkah.

Langkah-langkah untuk memindahkan k+1 piringan adalah:
   a. Pindahkan k piringan teratas dari menara A ke menara B (menggunakan menara C sebagai bantu), ini memerlukan 2^k - 1 langkah (berdasarkan asumsi induksi).
   b. Pindahkan piringan terbesar (piringan ke-k+1) dari menara A ke menara C. Ini memerlukan 1 langkah.
   c. Pindahkan k piringan dari menara B ke menara C (menggunakan menara A sebagai bantu), ini juga memerlukan 2^k - 1 langkah.

Jumlah total langkah = (2^k - 1) + 1 + (2^k - 1)
Jumlah total langkah = 2^k + 2^k - 1
Jumlah total langkah = 2 * 2^k - 1
Jumlah total langkah = 2^(k+1) - 1

Karena langkah induksi terbukti benar, maka teorema tersebut benar untuk semua n ≥ 1.