Mathematical Induction

To engage students in the formal method of mathematical induction, the instructor introduced the six scenerios shown in the image below. Students considered whether the given information was enough to determine the proposition, P, was true for all positive integers. 

Following their initial evaluations (as notated in the image), the class compared the first and fifth scenarios. Note that scenario 1 includes the supposition of the theorem to be proved. In contrast, scenario 5 assumes only the implication that P(k) implies P(k+1). 

The instructor then used the class discussion, comparing scenarios 1 and 5, to launch group discussions in which students at each table discussed the logic behind scenario 5, as well as scenario 6.

When the class gathered back together to discuss scenario 5, one student shared that the given information does not say whether P(2) is true, but rather "if P(2) is true, then P(3) is true." Note, she is making a distinction here about the truth of the proposition for a given value and the truth of the implication for that value.

The instructor then illustrated this distinction in the drawing shown in the image above. The drawing represents the truth of particular values of n (or k) with filled in circles; and the truth of an implication, from one value to the next, with an arrow.

To further challenge the students on the potential conflation between the truth of the hypothesis and the truth of an implication, the instructor asked them to consider the following implication: "If for any k, k=k+1, then k+1=k+2." The video below comes from the Squre table, as they attempted to make sense of this implication (whose implied hypothesis is obviously false). 

After students had gained experience making informal inductive arguments, the instructor introduced formal proof by induction. She introduced it in two parts: (1) the base case, and (2) the inductive implication (see image below). 

In the following video, the instructor asks students how they might prove the inductive implication, which is universally quantified. When a student in the class suggested that the proof might begin by assuming P(k), the instructor pushed them to define and quantify k, as a fixed but arbitrary value of n.

In the next class, the instructor challenges students to complete a proof by induction, in their groups. So that the content of the proof would not interfere with the challenge of the new proof method, she chose a familar context. Students were to prove (by induction) that, for all positive integers, n, 3 divides 2²ⁿ-1. The video below shows the Triangle group working toward a proof. Note that the students quickly agree that they should assume P(k) is true, they question whether they need to explicitly state that. Also, although they have explicitly (and universally) quantified the inductive implication, they don't quantify k in the inductive assumption.

During whole-class discussion of the task, the instructor presses students to attend to the quantification of this new variable, k, that they have introduced. When pressed, students seem to agree that k should serve as a "fixed but arbitrary" value.

Typically in introducing proof by mathematical induction, textbooks and instructors will introduce n as a univerally quantified variable. For instance, they will say "we need to prove P(n) for all n," or "for all n, P(n) implies P(n+1)." However, this instructor took a different approach, introducing n as a fixed but arbitrary value to be reached by mathematical induction. Thus, in making the inductive argument, from the base case to this fixed value of n, a new variable was needed. The video shown below illustrates the approach in a class discussion about the roles and values of variables.

In the task shown below, the instructor presents the issue directly to the students, to work on in groups: "why do you think we use k instead of n?" The videos below show the Circle, Triangle, and Hexagon groups responding to this task.

The Triangle group:

The Hexagon group:

The instructor elicited consideration of the PUG in two different ways: first in a group task, asking students to consider the general structure of "for all" statements; second in a whole-class discussion about how students might constructively prove "for all" statements. Both of these efforts seemed effective, as students suggested "for all values" meant the thing as "for any arbitrary value." 

Once students had an intellectual need for the PUG (as in contructively proving universally quantified statements), the instructor introduced PUG as a principle. 

Although students did see the intellectual need for PUG and seemed to accept the instructor's suggestions for using it to prove universally-quantified statements, the principle still appeared to be problematic for students at times, as illustrated in the following whole-class discussion.