Contoh Korelasi Rekurensi: Menara Hanoi

Sebelumnya telah dijelaskan mengenai arti dari kekerabatan rekurensi. Juga sudah dipaparkan tumpuan permodelan matematika relasi rekurensi Kelinci dan Bilangan Fibonacci. Berikutnya ini ialah tumpuan aplikasi model matematika kekerabatan rekurensi dengan nama Problem Menara Hanoi.

Kasus:
Jenis Puzzle ini dikenalkan oleh spesialis matematika di simpulan masa ke-19 yang berasal dari Perancis yaitu Edouard Lucas. Problem ini dikenal dengan nama Menara Hanoi. Permasalahannya menyerupai berikut,

Puzzle menara hanoi ini terdiri dari tiga tiang yang diletakkan di atas papan bersama dengan piringan yang ukurannya berbeda. Pada kondisi awal piringan ini diletakan pada tiang pertama dalam urutan menurut ukuran, dengan piringan terbesar berada paling bawah. Aturannya adalah, piringan boleh dipindahkan dari tiang satu ke tiang lainnya sepanjang piringan yang lebih besar tidak diletakkan di atas piringan yang lebih kecil. Tujuan dari puzzle ini ialah memindahkan semua piringan dari tiang pertama ke tiang kedua dalam urutan menurut ukuran dengan syarat piringan paling besar ada di urutan paling bawah.

Misal $H_n$ dinotasikan sebagai banyaknya langkah minimal yang dibutuhkan untuk menuntaskan permasalahan menara hanoi dengan n piringan. Tentukanlah kekerabatan rekurensi untuk barisan ($H_n$)


Solusi 
Penyelesaian dimulai dengan n piringan pada tiang pertama. Lalu dapat dipindahkan n-1 piringan dari yang paling atas. Berdasarkan hukum main, dilanjutkan pada tiang ketiga dengan jumlah $H_{n-1}$ langkah.

Piringan terbesar pada tiang pertama dipindahkan pada tiang ke-dua dengan 1 langkah. Selanjutnya pindahkan piringan ketiga dengan memakai $H_{n-1}$ langkah ke tiang ke dua dengan menaruh piringan di atas piringan yang lebih besar yang diletakkan sebelumnya.

Bentuk umumnya dapat dituliskan,
$H_n= 2 H_{n-1}+1$ , syarat Awal $H_1=1$ lantaran 1 piringan dapat dipindahkan dari tiang pertama ke tiang kedua dengan 1 langkah.

Penjabaran berikutnya, akan dibentuk bentuk iterasi (pengulangan) dan disederhanakan sebagai berikut,
$\begin{align*} H_n &= 2H_{n-1} + 1\\ &=2(2H_{n-2} + 1) + 1\\ &= 2^2(2H_{n-3} + 1) + 2 + 1 = 2^3H_{n-3} + 2^2 + 2 + 1\\ &\vdots\\ &=2^{n-1}H_1 + 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^{n-1}+ 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^n - 1 \end{align*}$

Sebagai tambahan, misalkan akan dipindahkan menara Hanoi dengan 5 piringan. Secara hitungan akan dibutuhkan
$2^n-1 = 2^5-1 =32$ gerakan. Perhatikan pembuktiannya pada ilustrasi video menara Hanoi di bawah ini,

Berikutnya:Contoh Relasi Rekurensi Codeword
Sumber http://www.marthamatika.com/