# The tower of Hanoi and inductive logic.

Induction and the Australian Curriculum

The Tower of Hanoi problem contains deep, foundational mathematical truths. It requires, for example, knowledge (explicit or implicit) of the basic if not fundamental properties of odd and even numbers and (mathematical) inductive logic.

The broad notion of 'reasoning' emerges as a proficiency strand of the "Mathematical Proficiencies" in the Australian F-10 Mathematics curriculum (Australian Curriculum, Assessment and Reporting Authority, n.d., F-10 Curriculum: Mathematics, Content structure), and the concept of mathematical induction as a formal topic first suddenly surfaces (or "is introduced") in the senior secondary subject Specialist Mathematics in the Australian Curriculum (Australian Curriculum, Assessment and Reporting Authority, 2015, Specialist Mathematics, Structure of Specialist Mathematics, Overview, and Rationale, Curriculum, Unit 2). The related curriculum outcome is described as: "understand the nature of inductive proof including the 'initial statement' and 'inductive step'" (Australian Curriculum, Assessment and Reporting Authority, 2015, ACMSM064).

The language used is abstract, reflecting advanced arguments from propositional calculus: "Let there be associated with each positive integer n, a proposition P(n)" (Australian Curriculum, Assessment and Reporting Authority, 2015, Glossary). Two examples of proof by mathematical induction are suggested: the first would illustrate "sums", and the other "divisibility results".

My experiences tell me that, in the classroom, the first example of a proof by mathematical induction shown to students tends to be the general result for triangular numbers, but only modelled as symbolic representation (Bruner, 1966), or at the extended abstract level of the SOLO taxonomy (Biggs & Collis, 1982). Even for high ability students, this is quite a cognitive leap to make. Good, robust pedagogical theory (i.e., supported by formal research) tells us that, even if only briefly, it is necessary to introduce a new mathematical concept using enactive and iconic representations (Bruner, 1966), or building up from multi-structural and relational levels of cognitive complexity (Biggs & Collis, 1982).

One example of a hands-on, concrete manipulative that can be used actively to develop the concept of mathematical induction is the Tower of Hanoi problem. The iterative and recursive nature of its optimal solution forms the structure for an excellent illustration of the induction process.

The Lucas Tower

The so-called Tower of Hanoi problem is a well-known Mathematical puzzle and recreation. It is also frequently used as a task in cognitive psychology research on problem solving, and is a key component of Kanevsky's (2000) model of dynamic assessment. The namesake of the problem is an actual octagonal tower in Hanoi, Vietnam, built in 1812 and, when including its flag mast, standing 41 metres high (Pickover, 2014).

The Tower of Hanoi is also called the Lucas Tower after Edouard Lucas (1842-1891) of Saint Louis, France, who created it in 1883 (and published it under the pseudonym Professeur N. Claus de Siam, Mandarin du College de Li-Sou-Stian), or the Tower of Brahma after a true legend that Lucas invented to accompany the puzzle (Claus [Lucas], 1883). By the time the puzzle got to Ball (1892) the legend had become quite well embellished, and later, Gardner (1965), a popularist writer of mathematical puzzles and recreations, seemed to be confused about the story's details. Hence, I will cite the original description from the leaflet that accompanied the puzzle:

D'apres une vieille legend indienne, les brahmes se succedent depuis bien longtemps, sur les marches de l'autel, dans le Temple de Benares, pour executer le deplacement de la Tour Sacree de Brahma, aux soixante-quatre etages en or fin, garnis de diamants de Golconde. Quand tout sera fini, la Tour at les brahmes tomberont, et ce sera la fin du monde! (Claus [Lucas], 1883, recto).

That is, the Holy Tower of Brahma is to be found in a temple in the Indian city of Benares. It has 64 disks, each of pure gold and embossed with diamonds, on a cylindrical stele. The disks are to be transferred by the temple priests from the initial stele to one of two other steles, although it is not stated to which stele the disks will be moved, nor how often a disk is moved. When the task is completed, the priests will collapse and the tower will fall down, and the world will end. [Gardner (1965, p. 58) stated that, before the priests complete their task, "the temple will crumble into dust and the world will vanish in a clap of thunder."] The problem now, of course, is to determine how worried we need to be about when the world will end.

The Tower of Hanoi problem

In its current form, the Tower of Hanoi problem is well-defined, in the formal sense of the term: three pegs stand upright on a flat base; n disks of differing sizes are stacked in a column on one of the pegs; no disk lies below another disk that is larger than it; one, and only one, disk is moved at a time; when a disk is moved it must be moved to another peg; and a larger disk cannot be placed on a smaller disk. Although unstated in the rules, the real problem is to use the least number of moves to move the disks so that all n disks end up on a specified different peg.

In the example in Figure 1, the initial state is shown with three disks placed on Peg A, and two empty pegs are to the right. The goal state is also shown, with all three disks arranged on Peg B, with the largest disk at the bottom, the medium sized disk next and the smallest disk on the top. Most students, even those quite young, can complete the three-disk puzzle with little effort, although some may baulk at which peg to use for the first move in order to end up on the correct target peg, or may need to attempt the puzzle twice.

Now imagine that there are four disks of varying sizes, obeying the rule that no larger disk may be placed on a smaller disk, in a pyramidal shape fitting over peg (A). The object of the puzzle is to move the four disks to a third peg (C) via a temporary peg (B), one disk at a time, such that at no stage is there a larger disk on top of a smaller disk. Note that part of the solution to the four-disk problem requires the solution to the three-disk problem, or, better, requires in fact two iterations of the solution to the three-disk problem.

Of course, if you find four disks too easy, try this exercise of the imagination by starting with five or more disks (but not 64 disks, golden or otherwise, as stated in the original problem!). However, most people will approach cognitive overload when attempting to imagine solving the problem with five disks. Hence, I highly recommend that you build your own model of the Tower of Hanoi. My model comprises a base made from river red gum, three pegs made from dowel (mine are in a row, while the original configuration was an equilateral triangle), and a pile of eight disks made from silky oak (see Figure 2). Physically feeling and doing and seeing this problem, and immersing oneself in it as it unfolds, are all very important.

The minimum number of moves

Now, if we are to use the least number of moves to move the disks so that all n disks end up on a specified different peg, we need to determine what that number is; that is, we need to count the number of moves, or to find a way to count them. Following the advice of Polya (1945)--if you cannot solve the problem, find a simpler problem and solve it first--we can simplify the problem by starting with only one disk, and slowly but surely progress to 2, 3 and 4 disks, and so on. This approach will also concretely show the induction process as it occurs. At the same time, it would be important to think about how you know (or determine) which peg to move a disk to (especially if there is an empty peg), and what kinds of mathematical concepts are involved in progressing from step to step.

Because of the need to keep track of the progress of the solution, and to keep track of the number of moves taken, it is advisable to use small groups with one member of the group moving the disks and another counting the number of moves required. Once the table (Table 1) has been established, most secondary school students will quickly see the connection between the numbers on the second row ("the numbers go up by 2, then 4, then 8, and so on"), but should be prompted to express this in as many ways as possible.

If a hint is needed to generalise the result for n, add a third row which repeats the second row but with each number increased by 1. This third row will look like exactly like [2.sup.n], which will give the expression for the number of moves required to be:

H(n) = [2.sup.n] - 1

About now it is thought provoking to produce several rows of differences in the table, discovering that the differences do not become a constant. This (non-) result is directly related to the (differential) calculus of exponential functions, and actually indicates that the solution must be an exponential function. Teachers who use this activity in their junior secondary school curriculum should highlight to their students that what has been shown here foreshadows an exciting and important result in exponential functions that is usually first met in senior secondary school.

Inductive logic

Looking back, as Polya (1945) again advises, there is the matter of mathematical induction to tease out. First, from Table 1 above we can see immediately that

H (1) = 1 = [2.sup.1] - 1

so the number of moves required to move one disk is of the form [2.sup.n] - 1.

Second, we need to recognise or to acknowledge that one of the ways of seeing the pattern in the second row of Table 1 is, "To get the next number, double the previous number and add 1," or, expressed slightly differently, "To get the next number, take the previous number, add 1, then add the previous number again."

Third, this means that to progress from one iteration of the problem to the next, say from 4 disks to 5 disks, we can physically manipulate the concrete model of the Tower of Hanoi by moving the top 4 disks from peg A to peg B (which takes 15 moves), moving the bottom and largest disk from peg A to peg C (which takes 1 move), and again moving the pile of 4 disks but this time from peg B to peg C (which again takes 15 moves), all for a total of 31 moves, which is the next number in Table 1. This iterative process may then be illustrated in a diagram. Written as a sum, this looks like:

H(5) = H(4) + 1 + H(4) = 2 x H(4) + 1 = 2 x ([2.sup.4] - 1) + 1 = 2 x 15 + 1 = 31 = [2.sup.5] - 1

Here, H(4) = [2.sup.4] - 1 and H(5) = [2.sup.5] - 1 are both of the form H(n) = [2.sup.n] - 1.

In Figure 2, this same inductive process is shown for 8 disks.

Even for senior secondary students (and especially adults!), it is important to work through this stage of understanding the inductive process enactively (carrying out the operation on an actual model of the Tower of Hanoi), iconically (representing the process using illustrations or diagrams) and symbolically (Bruner, 1966).

Fourth, this inductive logic may now be generalised as follows:

H(n + 1) = H(n) + 1 + H(n) = 2 x H(n) + 1 = 2 x ([2.sup.n] - 1) + 1 = 2 x [2.sup.n] - 2 + 1 = [2.sup.n-1] - 1

which is of the required form. This shows, by mathematical induction, that the minimum number of moves required to move n disks will always be of the form H(n) = [2.sup.n] - 1.

A nice surprise

The 'powers of 2' that have emerged in the general solution above are quite suggestive. A neat trick when 'powers of 2' appear is to convert any numerical analysis from base 10 to base 2: with the Tower of Hanoi problem, it is fun to show the above inductive logic using binary notation ("There are 10 types of people: one who knows the meaning of the binary system, and one who does not"--source unknown). In binary notation, [2.sup.n] is written as a "1" followed by n zeros. Hence, analogous to [10.sup.n-1] being written as a string of n nines, our expression for H(n) can be rewritten as a string of n ones:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which allows the induction step to be succinctly shown as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now this string of ones (base 2) equates to a geometric series

[n.summation over (r=1)] [2.sup.r-1]

As there are no accidents in mathematics, the appearance of this geometric series, of the long string of ones (base 2), should give us pause to reflect on where the individual terms in the sum really come from--why is it so? This thought suggests to me that we should look for another way to count the number of moves, such as how many times each of the individual discs is moved to complete the task. The iterative and recursive process, seen through binary eyes, becomes clear: the largest disc moves once, or 1 (base 2) move; the second largest disc moves twice, or 10 (base 2) times ; the next largest disc moves four times, or 100 (base 2) times; and so on. That is, each of the terms in the sum, in the string of ones (base 2), corresponds to the number of moves made by a particular disc. We have both:

H (n) = 1 + 2 + 4 + ... + [2.sup.n-1]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In essence, the Tower of Hanoi is a beautiful, manual, binary computer!

The end of the world

Note that the 'enactive' model of the Tower of Hanoi can be 'enacted' by a group of students (albeit in rows rather than columns!): I recommend using five students of distinctly different heights. Each of the above results may be demonstrated using this human model or representation of the problem and its solution. This last result showing a remarkable pattern using binary numbers is quite striking as it is, but the point is emphasised when each of the individual "student disks" counts his or her moves, and, after the task is completed, the group lines up as a binary number.

As mentioned in the introduction, the concept of mathematical induction is usually first met in upper level course in senior secondary mathematics. However, if what Bruner says about a spiral curriculum is in any sense correct, then "any subject can be taught effectively in some intellectually honest form to any child at any stage of development" (Bruner, 1960, p. 33).

That is, junior secondary students could be, should be, introduced to problems and thinking related to inductive logic. Indeed, with a bit more careful scaffolding than what I have presented, most of the above activity is certainly accessible to a good proportion of students in junior secondary school. Furthermore, this "early" experience will make it a lot easier for those high ability students who will formally meet the concept of mathematical induction in a few years' time. In fact, the Australian Curriculum, Assessment and Reporting Authority (n.d., Student diversity, Gifted and talented students) notes that gifted and talented students are entitled to challenging, rigorous, relevant, enriching, extended, accelerated and engaging curriculum and learning opportunities to enable their gifts and talents to emerge, to be recognised and to be developed. Such curriculum and learning opportunities are illustrated by the inclusion of above level outcomes in examples of personalised learning.

Oh, and when will the temple priests complete their task of moving all of the 64 disks? Note that when n = 64, and assuming that one disk is moved each new day, the number of years to complete the task is:

H(64)/65 = [2.sup.64] - 1/365

A rough, upper-bound estimate of the size of this number gives:

[[log.sub.10] {H(64)/365}] = [[log.sub.10] {[2.sup.64] - 1/365} ] = 17

That is, when this number is expressed as a decimal, it is 17 digits long. Given that the earth is approximately 4.5 billion years old, it would take 10 000 000 times that long for the temple priests to complete their task. Hence, it appears that 'the tower and the temple priests will fall down' well before the task could ever be completed.

Peter Merrotsy

The University of Western Australia

peter.merrotsy@uwa.edu.au

References

Australian Curriculum, Assessment and Reporting Authority. (n.d.). Australian Curriculum. F-10 Curriculum: Mathematics. Retrieved from http://www.australiancurriculum.edu.au

Ball, W. W. R. (1892). Mathematical recreations and problems of past and present (2nd ed.). London, UK: Macmillan.

Biggs, J. B., & Collis, K. (1982). Evaluating the quality of learning: The SOLO Taxonomy (Structure of the Observed Learning Outcome). New York, NY: Academic Press.

Bruner, J. (1960). The process of education. Cambridge, MA: The President and Fellows of Harvard College.

Bruner, J. (1966). The culture of education. Cambridge, MA: Harvard University Press.

Claus, N. [Lucas, E.] (1883). La Tour d'Hanoi: Veritable casse-tete annamite. Tours, France: P. Bousrez.

Gardner, M. (1965). Mathematical puzzles and diversions. Harmondsworth, UK: Penguin. Kanevsky, L. (2000). Dynamic assessment of gifted students. In K. Heller, F. Monks, R.

Sternberg & R. Subotnik (Eds.), International handbook of giftedness and talent (2nd ed., pp. 283-295). Amsterdam, The Netherlands: Elsevier.

Pickover, C. A. (2014). Das Mathebuch: Von Pythagoras bis in die 57. Dimension 250 Meilensteine in der Geschichte der Mathematik. Kerkdriel, The Netherlands: Librero.

Polya, G. (1945). How to solve it: A new aspect of mathematical method. Princeton, NJ: Princeton University Press.
```
Table 1. Number of moves required.

Number of disks   1   2   3   4    5     n
Number of moves   1   3   7   15   31   H(n)
```
COPYRIGHT 2015 The Australian Association of Mathematics Teachers, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.