Question

16. Outline the basic structure of each proof technique direct proof, proof by contradiction, and induction.

Answer 1

The three fundamental proof techniques are:

1. Direct proof: Also termed as constructive proof which easy and simple to use out of all methods available. For a proof say P-->Q, there are basically two steps:

• An assumption is made that P is true
• By using P, try to prove that Q must be true

  

2. Proof by Contradiction: It is based on the fact that any proposition can either be true or false but not simultaneously both. The basic steps are as follows:

• An assumption is made that P is true
• An assumption is made that negation of Q is true
• By using P and negation of Q, a contradiction is demonstrated

3. Proof by Induction: It is a powerful method which makes use of recursion for demonstration an infinite number of facts in a finite time period. The basic outline of this method is as follows:

• For some basic case, show that P(x) is true
• For some value of n, show that P(n) is true, and then show that P(n+1) is true.
• As a result, P(n) is true for alll values of n greater than or equal to the basic case by the principle of induction