 |
INDUCTION AND CONTRADICTION |
See also ...
|
Two of the most important techniques of mathematical proof are proof by induction and proof by contradiction. There are other techniques, for example straight derivation of the required result, but in my opinion induction and contradiction lead to some extremely elegant proofs of results that would be hard to obtain by other means. |
Proof by Induction
Proof by induction is a technique for demonstrating the truth of statements that can be related – in some sense – to the natural numbers (i.e. 0, 1, 2 …) or a subset of the natural numbers. An example will illustrate what we mean by this. Consider the following statement about the sum of the first n integers:
In this case, the summation is a function of the integer n that we choose as the terminating point of the sum. The statement above is therefore related to the positive integers (i.e. 1, 2, 3 …) and so this statement would be a candidate for proof by induction.
So how does proof by induction work? In essence, there are two steps if we wish to prove that a statement such as the above holds for all values of n:
1. Demonstrate that the statement to be proved holds for the case n = 0 (or n = 1)
2. Demonstrate that if the statement to be proved holds for the case n, then it also holds for the case n + 1.
The second step is the key to proof by induction. The first step establishes a starting point, and the second step enables us to develop an argument – by induction – that establishes the truth of the statement for all values of n. The argument runs as follows:
From step 1, the statement holds for n = 0.
From step 2, if the statement holds for n = 0, then it must also hold for n = 1.
From step 2, if the statement holds for n = 1, then it must also hold for n = 2.
From step 2, if the statement holds for n = 2, then it must also hold for n = 3.
… and so on.
From this line of reasoning it can be seen that we can go on as far as we like, to any value of n that we choose. Thus, once steps 1 and 2 above have been established, the truth of the statement is established for all n.
The crux of a proof by induction is therefore the demonstration that step 2 above holds, namely that if a statement holds for the case n, then it follows that the statement also holds for the case n + 1. If this cannot be established, then the proof by induction fails.
In some of the following articles we will use the technique of proof by induction to establish some interesting results, including the statement about the sum of integers above. To see proof by induction in action, see the following articles:
Induction in Differential Calculus
Proof by Contradiction
Proof by contradiction is a very powerful tool for establishing the truth of a statement, and enables some seemingly difficult results to be obtained in a simple and logical manner. As with proof by induction, proof by contradiction is based on the formulation of a statement, the truth (or otherwise) of which is to be established. An example, which will be examined in detail in a later article, is the following:
S = There is an infinite number of prime numbers
Now, the basis of proof by contradiction is that this statement S can be one of two things – it is either true or it is false. In the proof by contradiction of this statement (or any other statement to be proved), the aim is to show that if it is assumed that the statement is false, then a contradiction arises. That is, if the statement S is true, then the assumption that it is false leads to inconsistent or nonsensical results.
As it happens, the above statement about prime numbers is true. If we assume that the statement is false, then this is equivalent to making another statement T that is the converse of statement S:
T = There is a finite number of prime numbers
Thus, if statement S is true, then T is false. Similarly, if T is true, then S is false.
Proof by contradiction of statement S then requires us to show that if we assume that statement T is true, then we would obtain a contradiction. If our analyses of the consequences of assuming that statement T is true indicate a contradiction, it shows that the statement T is in fact false, and hence statement S is true.
To see proof by contradiction in action, see the following articles:
Irrationality of the Square Root of Two