This is a new exercise introduced in the latest ($4$th) edition of the book and thus I haven't found a proof of this anywhere.
$\textit{Exercise}$ $2.2.7$. Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m)$ is true, $P(m++)$ is true. Show that if $P(n)$ is true, then $P(m)$ is true for all $m ≥ n$. (This principle is sometimes referred to as the principle of induction starting from the base case $n$.)
Where $n++$ denotes the succesor on $n$. The only Peano Axiom I called upon was his fifth. But here is a full list of everything that we can use here.
Axiom $2.5$. (Principle of mathematical induction). Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number $n$.
I tried something but I can't get it all to work. We assume that $\forall m\left(P(m)\implies P(m++)\right)$. We define "$Q(n):P(n)\implies\forall m\geq n$, $P(m)$" and use induction on $Q$. The base case $n=0$ together with our assumption tells us that $[P(0)\land (\forall m\left(P(m)\implies P(m++)\right)] \implies \forall m\geq 0$, $P(m)$ which is nothing more than Axiom $2.5$.
Now suppose inductively that $Q(n)$ is true i.e., $P(n)\implies \forall m\geq n$, $P(m)$. We want to show that $P(n++)\implies \forall m\geq n++$, $P(m)$. Assume that $P(n++)$ is true, then by our assumption $P((n++)++)$ is also true. But I need something to use to prove that $P(n)$ is true so that I get $\forall m \geq n, P(m)$. So that I can say $[P((n++)++)\land (\forall m\geq n$, $P(m))]\implies \forall m\geq n++$, $P(m)$ which would complete the induction. But I'm not sure how to get $P(n)$.
Is it valid to assume $P(n)$? Something like $P(n)\implies (P(n++)\implies P((n++)++))\land(\forall m\geq n$, $P(m))]\implies \forall m\geq n++)\implies Q(n++)$ ? I'm not sure if that reasoning makes sense. Or maybe we can use the base case of normal induction?
Best Answer
Define $Q(m) := P(n + m)$. Note that, in particular, $Q(0) = P(n)$.
We are looking to prove the statement "Whenever $P(m)$ is true, $P(m++)$ is true. If $P(n)$ is true, then $P(m)$ is true for $m \geq n$", and we will do so via induction on $Q$.
For the base case, we are already told we can assume $P(n)$ is true, so $Q(0)$ is true.
Then for the inductive step, we have $Q(m) = P(n + m) \implies P((n + m)++) = P(n + (m++)) = Q(m++)$. But since $Q(m) \implies Q(m++)$ and $Q(0)$, then $Q(m)$ is true for every natural $m$.
Now, consider $P(m)$ for $m \geq n$. By the ordering principle, this means that $m = n + a$ for some natural number $a$. That means we can write $P(m) = P(n + a) = Q(a)$, but by our inductive proof $Q(a)$ is true for any natural number $a$, therefore $P(m)$ is also true, and that completes the proof.
If you don't want to use the ordering principle, then an approach like yours applying induction on $n$ is essentially the same thing, but you missed that you are indeed meant to include $P(n)$ in your assumptions.