Proof techniques for algorithms are used to check the validity of the universal statement. We can do this either by proving or disproving the statement. Statement to be proved is called theorem or lemma. Proof can be either deductive or inductive. Proof techniques

Proof techniques
Proof techniques

In the inductive proof technique, the proof is derived using a sequence of statements with logical reasoning. The proof is derived by a chain of statements supporting each other

In deductive proof, the proof is derived by proving statement recursively with different parameters.

In this section, we will discuss various proof techniques like,

  • Proof by contradiction
  • Proof by mathematical induction
  • Direct proof
  • Proof by counter example
  • proof by contraposition

Proof Technique: Contradiction

In the method of contradiction, we start with the false assumption and prove that our assumption was wrong.

For the dependent statement like “if P then Q”, we start with the assumption that P is not true and with this assumption, we try to derive Q. If Q cannot be derived with a false assumption, it’s proved that our assumption was wrong and hence Q can be derived only if condition P holds.

Example: Prove by contradiction that “square root of 2 is irrational”.

Any number r is called rational if it can be expressed in the form of r = x / y, where y ≠0 and x and y both are integer values and have no common factor.

Let us start with the false assumption that √2 is rational. It implies there exist two integers x and y such that,

√2 = x / y

Squaring on both the sides,

2 = x2 / y2

x2 = 2y2

This means x2 is even. Square of odd number cannot be even. And hence x is an even number. If x is even than x2 must be divisible by 4 (e.g. 22 = 4, 42 = 16, 62 = 36… all are divisible by 4).

From x2 = 2y2, if x2 is divisible by 4 then y2 must be divisible by 2, and hence y2 and y are even. Thus x and y both are even and they have a common factor. It disproves our assumption. Thus, √2 cannot be rational.

Proof by Mathematical Induction

Mathematical induction is a very useful tool for the proof of recursive problems. It operates in three steps :

mathematical induction
Steps for mathematical induction

Step 1: Basis of induction  

This is the initial step of the proof. We prove that a given hypothesis is true for the smallest possible value. Typical problem size is n = 0 or n = 1.

Step 2: Induction hypothesis

In this step, we assume that the given hypothesis is true for n = k.

Step 3: Inductive step

In the inductive step, we prove that the hypothesis is also true for n = k + 1.

Example: Prove by induction 1 + 2 + 3 + . . . + n = n (n + 1)/2. 

Step 1 :   Basis of induction

                For n    =   1

                LHS    =   1

                RHS    =   n (n + 1)/2 = 1.(1+1) / 2 = 1

Here, LHS = RHS, so n = 1 is true

Step 2 :   Induction hypothesis

Assume that the given statement is true for n = k

             So, 1 + 2 + 3 + … + k = k (k + 1)/2                       …(1)

Step 3 :   Inductive step

Let’s try to prove that the statement is also true for n = k+1.

             RHS  =    n (n + 1)/2  = (k+1)(k+2)/2

 (because n = k + 1)

             LHS  =    (1 + 2 + 3 + … + k) + ( k + 1)

From Equation (1),

                              =   k(k+1)/2 + (k+1)

                              =   {k(k+1) + 2(k+1)} / 2

                              =   {k2 + k + 2k + 2} / 2

                              =   { k (k + 1) + 2(k + 1)} / 2

                              =   (k + 1)(k + 2) / 2

                              =   RHS.

Thus, it is proved that,

1 + 2 + 3 + … .+ n = n(n + 1)/2

Direct Proof Method

Direct proof is the simplest form of proof. The method of direct proof works on basic principles, axioms, lemmas, and theorems. It uses the mathematics and rules of inference to derive the conclusions. To prove the conditional statements like “If P then Q”, the method assumes that P is true. Statement Q is derived through logical deduction.

Example: Prove that negative of any even number is also even.

Let n be some even number, so n = 2m. (n is even, so it must be divisible by 2, m may be odd or even).

Let us multiply by -1 on both the sides

                     –n    =  –2m

              i.e. –n    =   2(–m)

–n is two multiple of –m, and hence n is even. Thus it is proved that negative of any even number is also even.

Proof by Counter Example

Technically, proof by counterexample is not a method of establishing the universal truth; disproving something is faster than proving it. In the counter-example method, we must verify for a condition in which the presented statement is false. The most common technique to refute a universal statement is to give a counter-example.

To test the validity of the assertion “All prime numbers are odd,” it is sufficient to demonstrate that 2 is a prime number and that it is not odd.

Example: Function f(n) = n2 – n + 41 creates values that are prime, where n is positive integer.

The function is true for an exhaustive test of the first forty integers. It is sufficient to convince that the function generates a prime number.

Let us test the function for n = 41.

             f(41) =    (41)2 – 41 + 41 = 41 ´ 41 Which is not the prime number, and hence the statement does not hold.

Proof by Contraposition

This method is based on the logical equivalence between statement and its contrapositive, i.e. it takes the advantages of logical equivalence between “P implies Q” and “Not Q implies not P”.

For example, the statement “If it is my pen, then it is blue” is equivalent to “If the pen is not blue, then it is not mine”.

Thus, in the contrapositive method, to prove P → Q, we shall prove ┍Q → ┍P. Where symbol ┍ indicates negation of a statement.

Example: Prove that, in n is positive integer such that (n % 4) = 2 or (n % 4) = 3 then n is not perfect square.

(n % 4) of any positive number returns 0, 1, 2 or 3.

To prove given statement using contrapositive, we shall prove that, “If the given number is a perfect square then
(n % 4) = 0 or (n % 4) = 1”

If n is a perfect square, then there must exist some integer k such that n = k2.

Let us consider the various case of k % 4:

If k % 4 = 0, then k is multiple of four, hence k = 4q.

But n = k2 = (4q)2 = 4(4q2), thus n % 4 = 0

If k % 4 = 1, then k = 4q + 1.

But n = k2 = (4q + 1)2 = 16q2 + 8q + 1 = 4(4q2 + 2q) + 1, thus n % 4 = 1

If k % 4 = 2, then k = 4q + 2.

But n = k2 = (4q + 2)2 = 16q2 + 16q + 4 = 4(4q2 + 4q + 1), thus n % 4 = 0

If k % 4 = 3, then k = 4q + 3.

But

n = k2 = (4q + 3)2 = 16q2 + 24q + 9 = 4(4q2 + 6q + 2) + 1, thus n % 4 = 1

All four cases show that if n is perfect square then
(n % 4) is either 0 or 1. And thus, the given statement is proved by counter example.

Thus, proof techniques are useful tool to verify the correctness of statement in quick time.


Additional Reading: Mathematical Proof [Wiki]