# 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 prooftechnique, 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 = x^{2} / y^{2}

x^{2} = 2y^{2}

This means *x ^{2}* is even. Square of odd number cannot be even. And hence

*x*is an even number. If

*x*is even than

*x*must be divisible by 4 (e.g. 2

^{2}^{2}= 4, 4

^{2}= 16, 6

^{2}= 36… all are divisible by 4).

From *x ^{2} = 2y*

^{2}, if

*x*is divisible by 4 then

^{2}*y*must be divisible by 2, and hence

^{2}*y*and

^{2}*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^{2} + 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) = n^{2} – 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 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 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 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^{2}.

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^{2} = (4q)^{2} = 4(4q^{2}), thus n % 4 = 0

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

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

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

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

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

But

n = k^{2} = (4q + 3)^{2} = 16q^{2} + 24q + 9 = 4(4q^{2} + 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]

Well-written article.

Thanks for showing interest

Here is an alternative interesting proof of “square root of 2(any prime) is irrational”(here take p=2).

courtesy:linkedin-Fermat’s Library

Yup.. thanks for supplying additional resource