Tower of Hanoi

On Thursday and Friday I worked on a Tower of Hanoi puzzle.  The tower of Hanoi is a mathematical puzzle that consists of three rods and a certain number of disks that are in ascending order on one rod.  The goal of this puzzle is to move all the disks to the third rod without placing a larger disk on top of a smaller disk.  For example if you have three disks on the first rod the goal would be to rearrange those disks on the third rod.  Although it may sound easy it gets very complicated very fast.  In our group we determined that to move 2 disks it would take 3 moves, 3 disks: 7 moves, 4 disks: 15 moves, 5 disks: 31 moves, 6 disks: 63 moves...etc.  We also found the general formula for this puzzle which is Tn=2n-1 which means that however many disks there are you subtract that by one and raise 2 to the power of that.  For the recursive formula we found that the formula is Tn-1=(Tn(2))+1 which means that you take the number of disks and subtract that by one and then multiply that by 2 and add 1 which will get you the number of moves.  We then used mathematical induction to prove the general formula by assuming true for n=k which made the formula Tk=2k-1 and then we showed true for k+1 which made the formula Tk+1=2(k+1)-1.  When you do the algebra the equation works out to equal 2k+1-1 on both sides.  Because they equal each other this shows that mathematical induction works.  We know that mathematical induction works to prove something when you can get both sides to equal the same thing.