Proof by Induction Without Using Inductive Hypothesis or Peano Axioms

inductionpeano-axioms

I thought the following was the case:
In a proof by induction, one must use the inductive hypothesis at some point. Otherwise, the proof is either a) wrong or b) correct yet needn't be written in the form of an induction.

Here's a solution to an exercise from Tao's Analysis I book in which an inductive proof is performed that does not utilize the inductive hypothesis:
https://taoanalysis.wordpress.com/2020/03/16/exercise-2-2-2/

Indeed, there is a second proposition in Tao's book that uses inductive proof without touching the inductive hypothesis. In this case, he provides the proof himself. (If you have the book, it's Proposition 2.2.8.).

I myself am not capable of pinpointing what's going on here. Questions:

  1. Can this proof be performed without using induction? If so, how? I'm not putting my money on this being possible, as Tao explicitly recommends using induction even in the newest edition of the book.
  2. If the proof must be written in this inductive form, what is going on here? What lesson can we extract concerning the nature of mathematical induction? Why do we need induction even though we don't need the inductive hypothesis?
  3. Are there other inductive proofs that ignore the inductive hypothesis? What "type of proof" constitutes this category?

If I'm terribly confused, be so kind and help me out of my confusion. (: Thanks!

Best Answer

The implicit assumption here is that if

  1. $P(0)$ is true, and
  2. $P(a)$ is true implies that $P(a + 1)$ is true for any natural $a$,

then $P$ is true over all naturals (including $0$). Notice that replacing \begin{align*} P(a) \ \text{is true implies that} \ P(a + 1) \end{align*} with \begin{align*} P(a) \ \text{and} \ P(a + 1) \ \text{are true} \end{align*} results in a stronger assumption. So, if we have a proof that works with the stronger assumption, it still implies that $P$ is true over all naturals.

Usually, any proof using this stronger assumption would mean that the induction is redundant. But any proof of this problem that avoids using this inductive process results in having to use the fact that every natural has a predecessor, which is part of what we're trying to prove!

So, we can only use the fact that successors are defined. Then the proof looks like a traditional proof by induction because we're using the assumption mentioned at the beginning along with successor operators, both of which we happen to do in proofs by induction in general.

Put another way, this is a linguistic issue. The notion usually associated with the word "induction" is building up truth successively to prove that a statement is true over positive integers. This is the point that the hint is getting at, rather than strictly requiring that the induction hypothesis be used to show that $P(a) \implies P(a + 1)$ for any positive integer $a$.

Related Question