B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

What are proofs?

A proof is a clear explanation, accepted by the mathematical community, of why something is true.

Ancient Babylonian and Egyptian mathematics had no proofs, just examples and methods.

Proofs in the way we use them today began with the Greeks and Euclid

Methods of Proof:

There are different methods of proof as follows:

• 
  Direct method
  
• 
  Indirect method.
  
• 
  Contradiction method.
  
• 
  Vacuous method.
  
• 
  Method of induction etc
  

Already you have the idea about above mentioned methods. Let us discuss method of induction.

MATHEMATICAL INDUCTION

Here we discuss another proof technique. Suppose the statement to be proved can be put in the from P(n),  n  n₀. where n₀ is some fixed integer.

That is suppose we wish to show that P(n) is true for all integers n  n₀.

The following result shows how this can be done.

Suppose that

1. 
   P(n₀) is true and
   
2. 
   If P(K) is true for some K  n₀, then P(K + 1) must also be true. The P(n) is true for all n  n₀.
   

This result is called the principle of Mathematical induction.
Thus to prove the truth of statement  nn₀. P(n), using the principle of mathematical induction, we must begin by proving directly that the first proposition P(n₀) is true. This is called the basis step of the induction and is generally very easy.

Then we must prove that P(K)  P(K + 1) is a tautology for any choice of K  n₀. Since, the only case where an implication is false is if the antecedent

is true and the consequent is false; this step is usually done by showing that if P(K) were true, then P(K + 1) would also have to be true. This step is called induction step.

In short we solve by following steps.

1. 
   Show that P(1) is true.
   
2. 
   Assume P(k) is true.
   
3. 
   Prove that P(k +1) is true using P(k) Hence P(n) is true for every n.