Mathematical induction is a method for proving a condition is true of an infinite set that obeys the well-ordering principle.
A set is considered well-ordered if for any subset of elements, one can always find one element which is the smallest. An example of a well-ordered set is the set of positive integers. One element is clearly the smallest. For example, if 1 is an element in the set, then it will be the smallest element.
Not all sets are well-ordered. For example, negative integers are not well-ordered. In such an infinite set, there is never one element which is the smallest. Likewise, real numbers are not a well-ordered set. For any number, it is possible to find another number which is smaller if only by a fraction. There is no smallest value.
It is useful to introduce some notation when talking about well-ordered sets. Sets are often refered to as capital letters such as S, T, R. Elements are often refered to as lowercase letters such as s,t,r.
We can imagine that s is an element of S, t is an element of T, and r is an element of R. Likewise, we can use a subscript to differentiate elements so that s1, s2, etc. are all elements of S. t1, t2, etc. are all elements of T.
When talking about induction, we are always trying to prove some proposition true about an entire set. When talking about a proposition or fact, I will use the following form p(). So, for example, p(s1) means that the proposition is true of the first element of the set S. Likewise p(S) means that the proposition is true of all elements of set S.
Finally, I need to use the concept of implication which is symbolized by →. Implication doesn't say something is true or false. Rather, it describes a relationship. If a certain condition is true, then another condition follows. If I were president, I would be living in Washington, D.C. This doesn't mean that I am president and it doesn't mean that if I am living in Washington, D.C., then I am the president. It simply means that if the first condition were true (if I were the president), then the second condition would follow (then I would live in Washington, D.C.).
With this notation, I can now state the Principle of Mathematical Induction:
Theorem: Principle of Mathematical Induction: if p(s1) is true and if p(sn) → p(sn+1), then p(S).
(1) Let's start by assuming that the theorem is false.
(2) Let's let si be the first element in order where p(si) is not true.
(3) Well i cannot be the first element since we are assuming that p(s1) is true.
(4) So, this means that p(si-1) must be true since i is the first element where the proposition is not true.
(5) But if p(sn) is true, then p(sn+1) is true, so therefore p(si) must be true since p(si-1) is true.
(6) But this is a contradiction so we reject (1) and conclude that the theorem is true.
QED
