Teaching strong induction instead of induction

Question

After teaching induction and then strong induction (i.e. the version where you assume $\forall k<n, P(k)$ and prove $P(n)$), one of my students asked why we ever use ordinary induction, since strong induction is stronger. I said that some people just find it simpler to think about, and often it's good enough.

But it made me wonder: would it be ridiculous to teach strong induction right off the bat, and only then specialize it to ordinary induction?

A possible advantage of this that I can see is that it would separate the "inductiveness" from the "division into cases" aspect of ordinary induction. There's something "cleaner" about strong induction: we only have to give one method, and it works for all natural numbers. Then we can just say well, it happens often that when doing a (strong) induction, we have to divide into cases based on whether $n=0$ or $n>0$.

A possible disadvantage I can see is that it might be hard to find very many examples of strong inductions that don't require such a case split.

Has anyone ever taught induction this way? If so, was it a success or a failure?

Answer 1

The main problem with teaching strong induction as you define it is its logical complexity. What you seem to be doing is replacing quantification over a single integer by quantification over a set of integers (namely all those less than $n$). This is of course only appearances but appearance of difficulty can be daunting to a beginning student also.

To respond to Mike's question, in my experience as a teacher I only taught the ordinary induction, never "strong induction." In my experience as a highschool student, I recall first encountering "strong induction" and finding it rather confusing. In retrospect, I feel this was because "all integers smaller than $n$" is harder to encompass in one mind's eye than "$n-1$". This only resembles the distinction between first and second order quantification, but psychologically may involve the same kind of barrier.

Just a quick additional comment: "strong induction" not only seems to involve added complexity because of additional quantification, but actually does involve additional quantification, though of course only of first order. Namely, you do have to say "for all" integers less than $n$. This could be compared to the difference between Cauchy's infinitesimal definition of continuity and the epsilon-delta paraphrase introduced by Weierstass, with its hair-raising (for students) quantifier alternations.

Answer 2

I'm not sure how much this experience is worth, because it is such a different environment than the standard college proof environment, but the high school math program PROMYS does this. I believe Ross, which an older program that PROMYS is strongly influenced by, uses the same model.

More precisely, in the first two weeks of PROMYS, students are challenged to prove statements about integers and allowed to keep a list of what axioms they choose to use. In the second week, we start discussions about which axioms might be redundant or better in one way or another. (The statement $x \times 0 = 0$ is on a lot of axiom lists at first, but is eventually realized to follow from the other ring properties.) By the end of the second week, we converge to the standard PROMYS axioms of $\mathbb{Z}$ which are:

$\mathbb{Z}$ is a commutative ordered ring, and every nonempty set of positive integers has a least element.

Here are some problems which occur during the first two weeks, and are substantially easier with strong than weak induction:

• If $x$ and $y$ are positive integers and $x|y$, then $x \leq y$.

• If $a$ is an integer and $b$ a positive integer, there exist integers $q$ and $r$, with $0 \leq r < b$, such that $a = qb+r$.

• Every integer $\geq 2$ is divisible by a prime.

• Every integer $\geq 2$ can be written as a product of primes.

• If $a$ and $b$ are integers, then there are integers $x$ and $y$ such that $ax+by$ divides $a$ and divides $b$.

We always get a number of students who have already seen standard induction in high school, so I got used to (a) showing how to deduce strong induction from standard induction and (b) showing how strong induction proofs of the above statements were nicer to write than standard ones. I also think that PROMYS made a good choice in choosing the phrasing:

Every nonempty subset of positive integers has a least element.

rather than

If you can prove the implication $\forall_{m <n} S(m) \implies S(n)$ then you can prove $\forall_n S(n)$.

They are logically the same, but I think that thinking about manipulating statements $S( \ )$ like that is confusing. In the comments below, katz points out that there are two differences between the statements: I have switched from first order to second order logic, as well as taking the contrapositive. See the discussion below.

However, I would caution that these are really smart and dedicated kids, so they probably aren't a good model for a college class.

Answer 3

Note that the "strong induction" is not even the most general induction scheme you can design. A high school level example is the proof of the AM-GM inequality for $n$ positive numbers where you can first use the two-number version to get it for $n=2^k$ and then to descend from any $n$ to any smaller $n'$ by setting the last $n-n'$ variables to be the AM (or GM, if you prefer) of the first $n'$ ones.

I usually start teaching induction with drawing a long train on the board and saying something like "the engine starts to move; how do we know that the rest of the cars will follow?". The underlying idea is that each car is hooked to the previous one and that is the classical $n-1$ to $n$. Then, after reasonably many examples of that one, I ask the students how else we can link the cars to ensure that the whole train moves, opening a Pandora box with strong induction and all other types. You should be a bit careful here because the train analogy is not absolutely perfect, but one can usually get a clear idea and work out the details from it nevertheless.