2

I'm reading Gallian's "Contemporary Abstract Algebra", here there are the following principles of mathematical induction from the aforementioned book:

enter image description here

enter image description here

Now, there is this proof of the fundamental theorem of arithmetic:

enter image description here

enter image description here

And then there is this commentary:

enter image description here

Why is the proof with the second principle of mathematical induction "more natural" than the proof with the first principle of mathematical induction? I don't see what is the difference of the proofs produced with the first and second principles of mathematical induction. It's not clear to me why we can't produce the same proof in there with the first principle of mathematical induction. Can you help?

Red Banana
  • 23,956
  • 20
  • 91
  • 192
  • Note that the first principle is typically called "induction", and the second "strong induction". This is the usual terminology you'll see in other texts. – Mark Saving Sep 28 '21 at 19:54
  • 1
    Can you give a quick writeup of how the proof would go with the first principle? This will illuminate where the process goes wrong. – Mark Saving Sep 28 '21 at 19:55
  • @MarkSaving Hm... I don't think it even works with the 1st principle. So it's not about 2nd principle being more natural, it's just that the 1st principle doesn't even work (or makes the induction step much harder). – peter.petrov Sep 28 '21 at 20:04
  • @MarkSaving Can't we just repeat: Suppose $2\in S$ and $n\in S$, if $n+1$ is prime, then $n+1 \in S$ and if $n+1$ is composite, then $n+1=ab$ with $1<a,b<n$? – Red Banana Sep 28 '21 at 20:28
  • 1
    @RedBanana Yes, but what are you going to do with the information $1 < a, b, < n$? You can't use the inductive hypothesis to prove that $a$ and $b$ are the product of primes - the inductive hypothesis is that $n$ is the product of primes. – Mark Saving Sep 28 '21 at 20:32
  • @MarkSaving Ah, I think I see now: Even if I could do that way, I'd be saying stuff about integers $\geq n$ but there could be integers between $2$ and $n$ that weren't proved to have the given property? – Red Banana Sep 28 '21 at 20:39
  • 1
    @RedBanana This is almost right. Formally, we must prove the statement $\forall n \in S (n + 1 \in S)$. This means that we are only allowed to assume $n \in S$ when proving $n + 1 \in S$. This does not allow us to conclude that $a, b \in S$ just because $a, b \leq n$. – Mark Saving Sep 28 '21 at 20:43

2 Answers2

4

The proof does not work with the first principle (often called "weak induction", as opposed to "strong induction" for the second principle) because the first principle only assumes the inductive hypothesis for the immediate predecessor.

But this is not enough for the argument given: when we reduce to cases and conclude that either $n+1$ is prime or else $n+1$ factors as $ab$ with $a, b \leq n$, we cannot make further progress on the second case without assuming the inductive hypotheses for all $k \leq n$ (so that, in particular, we can capture $a$ and $b$).

As an aside, it baffles me that so much pedagogical attention is paid to the distinction here, when we can simply always use strong induction and then never have to worry...

user3716267
  • 1,165
2

I suggest you don't memorize these formalities.
I've never heard of these terms "1st principle" and "2nd principle" yet I've read lots of proofs using both forms and I can understand them just fine.

Both forms are natural. It's all about the problem at hand.

Sometimes to prove something about $n+1$, it is just not sufficient to know that that same thing holds for $n$. But in these cases it may turn out that if you assume that thing (statement) holds for all integers k: $1 \le k \le n$, then you can easily prove it for $n+1$. That's exactly what that commentary is saying.

That 2nd form may be called strong induction but I think in a way it's weaker. Why? Because your assumption is stronger hence your job when doing the induction step is in fact easier.

But OK, I guess they call it strong induction exactly because the assumption is stronger, not because the process itself is stronger.

You can even have forms of "multidimensional induction" but anyway... I guess that's another topic.

peter.petrov
  • 12,568