Let $P(n$) be a statement about positive integers and
- $P(1)$ is true
- For every positive $k \in \mathbb{N}$, if $P(k)$ is true for all $k<m$, then $P(m )$ is true
Then we may conclude that $P(n)$ is true $\forall n \in \mathbb{N}$
Now I assume for the sake of contradiction that this is not the case. So, there exists some $n_0$ such that $P(n_0)$ is false. I collect all these in a set, say $S = \{ n \in \mathbb{N}|\text{$P(n)$ is false} \}$, so by the well-ordering principle it has least element, say $r$. So $P(r)$ is false and $r$ is minimum. So for all natural numbers less that $r$, $P(n)$ is true. But by hypothesis if $P(n)$ is true for all numbers less than $r$, then $P(r)$ is also true. This is a contradiction. Thus strong induction is valid.
I am not sure if this is correct. Could someone review my proof?
Just to remove it from the list of unanswered questions. Yes your proof is perfectly fine. It's indeed correct.