2
$\begingroup$

I'm currently studying mathematical induction and this is the definition for strong induction presented in Terrence Tao's Analysis book.

Proposotion 2.2.14 Let m0 be a natural number and let P(m) be a property pertaining to an arbitrary natural number m. Suppose that for each m≥m0, we have the following implication: if P(m′) is true for all natural numbers m0≤m′<m, then P(m) is also true. (In particular, this means that P(m0) is true, since in this case, the hypothesis is vacuous.) Then we can conclude that P(m) is true for all natural numbers m≥m0.

I've also seen this other definition for strong induction:

Let A⊆N such that for all n,m∈N we have (m<n ⟹ m∈A) ⟹ n∈A. Then A=N.

In both cases, it seems to be that these definitions do not include as a separate case the "base case". But my question is if I still need to show its truth.

So for example first looking at Terrence Tao's definition if we wanted to prove something by strong induction, we would let m0, m∈N with m≥m0 and assume ∀m' (m0≤ m'≤ m ⟹ P(m')) and we would want to show P(m).

In the case m' = m0, because the hypothesis is vacuously true, we must show P(m0) is true in order to have a true implication.

Now in the second definition, it happens the same, let n be the smallest element of the set, then the hypothesis would be vacuously true and we would have to prove P(n) is true in order to have a true implication.

Is my reasoning about our need to prove a base case correct?

Thanks in advance for your answers.

$\endgroup$
3
  • 2
    $\begingroup$ "$m_0$" and $"n"$ are the base cases! $\endgroup$
    – user247327
    Nov 3, 2021 at 0:57
  • $\begingroup$ @user247327 I think in the second definition, the base case is $n$ being the smallest natural number $($so $0$ or $1)$ $\endgroup$
    – Henry
    Nov 3, 2021 at 1:11
  • $\begingroup$ @MMMagician I think your reasoning is correct, that means that also the definitions you are analyzing are correct $\endgroup$
    – Tortar
    Nov 6, 2021 at 8:12

1 Answer 1

3
+50
$\begingroup$

Although Terry Tao's version of strong induction does not treat the base case of m0 as a separate case, it is nevertheless a part of the hypothesis

"If P(m') is true for all natural numbers m0 ≤ m'< m, then P(m) is also true"

that must be verified in order to conclude that

"P(m) is true for all natural numbers m ≥ m0".

Specifically, the m0 case is when m' = m0.

Whether you prove this separately or together with the rest of the hypothesis is a matter of convenience, but it must be proven, one way or the other, in order to use the strong induction principle.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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