# Can someone please explain why this proof using strong induction makes intuitive sense?

Theorem: Every integer $n>1$ is either prime or a product of primes. Proof: By strong induction. Let $n$ be an arbitrary natural number greater than 1. Inductive hypothesis: Assume that for every integer $1<k<n$ that $k$ is either prime or the product of primes. If $n$ is prime then no further work is necessary. If $n$ is not prime, then we can choose some natural numbers $a$ and $b$, such that $n=ab$, where $a<n$ and $b<n$. Thus, by the inductive hypothesis, each of $a$ and $b$ is either prime or a product of primes, and since $n=ab$, it follows that $n$ is a product of primes. $□$

My question: Given only this proof, how do we know that the induction hypothesis is not false? If it was false, then we would not have been able to conclude from it that n must be the product of primes. I understand that that the theorem is true and even that it makes intuitive sense, but given the reason just stated I do not understand why this particular proof can be said to have proved the theorem. Can someone please help me pinpoint the gap in my reasoning?

EDIT: My question is about strong induction in general. The book I am using makes the claim that we do not need to show any base case for a proof by strong induction because it is built into the proof itself. The proof above is an example of the author's understanding of proof by strong induction. If a base case was given in the above proof I think I would have less of an issue with it, but I have a feeling that my question about the assumption not being valid would still linger. Here is a quote from the book that explains why the base case is said to e built in (How to Prove it A structured Approach): "Suppose that we’ve followed the strong induction proof strategy and proven the statement ∀n[(∀k < nP(k)) → P(n)]. Then, plugging in 0 for n, we can conclude that (∀k < 0P(k)) → P(0). But because there are no natural numbers smaller than 0, the statement ∀k < 0P(k) is vacuously true. Therefore, by modus ponens, P(0) is true. (This explains why the base case doesn’t have to be checked separately in a proof by strong induction; the base case P(0) actually follows from the modified form of the induction step used in strong induction.) Similarly, plugging in 1 for n we can conclude that (∀k < 1P(k)) → P(1). The only natural number smaller than 1 is 0, and we’ve just shown that P(0) is true, so the statement ∀k < 1P(k) is true. Therefore, by modus ponens, P(1) is also true."

• Are you having a problem with the concept of strong induction in general? Your question about assuming the hypothesis would apply to any induction proof and not just this particular one. – Erick Wong Nov 2 '16 at 20:09
• @ErickWong See my edit. – IgnorantCuriosity Nov 2 '16 at 20:21
• Thanks. Can you tell me whether you accept the argument for $P(1)$ being true as quoted in your question? If so, where is your problem? Is it that you sense intuitively that one shouldn't be assuming the induction hypothesis? This is a common beginner's objection to regular induction, so I wonder if that's the case here. – Erick Wong Nov 3 '16 at 2:24
• @ErickWong I do indeed sense that we should not be assuming the induction hypothesis, though only because no explicit base case is given. I understand that P(2) is true, but the proof never calls on this fact, so it seems to be making a claim that is never proven true, and then draws a conclusion based on that unjustified claim. As the proof stands, it seems that it is equally likely for P(2) to be false as it is to be true, since nothing in the proof seems to show that it is one or the other. Thus, I do not see why the proof is able to draw the conclusion that it does. – IgnorantCuriosity Nov 3 '16 at 3:24
• But earlier you said that the missing base case was not the only problem you had with the argument. I'm asking about what would still be bothering you even if the base case is added. – Erick Wong Nov 3 '16 at 18:24

## 2 Answers

They should really write something like a base case by saying the induction hypothesis is vacuously true for $n=2$ since there are no integers between $1$ and $2$. That said, in strong induction proofs it's a common pattern for there to be a case in which the induction hypothesis is vacuously true, so it's common for the proof not to explicitly point out that base case.

• Thanks for the reply. Can you possibly explain why my question is not a valid concern in light of this? – IgnorantCuriosity Nov 2 '16 at 20:47
• I think calling this a common pattern is an understatement. Any strong induction hypothesis is of the form "$P(k)$ holds for all $k<n$ in the domain of consideration," which means it will always be vacuously true for the smallest integer in that domain. So leaving out the base case is in some sense entirely justified. – Micah Nov 2 '16 at 20:49
• @Micah, you're right. I had in mind structural inductions or subtle cases where perhaps the hypothesis really requires non-vacuous truth to make the argument go. (That's easier to see in famous false induction proofs.) – Mark S. Nov 3 '16 at 18:50

You may, if you like, define $P(0)$ to be always true. For example, if you wish to prove $\forall n \in \mathbb{N} \ Q(n)$, let $Q'(0)$ be the statement $2+2=4$ and $Q'(n)=Q(n-1)$ for all $n \in \mathbb{N^+}$; then the base case is true by definition and you just proceed with the induction hypothesis. In most cases this is a silly thing to do, but sometimes it might save you from writing one or two sentences more (and this somehow worths the potential misunderstandings by careful readers like you...)

P.S.: Try to think that lacking base case as something obvious, it will be after some experience. Essentially the author suppressed the statement '$P(0)$ is obviously true'.

EDIT: To address the question in your exapmple. What they prove is that $$\forall k \in \{ \text{ integers between } 1 \text{ and } n \} : \ P(k) \Rightarrow P(n),$$ $P(2)$ means that $2$ is an prime or a product of two primes, and it is so obvious that the writer claims it is 'built in the proof', the same way you claim that the implication $x = 10 \Rightarrow x^2+2x-120=0$ is true just by showing that $10$ is a solution of $x^2+2x-120=0$, without mentioning that even if $x \neq 10$ the implication is still true (yes, if you want to be insanely rigorous you should!)

• I still seem to be missing something. Could you possibly direct your response to the question I posed in my post? (The one about not knowing if the induction hypothesis is true). – IgnorantCuriosity Nov 2 '16 at 21:09