It is possible to prove that mathematical induction works using a form of natural deduction logic and using proof by contradiction.
A simplified version is given here. This proof does not use the standard mathematical symbols for there exists and for all to make it more accessible to less mathematically motivated readers.
Suppose
P(0) [1]
and
For all n >=0, P(n) => P(n+1) [2]
Consider also the statement
For all m >=0, P(m) [3]
- in other words P is true for all integer values of m.
Assume this is false, which is equivalent to
There exists an m such that not P(m) [4]
The proof hinges on showing that if [1] and [2] hold, then [4] is false, hence [3].
Assume [1], [2] and [4].
Using [4], let m' be the smallest such value such that not P(m), hence not P(m')
Clearly m' cannot be 0, since this leads to an immediate contradiction [ P(0) & not P(0] with P(0) - rule [1]
Suppose m'>0.
From the definition of m', P(m'-1), hence by [2] P(m'). This also gives a contradiction [P(m') & not P(m')] since we are assuming not P(m').
It thus follows that [1] and [2] together imply not [4], which we have already established is just [3].
Hence if
P(0) [1]
and
P(n) => P (n+1) [2]
it follows that (with a trivial change of variable)
for all n >=0, P(n) [3],
which is the principle of mathematical induction.