TOC 1.2

1.2. Methods of Proof

Here we introduce three basic methods of proofs:

(i) mathematical induction, (ii) pigeonhole principle, and (iii) diagonalization.

Mathematical Induction

Let A be a set of natural numbers such that:

1. 0 ∊ A
2. for each natural number n, if {0, 1, 2, ..., n} ∊ A, then n + 1 ∊ A. Then A = N. In particular, induction is used to prove assertions of the form “For all n ∊ N, the property P is valid.” i.e.,

1. In the basis step, one has to show that P(0) is true i.e., the property is true for 0.
2. P holds for n will be the assumption.
3. Then one has to prove the validity of P for n + 1.

Example 1.4.

Property for all n ≥ 0. To see the validity of P for all n ≥ 0, we employ mathematical induction. P is true for n = 0 as left-hand side and right-hand side of P will be 0. Assume P to be true for some n ≥ 0, with . Consider which is P(n + 1). Sometimes a property P(x) may hold for all n ≥ t. In this case for basis clause one must prove P(t).

Strong Mathematical Induction

Another form of proof by induction over natural numbers is called strong induction. Suppose we want to prove that P(n) is true for all n ≥ t. Then in the induction step, we assume that P(j) is true for all j, t ≤ j < k. Then using this, we prove P(k). In ordinary induction (called weak induction) in the induction step, we assume P(k−1) to prove P(k). There are some instances, where the result can be proved easily using strong induction. In some cases, it will not be possible to use weak induction and one has to use strong induction.

Let us give some examples.

Example 1.5.

P(n): sum of the interior angles of an n-sided convex polygon is (2n − 4)π/2. Basis: P(3): Interior angles of a triangle sum upto 180° = (2 * 3 − 4)π/2. Induction Step: Let the result be true for all n upto k, 3 ≤ n ≤ k. To prove P(k + 1): Sum of the interior angles of a (k + 1)-sided polygon is to be computed. Let the polygon be, To compute the sum, join vertex numbered ‘1’ with vertex numbered j, (j ≠ 2 or k+1). Now, the interior angle sum will be the sum of interior angles of two convex polygons ‘1’ and ‘2’. Polygon ‘1’ has j sides and polygon ‘2’ has k + 3 − j sides. The sum of interior angles of polygon ‘1’ is (2j − 4)π/2 and the sum of interior angles of polygon ‘2’ is (2(k + 3− j)− 4)π/2. Hence, sum of the interior angles of the (k + 1)-sided polygon is (2(k + 1)−4)π/2.

Pigeonhole Principle

If A and B are two non-empty finite sets with #A> #B, then there exists no 1–1 function from A to B. i.e., if we attempt to pair the elements of A with the elements of B, sooner or later, we have to put more than one element of A in the already paired group.

Example 1.6.

Among any group of 367 people, there must be at least two with the same birthday, because there are only 366 possible birthdays.

Diagonalization Principle

Let R be a binary relation on a set A and let D = {a|a ∊ A, and (a, a) ∉ R}. For each a ∊ A, let R_a = {b|b ∊ A, and (a, b) ∊ R}. Then D is distinct from R_a for all a ∊ A.

Example 1.7.

Let A = {a,b,c,d} and R = {(a,b), (a,d), (b,b), (b,c), (c,c), (d,b)}. R can be represented as a square array as below:

	a	b	c	d
a		X		X
b		X	X
c			X
d		X

R_a = {b, d}, R_b = {b, c}, R_c = {c}, R_d = {b}, D = {a, d}

Clearly, D ≠ R_a; R_b; R_c; R_d.

Remark The diagonalization principle holds for infinite sets as well.