Definition D1
Given a sequence of moves that transfers n disks of pairwise distinct sizes from one peg to another while obeying the rules, let M(n) denote the smallest such length.
Proof.
(1)There are four rules. One disk is moved at a time, the disk moved is the top disk of its peg, a larger disk is never placed on a smaller one, and there are three pegs.A2, A3, A4, A5
(2)The length of a move sequence is a natural number, so if any such sequence exists, the set of lengths has a least element.(1), A7
(3)With one disk, moving it once to the target peg suffices, and fewer than one move is impossible. Therefore M(1) = 1.(1), (2), A2
∎
Lemma L1
If n ≥ 2 and M(n−1) is defined, then M(n) is defined and M(n) ≤ 2M(n−1) + 1
Proof.
(1)Number the disks 1 through n in order of size, with disk n the largest.convention
(2)Call the starting peg X, the target peg Z, and the remaining peg Y. There are three pegs, so this is all of them.A5
(3)Move disks 1 through n−1 from X to Y in M(n−1) moves. Disk n sits at the bottom of X and is the largest, so any disk may be placed on top of it.assumption, D1, A4
(4)Move disk n from X to Z in one move. Z is empty.(3), A2, A3
(5)Move disks 1 through n−1 from Y to Z in M(n−1) moves. Disk n sits at the bottom of Z and is the largest, so no rule is violated.(4), D1, A4
(6)The length of this move sequence is M(n−1) + 1 + M(n−1) = 2M(n−1) + 1(3), (4), (5), N
(7)A move sequence transferring the n disks exists, so M(n) is defined, and the minimum does not exceed this length.(6), D1
∎
Lemma L2
If n ≥ 2, then M(n) ≥ 2M(n−1) + 1
Proof.
(1)Take an arbitrary move sequence that transfers the n disks.assumption, D1
(2)Disk n must go from the starting peg to the target peg, so it is moved at least once.(1), D1
(3)At the moment disk n is first moved, it is at the top of its peg and the peg receiving it is empty. Disk n is the largest, so it cannot be placed on any other disk.(2), A3, A4
(4)There are three pegs, so at that moment disks 1 through n−1 are all gathered on the remaining peg.(3), A5
(5)The moves up to that point never moved disk n, so they involve only disks 1 through n−1, and they transferred all n−1 of them from the starting peg to another peg.(3), (4)
(6)Throughout, disk n sits at the bottom of the starting peg and is the largest, so it never obstructs placing any disk on top of it. Hence those moves form a move sequence for n−1 disks, and their number is at least M(n−1).(5), A4, D1
(7)The same argument applies at the moment disk n is last moved. At that moment disks 1 through n−1 are gathered on the remaining peg, and the moves after it must gather them on the target peg, so their number is also at least M(n−1).(3), (4), (6), A5, D1
(8)The three parts do not overlap: before disk n is first moved, the moves of disk n, and after disk n is last moved.(2), (6), (7)
(9)Therefore the length of this move sequence is at least M(n−1) + 1 + M(n−1) = 2M(n−1) + 1.(8), N
(10)This holds for an arbitrary move sequence, so the minimum M(n) is at least as large.(1), (9), D1
∎
Lemma L3
M(1) = 1, and if n ≥ 2, then M(n) = 2M(n−1) + 1
Proof.
(1)M(n) ≤ 2M(n−1) + 1L1
(2)M(n) ≥ 2M(n−1) + 1L2
(3)From the two inequalities, M(n) = 2M(n−1) + 1(1), (2), O
(4)M(1) = 1D1
∎
Theorem T1
For every natural number n, M(n) = 2ⁿ − 1
Proof.
(1)Let P(n) be the statement 'M(n) = 2ⁿ − 1'.convention
(2)M(1) = 1 and 2¹ − 1 = 2 − 1 = 1, so P(1) holds.L3, A6, N
(3)Suppose P(k). M(k) = 2ᵏ − 1assumption
(4)M(k+1) = 2M(k) + 1L3
(5)2M(k) + 1 = 2(2ᵏ − 1) + 1 = 2ᵏ·2 − 2 + 1 = 2ᵏ⁺¹ − 1(3), (4), A6, N
(6)Therefore P(k+1) holds.(4), (5)
(7)Therefore P(n) holds for every n.(2), (6), A1
∎