Mathematical Induction

Document last modified: 

Resources

C251 text: Discrete Mathematics and Its Applications by Rosen

Overview

proposition - a statement that is either true or false.

theorem - a statement that can be shown to be true.

proof - sequence of steps that demonstrate a theorem is true.

Example

The sky is blue.

3 > 4

Algorithm analysis requires mathematical tools which we are beginning to understand and apply.

One of the most powerful is mathematical induction, first formally described by De Morgan in 1838. Induction closely parallels an algorithm's iteration or recursion and is commonly used to prove recurring properties.

For example, each of the following algorithms result in the sum of the positive integers from 1 to n.

O(n) O(n) O(1)
{ n ³ 1 }

int Sum( n )

  sum = 0

  i = 1;

  while (i ≤ n)

    sum = sum + i

    i = i + 1

{ result = n ( n + 1 ) / 2 }

 { n ³ 1 }

int Sum( n )

  if (n = 1) return 1

  else return Sum(n-1) + n;

{ result = n ( n + 1 ) / 2 }

 

 { n ³ 1 }

int Sum( n )

  return n * (n + 1) / 2;

{ result = n ( n + 1 ) / 2 }

 

The postcondition states:

1+2+...+n = n ( n + 1 ) / 2

a closed-end formula that does not require repetition. The postcondition is a proposition and may be true or false but if we can prove it correct it now is a theorem and is provably true.

One practical result is that we can now use an O(1) algorithm rather than an O(n).

Induction can be used to prove:

1+2+...+n = n ( n + 1 ) / 2

We will prove later as an exercise.

 

Induction

P(n) is a propositional function over positive integers and we typically want to prove "n: n ³ 1 P(n)

To prove this using induction we must show:
  • P(1) is true
  • P(k) ® P(k+1)

In other words [P(1) ^ ("k: P(k) ® P(k+1))] ® "n: P(n)

Need to show that P(k+1) cannot be false when P(k) is true

This is accomplished by:

  • show base case (e.g. P(1)) is true
  • assuming P(k), induction hypothesis, to be true
  • then use hypothesis to show that P(k+1) must also be true.
p q  p ® q
F F T
F T T
T F F
T T T

 

Example (page 242 of Rosen): Use induction to prove that for every integer n ³ 1

P(n): 1 + 2 + 22 + ... + 2n = 20 + 21 + 22 + ... + 2n = 2n+1 - 1

Question 2.11 What is P(4)?

Base Step: P(1)

n = 1 then:
       20 + 21 = 21+1-1 = 22-1 = 3
                 3 = 3

Question 2.12 Why is P(1) the base?

Inductive Step: P(k) ® P(k+1)

Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true

By P(k):

20 + 21 + 22 + ... + 2k = 2k+1 - 1 

Must show for P(k+1)

20 + 21 + 22 + ... + 2k + 2k+1 = 2k+2 - 1 

Start with assumption P(k):

P(k) + 2k+1 = [20 + 21 + 22 + ... + 2k] + 2k+1  Add 2k+1 to both sides (for the k+1 result)
  = 2k+1 - 1 + 2k+1 Induction hypothesis:
P(k): 20 + 21 + 22 + ... + 2k = 2k+1 - 1
  = 2*2k+1 - 1          2*2k+1 = 2k+1 + 2k+1
\ = 2k+2 - 1 Multiply by 2

 

Example (page 240 of Rosen): Use induction to prove that the sum of the first n odd positive integers = n2

P(n): 1 + 3 + 5 + ... + 2n - 1 = n2

Even n = 2k

Odd n = 2k-1

Note that:

P(1): 1=1 P(2): 1+3=4 P(3): 1+3+5=9 P(4): 1+3+5+7=16 P(5): 1+3+5+7+9=25

Question 2.13 What is P(6)?

Base Step: P(1)

n = 1 then:
   (1 * 2) - 1 = 12
           2 - 1 = 1
                1 = 1

Inductive Step: P(k) ® P(k+1)

Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true

P(k):

1 + 3 + 5 + ... + 2k - 1 = k2 

Must show for P(k+1):

(1 + 3 + ... + 2k - 1) + 2(k + 1) - 1 = (k+1)2

Start with assumption P(k):

P(k) + 2(k + 1) - 1 = [1 + 3 + ... + 2k - 1] + 2(k + 1) - 1  Add 2(k+1)-1 to both sides (for the k+1 result)
  = [1 + 3 + ... + 2k - 1] + 2k + 1        Multiplication, Addition and Associative properties
  = [ k2 ] + 2k + 1            Induction hypothesis: P(k): [1 + 3 + ... + 2k - 1] = k2
  = (k+1)(k+1)     Factoring: k2 + 2k + 1 = (k+1)(k+1)
\ = (k+1)2  

 

Example: ^ is AND, v is OR.

Recall the De Morgan law that:

   ______    __    __
   A1 ^ A2 = A1 v A2   

Use induction to prove the following generalization for the De Morgan law of Boolean algebra.

         ______________     __    __          __
P(n): A1 ^ A2 ^ ... ^ An = A1 v A2 v ... v An   for every integer n³2

Base Step: P(2)

n = 2 then De Morgan's law holds:
             ______    __    __
P(2):     A1 ^ A2 = A1 v A2   

Question 2.14 Why is P(2) the base?

Inductive Step: P(k) ® P(k+1)

Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true

        ______________     __    __          __
P(k): A1 ^ A2 ^ ... ^ Ak = A1 v A2 v ... v Ak

Need to show P(k+1):

            _____________________   __    __          __    ____
P(k+1): A1 ^ A2 ^ ... ^ Ak ^ Ak+1 = A1 v A2 v ... v Ak v Ak+1

Start with k+1 case where k³2 since already proven for P(2):

_____________________
A1 ^ A2 ^ ... ^ Ak ^ Ak+1 		   _______________________
= (A1 ^ A2 ^ ... ^ Ak ) ^ Ak+1 		 
     _________________   ____
= (A1 ^ A2 ^ ... ^ Ak ) v Ak+1 		De Morgan's law
\    __    __          __    ____
= A1 v A2 v ... v Ak v Ak+1

              ______________     __    __          __
IH: P(k): A1 ^ A2 ^ ... ^ Ak = A1 v A2 v ... v Ak

 

Example: Use induction to prove that 2n < n! for every integer n ³ 4

P(n): 2n < n! for every integer n³4

Base Step: P(4)

n = 4 then:
   24 = 16 < 24 = 4!

Question 2.15 Why is P(4) the base? Try P(3).

Inductive Step: P(k) ® P(k+1)

Inductive Hypothesis (IH): assume P(k) is true, then under this assumption show that P(k+1) must also be true

By P(k) for k ³ 4:

2k < k! 

Need to show P(k+1) for k ³ 4:

2k+1 < (k+1)!

Start with P(k) assumption:

2*2k < 2*k!  IH:  2k < k! 
multiply both sides by 2
  < (k+1) * k!  k ³ 4 so 2 < k+1
\ = (k+1)!        definition of n!

 

Example: Prove by Induction that: 5 divides n5 - n

Inductive Hypothesis

P(n): 5 divides n5 - n

Base Step:

P(0): 5 divides 0.

Question 2.16 Why is P(0) base?

Inductive Step: P(k) ® P(k+1)

Assume P(k): 5 divides k5 - k

Must prove P(k+1): 5 divides (k + 1)5 - (k + 1)

k5 - k   IH: P(k): 5 divides k5 - k
(k + 1)5 - (k + 1) = k5 + 5k4 + 10k3 +10k2 +5k + 1 - k - 1 Substitute k+1 in IH for k and multiply
  = k5 + 5k4 + 10k3 +10k2 +4k Collect terms
  = (k5 - k) + (5k4 + 10k3 +10k2 + 5k) Factor
  = P(k) + (5k4 + 10k3 +10k2 + 5k) IH: P(k): 5 divides k5 - k
\ = P(k) + 5(k4 + 2k3 +2k2 + k) 5 divides both terms of sum, 5 divides the sum

 

Question 2.17 (p245 of Rosen): Show for n ³ 1

1+2+...+n = n(n+1)/2

You might recall:

Induction Hypothesis:

P(n): 1+2+...+n = n(n+1)/2

Base Step:

 

Inductive Step:

 

Question 2.18 (p253 of Rosen): Find a closed-end formula by examining small values of n for:

1/2+1/4+1/8+...+1/2n

P(1): 1/21=1/2=1-1/21

P(2): 1/2+1/22=1/2+1/4=3/4=1-1/22

P(3): 1/2+1/4+1/23=1/2+1/4+1/8=7/8=1-1/23

P(n): 1/2+1/4+1/8+...+1/2n = 1-1/2n

Question 2.19 Prove above formula using induction.

Induction Hypothesis:

 

Base Step:

 

Inductive Step:

 

Proof:    Recall that 1/2*1/2n = 1/2n+1