Tower of Hanoi : Part 2 of 3

Now since we know the background of the puzzle let's start proving the formula.

2 vital keys

Let's start with what we definitely know:

To solve an n-disk puzzle

step 1: use multiple steps to move n-1 disks from RodA to RodB

step 2: move the largest disk from RodA to RodC

step 3: use multiple steps to move n-1 disk from RodB to RodC

let's say the number of steps required to solve an n-disk Hanoi puzzle is T{n}, then we definitely know that

T{n} = T{n-1} + 1 + T{n-1} = 2T{n-1} + 1

/*
in this case, we use "{}" to state the subscript
total steps = step1(move n-1 disks) + step2(move the largest disk) + step3(move the n-1 disks again)
*/

another thing that we definitely know that is

T{0} = 0
// you will need 0 steps to finish a 0-disk Hanoi puzzle

---

the Proof :

The main idea is to keep expanding T{n} until we reach the term T{0}. so here we go~

T{n}
= 2  T{n-1}                                            +1
= 2 (2 T{n-2}                                       +1)+1
= 2 (2 (2 T{n-3}                                 +1)+1)+1
= 2 (2 (2 (2 T{n-4}                           +1)+1)+1)+1
.
.
.
= 2(2(2(2 ... 2(2(2(2T{n-n=0}+1  )+1  )+1  )+1  ...+1  )+1  )+1  )+1
= 2(2(2(2 ... 2(2(2(2T{n-n=0}+2^0)+2^0)+2^0)+2^0...+2^0)+2^0)+2^0)+2^0
= 2(2(2(2 ... 2(2(2(2^1 T{0} +2^0)+2^0)+2^0)+2^0...+2^0)+2^0)+2^0)+2^0
= 2(2(2(2 ... 2(2(  2^2 T{0} +2^1 +2^0)+2^0)+2^0...+2^0)+2^0)+2^0)+2^0
= 2(2(2(2 ... 2(    2^3 T{0} +2^2 +2^1 +2^0)+2^0...+2^0)+2^0)+2^0)+2^0
= 2(2(2(2 ...       2^4 T{0} +2^3 +2^2 +2^1 +2^0...+2^0)+2^0)+2^0)+2^0
.
.
.
= 2^n T{0} + 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^2 + 2^1 + 2^0

since we know that T{0} = 0

what we have to deal with is the "2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 4 + 2 + 1" part

first, we need to come up with a proof that we can "collapse" this string:

∀ x∈ℤ
2^x + 2^x
= 2^x(1 + 1)
= (2^x)(2)
= 2^(x+1)

with this we can try to focus on that string, say that string is S, so we would have

S       = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^2 + 2^1 + 2^0
S + 2^0 = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^2 + 2^1 + 2^0 + 2^0
        = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^2 + 2^1 + 2^1
        = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^2 + 2^2
        = 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^3
        .
        .
        .
S + 2^0 = 2^n
S = 2^n - 1     

so if we plug this thing back in where we left off, we would have

T{n} = 2^n T{0} + 2^(n-1) + 2^(n-2) + 2^(n-3) + ... + 2^2 + 2^1 + 2^0
     = 2^0 (0)  + S
     = 0        + 2^n - 1

and so finally we have proved that the least number of required steps to solve an n-disks Tower of Hanoi puzzle is :

T{n} = 2^n - 1, ∀ x∈ℤ, x≥0

---

more stuff for Part 3