PadhaikoAll subjects

Induction, Diagonalization & Pigeonhole Principle

Theory of Computation (ENCT 203)

Open in the Padhaiko app

1.3 Proof Techniques Overview (Book 1.3.4)

Definition

Proof, Theorem, Lemma, and Corollary

Besides the three fundamental proof principles of Mathematical Induction, the Diagonalization Principle, and the Pigeonhole Principle, standard proof strategies include:

Proof by Principle of Mathematical Induction

Theorem

Principle of Mathematical Induction

Mathematical induction is a proof technique for establishing that a statement holds for all integers (typically or ) by showing that is true and that truth at any integer implies truth at the next integer .

A proof by mathematical induction consists of three essential parts:

  1. Basis Step (Base Case): Verify directly that the statement holds for the starting integer (e.g., or ).
  2. Inductive Hypothesis: Assume that holds for an arbitrary integer , i.e., assume is true.
  3. Inductive Step: Using the inductive hypothesis , prove that must also be true.

Once both the basis step and inductive step are established, we conclude that is true for all integers .

Worked Out Examples: Mathematical Induction

Example 1.19

1.19

Use mathematical induction to show that

Basis step (): Let be the statement . For :

Since , holds true.

Inductive hypothesis (): Assume that holds true for an arbitrary positive integer :

Inductive step (): We must show that holds true, namely:

Starting from the left-hand side and substituting equation (i):

Thus holds true whenever holds true.

Answer:

By the principle of mathematical induction, holds for all integers .

Example 1.20

1.20

Use mathematical induction to show that the sum of the first positive odd numbers is :

Basis step (): Let be the statement . For :

Hence holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer :

Inductive step (): We show that holds, i.e., :

Thus holds true whenever holds true.

Answer:

By the principle of mathematical induction, holds for all positive integers .

Example 1.21

1.21

Prove by using mathematical induction:

Basis step (): Let . For :

Therefore, holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer :

Inductive step (): We show that holds, i.e., :

Thus holds true whenever holds true.

Answer:

By mathematical induction, for all positive integers .

Example 1.22

1.22

Prove that is divisible by whenever is a positive integer.

Basis step (): Let be the statement " is divisible by ." For : , which is divisible by (). Thus holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer , i.e., is divisible by .

Inductive step (): We show that is divisible by :

By the inductive hypothesis (i), is divisible by , and is clearly a multiple of . Therefore, their sum is also divisible by , so holds true.

Answer:

By mathematical induction, is divisible by for all positive integers .

Diagonalization Principle & Pigeonhole Principle

Theorem

Cantor's Diagonalization Principle

Let be a binary relation on a set .

Then the Diagonalization Principle states that is distinct from every row set —that is, for all .

Proof

Suppose, for the sake of contradiction, that for some element . Consider whether belongs to :

In either case, and disagree on the element itself. Hence for every . (This principle is used to prove that the power set and the set of all languages over are uncountable, and that the Halting Problem is undecidable.)

Example 1.23

1.23

Let and let be the binary relation on given by:

Verify the diagonalization principle.

Tabulating the relation and extracting its main diagonal: We represent as a table where indicates :

Matrix Representation of Relation R on A = {1, 2, 3, 4, 5}

Along the main diagonal , the entries are .

Complementing the diagonal to form : Complementing the diagonal entries gives , which corresponds to the diagonal set:

Comparing against every row set : Reading each row of the table:

  • (differs at )
  • (differs at )
  • (differs at )
  • (differs at )
  • (differs at )
Answer:

The diagonal set is different from each of the row sets , verifying the diagonalization principle.

Theorem

Pigeonhole Principle

If or more pigeons are placed into pigeonholes, then at least one pigeonhole is occupied by two or more pigeons.

Mathematical Formulation: Let (pigeons) and (pigeonholes) be two finite sets with . Then no one-to-one (injective) function can exist from to —that is, for any function , there exist distinct elements () such that .

For example, let () and (), and define by . Because , cannot be one-to-one: two distinct domain elements ( and ) map to the same codomain element . (In Chapter 2, the Pigeonhole Principle is used to prove the Pumping Lemma for Regular Languages.)

Solutions to Important Questions (Book Pages 42–49)

Example Imp. 1

Imp. 1

Prove that is divisible by using the principle of mathematical induction. [2082 Kartik]

Basis step (): Let be the statement " is divisible by ." For , , which is divisible by . (For , , which is also divisible by .) Thus holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer , i.e., is divisible by .

Inductive step (): We show that is divisible by :

By equation (i), is divisible by , and is divisible by . Therefore, their sum is divisible by , so holds true.

Answer:

By mathematical induction, is divisible by for all integers .

Example Imp. 2

Imp. 2

Prove the following statement by using mathematical induction:

Basis step (): Let . For :

Thus holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer :

Inductive step (): We show that holds, i.e., :

Thus holds true whenever holds true.

Answer:

By mathematical induction, for all integers .

Example Imp. 3

Imp. 3

Prove that using mathematical induction for any positive integer . [2081 Chaitra]

Basis step (): Let . For :

Since , holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer :

Inductive step (): We show that holds, i.e., :

Thus holds true whenever holds true.

Answer:

By mathematical induction, for all positive integers .

Example Imp. 4

Imp. 4

Prove that is divisible by for where is an integer. [2081 Bhadra, 2080 Baishakh]

Basis step (): Let be the statement " is divisible by ." For : , which is divisible by . Thus holds true.

Inductive hypothesis (): Assume holds true for an arbitrary integer , i.e., is divisible by .

Inductive step (): We expand and group terms:

  • is divisible by by the inductive hypothesis (i).
  • is clearly a multiple of .
  • is divisible by because is the product of three consecutive integers, one of which is always a multiple of .

Since all three terms are divisible by , their sum is divisible by .

Answer:

By mathematical induction, is divisible by for all integers .

Example Imp. 5

Imp. 5

Show that for all positive integers by using mathematical induction. [2079 Baishakh]

Basis step (): Let . For : , which is true. Thus holds.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer :

Inductive step (): We must show that . Since , we have . Adding to both sides of (i):

Thus holds true whenever holds true.

Answer:

By mathematical induction, holds for all positive integers .

Example Imp. 6

Imp. 6

Prove that

using the mathematical induction principle. [2071 Shrawan]

Basis step (): Let . For :

Hence holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer :

Inductive step (): We show that holds, i.e., :

Thus holds true whenever holds true.

Answer:

By mathematical induction, for all positive integers .

Example Imp. 7

Imp. 7

Use the principle of mathematical induction to prove that is divisible by for all integers . [2071 Chaitra]

Basis step ( and ): Let be the statement " is divisible by ." For , , and for , ; both are divisible by . Thus the base case holds.

Inductive hypothesis (): Assume holds true for an arbitrary integer , i.e., is divisible by .

Inductive step (): We rewrite :

By equation (i), is divisible by , and is divisible by . Hence their sum is divisible by .

Answer:

By mathematical induction, is divisible by for all integers .

Example Imp. 8

Imp. 8

Prove that is a multiple of by the mathematical induction method.

Basis step (): Let be the statement " is a multiple of ." For : , which is a multiple of . Thus holds true.

Inductive hypothesis (): Assume holds true for an arbitrary positive integer , i.e., is a multiple of .

Inductive step (): Expanding :

  • is a multiple of by (i).
  • is the product of two consecutive integers and is therefore even (), so is a multiple of .
  • is a multiple of .

Hence their sum is a multiple of .

Answer:

By mathematical induction, is a multiple of for all positive integers .

Example Imp. 9

Imp. 9

Prove that for any positive integer with by the principle of mathematical induction.

Basis step (): Let for . For : and . Since , holds true.

Inductive hypothesis (): Assume holds true for an arbitrary integer :

Inductive step (): We show that :

Thus holds true whenever holds true.

Answer:

By mathematical induction, holds for all integers .

Exercises

Exercise — Proof Techniques, Induction, Diagonalization & Pigeonhole

Question 3

State diagonalization principle with an example. [2082 Baishakh, 2081 Chaitra, 2076 Chaitra]

Formal statement of the Diagonalization Principle: Let be a binary relation on a set . For each element , define the row set (or characteristic set) as:

Define the diagonal set as the set of all elements in that are not related to themselves:

The diagonalization principle states that the diagonal set differs from every row set :

Proof of the principle by contradiction: Suppose for contradiction that for some specific element . Now consider whether :

  • If , then by definition of , . But since , , which by definition of means — a contradiction.
  • If , then by definition of , . But since , , which implies — again a contradiction.

In both cases, , which is impossible. Hence no such can exist, proving for all .

Concrete illustrative matrix example: Let . Represent a relation by a boolean matrix where entry if : Let . The row sets are:

The diagonal entries are , , . Thus, the diagonal set is:

Comparing with each row set:

  • (differs on element : but , and but )
  • (differs on element : but )
  • (differs on element : but )

Thus differs from every row set , verifying the principle.

Answer:

Let be a binary relation on a set , with row sets for each and diagonal set . The diagonalization principle states that differs from every row set ( for all ), because . (See Worked Out Example 1.23 for a example where for .)

Question 5

Explain pigeonhole principle with a suitable example. [2081 Bhadra, 2080 Baishakh, 2078 Bhadra]

Statement of the Pigeonhole Principle: The Pigeonhole Principle (Dirichlet's Drawer Principle) states that:

  • Basic form: If or more pigeons are placed into pigeonholes (where is an integer), then at least one pigeonhole must contain two or more pigeons.
  • Function formulation: If and are finite sets with , then no function can be injective (one-to-one). There must exist at least two distinct elements () such that .
  • Generalized form: If objects are placed into boxes, then at least one box contains at least objects.

Proof by contradiction: Suppose for contradiction that every one of the pigeonholes contains at most pigeon. Then the total number of pigeons in all pigeonholes combined would be:

However, we are given that there are at least pigeons in total. This gives , which is a contradiction. Therefore, at least one pigeonhole must contain two or more pigeons.

Concrete examples:

  1. Birth month example: In any group of people, at least two individuals must share the same birth month. Here, the people are the "pigeons" and the months of the year are the "pigeonholes". Since , .
  2. Formal set mapping: Let and . Since , any function must assign two domain elements to the same codomain element. For instance, if , then .
Answer:

The pigeonhole principle states that if or more pigeons are placed into pigeonholes, then at least one pigeonhole contains two or more pigeons. Equivalently, if and are finite sets with , no one-to-one function can exist. For example, if and with , at least two elements of ( and ) map to the same element .

Question 7

Define induction principle. [2078 Bhadra]

Principle of Mathematical Induction (Weak Induction): Let be a predicate or mathematical property defined for all integers (where is a fixed integer, typically or ). The Principle of Mathematical Induction (PMI) asserts that is true for all integers if the following two conditions are satisfied:

  1. Basis Step (Base Case): Verify that is true.
  2. Inductive Step: Prove that for every integer , if is true (Inductive Hypothesis), then must also be true:

Under both conditions, by mathematical induction, is true for all integers .

Strong Induction (Principle of Complete Induction): In strong induction, the inductive hypothesis is strengthened: to prove , one assumes that is true for all integers such that :

Weak induction and strong induction are logically equivalent to each other and to the Well-Ordering Principle of the natural numbers.

Concrete illustrative proof: Prove that for all integers .

  • Basis Step ():
  • Inductive Step: Assume is true for an arbitrary integer :

We must deduce :

which is exactly . Therefore, by PMI, is true for all integers .

Answer:

The principle of mathematical induction states that if a mathematical statement satisfies (1) the basis step: is true for a starting integer (such as or ), and (2) the inductive step: for every integer , the inductive hypothesis that is true implies that is true, then is true for all integers .

Question 9

Verify the diagonalization principle for and be the relation defined on and given as:

Listing all ordered pairs of relation : Given and . The sum is even (divisible by ) if and only if and share the same parity (both are odd or both are even):

  • Odd elements in :
  • Even elements in :

Thus, the pairs of are:

Determining the row sets for each : By definition, :

  • For :
  • For :
  • For :
  • For :
  • For :

So there are two distinct row sets: (for odd ) and (for even ).

Constructing the diagonal set : The diagonal set is defined as . Let us test the diagonal elements for all :

For every , is an even number, which means for every . Since no element satisfies , the diagonal set is the empty set:

Verifying for every : Now compare the diagonal set with each row set:

  • For : .
  • For : .

Since holds for all , the diagonalization principle is completely verified.

Answer:

For every , is divisible by , so for all . Therefore, the diagonal set is . Meanwhile, the row sets are and . Since differs from both and , for every , verifying the diagonalization principle.

Past exam questions for Theory of Computation

← Propositional Logic, Rules of Inference & Predicate LogicAlphabets, Languages & Operations on Languages →