Discrete Mathematics for Computer Science

The Tower of Hanoi Problem 553

= 8T(n - 3) + 4 + 2 + 1

2

= 23 T(n - 3) + Z2'

i=0

At this point, we want to look at the results of back substitution and see if a pattern is

emerging. Seeing a pattern may suggest what will result from the remaining steps needed

to reduce T(n) to an expression involving n and T(l).

In the case when the right-hand side contains T(n - i) for i = 1, 2, and 3, observe two

things: the power of 2 in the expression that is the coefficient of T (n - i) is 2i, and the other

constants on the right-hand side of the expression that are summed are 20, 21 ... 2 i-1. If

this is the pattern that will continue, then it appears that after i steps, the representation for

T(n) would be

T(n) = 2iT(n - i) + 2i- +2-2±+...+2+1 2

Using this pattern and continuing the back substitution for n - 2 steps, the resulting

expression is

T(n) = 2`^2 T(2) + 2 -3 + 2n-4 + ... + 2 + 1

One more back substitution step gives T(n) as a function of n and T(1):

T(n) = 2n-2(2T(1) + 1) + 2n-3 + 2n-4 + .-. + 2 + l

= 2n-lT(l) +2n-2 +2n-3 +...+2+1

Since the initial value for T (1) = 1, we replace the reference to the function T on the

right-hand side and get

T(n) =2n- +2n-2+...+2+1

n-1

i=0
We compute a closed form for this sum as explained in Section 1.7.5. The computation
with ratio 2 is

2T(n) = 2 + 4 +.••+2 2n-2 +2 2n-1 +2 2n

-T(n) = 1 +2+4+... + 2n-2 +2n-1

T(n) = 2n - 1
The back substitution has led to a function of n that we must now prove to be the
solution for the Tower of Hanoi recurrence relation, because the generalization step in
back substitution is not a proof. The generalization from the pattern for three terms to a
pattern for all the terms was only justified by the idea that the pattern would continue as
it was developing. A formal proof of a property for all values of n requires a proof by
induction.

Theorem 1. For n > 1, T (n) = 2n - 1 is a solution for the Tower of Hanoi recurrence
relation.