Pada Menara Hanoi banyaknya pemindahan untuk sebuah piringan ke menara tujuannya adalah

Barisan rekursif yang telah dibahas sebelumnya dapat diaplikasikan untuk menyelesaikan berbagai masalah kalkulus, teori bilangan, dan kombinatorika. Salah satunya adalah untuk menentukan langkah paling sedikit dalam menyelesaikan permainan Menara Hanoi.

Menara Hanoi merupakan salah satu permainan yang mana terdiri dari tiga tiang dan sejumlah piringan (paling sedikit satu) dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Di awal permainan, piringan tertumpuk secara rapi dan berurutan berdasarkan ukurannya dalam salah satu tiang. Piringan terkecil diletakkan paling atas, dan piringan terbesar diletakkan paling bawah sehingga membentuk kerucut.

Tujuan dari permainan ini adalah untuk memindahkan seluruh tumpukan piringan tadi ke tiang yang lain, tapi harus mengikuti aturan berikut:

• Dalam satu waktu hanya boleh memindahkan satu piringan;
• Memindahkan piringan paling atas dari satu tiang dan memasukkannya ke tiang  yang lain;
• Tidak boleh meletakkan piringan di atas piringan lain yang lebih kecil ukurannya. [Wikipedia]

Sekarang, mari kita bermain dengan menara Hanoi tersebut!

Jika menara Hanoi hanya memiliki satu piringan, maka cara memindahkan piringan tersebut ke tiang yang lain sangat mudah. Perhatikan gambar berikut:

Kita hanya melakukan satu kali perpindahan piringan.

Jika menara Hanoi memiliki dua piringan, maka kita lakukan perpindahan sebagai berikut

Perhatikan bahwa kita melakukan dua kali langkah yang sama seperti pada menara Hanoi dengan satu piringan, dan langkah terakhir memindahkan piringan terkecil di tempat teratas. Secara matematis, banyaknya langkah dapat dituliskan

Jadi, kita melakukan 3 kali perpindahan.

Jika menara Hanoi memiliki tiga piringan, maka cara untuk memindahkan ketiga piringan tersebut ke tiang yang lain adalah sebagai berikut

Perhatikan bahwa kita melakukan dua kali langkah yang sama seperti pada menara hanoi dengan dua piringan, dan langkah terakhir meletakkan piringan terkecil di tempat teratas, dituliskan

Jadi kita melakukan 7 kali perpindahan.

Sekarang misalkan menyatakan langkah paling sedikit yang dibutuhkan untuk menyelesaikan menara Hanoi yang memiliki buah piringan. Berdasarkan percobaan sebelumnya diperoleh

yang mana merupakan barisan rekursif. Berapa langkah paling sedikit untuk menyelesaikan menara Hanoi yang memiliki 4 buah piringan? lebih jauh lagi, untuk buah piringan? Tentu, kita dapat melihat polanya dengan mudah. Untuk buah piringan maka kita punya rumus rekursif

dan untuk

Belum lengkap rasanya jika tidak disertai bentuk eksplisit dari rumus rekursif tersebut. Untuk mencarinya, pandang barisan rekursif berikut

Jumlahkan setiap baris untuk mendapatkan

Perhatikan bahwa merupakan deret geometri berhingga dengan rasio yang memiliki jumlah . Karena , jadi dapat dituliskan sebagai

Akhirnya kita mendapatkan bentuk eksplisit dari sebagai

, untuk

Dari sini kita tahu bahwa langkah paling sedikit untuk menyelesaikan menara Hanoi dengan 5 piringan adalah sebanyak langkah. Sekarang, bisakah teman-teman menyusun menara Hanoi dengan 5 buah piringan tersebut hanya dengan 31 langkah?

Barangkali ingin mencoba permainannya, sila buka link dari Khan Academy berikut: Bermain Menara Hanoi dengan 5 Piringan (Game hanya bisa dimainkan di PC).