[3.1] (Inductive definition of all natural numbers) The list N of all natural numbers is defined as follows:
(a) the natural number 1 is in the list, and
(b) any natural number already in the list guarantees somehow that the next natural number, the immediate successor, is also in the list.
Consider the following equations:
1 = 1;
1 + 2 = 3;
1 + 2 + 3 = 6;
1 + 2 + 3 + 4 = 10;
1 + 2 + 3 + 4 + 5 = 15;
These are simple sums and are easily computed. But more tedious is the sum of the first 100 natural numbers:
1 + 2 + 3 + ... + 99 + 100 = ?
A formula for finding these sums has been discovered: n(n+1)/2, where n is the last (largest) natural number in the sum:
1 + 2 + 3 + ... + n = n(n+1)/2
(Click here for a remarkably simple derivation of this formula.)
The application of this formula with the sums can be expressed as an open statement without dots:
(#) the sum of the first n natural numbers is equal to n(n+1)/2
The above equalities show that this open statement is obviously true for n=1,2,3,4,5. It is desirable to prove it is true for all natural numbers.
The goal can be expressed in the form of a list. Let L be the list of all natural number values for n which make the open statement (#) a true statement. It is desirable to show that L contains all natural numbers, that is, L = N. The definition [3.1] provides a method to do this.
The trivial equation 1=1 shows that 1 is in list L, and fulfils condition (a).
Next, according to condition (b) of [3.1] it is necessary to show that any natural number k is in list L guarantees that its immediate successor k+1 is also in list L.
If k is in list L, then the open statement is true for that k. This means that:
the sum of the first k natural numbers = k(k+1)/2
Now add k+1 to both sides of the equation:
the sum of the first k natural numbers + k+1 = k(k+1)/2 + k+1
The left side involves now the first k+1 numbers, while the right side by algebra is equal to (k+1)(k+1 + 1)/2 (click here to see the algebraic process.). But this formula is merely n replaced by k+1. Therefore it is true and the immediate successor k+1 is also in the list L.
Since both conditions (a) and (b) of definition [3.1] are fulfilled for list L, then L=N and the open statement (#) is true for all natural numbers n.
Recall the notation from Chapter 1 for open statements. Here the open statement (#) is given the name p(n):
p(n): the sum of the first n natural numbers is equal to n(n+1)/2
The first five components are equivalent to the following:
p(1): 1 = 1;
p(2): 1 + 2 = 3;
p(3): 1 + 2 + 3 = 6;
p(4): 1 + 2 + 3 + 4 = 10;
p(5): 1 + 2 + 3 + 4 + 5 = 15
The reader can continue with this; each left side of the following equations is the result of the sum, and the right side is the result of the formula:
p(5): 15 = 15
p(6): 21 = 21
p(7): 28 = 28
p(8): 36 = 36
...
p(100): 5050 = 5050.
The goal was to prove that all of the components p(1), p(2),..., p(k), .... were true. The truth of p(1) was trivial. It was not difficult to show that if p(k) were true, then p(k+1) would be true by addition of the term n+1 to both sides of the equation p(k). Actually this proves the truth of the implication p(k) => p(k+1).
[3.2] Mathematical Induction) An open statement p(n), where variable n may be replaced by any natural number, becomes true for every natural number if two conditions for p(n) are satisfied:
(a) p(1) is true;
(b) the implication p(k) => p(k+1) is true for any natural number k (replacing n).
Intuitively speaking, part (b) proves that the infinite chain of implications p(1) => p(2) => p(3) => ... is true.
List L is best used with [3.1]. But it may be used with [3.2] as the list of all natural numbers that can replace n to make true statements. However [3.2] may be used directly without mentioning L, as is shown in the following example.
The task is to prove that (uv)n = unvn for all natural numbers n, and any numbers u and v.. Therefore,
(##)
p(n): (uv)n = unvn
is the open statement given the name p(n). (This name is not related to the name p(n) given to open statement (#).)
The first component states:
p(1): (uv)1 = u1v1.
The prove of this is trivial because of [2.7]:
(uv)1 = uv = u1v1.
Therefore part (a) of [3.2] is proven.
To prove part (b) start with the assumption that p(k) is true: p(k): (uv)k = ukvk. This equality needed in the proof that p(k+1) is true.
(uv)k+1 = (uv)k (uv)1
[By [2.6] in the product wk+1 there is one more w than in the product wk]
= ukvk u1v1
= uku1 vkv1
= uk+1vk+1
This proves that p(k) => p(k+1) and part (b) of [3.2].
For more examples of proofs using mathematical induction click here.