16

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?

Mike Shulman
  • 6,560
  • 21
  • 53
  • 5
    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. – Benjamin Dickman Dec 08 '15 at 06:01
  • @MichaelE2 Strong induction is so-called because the inductive hypothesis you get is stronger. That makes the "inductive step" that you have prove a weaker statement, since it uses a stronger hypothesis to get the same result. But the end result is that you have a more powerful tool, since you can get away with proving something weaker in the induction step. (Or did I misunderstand you?) – Mike Shulman Dec 09 '15 at 04:54
  • 1
    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. – KCd Dec 09 '15 at 05:48
  • 1
    @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$. – DRF Dec 09 '15 at 09:20
  • 1
    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. – Mike Shulman Dec 09 '15 at 10:32
  • 1
    @MichaelE2 your point seems to be that the statement "SI holds for all predicates" is weaker (in some sense) than the statement "WI holds for all predicates". But I wouldn't want to encourage my students to even think about that question; I think it is too "meta" for their level of understanding and would just confuse them. When learning induction, what we work on is using it to prove other things, not analyzing the proof-theoretic strength of induction as an axiom. – Mike Shulman Dec 09 '15 at 19:14
  • 1
    I don't understand the vocabulary used. I explain why.

    Induction shows the validity of one property $P(n)$. Your property can be $P(n) = \text{"Something for a single natural n"}$, but the something can be for example the set of expressions for all $k$ such that $k \leq n$. This makes absolutely no difference.

    Real problems can come with inductions with several natural naturals properties $P(m,n,\dots)$

     – projetmbc Dec 15 '15 at 08:41
  • @projetmbc as has been said, the two forms of induction are logically equivalent (except perhaps in very weak ambient foundations); looking at all $k\le n$ is indeed how you prove one from the other. But pedagogically they are different methods. – Mike Shulman Dec 15 '15 at 22:48

3 Answers3

7

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.

Mikhail Katz
  • 2,242
  • 15
  • 23
  • 2
    Okay. I'm looking for experience from someone who has tried teaching strong induction first. – Mike Shulman Dec 10 '15 at 19:49
  • 1
    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. – Cort Ammon Dec 11 '15 at 03:49
  • 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. – Taladris Dec 11 '15 at 11:31
  • @Taladris, the conceptual step from 1 to 2 (or 3, or...) is just less than from 1 than "all less than...". Concrete, fixed size set vs set of indeterminate, growing size. – vonbrand Dec 23 '15 at 12:01
5

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.

David E Speyer
  • 5,322
  • 20
  • 32
  • 1
    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. – Mikhail Katz Dec 15 '15 at 16:09
  • 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))$." – David E Speyer Dec 15 '15 at 16:15
  • 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. – David E Speyer Dec 15 '15 at 16:17
  • You will only find very few students who ask "what is a statement" or "what is a set", even with the high level students PROMYS gets. Of course, it is fun to talk to those who do! – David E Speyer Dec 15 '15 at 16:18
  • 1
    David, I agree with everything you wrote, except the statement that those are logically the same. – Mikhail Katz Dec 15 '15 at 16:23
  • Fair enough, I've edited a note to that effect. – David E Speyer Dec 15 '15 at 16:29
  • 2
    There is no obligation at stackexchange to keep copies of old versions by crossing out edited text :-) – Mikhail Katz Dec 15 '15 at 16:55
  • Thanks, this is very helpful, particularly the additional examples where strong induction is required. I agree that there's a certain attraction to the well-ordering version, but I really dislike how it forces you to insert double negatives and do everything as a proof by contradiction. That's probably partly just my own affection for constructive logic, but I think even for the purely classical mathematican there is inelegance and potential for confusion in an unnecessary proof by contradiction. – Mike Shulman Dec 15 '15 at 22:55
  • The positive/constructive version can of course also be formulated using sets rather than statements: if a set $S$ of natural numbers has the property that if it contains all $k\le n$ then it contains $n$, then it is all of $\mathbb{N}$. I personally don't object to talking about statements like $P(n)$; the book I use (Velleman, "How to prove it") spends a while discussing statements of this sort at the beginning, and it pays off already when describing the proof rules for working with quantifiers, before we even get to induction. – Mike Shulman Dec 15 '15 at 22:59
  • Another advantage of the "statements" version is that it matches the pattern of definition by recursion. You define the $n$th Fibonacci number in terms of the previous Fibonacci numbers, then you prove something about the $n$th Fibonacci number by assuming the same thing about the previous ones. You don't define the $n$th Fibonacci number by showing that the set of undefinable Fibonacci numbers has no least element. (You can of course deduce definition by recursion from the well-ordering property too, but it's more work.) – Mike Shulman Dec 15 '15 at 23:24
  • @MikeShulman, you left me in the dust there. What does double negation have to do with it? Your question does not say anything about this. I am all in favor of constructive proofs, but I don't see how strong induction is more constructive than ordinary one. This is a very interesting idea but I haven't caught on yet. – Mikhail Katz Dec 23 '15 at 12:35
  • @katz when doing a proof by well-ordering, instead of proving that $\forall n, P(n)$, you consider the set of all $n$ such that $\neg P(n)$ and show that it has no least element, hence is empty; thus $\neg \exists n, \neg P(n)$. To get from there to the desired $\forall n, P(n)$ involves canceling a double-negation, which is non-constructive. – Mike Shulman Dec 23 '15 at 22:56
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.

fedja
  • 3,809
  • 7
  • 20