Thoughts on teaching induction

I don’t plan on doing this very often, but I thought I’d re-post one of my earlier blog posts—one that I wrote a year ago, when I had many fewer readers. Now is an appropriate time for me to re-post it because I am currently teaching induction in my Discrete Mathematics course. Enjoy.

In their article “Some observations on teaching induction,” (MAA Focus, May/June 2008, pp. 9–10) Mary Flahive and John Lee give tips on how to teach induction. For a variety of reasons, they encourage professors to downplay proofs of theorems such as the “baby Gauss” formula

$\displaystyle\sum_{k=1}^n k=\frac{n(n+1)}{2}$ for all $n\ge 1$ .

Indeed, I have noticed that students can master such proofs pretty quickly, yet not really understand proofs by induction. The proofs of sum and product formulas are pretty mechanical: prove the base case $P(1)$ , state the inductive hypothesis $P(k)$ , write the sum/product for the case $n=k+1$ , pop off the $k+1$ st term, substitute the $n=k$ formula, and do a little algebra to prove $P(k+1)$ . All the problems look the same and they figure out the pattern pretty quickly.

Then in later courses they have lot of difficulty with proofs by induction.

This semester I decided to teach induction differently (I was teaching Discrete Mathematics, our gateway course to the mathematics and computer science majors). I started with sum/product proofs, but quickly moved on to other examples that were not of this standard type. Here are some that I gave.

1. Interval of integers. An interval of integers is a set of the form $~[a,b]=\{a,a+1,...,b-1,b\}\subset\mathbb{Z}$ (where $a\le b$ ). If $I$ is an interval of integers containing $n$ elements, how many subintervals does it contain? Prove your result using induction.

2. Matchstick squares I. It is possible to make a square with four matchsticks and to make two adjacent squares using seven matchsticks. How many matchsticks does it take to make line of $n$ squares? Prove your result using induction.

3. Matchstick squares II. In the example above define a joint to be a spot where two or more matchsticks meet. One square has four joints and two squares have six joints. How many joints will $n$ adjacent squares have? Prove your result using induction. (I had them do (2) for homework and put (3) on their exam.)

4. Trominoes. Start with a board consisting of an $n\times n$ grid of squares and a pile of trominoes (el-shaped pieces that cover 3 squares each). Pick any square on the board and color it black. The question is: is it possible to tile the entire board except the blackened square with trominoes? The answer, in general, is “no.” Find a counterexample. However, if the board is $2^k\times 2^k$ then it is always possible. Prove this by induction. (Here are some printable trominoes puzzles and pieces. Here is a Trominoes applet to play with.)

5. Let us teach guessing. I spent one class showing George Polya‘s 1965 video Let us Teach Guessing (now out on DVD). Polya leads his class through a discussion of the question: five planes divide space into how many regions? It is a fascinating problem with a surprising conclusion. At the end of the video the students know the answer to that question and can find the number of regions into which $n$ planes divide space. For homework I have them prove this result. I was inspired to try this by David Bressoud who wrote about it in his Launchings column for the MAA.

It was really enlightening to grade these problems. For example, for the matchstick problem, many of the students wanted to give a purely algebraic proof—one that never referred to the matches at all. They applied their formula in the base case and said it worked without talking about how many matches it takes to make a single square. Then they tried to prove the inductive case without ever referring to a line of $k$ or $k+1$ squares—they wanted to do it purely from the equations. When I spoke with them about it afterward they said that they didn’t think that the matches and squares were mathematical enough, but the algebra was. Another group of students proved the inductive case “backward”—they started with the formula for $n=k+1$ and tried to conclude something about the squares.

By the end of the unit on induction they seemed to have a pretty good grasp of the proof technique. I’m curious to see how well this group of students will do as they go through the major.

One Comment

Maximilian says:

October 24, 2009 at 9:18 pm

I couldn’t agree more. I’m myself a student that was taught induction in a “mechanical way”. So I can solve the typical induction problem like the “Baby Gauss” formula quite fast and easy, but give me something a bit more complex, and I’m done for.

By the way, very nice blog.
Regards.
Max, an argentinean math student.

Comments are closed.

Share this:

Like this:

Related

One Comment