Methods of Proof

To prove mathematical results, in general we use any of the following methods.

(1) When statements of the form p \Leftrightarrow q are used to arrive at the truth of a certain mathematical result, this kind of approach to establish the result is known as the “direct proof”.

(2) In case an equivalent statement is used to arrive at the result, then this method of proof is known as “indirect proof”. In particular, in place of arriving at a statement q form a statement p if we arrive at  \sim p from  \sim q then such a kind of proof is called “contrapositive proof”.

Symbolically, we establish  \sim q  \Rightarrow  \sim p in place of p \Rightarrow q.

(3) Sometimes, to prove a certain result p, it is convenient to prove the equivalent form  \sim ( \sim p), i.e. negation of  \sim p. This method of proof involves contradiction of negation of p.

For example, to prove the uniqueness of a certain element x, if possible, suppose y is
an element satisfying the properties of x then we show that x = y. In such a case, instead of directly proving the proposition p= x is unique,” i.e. for every y satisfying properties of x, x = y, we prove  \sim ( \sim p) or  \sim (x \ne y) i.e. x = y.

(4) To prove a mathematical result p(n) concerning natural number n, it is sometimes convenient to prove the truth of p(n) for n + 1 whenever p(n) holds true for n. And if is the least natural number for which p(n) holds, then the truth of p(n) is established for all n \geqslant m. Such a method of proof is called the “method or principle of finite induction”. This method depends upon the fact that the natural numbers follow the principle of finite induction.

 

To illustrate this method, let us prove for all natural numbers n \geqslant 3that

n > {\left( {1 + \frac{1}{n}} \right)^n}{\text{ }}\forall n \geqslant 3\,\,\,\,\, - - - \left( * \right)

The result (*) is evident for n = 3. Let us suppose that it is true for some n \geqslant 3. Then (*) gives that

n + 1 > {\left( {1 + \frac{1}{{n + 1}}} \right)^n} + 1

And

n + 1 > {\left( {1 + \frac{1}{{n + 1}}} \right)^n}

i.e.

1 > \frac{1}{{(n + 1)}}{\left( {1 + \frac{1}{{n + 1}}} \right)^n}

Therefore,

n + 1 > {\left( {1 + \frac{1}{{n + 1}}} \right)^n} + \frac{1}{{(n + 1)}}{\left( {1 + \frac{1}{{n + 1}}} \right)^n}

i.e.

n + 1 > {\left( {1 + \frac{1}{{n + 1}}} \right)^{n + 1}}

Thus, (*) being true for n \geqslant 3 is also true forn + 1. And it already holds for n = 3. Hence (*) is established.

The use of methods described in (1) to (4) will appear in various places in our subsequent course of study. In various types of proofs the quantifier symbols \forall and \exists are found to be quite useful. These symbols \forall and \exists stand for the words “for all” and “there exists,” respectively. Whenever we write\exists , it stands in the sense that we can find the quantity it precedes under specified conditions.