Understanding Mathematical Induction by Writing Analogies

Andrew A. Cooper

August 6, 2019

Abstract: Mathematical induction has some notoriety as a difficult mathematical proof technique, especially for beginning students. In this note, I describe a writing assignment in which students are asked to develop, describe in detail, critique, defend, and finally extend their own analogies for mathematical induction. By putting the work of explanation into the students' hands, this assignment requires them to engage in detail with the necessary parts of an inductive proof. Students select their subject for the analogy, allowing them to connect abstract mathematics to their lived experiences. The process of peer review helps students recognize and remedy several of the most common errors in writing an inductive proof. All of this takes place in the context of a creative assignment, outside the work of writing formal inductive proofs.

Introduction

An essential and ubiquitous mode of proof in mathematics—thus, an essential tool that any mathematics student must develop in their toolkit early on—is the proof by induction. Proof by induction is a method to prove statements that are universally quantified over the natural numbers. These include statements such as

For any natural number n, 52n − 1 is a multiple of 8.

but also less obviously mathematical statements like

The Tower of Hanoi puzzle with n disks has a solution in at most 2n − 1 moves.

This technique is notoriously difficult for students to acquire. One typical approach to overcoming this difficulty is for the course instructor to introduce the underlying mathematical machinery by means of one or more of a handful of standard analogies.

Inspired by a talk at the Centennial MathFest (Holden, 2015), I developed a writing assignment in which students are asked to develop, describe in detail, critique, defend, and finally extend, their own analogies for mathematical induction. This assignment begins shortly after the idea of induction is introduced and takes about two weeks to complete, with the final work product submitted at the end of the induction unit.

What is induction and why is it so difficult to learn?

A proof by induction runs on one of the three following engines, which are mathematically equivalent to one another:

These statements appear to have been used about as long as formal mathematics has been done. Aristotle (300s BCE) uses some inductive arguments (Bodnar, 2006). Euclid (300 BCE) gave a proof that any natural number other than 1 has a prime factorization which uses WOP, albeit implicitly. Al-Karaji (1000s CE) gave the first examples of inductive derivations of formulas such as [equation] (Katz, 2009); Bhāskara II (1100s CE) used inductive methods to solve algebraic equations (Plotker, 2009).

A conscious labeling of inductive arguments, however, did not emerge until the late 1600s, and then only sparsely; most uses of mathematical induction remained implicit. Indeed it was only in the middle of the 19th Century that the three inductive statements were formalized, and the rigorous underpinnings of what is recognized as a modern proof by induction were laid out by Giuseppe Peano (1960).

A properly-written proof by induction uses, for example, PWI, in the following way:

Claim. For every natural number n, P(n).

Proof. First we will show P(1).

[here follows work to establish P(1)]

To prove that, for every natural number n, P(n) guarantees P(n+1), we fix n and assume P(n) holds.

[here follows work which uses P(n) to establish P(n+1)]

Having assumed P(n) and concluded P(n+1), we have shown that P(n) guarantees P(n+1); since n was arbitrary we have shown this for every n.

By the Principle of Weak Induction, this establishes that P(n) is true for all n.

In order to implement this outline to prove a particular claim, the student must successfully carry out the following steps (which I number for reference though they need not be actually carried out by the student in this order):

1. Identify the predicate P(n).

2. Establish the base case P(1).

3. State and distinguish between P(n) and P(n+1).

4. Establish the inductive step from P(n) to P(n+1).

While the mistakes students make are myriad, there is a Pareto principle at work here; most of the struggles students have fall into a small number of categories:

Failure to choose an inductive variable: Induction requires the variable n to be a natural number; identifying which variable in a particular problem we will be inducting on is necessary to get the process off the ground at all. Often the inductive variable is obvious, but to prove statements like

Every finite list of words has an alphabetically-first element.

one must first recognize that the statement can be rephrased

For any natural number n, any list of n words has an alphabetically-first element.

That is, the student must identify the length of the list as the variable to induct on.

“Mechanical” errors: A mistake in step (1) will more or less entirely prevent a student from writing anything like a correct inductive proof; luckily these are relatively rare. However, some students will struggle in step (3), mistakenly using, for example,

The Tower of Hanoi puzzle with n+1 disks has a solution in at most 2n − 1 moves.

for P(n+1).

The “aren’t we cheating?” error: The inductive step (4) involves assuming P(n) and using it to establish P(n+1). For example, we assume

The Tower of Hanoi puzzle with n disks has a solution in at most 2n − 1 moves.

and try to use this assumption to establish

The Tower of Hanoi puzzle with n+1 disks has a solution in at most 2n + 1 − 1 moves.

Having been admonished many times that the only real sin in mathematics is to assume what you are trying to prove, a substantial portion of students will reject this project entirely, because the difference between P(n) and P(n+1) is just too subtle for comfort. This is mainly an error that resides in step (3).

The “this feels like magic” error: Some students have difficulty with inductive proofs because they do not believe something so mechanical could possibly work to prove substantive claims. These students master the four steps of writing a proof by induction, but find it too easy to be trusted. Typically the student’s response will be to try to use a non-inductive approach, which will turn out to be (depending on the problem) either much more difficult or in fact impossible.

Why Analogies?

At its core, induction is actually a very simple idea. One could faithfully gloss the three inductive statements as follows:

PWI. If you can get started, and you can keep going, you can get as far as you want.

PSI. If you can get started, and (possibly relying on your momentum) you can keep going, you can get as far as you want.

WOP. If something happens, but did not always happen, it must have begun to happen.

In my own experience—as a student, in discussion with colleagues, reviewing textbooks—induction is nearly always informally introduced by means of one of the following analogies:

dominoes: The base case is the first domino to topple; the inductive step is when one domino falls onto the next.

walking: The base case is the first step; the inductive step is the act of taking a step.

climbing stairs or a ladder: The base case is the first step or rung; the inductive step is the act of using one stair or rung to get to the next.

Typical practice is to introduce these analogies when induction is first introduced in class, before the formal aspects of an inductive proof, and then shift gears into the formal aspects.

While these analogies serve as a useful introduction, most students discard them as mere dicta. The standard mistakes articulated above can all be minded and mended, or at least mitigated, with reference to such analogies. The main difficulty, then, is to get the student to invest in and refer to the analogy. To this end, I built on Holden’s original analogy assignment (2015) by extending it both in time and in depth.

My goals for this assignment are for students to:

The Assignment

(Note: To view a PDF facsimile of the original formatting of this assignment, scroll to the top, look to the right-hand Article Tools, and click the Supplementary Files link.)

I will describe the details of the assignment, as it currently stands, having been refined over the course of four semesters’ use. As this is a write-to-learn assignment, the precise formatting and style of the final product are not specified or evaluated. In this decision, and many of the choices in structuring the assignment, I was greatly informed by Bahls’s work (Bahls, 2012).

Holden’s Original Assignment

Holden has his students select an analogy topic, write their analogy, and share it with the class (2015). Holden emphasizes, both to his colleagues and in the assignment itself, that the analogy for induction is “merely an analogy”, i.e. the students are not producing a true proof by induction. His assignment is also small in scale: it is a one-class activity that asks students to address only PWI. I extended this idea as described below.

Scope

In all, the induction analogy assignment runs the entire length of the induction unit—about three weeks.

Analogy Selection

I leave selection of the analogy itself to the students. Here are the instructions:

The last two points are essential: some students will inevitably try to take the easy way out by adapting an existing analogy, which defeats the entire exercise. The purpose of the first point is two-fold. First, it prevents different students picking the same analogy. Second, the constraint forces students to be a little more creative (Stokes, 2005); they cannot pick the first analogy that came to their head and must search around a bit for real-world situations where the inductive idea is present. (It is important to be somewhat flexible, as students whose family names begin with rare-in-English letters like Q, X, Z, etc., may have some difficulty finding a word.)

I collect analogy proposals and approve or require a change within two or three days of the initial assignment. About two-thirds of initial submissions are approved. (I like to approve them with a positive comment such as, “This sounds like it has real promise!”) Some submissions I reject as derivative of already-discussed analogies. Others strike me as unworkable, which prompts a back-and-forth with the student to clarify what their analogy will be. Sometimes this back-and-forth results in the student choosing another word; sometimes it turns out they have just been much more creative than I had thought!

Initial Analogy (PWI)

The instructions for the initial submission of the analogy are as follows:

Write an explanation of induction using your word as an analogy. This analogy must explicitly address each aspect of a proper proof by induction:

1. the base case P(1)

2. the inductive hypothesis P(n)

3. the inductive step for all n, P(n) ⇒ P(n + 1)

4. the conclusion for all n, P(n)

Your write-up must also include some kind of visual depiction. You can draw or create the depiction yourself. You can find it somewhere (in a book, online, etc.). You must credit your source. Your depiction must illustrate all the parts of your analogy.

Peer Feedback

Following the submission (with a break of a day or so), I assign student groups of three to four for peer critique and feedback. The peer feedback instructions ask the evaluators to assess, in a paragraph or two, the clarity, accuracy, relevance, depth, originality, and appropriateness of the peer’s submission.1 I also provide the following guiding questions for peer evaluation:

In addition to peer feedback, I provide feedback of my own to each student.

Revision and Extension

For a grade of “B”, students must revise their submission according to my feedback and that from their peer group. For a grade of “A”, students must, as part of their revision, extend their analogy to encompass the PSI; that is, they must explain how their analogue of P(n+1) depends not merely on P(n), but also on P(n-1), P(n-2), etc.

Reflection

Each stage of the assignment is accompanied by questions in the course reflection journal:

Administration

The entire assignment is administered via my institution’s Google Docs/Google Drive. This is helpful in checking and recording student progress in all aspects of the assignment, but particularly in coordinating peer feedback. The comment feature also allows for back-and-forth discussion within peer groups; this happened spontaneously in some instances, and I plan to encourage it in future uses of the assignment.

Some Examples of Student Work

Student Analogies

While some of the student responses have been only mediocre, I have been quite impressed with the creativity, depth, and attention to detail some students have shown in their work on this assignment. Some salient examples, which I think speak for themselves (analogies are stated in my own words unless expressly quoted):

hammer The base case is setting the nail; the inductive step is somewhat different action of using the rebound from one strike power the next.

phalanx: A phalanx is a military formation of spear-and-shield armed soldiers. Each phalangite carries a shield over the left arm and uses the right arm to fight with a long pike. The inductive content of the analogy that each phalangite (P(n)) provides protection to the soldier to his left (P(n+1)), via the large shield. This leaves the phalangite at the far right of the line (P(1)) in a uniquely vulnerable position; experienced soldiers were placed there to anchor the unit.

gallop: I nearly disallowed this analogy as too close to walk, but ultimately allowed it because the student demonstrated an understanding of PSI. My faith was rewarded in the extension part the assignment:

“For a horse to have made 4 galloping motions, the horse must have made 3 previous motions being the 3rd motion, 2nd motion, and 1st motion.”

This was accompanied by an illustration of the sequence of four ‘motions’ that make up a gallop. My only suggestion to this student was to amend “to have made 4 galloping motions” to “to make the 4th galloping motion”.

axon: “The inductive step P(n) ⇒ P(n + 1) is the step where the signal in one node P(n) causes a change in charge of the next node P(n+1), causing the node P(n+1) to depolarize and thus causing the signal to continue into node n+1.”

Student Feedback and Reflection

Initially, many submissions reflect a surface-level understanding of induction as a sequence of events. Through the peer feedback process (both in giving and in receiving peer feedback), and in reflecting on their own process and work, most students come to a deeper understanding of the inductive idea that the successive predicate P(n+1) depends on prior predicates (in the case of weak induction, just P(n); in the case of strong induction, perhaps other prior predicates also). Here are some examples of peer feedback:

“I think the analogy could benefit from specifying units or layers just to give a bit more conceptual context. In this particular example, it looks like layers of snow would be the most appropriate here. (So, it would just be a matter of changing ‘n’ to ‘n layers’). However, I think the analogy is otherwise easy to follow and is logically sound. It also has a solid foundation for expanding the analogy to complete [strong] induction.”

“Is a one story building a skyscraper? . . . . I would recommend a different picture for the n+1 step because it includes a number of unfinished floors. It is better to clearly outline which part is the n assumption and which part is the n+1.”

The reflection questions also generated some interesting responses:

Among the Intellectual Standards of Critical and Creative Thinking, pick three which might be appropriate to evaluate your work.

“I feel like three words that might be appropriate to evaluate my work on this assignment is precision, depth, and logic. Precision because for this assignment, I would need to be precise on what I am saying on this analogy induction assignment such as being more specific about the proof or giving more details. Depth because for this assignment, I would need to think about what would make this problem hard and how I could do a better job explaining any misconception about my induction proof. Moreover, logic is an important one because I would want the whole proof to make sense.”

Of your peers’ analogies, which did you find most surprising?

“A Dam breaking downstream, as I wasn’t thinking of water as something which could be described as a natural number.”

Describe your process of coming up with a word to use for your analogy.

“I googled all nouns that start with S and looked through the list looking for something that could be repetitive. I considered using sand or seasons. I didn’t use sand because although there is a lot of it there’s not a clear order to it and I didn’t use seasons because although they are successive they repeat. I used the 4 requirements for induction to evaluate each potential candidate.”

Reflection and Conclusion

By having students create their own analogies (rather than relying on one of the handful of standard analogies), I believe this assignment encourages deeper thinking about what induction is. Experience has shown that the students are both more likely to accept the fundamental premise of induction, and also less likely to view it as either a magical incantation that “just works” or a specialized form of reasoning apart from ordinary discourse, than before I started using this assignment.

The peer critique and self-reflective components require students to engage with the details of induction in a less mechanical way than simply assigning many proofs by induction. (This is not to downplay the importance of writing formal inductive proofs, which the analogy assignment is intended only to complement.)

The creative aspects of the assignment—coming up with an analogy and creating or curating visual representations—help connect with students who otherwise may feel left out of the traditional mathematics curriculum, and to encourage all students to engage the creative aspects of thinking that even traditionally-successful mathematics students may not see the importance of in early major courses.

Finally, one important innovation was simply to lengthen the time period over which the assignment runs. By having students critique and revise their work, I ensure they remain engaged with the critical and creative thinking required by it throughout the entire induction unit of the course. This allows for a kind of feedback effect between the assignment and more traditional formal proof writing.

The core idea of the induction analogy assignment, and its implementation, could in principle be adapted to other perennial stumbling-blocks in the mathematics curriculum, for example linear independence or cosets. The advice I would suggest for educators is: whenever you find yourself using the same two or three analogies to explain a topic, try letting your students have a turn at doing the explaining.

References

Bahls, P. (2012). Student writing in the quantitative disciplines: A guide for college faculty. San Francisco: Jossey-Bass.

Bodnar, I. (2006). Aristotle’s natural philosophy. In E. N. Zalta (Ed.), Stanford encyclopedia of philosophy.

Cooper, A. A. (2018). Incorporating critical and creative thinking in a transitions course.

Holden, J. (2015). Why induction is like ice cream: Writing about analogies in discrete mathematics courses.

Katz, V. J. (2009). A history of mathematics. Pearson.

Paul, R., & Elder, L. (2012). The nature and functions of critical and creative thinking. Tomales, CA: Foundation for Critical Thinking Press.

Peano, G. (1960). Formulario mathematico. Rome: Edizioni Cremonese.

Plotker, K. (2009). Mathematics in India. Princeton: Princeton University Press.

Stokes, P. (2005). Creativity from constraints: The psychology of breakthrough. New York: Springer.

  1. These qualities are drawn from a list of thirteen standards of critical and creative thinking which are a running theme in the course (Cooper, 2018). They are adapted from Paul and Elder (2012).↩