I am studying analysis 1 by Tao. And i am trying to prove strong induction.
Strong induction: Let $m_0$ be a natural number,and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m≥m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0≤m'<m$, then $P(m)$ is also true.(In particular, this means that $P(m_0)$ is true, since in the case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m≥m_0$.
Proof:1: Assume to the contrary that $P(m)$ is not true for some $m ∈ ℕ $. Let $n$ be the least natural number s.t $P(n)$ is not true. If $m≤m_0$ , then the hypothesis, for all $m'$ s.t $m_0≤m'<m$ implies $P(m')$ is vacuous. Thus $P(m_0)$ must be true for all $m≤m_0$. So we have $n>m_0$. By assumption $P(m')$ ka true for all $m'$ s.t $m_0≤m'<n$, thus we deduce that $P(n)$ is true. A contradiction.
Proof:2: We use induction on $m$.
Base case: If $m=m_0$, then $P(m_0)$ is true, since hypothesis is vacuous.
Inductive case: Assume inductively that the statement is true for some $k≥m_0$, i.e. for all $m'$ s.t $m_0≤m'<k$ implies $P(m')$ thus we have $P(k)$. We shall show statement is true for $S(k)$. By inductive hypothesis we see for all $m'$, $m_0≤m'≤k<S(k)$ we have $P(m')$ which implies $P(S(k))$, by assumption, as desired. This closes the induction.
$S(k)$ denotes successor of $k$.
Question:
(1) Are both proofs correct? If not, then please mention.
(2)In the book Tao gives hint "define $Q(n)$ to be the property that $P(m)$ is true for all $m_0≤m<n$". Did author give the hint because to not get confused in wording?
(3) I don't know why i feel less confident about my proofs. I feel both are incomplete and not rigours proofs. Is it common to feel like this?
Thank You.