Mathematical Induction

Algorithms - CS2500 - 1 February 2018

  • Methodology in designing algorithms that proves program correctness
  • Forms:
    • Simple Induction
    • Strong Induction

Simple Induction

  • Let P be the property Domain D
  • to prove P(n), n < N is True:
    1. Base case: Verify that P(b) is true for b, start value
      • Check for two other values
    2. Induction Hypothesis: Assume P(n-1)
    3. Induction Step: Prove P(n) is True

Procedure?

  1. Define the problem
  2. Check base case and two other values
  3. Assume that P(n-1) is true.
  4. Prove that P(n) is true when base case is true and with the induction hypothesis.
  5. Invoke principle of simple induction to prove that P(n) is true for all n in set of natural numbers.

Example:

Q. Prove that (n^3+2n) mod 3 = 0

  1. Define the problem
    • Domain D = Set of natural numbers N
    • f(n) = (n^3+2n)
  2. Check base case and two other values
    • n=0 f(0) mod 3 = 0 ✓
    • n=0 f(1) mod 3 = 0 ✓
    • n=0 f(2) mod 3 = 0 ✓
  3. Induction Hypothesis
    • Assume f(n-1) mod 3 = 0
    • (n^3 - 3n + 5n - 3) mod 3 = 0
  4. Induction Step
    • We have to prove that f(n) mod 3 = 0
    • f(n) - f(n-1) = 3n^2 - 3n + 3
    • f(n) = 3(n^2 - n + 1) + f(n-1)
    • f(n) mod 3 = 3(n^2 - n + 1) + f(n-1) mod 3
    • f(n) mod 3 = 0 + 0
  5. By Principle of Induction, we conclude that f(n) mod 3 = 0 for all natural numbers

Something is going on?

Assume:

  • Addition of nth line adds n regions (natural numbers might be domain??)
  1. Base case:
    • n=1 we have 2 regions, Addition of one line introduces 1 more regions ✓
    • n=2 we have 4 regions, Addition of a second line introduces 2 more regions ✓
    • n=3 we have 7 regions, Addition of a third line introduces 3 more regions ✓
    • i <= 3 this holds
  2. Induction Hypothesis:
    • Addition of (n-1)th line introduces (n-1) more regions
  3. Inductive Step:
    • Addition of nth line introduces n more regions
    • Adding 1 line to existing (n-1) lines in general position in plane increases the number of regions by n
    • Since lines are in general position (non parallel, not more than 2 lines intersecting) it has to cut through the region
    • So, nth line intersects n existing regions
    • Lets consider the nth line to draw from our Induction hypothesis
    • Lets assume nth line is added. When (n-1)th line is not there. By Induction hypothesis it will introduce (n-1) regions