# Base Case Strong Induction Terrence Tao question

Terrence Tao formulates strong induction as follows: "(Strong principle of induction). Let $$m_o$$ be a natural number, and let $$P(m)$$ be a property pertaining to an arbitrary natural number 𝑚. Suppose that for each $$m \geq m_0$$, we have the following implication: if $$P(m')$$ is true for all natural numbers $$m_0 \leq m' \lt m$$, then $$P(m)$$ is also true. (In particular, this means that $$P(m_0)$$ is true since in this case, the hypothesis is vacuous.) Then we can conclude that $$P(m)$$ is true for all natural numbers $$m \geq m_0$$. "

Since we are assuming that $$P(m')$$ is true for all $$m_0 \leq m' \lt m$$. Where in this statement does it suggest to prove the base case first? To me all its suggesting is to simply suppose $$P(m')$$ is true for all $$m_0 \leq m' \lt m$$ without proving a base case?

• one classic example for understanding the various ingredients in this description of strong form of mathematical induction is the fundamental theorem of arithmetic which says that every positive integer $n \ge 2$ can be written as a product of primes which is also unique up to rearrangement; here you have to verify the result for $n=2$ as the base case, and then it is easy to see that if we consider the result to be true for each $k \in \{2,3,......, m \}$ for some $m$ then $m+1$ is either a prime or divisible by a prime; using the (strong) induction hypothesis then proves the claim. Mar 25, 2021 at 0:47

Well, it seems to be a bit weird. But he is saying that the base case comes in when you prove the inductive condition when $$m=m_0$$. Which is a bit strange because in this case the hypothesis is vacuous, so essentially you have to prove the base case. So the author covers this point in the part " (In particular, this means that $$P(m_0)$$ is true since in this case, the hypothesis is vacuous)".
• @JCAL no, it means that the first inductive step is the same thing as the base case, because you are going from the empty set to the set containing only $m_0$. So you need to prove the base case in the same way it is proved with normal induction. Mar 25, 2021 at 21:08
This is often a useful approach for using induction to prove a statement's contrapositive. Assume toward a contradiction that $$P(m)$$ is false for some $$m$$. Then there must be a least $$m$$ for which it is false. Tao's implication, though, demonstrates that if $$P(m')$$ is true for all smaller $$m'$$, then it must also be true for $$P(m)$$, which means that $$m$$ was not in fact the smallest possible counterexample, establishing a contradiction.
Thus, the set of counterexamples to $$P(m)$$ has no least element and therefore must be empty.