Editing Tower of Hanoi (section)

==== Logical analysis of the recursive solution ====
{{More citations needed section|date=January 2024}}
<!-- TODO:  This section needs copy-editing for tone, professionalism and clarity: edited/bolded .-->
As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of ''h'' (height) disks from a starting peg ''f'' = '''A''' (from) onto a destination peg ''t'' = '''C''' (to), '''B''' being the remaining third peg and assuming ''t'' ≠ ''f''. First, observe that the problem is symmetric for permutations of the names of the pegs ([[Symmetric group|symmetric group ''S''<sub>3</sub>]]). If a solution is known moving from peg '''A''' to peg '''C''', then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If ''h'' = 1, then move the disk from peg '''A''' to peg '''C'''. If ''h'' > 1, then somewhere along the sequence of moves, the largest disk must be moved from peg '''A''' to another peg, preferably to peg '''C'''. The only situation that allows this move is when all smaller ''h'' − 1 disks are on peg '''B'''. Hence, first all ''h'' − 1 smaller disks must go from '''A''' to '''B'''. Then move the largest disk and finally move the ''h'' − 1 smaller disks from peg '''B''' to peg '''C'''. The presence of the largest disk does not impede any move of the ''h'' − 1 smaller disks and can be temporarily ignored. Now the problem is reduced to moving ''h'' − 1 disks from one peg to another one, first from '''A''' to '''B''' and subsequently from '''B''' to '''C''', but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the ''h'' − 1 problem to ''h'' − 2, ''h'' − 3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows.

Identify the disks in order of increasing size by the natural numbers from 0 up to but not including ''h''. Hence disk 0 is the smallest one, and disk ''h'' − 1 the largest one.

The following is a procedure for moving a tower of ''h'' disks from a peg '''A''' onto a peg '''C''', with '''B''' being the remaining third peg:
# If ''h'' > 1, then first use this procedure to move the ''h'' − 1 smaller disks from peg '''A''' to peg '''B'''.
# Now the largest disk, i.e. disk ''h'' can be moved from peg '''A''' to peg '''C'''.
# If ''h'' > 1, then again use this procedure to move the ''h'' − 1 smaller disks from peg '''B''' to peg '''C'''.

By [[mathematical induction]], it is easily proven that the above procedure requires the minimum number of moves possible and that the produced solution is the only one with this minimal number of moves. Using [[recurrence relation]]s, the exact number of moves that this solution requires can be calculated by: <math>2^h - 1</math>. This result is obtained by noting that steps 1 and 3 take <math>T_{h-1}</math> moves, and step 2 takes one move, giving <math>T_h = 2T_{h-1} + 1</math>.