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

341 Views Asked by At

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."

2

There are 2 best solutions below

3
On

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.

1
On

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!)