Skip to content

Chapter 2: Pigeonhole Principle, Mathematical Induction and Strong Induction

1. Pigeonhole Principle

Basic Pigeonhole Principle

Statement: If n + 1 objects are placed into n boxes, then at least one box contains two or more objects.

This principle is non-constructive: it guarantees existence but does not tell which box.

Example 1

If 13 people are in a room, at least two people have birthdays in the same month.

Reason:

  • Objects = 13 people
  • Boxes = 12 months Since 13 > 12, at least one month has ≥ 2 birthdays.

Generalized Pigeonhole Principle

Statement: If N objects are placed into k boxes, then at least one box contains at least:

[ \left\lceil \frac{N}{k} \right\rceil \text{ objects} ]

Example 2

In a class of 100 students, at least how many students have the same grade (A, B, C, D, F)?

  • Objects = 100
  • Boxes = 5

[ \left\lceil \frac{100}{5} \right\rceil = 20 ]

Answer: At least 20 students have the same grade.

Applications in Computer Science

  • Hashing and collisions
  • Load balancing
  • Data distribution
  • Network routing guarantees

2. Mathematical Induction

Mathematical induction is a proof technique used to prove statements that are true for all natural numbers.

Principle of Mathematical Induction (PMI)

Let P(n) be a statement about a natural number n.

To prove P(n) is true for all n ≥ n₀:

  1. Base Step: Prove P(n₀) is true.
  2. Inductive Hypothesis: Assume P(k) is true for some k ≥ n₀.
  3. Inductive Step: Prove P(k + 1) is true using the hypothesis.

Example 1: Sum of First n Natural Numbers

Claim: [ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} ]

Proof:

Base Case (n = 1): [ 1 = \frac{1(1+1)}{2} = 1 ]

True.

Inductive Hypothesis: Assume the formula is true for n = k:

[ 1 + 2 + \cdots + k = \frac{k(k+1)}{2} ]

Inductive Step: For n = k + 1:

[ 1 + 2 + \cdots + k + (k+1) ]

Using hypothesis: [ = \frac{k(k+1)}{2} + (k+1) ] [ = \frac{(k+1)(k+2)}{2} ]

Thus, true for k + 1.

Common Mistakes in Induction

  • Skipping base case
  • Using what you are trying to prove
  • Incorrect algebra in inductive step

3. Strong Mathematical Induction

Statement

To prove P(n) is true for all n ≥ n₀:

  1. Prove P(n₀) is true.
  2. Assume P(n₀), P(n₀ + 1), ..., P(k) are all true.
  3. Prove P(k + 1) using all previous cases.

Why Strong Induction?

Some problems cannot be proved using simple induction because P(k + 1) depends on multiple previous values, not just P(k).

Example: Every Integer n ≥ 2 Can Be Written as a Product of Primes

Claim: Every integer n ≥ 2 is either prime or a product of primes.

Proof Using Strong Induction

Base Case (n = 2): 2 is prime.

Inductive Hypothesis: Assume the statement holds for all integers 2 ≤ m ≤ k.

Inductive Step: Consider k + 1.

  • If k + 1 is prime → done.
  • If composite, then: [ k + 1 = a \cdot b ] where 2 ≤ a, b ≤ k

By hypothesis, both a and b are products of primes. Hence k + 1 is also a product of primes.

Example 2: Fibonacci Numbers

[ F_n = F_{n-1} + F_{n-2} ]

Strong induction is used because each term depends on two previous terms.

4. Comparison: Induction vs Strong Induction

Aspect Simple Induction Strong Induction
Assumption P(k) P(1) to P(k)
Power Less More
Use cases Linear dependence Multiple dependencies
Validity Equally valid Equally valid

5. Induction in Computer Science

  • Correctness of algorithms
  • Recurrence relations
  • Loop invariants
  • Recursive function proofs
  • Data structure properties (trees, heaps)

Comments