16
$\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$
8
  • 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$ Dec 8, 2015 at 6:01
  • 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, 2015 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, 2015 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$ Dec 9, 2015 at 10:32
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 9, 2015 at 19:14

3 Answers 3

7
$\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$
4
  • 2
    $\begingroup$ Okay. I'm looking for experience from someone who has tried teaching strong induction first. $\endgroup$ Dec 10, 2015 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, 2015 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, 2015 at 11:31
  • $\begingroup$ @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. $\endgroup$
    – vonbrand
    Dec 23, 2015 at 12:01
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 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.

$\endgroup$
12
  • 1
    $\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$ Dec 15, 2015 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$ Dec 15, 2015 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$ Dec 15, 2015 at 16:17
  • 1
    $\begingroup$ David, I agree with everything you wrote, except the statement that those are logically the same. $\endgroup$ Dec 15, 2015 at 16:23
  • 2
    $\begingroup$ There is no obligation at stackexchange to keep copies of old versions by crossing out edited text :-) $\endgroup$ Dec 15, 2015 at 16:55
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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