Proof by Induction

Proof by Induction is a method of mathematical proof that establishes a base case to develop an induction hypothesis that can then be proven by induction.

Base Case

The base case verifies the problem or statement through a specific initial value or values. (n = 0, n = 1)

Induction Hypothesis

The induction hypothesis assumes that the statement holds for some k, or range of values using k as a boundary.

• Weak Induction: Induction typically based on a specific assumption.(P(n) = P(k), or n = k)
• Strong Induction: Induction typically involving a range or global case of an assumption. (All integers less than or equal to k.)

Inductive Step

The inductive step proves the statement holds based on the inductive hypothesis.

Example

Prove by induction that 2^n > 2n

Base case:

  When n = 3 then 2^3 > 2 x 3
    8 > 6 TRUE

Induction Hypothesis:

  Assume the P(k) is correct for some positive integer k.
    2^k > 2k.

Induction Step:

  Since P(k) is true for all positive integers greater than 2, P(k+1) is true.

    2^(k + 1) is the same as 2 x 2^k, which is clearly greater than 2 x 2k,which is equivalent
    to 2(1 + k) or due to the communitive property of multiplication is equivalent to 2(k + 1),
    for all k > 2. Or,

        2^(k+1) = 2 x 2^k > 2 x 2k = 2(k + 1)  for k>2

    Hence by mathematical induction P(n) is true for all positive integers n > 2.

All mathematical proofs by induction consist of these three parts. Be sure to prove all necessary base cases, more than one is possible.

Note: Any proof by weak induction is also a proof by strong induction, the distinction between the two is determined by the need to prove a substantive range of assumptions.

Proof by Induction’s Application to Computer Science

A very strong relationship is present between recursion and mathematical induction. Recursion solves a problem by specifying a solution to one or more base cases and then demonstrating how to derive the solution to one or more base cases and then demonstrating how to derive the soltion to a problem of an arbitrary size from the solutions to smaller problems of the same type. Similarly, mathematical induction proves a property about the natural numbers by proving the property about a base case and then proving that the property must be true for an arbitrary natural number n if it is true for the natural numbers smaller than n.

Example

Below is psuedocode of a function to compute a factorial, recursive steps will be done in parallel to show similarity:

  factorial(n: integer): integer

    if (n == 0)
      return 1
    else
      n = n * factorial(n - 1)

Recursion:

Basis: If n is equal to 0, then return 1

       factorial(0) = 1

Induction:

Base case: n! when n = 0

$0! = 1$

Recursion:

  factorial(n) = n * (n - 1) * (n - 2) * ... * 1

Induction:

Inductive Hypothesis: Assume that this property holds true for n = k. For all k > 0.

$k! = k x (k - 1) x (k - 2) x ... x 1$

Inductive Step: Let n = k + 1.

$(k + 1)! = (k + 1) x k x (k - 1) x (k - 2) x ... x 1

  (k + 1)! = (k + 1) x k!  From the *Induction Hypothesis*$

Thus, the property is true due to the definition of factorials.

Note: Typically, the problem will be to solve an expression or inequality.