"Mathematical induction" is a misleading name.
Ordinarily, "induction" means observing that something is true
in all known examples and concluding that it is always true. A
famous example is "all swans are white", which was believed true
for a long time. Eventually black swans were discovered in
Australia.
Mathematical induction is quite different. The principle of
mathematical induction says that:
* if some statement S(n) about a number is true for the number
1, and
* the conditional statement S(k) true implies S(k+1) true, for
each k
then S(n) is true for all n. (You can start with 0 instead of 1
if appropriate.)
This principle is a theorem of set theory. It can be used in
deduction like any other theorem. The principle of definition by
mathematical induction (as in the definition of the factorial
function) is also a theorem of set theory.
Although it is true that mathematical induction is a theorem of
set theory, it is more true in spirit to say that it is built into
the foundations of mathematics as a fundamental deductive
principle. In set theory the Axiom of Infinity essentially contains
the principle of mathematical induction.
My reference for set theory as a foundation for mathematics is
the classic text "Naive Set Theory" by Paul Halmos. Warning: This
is an advanced book, despite the title. Set theory at this level
really only makes sense after several years of college/university
mathematics study.
