How to prove the mathematical induction is true?

I have no idea about the underlying theory from which the mathematical induction was derived.

How to prove the mathematical induction is true?

Solution 1:

A "proof" in mathematics always means a proof in some system/theory. You have to specify the system/theory that you want a proof for the induction axiom. (You should also formally specify what you mean by the induction axiom since there are various axioms that are called induction axiom.)

The induction axiom in an arithmetical theory (like Peano arithmetic) is an axiom, i.e. it is one of the axioms of the theory, and therefore the proof is just a single line stating the axiom.

In a set theory like $ZFC$ we can prove the induction axiom for the set of natural numbers using the fact that the set of natural numbers is defined as the smallest inductive set that contains zero, and the proof is almost trivial. (An inductive set means a set that contains the successor of $x$ whenever it contains $x$).

In high school or undergraduate courses, when one is asked to prove induction axiom, they are usually asked to derive the induction axiom from some other axioms like the least number principle for natural numbers.

Another possible question is what are the justifications for believing that the induction axiom is true (or for accepting it as an axiom), which is a question in philosophy of mathematics and might be more suitable for MathOverflow.

Solution 2:

The principle of induction (on the natural numbers) is equivalent to the axiom of well-foundedness of the natural numbers. Wikipedia gives (half of) a proof here.

Solution 3:

The induction axiom in Peano Arithmetic says that for any predicate (statement about numbers) $\phi$, if you can prove $\phi(0)$ is true and you can also prove that for any number $n$, $\phi(n) \implies \phi(n+1)$ then $\phi(n)$ is true for all $n$. So you have proven $\phi(0)$ and $\phi(0) \implies \phi(1)$ and $\dots$ $\phi(10) \implies \phi(11)$ and $\dots$. Intuitively, if there is an $m$ such that $\phi(m)$ is not true, the base case of $\phi(0)$ or one of these implications must have broken down.

The usual structure of an inductive proof is designed to take advantage of this, so following one carefully may help. Arturo Magidin gave an excellent discussion in his answer to this post