Menara Hanoi adalah permainan "tiga menara". Pada menara

Menara Hanoi adalah permainan "tiga menara". Pada menara paling kiri terdapat tumpukan n piringan. Kita hanya boleh memindahkan satu demi satu piringan, tetapi tidak boleh menumpuk piringan yang lebih besar di atas piringan yang lebih kecil. Tujuan permainan adalah memindahkan semua piringan ke salah satu dari dua menara yang lain. Pertanyaannya: Berapa banyak langkah minimum yang diperlukan untuk memindahkan semua piringan ke n menara yarg lain? Teorema berikut ini menjawab pertanyaan di atas. Untuk memindahkan n piringan, diperlukan paling sedikit 2^n-1 langkah. Buktikan teorema tersebut dengan menggunakan induksi matematika.