Tower of hanoi problem

This paper looks at the tower of hanoi problem and how to generate the closed formula from the recursive formula using linear algebra and matrix operations.

1. Generating the Closed Formula for the Tower of Hanoi
Problem Using Matrix Algebra
Tyler Murphy
September 29, 2014
1 Background
The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes
pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of
disks of dierent sizes which can slide onto any rod. The puzzle starts with the disks in
a neat stack in ascending order of size on one rod, the smallest at the top, thus making a
conical shape.
Figure 1: Tower of Hanoi Game
The objective of the puzzle is to move the entire stack to another rod, obeying the
following simple rules:
Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack i.e. a disk can only be moved if it is the uppermost disk on a
stack.
No disk may be placed on top of a smaller disk.
We are interested in nding the smallest number of moves it takes to move a tower
withndiscs to another location. First, we generate a table of experimentation values
1

2. Number of Discs (n)Minimum Number of Moves (Mn)
1 1
2 3
3 7
4 15
5 31
6 63
We see that after this point, experimentation begins to take a long time, so we stop
here and try to devise a pattern.
2 Recurrence Form
We notice that each value forMnis twice the value ofMn1plus 1. So we need to know
the value forMn1, which we can see would be dicult to generate for any largen. So
calculating the value forMnbecomes no small task when we use the recurrence formula to
nd it. We need a simpler way.
It turns out that if can design a matrix that models this recurrence relation, we will be
able to use this matrix to generate a closed formula to ndMnwithout having to know
Mn1.
3 Designing the Matrix
Recall that a matrix is simply another way to write a system of equations.
For example, the equations
2x+ 3y= 4 (1)
and
x+y=1: (2)
These can be written in matrix multiplication form as:

2 3
1 1

x
y

=

4
1

So we can write our recursive formula in this manner.
We will eventually end up with something of the form
A
n
b=c
WhereAis our matrix,bis our initial value vector andcis our solution vector.
2

3. Because of the constant term in the recursion relation and becauseMn+1only depends
onMnbut notMn1(like the Fibonnaci sequence), we will use vectors of the form

Mn
1

We also know our matrix will be a 2x2 matrix because we only have two terms in our
recurrence formula. So:
A=

a11a12
a21a22

We want a matrixAsuch that

Mn+1
1

=A

Mn
1

The equations represented by this are:
Mn+1=a11Mn+a12
and
1 =a21Mn+a22:
To make the rst equation true, we use the recursion relation and choosea11= 2; a12=
1. The second equation becomes true if we choosea21= 0 anda22 = 1. Thus our matrix
is
A=

2 1
0 1

So, using this matrix, we can nd that

Mn+1
1

=

2 1
0 1

Mn
1

This makes sense when we put it back into equation form and obtain:Mn+1= 2Mn+1
and 1 = 0Mn+ 1.
The problem now is that we still need an input vector that requiresMnin order to give
usMn+ 1.
But consider that
Mn+1
1

=A

Mn
1

So forn= 1,

M2
1

=A

M1
1

3

4.
M3
1

=A

A

M1
1

=A
2

M1
1


M4
1

=A

A
2

M1
1

=A
3

M1
1

So we see the pattern that:

Mn+1
1

=A
n

M1
1

4 Quickly Computing A
n
Since computingA
n
for any largenwould be extremely cumberson and dicult, we
must nd a better way to computer these large powers ofA.
Linear Algebra teaches us that if a matrix can be diagonalized, then this process of
computing powers becomes very simple. When a matrix is diagonalized, it becomes of the
formA=SDS
1
whereSis the matrix composed of the eigenvectors of the matrix, and
Dis the diagonal matrix composed of the eigenvalues () ofA. That is,D=I, whereI
is the Identity Matrix.
4.1 Finding the Eigenvalues ofA
So rst we nd the eigenvalues associated withA. This is done by nding the values for
that satisfy the equation:
det(AI) = 0
First, we nd (AI) =

21
0 1

Recall that the determinant of a 2x2 matrixA=

a b
c d

isadbc
So ,Det(A=I) = (2)(1)(0)(1).
Setting this equal to zero and solving we nd= 1;2.
So we can plug these values intoIto ndD=

1 0
0 2

4.2 Finding the Eigenvectors ofA
Now we need to nd the eigenvectors ofAin order to nd our matrixS.
This is done by solving the equation
(AI)x=0
4

5. for each.
First, we choose= 1.

21 1
0 11

x1
x2

=

1 1
0 0

x1
x2

=

0
0

Converting this to equations, we gets that
x1+x+ 2 = 0)x1=x2
and
0x1+ 0x2= 0
Since the second equation tells us nothing, we use the rst equation and nd that the
basis vectorx=1=

1
1

.
Doing the same thing for= 2, we nd thatx=2=

1
0

.
Now we put these two eigenvectors into MatrixS, remembering that the order we put
them into the matrix should match the order we put the eigenvalues intoD. So,
S=

1 1
1 0

.
4.3 ComputingS
1
Recall that the inverse of a 2x2 matrixA=

a b
c d

=A
1
=
1
Det(A)

db
c a

So
S
1
=
1
(1)(0)(1)(1)

01
11

=1

01
11

=

0 1
1 1

4.4 Dealing withA=SDS
1
So all put together,A=SDS
1
=

1 1
1 0

1 0
0 2

0 1
1 1

It is a simple matter of matrix multiplication to verify the truth of this.
Now recall that
Mn+1
1

=A
n

M1
1

5

6. 5 Computing the Closed Formula
The reason we diagonalize matrices is becauseA
n
=SD
n
S
1
andD
n
is easily computed.
So
Mn+1
1

=

1 1
1 0

1 0
0 2

n
0 1
1 1

M1
1

Now realize that

1 0
0 2

n
=

1
n
0
0 2
n

=

1 0
0 2
n

So we have
Mn+1
1

=

1 1
1 0

1 0
0 2
n

0 1
1 1

M1
1

Now we can do some matrix multiplication to simplify this.
We get

Mn+1
1

=

1 1
1 0

1 0
0 2
n

0 1
1 1

M1
1


Mn+1
1

=

1 2
n
0 2
n

0 1
1 1

M1
1


Mn+1
1

=

2
n
2
n
1
2
n
2
n

M1
1

Recall now thatM1= 1.
So we have
Mn+1
1

=

2
n
2
n
1
2
n
2
n

1
1

Now we can convert this back into equational format and we nd that
Mn+1= 2
n
(1) + (2
n
1)(1) = 2
n
+ 2
n
1 = 22
n
1 (1)
This is ok, but we want a formula that gives isMn. We can get this by using our
original recursive formula.
Mn+1= 2Mn+ 1 (2)
Substituting (2) into equation (1) we get:
2Mn+ 1 = 22
n
1
Now we simplify this.
2Mn+ 1 = 22
n
1
2Mn= 22
n
2
Mn= 2
n
1
So we nally have our closed form.
The minimum number of moves for a tower ofndiscs is 2
n
1.
6