Proof Techniques for Algorithms

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. A statement to be proved is called a theorem or lemma. Proof can be either deductive or inductive.

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 sides,

2 = x² / y²

x² = 2y²

This means x² is even. A square of odd numbers cannot be even. Hence, x is an even number. If x is even, then x² must be divisible by 4 (e.g. 2² = 4, 4² = 16, 6² = 36… all are divisible by 4).

From x² = 2y², if x² is divisible by 4 then y² must be divisible by 2, and hence y² 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 :

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

=   {k² + 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 mathematics and rules of inference to derive 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 multiples of –m, and hence n is even. Thus, it is proved that the 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) = n² – 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)² – 41 + 41 = 41 x 41, which is not a prime number, and hence the statement does not hold.

Proof by Contraposition

This method is based on the logical equivalence between a 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 the symbol ¬ indicates the 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 a perfect square.

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

To prove the 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 = k².

Let us consider the various case of k % 4:

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

But n = k² = (4q)² = 4(4q²), thus n % 4 = 0

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

But n = k² = (4q + 1)² = 16q² + 8q + 1 = 4(4q² + 2q) + 1, thus n % 4 = 1

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

But n = k² = (4q + 2)² = 16q² + 16q + 4 = 4(4q² + 4q + 1), thus n % 4 = 0

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

But

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

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

Thus, proof techniques are a useful tool to verify the correctness of statements in a short time.

---

Additional Reading: Mathematical Proof [Wiki]

Short Questions:

Q: Enlist types of proof

We can categorise proof approaches in one of the following categories:

• Direct proof
• Indirect proof

Q: Define inductive proof

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

Q: Define deductive proof

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

Q: Enlist some popular proof techniques

Following are some of the popular proof techniques:

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