15
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ I do not have an answer, but I was wondering about a similar question a few days ago. The context was proving the fundamental theorem of arithmetic: The existence part, if you wish to avoid proof by contradiction (i.e., the well-ordering route), proceeds by induction, but it is strong induction. $\endgroup$ – Benjamin Dickman Dec 8 '15 at 6:01
  • 1
    $\begingroup$ @DRF the well-ordering argument that I know is exactly as strong as strong induction. Unless you meant to teach transfinite ordinal numbers at the same time as they are first learning about induction, which seems ridiculous to me. $\endgroup$ – Mike Shulman Dec 8 '15 at 17:34
  • 1
    $\begingroup$ In practice most uses of induction in undergraduate math courses require only ordinary induction: the previous case is enough to derive the next case. (Counterexamples include the existence of prime factorization and theorems in group theory proceeding by induction on the order of the group.) I bet if you tried introducing induction only as strong induction then someone would ask why you have to assume all previous cases when the initial examples of induction only involve the previous case, if only because almost any reference they look up on induction will introduce it that way. $\endgroup$ – KCd Dec 9 '15 at 5:48
  • 1
    $\begingroup$ @MikeShulman Weak and strong inductions are also equivalent under standard assumptions over the natural numbers. My point was that the well-ordering argument is somewhat more general. I suppose at the point you would tend to teach induction for the first time this is not particularly useful given that the only well ordered set the students will know will be $\omega$. $\endgroup$ – DRF Dec 9 '15 at 9:20
  • 1
    $\begingroup$ Yes, of course they're all equivalent, but I think strong induction and well-ordering are "more directly" equivalent: given a proof using one, modifying it to use the other instead is really just a matter of rearrangement (and inserting some negations). I don't agree that the "least counterexample" version of well-ordering is more general either; induction over any well-ordering can also be phrased in a way analogous to strong induction. $\endgroup$ – Mike Shulman Dec 9 '15 at 10:32
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you speaking from experience or imagination? I was hoping to hear from experience. $\endgroup$ – Mike Shulman Dec 10 '15 at 16:00
  • 1
    $\begingroup$ @MikeShulman: from experience, to the extent explained in the answer. $\endgroup$ – Mikhail Katz Dec 10 '15 at 19:08
  • 1
    $\begingroup$ Okay. I'm looking for experience from someone who has tried teaching strong induction first. $\endgroup$ – Mike Shulman Dec 10 '15 at 19:49
  • 1
    $\begingroup$ I can't say I've tried to teach this, but as someone whose mind naturally works in the way strong induction works, I can say that the "ordinary" induction does provide a lot more focus for where to start from. Ordinary induction lets you do everything in algebra land, while strong induction requires you to jump over to logic and predicates every time you want to do anything. Of course we both know they're effectively the same, but they have a different feel. Its like how in shooting, you are told to aim for a point on a target rather than just trying to hit the box. $\endgroup$ – Cort Ammon Dec 11 '15 at 3:49
  • $\begingroup$ Do you use in high school examples of sequences that are defined by a recursive expreaaion of depth 2 (not sure of the terminology) like Fibonacci sequences? That's a nice situation where ordinary induction may not be sufficient. $\endgroup$ – Taladris Dec 11 '15 at 11:31
5
$\begingroup$

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 is the older program, uses the same model.

More precisely, in the 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.

$\endgroup$
  • $\begingroup$ I am not sure these two statements are logically the same. The second one can be formalized in Peano axioms but the first one may be problematic. $\endgroup$ – Mikhail Katz Dec 15 '15 at 16:09
  • $\begingroup$ This is the usual issue about first versus second order logic. If I were to put the first statement into PA, I'd make an axiom schema: "For every statement $P$, we have $\exists_x P(x) \implies (\exists y : P(y) \vee (\forall_z P(z) \implies z \geq y))$." $\endgroup$ – David E Speyer Dec 15 '15 at 16:15
  • $\begingroup$ Putting it into formal logic like that, of course, destroys any readability advantage of the first formulation. What I LIKE about the first formulation is that I think it flows nicely with sets. The second one, with sets, would say something like "For every set $S$, if $\{ m : m < n \} \subset S$, then $S = \mathbb{Z}_{\geq 0}$," which I do think is as nice. $\endgroup$ – David E Speyer Dec 15 '15 at 16:17
  • 1
    $\begingroup$ David, I agree with everything you wrote, except the statement that those are logically the same. $\endgroup$ – Mikhail Katz Dec 15 '15 at 16:23
  • 1
    $\begingroup$ There is no obligation at stackexchange to keep copies of old versions by crossing out edited text :-) $\endgroup$ – Mikhail Katz Dec 15 '15 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.