Chapter 4
Mathematical Induction

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter4/self_assessments.html - Chapter self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter4/extra_examples.html - Extra examples with solutions.

Basics of Induction

We determine that:

P(1) = 2 = 2 * 1

P(2) = 2 + 2 = 4 =  2 * 2

P(3) = 2 + 2 + 2 = 6 = 2 * 3

P(4) = 2 + 2 + 2 + 2 = 8 = 2 * 4

 

Want to show that n additions of 2 to be:

P(n) = 2 + 2 + ... + 2 = 2 * n

 

How can we prove?

1. Prove one case (base case) to be true.

   P(1) = 2 = 2 * 1

   P(2) = 2 + 2 = 4 =  2 * 2

   P(3) = 2 + 2 + 2 = 6 = 2 * 3

   P(4) = 2 + 2 + 2 + 2 = 8 = 2 * 4

   We have proven a base case.

   Pick any one of the above.

    

2. Assume hypothesis true for some case n.

   P(n) = 2 + 2 + ... + 2 = 2 * n

   We proved true in the base case: n=1, 2, 3 or 4.

    

3. Prove true for case n+1 that:

   P(n+1) = 2 * (n+1)
    

4. Use direct proof to show:

        p → q

   P(n) → P(n+1)

   P(n+1)	= 2 + 2 + ... + 2 + 2	Definition: P(n+1) = n+1 additions of 2
   	= P(n)                 + 2	Substitute: 2 + 2 + ... + 2 = P(n)
   	= 2*n + 2	Substitute: P(n) = 2*n
   	= 2 * (n+1)	∴ P(n) → P(n+1)

Assume true

P(n) = 2 + 2 + ... + 2 = 2 * n

because we showed some base case true: n = 4:

P(4) = 2 + 2 + 2 + 2 = 8 = 2 * 4

Proved P(n+1) true for any n+1 case.

P(n) → P(n+1)

 

P(n) p	P(n+1) q	P(n) → P(n+1)     p → q
F	F	T
F	T	T
T	F	F
T	T	T

Assuming P(n) true and proving P(n+1) true makes P(n) → P(n+1) true.

 

Example - Basics of Induction

We determine that:

P(1) = 2 = 2¹

P(2) = 2 * 2 = 4 = 2²

P(3) = 2 * 2 * 2 = 8 = 2³

Define n multiplications of 2 to be:

P(n) = 2 * 2 * ... * 2 = 2ⁿ

 

How can we prove?

1. Prove a base case.

   P(1) = 2 = 2¹

   P(2) = 2 * 2 = 4 = 2²

   P(3) = 2 * 2 * 2 = 8 = 2³

    

2. Assume hypothesis true for some case n.

   P(n) = 2 * 2 * ... * 2 = 2ⁿ

   Proved correct for base case: n=1, 2 or 3.

    

3. Prove true for case n+1 that

   P(n+1) = 2ⁿ⁺¹
    

4. Use direct proof to show:

        p → q

   P(n) → P(n+1)

P(n+1)	= 2 * 2 * ... * 2 * 2	Definition: P(n+1) = n+1 multiplications of 2
	=       P(n)          * 2	Substitute: 2 * 2 * ... * 2 = P(n)
	=        2n             * 2	Substitute: P(n) = 2n          Hypothesis
	= 2n+1	2n * 21 = 2n+1
		P(n) → P(n+1)

Assume true

P(n) = 2 * 2 * ... * 2 = 2ⁿ

Showed some base case true: n = 3:

P(3) = 2 * 2 * 2 = 8 = 2³

Proved P(n+1) true for any n+1 case.

P(n) → P(n+1)

Question 4.2

We determine that:

P(1) = 4 = 4 * 1

P(2) = 4 + 4 = 8 =  4 * 2

P(3) = 4 + 4 + 4 = 12 = 4 * 3

Define n additions of 4 to be:

P(n) = 4 + 4 + ... + 4 = 4 * n

 

How can we prove?

1. Prove a base case to be true.

   P(4) = ______________________

2. Assume hypothesis true for some case n.

   What is the definition of P(n)?

   P(n) = ___________________

3. For case n+1

   What is the definition of P(n+1)?

   P(n+1) = _________________

4. P(n) → P(n+1)

   Prove for case n+1 that:

   P(n+1) = __________________

   P(n+1)	=	Definition: P(n+1) = n+1 additions of 4
   	=
   	=
   	=	P(n) → P(n+1)

From our previous example:

P(n+1) = 2ⁿ⁺¹

P(n+1)	= 2 * 2 * ... * 2 * 2	Definition: P(n+1) = n+1 multiplications of 2
	=       P(n)          * 2	Substitute: 2 * 2 * ... * 2 = P(n)
	=        2n             * 2	Substitute: P(n) = 2n                Hypothesis
	= 2n+1	P(n) → P(n+1)

 

4.1 Mathematical 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) is true when P(k) is true Accomplished by: assume P(k), induction hypothesis, to be true   use P(k) to show that P(k+1) also true.

P(k) p P(k+1) q P(k) → P(k+1) p → q F F T F T T T F F T T T

Example

P(1) = 1 = 1(1+1)/2 = 2/2 =1

P(2) = 1+2 = 2(2+1)/2 = 2(3)/2 = 6/2 = 3

P(3) = 1+2+3 = 3(3+1)/2 = 3(4)/2 = 12/2 = 6
                        :
P(n) = 1 + 2 + 3 + ... + n = n(n+1)/2

Define P(n) = 1 + 2 + 3 + ... + n = n(n+1)/2

 

Proof - Use induction to prove that for every integer n ≥ 1:

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

 

Base Step: P(1)

n = 1 then:

1 = 1(1+1)/2 = 2/2 = 1

 

Induction Hypothesis: P(k)

Inductive Hypothesis (IH):

Assume P(k) is true

shown for Base Step, when k=1, P(1) = 1,

then under this assumption show that P(k+1) must also be true

P(k) induction hypothesis is true:

P(k)

= 1 + 2 + 3 + ... + k

= k(k+1)/2

 

Prove: P(k+1)

Must show P(k+1):

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

                                             = (k+1)(k+2) / 2

P(k+1)	= 1 + 2 + ... + k + (k + 1)	Definition of P(k+1 )
	= P(k)                 + (k + 1)	Substitute P(k) = 1 + 2 + ... + k
	= k(k+1)/2        + (k + 1)	Substitute P(k) = k(k+1)/2        Induction Hypothesis
	= k(k+1)/2 + 2(k+1)/2	Common denominator of 2
	= [ k(k+1) + 2(k+1)] / 2
	= [ (k2 + k)+ (2k+2)] / 2	Multiply
	= [ k2+3k+2] / 2	Simplify
∴	= (k+1)(k+2) / 2	P(k) → P(k+1)

 

Example - Use induction to prove that for every integer n ≥ 1:

P(n): 1 + 2 + 2² + ... + 2ⁿ = 2⁰ + 2¹ + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1

Question 4.3.1   What are:

P(1)?    P(2)?  P(4)?

 

Base Step: P(1)

n = 1 then:
      2⁰ + 2¹ = 2¹⁺¹ - 1
          1 + 2 = 2² - 1
                3 = 3

Question 4.3.2   Will P(1) work as the base?

 

Induction Hypothesis: P(k)

P(k) = 2⁰ + 2¹ + 2² + ... + 2^k
       = 2^k+1 - 1 

Prove: P(k+1)

2⁰ + 2¹ + 2² + ... + 2^k + 2^k+1  = 2^k+1+1 - 1 
                                                  = 2^k+2 - 1 

P(k)	= 2k+1 - 1	Inductive Hypothesis P(k)
P(k + 1)	= 20 + 21 + ... + 2k + 2k+1	Definition: P(k+1)
Question 4.3.3	=                               + 2k+1	Substitute: P(k)
	=                               + 2k+1	Substitute: Inductive Hypothesis
	= (2k+1 + 2k+1) - 1
	= 2*2k+1 - 1	2*2k+1 = 2k+1 + 2k+1
∴	= 2k+2 - 1	P(k) → P(k+1)

 

Question 4.4

Prove, using induction, that the sum of the first n even positive integers is:

P(n) = 2*1 + 2*2 + 2*3 + ... + 2n = 2 + 4 + 6 +…+ 2n = n(n+1)

1. What is P(1)?
    
2. What is P(2)?
    
3. Base step?

   P(1) =
    

4. P(k) = 2 + 4 + 6 +…+ 2k =   ?                          Inductive Hypothesis
    
5. P(k + 1) = 2 + 4 + 6 +…+ 2k +    ?                   Definition
    
6. Show P(k+1) =     ?       

P(k)	=  2 + 4 + 6 +…+ 2k = k(k+1)	Inductive Hypothesis P(k)
P(k + 1)	= 2 + 4 + 6 +…+ 2k +    ?	Definition: P(k+1)
	=	Substitute: P(k)
	=	Substitute: Inductive Hypothesis
	=
	=
∴	=	P(k) → P(k+1)

 

Example - Use induction to prove for positive integer n:

P(n) = 12+22+32+…+n2 = n(n+1)(2n+1)/6

Base Step: P(1)

n = 1 then:
       1² = 1(1+1)(2*1+1)/6                    
         1 = 6/6
         1 = 1

Induction Hypothesis: P(k)

P(k) = 12+22+32+ … +k2

       = k(k+1)(2k+1)/6

Prove: P(k+1):

  12+22+32+ … +k2 + (k+1)2

            = (k+1)(k+2)(2k+3)/6

P(k)	= 12+22+32+…+k2 = k(k+1)(2k+1)/6	Induction Hypothesis: P(k)
P(k+1)	= 12+22+32+ … +k2 + (k + 1)2	Definition: P(k+1)
	= P(k) + (k + 1)2	Substitute: P(k)
	= k(k+1)(2k+1)/6 + (k + 1)2	Substitute: Induction Hypothesis
	= (2k3 + 3k2 + k)/6 + 6(k2 + 2k + 1)/6	Multiplication, Addition and Associative properties
	= (2k3 + 9k2 + 13k + 6)/6	Factor
∴	= (k+1)(k+2)(2k+3)/6	P(k) → P(k+1)

 

Example - Use induction to prove that the sum of the first n odd positive integers = n²

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

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 4.5    

a.    What is P(6)?  _____________________

b.     Base Step: P(1)? __________________

c.     Induction Hypothesis: P(k)

P(k) =     ?         =             ?             

d.     Prove: P(k+1)

P(k+1) =          ?          =           ?          

P(k)	=	Induction Hypothesis: P(k)
P(k+1)	=	Definition: P(k+1)
	=	Substitute: P(k)
	=	Substitute: Induction Hypothesis
	=	Math
	=	Factoring:
∴	=	P(k) → P(k+1)

 

Question  Find a closed formula for a summation by examining small values of n for:

Summation:

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

Examine:

1/2 + 1/4 + 1/8 = 4/8 + 2/8 + 1/8 = 7/8

Closed formula guess:

P(n) =

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

Question 4.6    Prove above formula using induction. 

a.    Hypothesis:

    P(n) =

b.    Base Step:

    P(1) =

c.    Induction Hypothesis:

    P(k) =

d.    Prove:

    P(k+1) =

Hint: Recall that

2*2ⁿ = 2ⁿ⁺¹

2/2 * 1/2ⁿ = 2/2*2ⁿ = 2/2ⁿ⁺¹

 

Example    n!

Definition: 1! = 1

                2! = (2-1)! * 2
                        :
                n! = (n-1)! * n

  (n+1)! = n! * (n+1)

P(n) = 1 * 2 * 3 * ... * n = (n-1)! * n = n!

Base Step:

P(1): 1 = 1!

Induction Hypothesis: P(k)

Assume P(k): P(k) = 1 * 2 * 3 * ... * k = (k-1!) * k = k!

Prove: P(k+1)

Must prove P(k+1):

P(k+1) =  1 * 2 * 3 * ... * k * (k+1) = k! * (k+1) = (k+1)!

P(k)	= k!	Induction Hypothesis
P(k+1)	= 1 * 2 * 3 * ... * k * (k+1)	Substitute P(k)
	= P( k ) * (k+1)
	= k! * (k+1)	P(k) = k! Induction Hypothesis
	= (k + 1)!	Definition: n! = n * (n-1)!

Example

Definition: 1! = 1

                2! = (2-1)! * 2
                        :
                n! = (n-1)! * n

{ Precondition: n ≥ 1 } FACTORIAL(n)     if n = 1 then return 1     else return FACTORIAL(n-1) * n { Postcondition: FACTORIAL(n) == n! }

Prove by induction that: FACTORIAL(n) = n!

Base Step:

P(1): If n=1 then return FACTORIAL(1) = 1!

Induction Hypothesis: P(k)

Assume P(k): FACTORIAL(k) = k!

Prove: P(k+1)

Must prove P(k+1):

FACTORIAL(k+1) = (k+1)!

FACTORIAL(k+1), k+1 > 1 so the algorithm else is executed.

FACTORIAL(k+1)	= FACTORIAL((k+1)-1) * (k+1)	Substitute (k+1) for n in: return FACTORIAL(n-1) * n
	= FACTORIAL( k ) * (k+1)	k = ((k+1)-1)
	= k! * (k+1)	FACTORIAL(k) = k! Induction Hypothesis
	= (k + 1)!	Definition: n! = n * (n-1)!

 

Example - The Number of Subsets of a Finite Set

Use mathematical induction to show that if S is a finite set with n elements where n is a nonnegative integer, then S has 2ⁿ subsets.

P(n) = 2ⁿ

For n=0, there are 2⁰ = 1 subsets.

S = ∅

Subsets are: ∅

For n=2, there are 2² subsets.

S = {b, c}

Subsets are: {b, c}, {b}, {c}, ∅

For n=3, there are 2²+2² = 2³ subsets.

S = {b, c} ∪ {a}

Subsets are: {b}, {c}, {b, c}, ∅, {a, b, c}, {a}, {a, b}, {a, c}

Proof

P(n) proposition that a set with n elements has 2ⁿ subsets.

Base step

2⁰ = 1 so P(0) is true for ∅

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

For k elements assume 2^k subsets, P(k) is true.

Must show:    P(k+1) is true, that a set of k+1 elements has 2^k+1 subsets

                     P(k+1) = 2^k+1

P(k)	= 2k	Inductive Hypothesis
S has k elements	and 2k subsets	Inductive Hypothesis
T	= S ∪ {a}	T has k+1 elements including a
S	= T - {a}
X ⊆ S		X is any subset of S
X ⊆ T ^ X∪ {a}⊆ T		For each X ⊆ S there are two subsets of T
S has k elements	and 2k subsets	Inductive Hypothesis
T has k+1 elements	and 2k + 2k subsets
P(k+1)	= 2k + 2k
	= 2(2k)
∴	= 2k+1

 

Example

Recall the De Morgan law that:

   ______    __    __
   A₁ ^ A₂ = A₁ v A₂   

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

         ______________     __    __          __
P(n): A₁ ^ A₂ ^ ... ^ A_n = A₁ v A₂ v ... v A_n   for every integer n≥2

Base Step: P(2)

n = 2 then De Morgan's law holds:
             ______    __    __
P(2):     A₁ ^ A₂ = A₁ v A₂   

Question 4.7.2    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): A₁ ^ A₂ ^ ... ^ A_k = A₁ v A₂ v ... v A_k

Need to show P(k+1):

            _____________________      __    __          __    ____
P(k+1): A₁ ^ A₂ ^ ... ^ A_k ^ A_k+1 = A₁ v A₂ v ... v A_k v A_k+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	Grouping (A1 ^ A2 ^ ... ^ Ak )
	_________________    ____ = (A1 ^ A2 ^ ... ^ Ak ) v Ak+1	De Morgan's law for P(2)
∴	__    __          __    ____ = A1 v A2 v ... v Ak v Ak+1	______________       __    __          __ IH: P(k): A1 ^ A2 ^ ... ^ Ak = A1 v A2 v ... v Ak

 

 

Note:

1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
4! = 4 * 3! = 24
     :
n! = n * (n-1)!

(n+1)! = (n+1) * n!

 

Example - Use induction to prove that 2ⁿ < n! for every integer n≥4

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

Base Step: P(4)

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

Question 4.8 Why is P(4) the base?

n = 3 then:
   2³ = 9 > 6 = 3!

 

Inductive Hypothesis: P(k)

By P(k) for k≥4:

2^k < k! 

Prove:  P(k+1)

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

2^k+1 < (k+1)!

Start with P(k) assumption:

2k	< k!	P(k) Inductive Hypothesis
2*2k	< 2 * k!	Multiply both sides by 2 P(k+1) defined as 2k+1
2k+1	< 2 * k!	Simplify
	< (k+1) * k!	k≥4 so 2 < k+1
∴	= (k+1)!	Definition of (k+1)! = (k+1) * k!

 

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

P(0)        5 divides 0⁵ - 0 = 0 - 0 = 0

P(1)        5 divides 1⁵ - 1 = 1 - 1 = 0

P(2)        5 divides 2⁵ - 2 = 32 - 2 = 30

P(n)        5 divides n⁵ - n

Base Step:

P(0): 5 divides 0⁵ - 0 = 0 - 0 = 0

Question 4.9    Why is P(0) base?

 

Induction Hypothesis: P(k)

5 divides k⁵ - k

Prove: P(k+1)

5 divides (k + 1)⁵ - (k + 1)

P(k)	5 divides k5 - k	Induction Hypothesis
P(k+1)	= (k + 1)5 - (k + 1)	P(k+1): Substitute k+1 for k in k5 - k
	= k5 + 5k4 + 10k3 +10k2 +5k + 1 - k - 1	Multiply
	= k5 + 5k4 + 10k3 +10k2 +4k	Collect terms
	= (k5 - k) + (5k4 + 10k3 +10k2 + 5k)	Factor
	= P(k) + (5k4 + 10k3 +10k2 + 5k)	Induction Hypothesis:    P(k): 5 divides k5 - k
∴	= P(k) + 5(k4 + 2k3 +2k2 + k)	5 divides P(k) 5 divides 5(k4 + 2k3 +2k2 + k) 5 divides (k + 1)5 - (k + 1)

Question 4.10

Prove that 2 divides n2+ n for positive integers

P(n) = 2 divides n2+ n for positive integers

1. What is P(1)?            ?             
    
2. What is P(2)?           ?             
    
3. Base step?

   P(1) =            ?             
    

4. Induction Hypothesis?

   P(k) =            ?               
    

5. Prove?

   P(k+1) =            ?               
    

6. Complete the proof.

P(k)	2 divides k2 + k	Induction Hypothesis
P(k+1)	=            ?	P(k+1): Substitute k+1 for k
	=            ?	Multiply
	=            ?	Collect terms
	=            ?	Factor
	= P(k) +            ?	Induction Hypothesis: P(k): 2 divides k2 + k
∴	= P(k) +            ?	2 divides k2 + k 2 divides            ?              2 divides            ?

4.5    Program Correctness

Composition rule of inference

p: precondition    S1                                 Statements S1... Sn are executed      :    Sn q: postcondition    p {S1} r                        Precondition p is true and postcondition r of statement {S1} is true    r {S2} q                        Precondition r is true and postcondition q of statement {S2} is true __________                     ___________________________________________________________ ∴p {S1; S2} q                  Precondition p is true and postcondition q of statements {S1;S2} is true

 

Example

{ p: x = 1}      y ← 2      z ← x + y { q: z = 3 }

Assume preconditions true { p: x = 1}

y ← 2   z ← x + y

Prove algorithm ensures postcondition true { q: z = 3 }

Proof (Direct)    { p: x = 1}  →  { q: z = 3 }

x = 1	p: x = 1
y = 2	y ← 2       Assignment
x = 1 ^ y = 2	r: x = 1 ^ y = 2       Conjunction
z ← 1 + 2	z ← x + y       Substitution for x and y
z ← 3	Addition 1 + 2
z = 3	z ← 3      Assignment
z = 3	∴ q: z = 3
	p → q

Question 4.11 - Prove postcondition.

{ p: x = 3 }   y ← x + 2   z ← y * 4 { q: z = 20 }

 

Conditional Statements - Rules of Inference

p: precondition   if condition then         S1   else         S2 q: postcondition    p ^ condition {S1} q                                        When p ^ condition is true, after S1, q is true    p ^ ¬condition {S2} q                                      When p ^ ¬condition is true, after S2, q is true _________________________________             ___________________________________________________________ ∴p { if  condition then S1 else S2} q                 p is true and q is true after if-then-else

Example

The algorithm below determines the maximum of two values.

Precondition is true (assuming two integers are supplied).

-- p:  true procedure maxOf( x, y : integers) if  x > y then maxOf ← x       else maxOf ← y -- q: maxOf  ≥ x ^ maxOf  ≥ y

Both the true and false case must be proven to produce the same postcondition.

true: {true ^ x > y } maxOf ← x { maxOf  ≥ x ^ maxOf  ≥ y }

false: {true ^ ¬(x > y) } maxOf ← y { maxOf  ≥ x ^ maxOf  ≥ y }

 

Proof of true (then) case:  x > y

true ^ x > y	x > y true on execution of then
x > y	Simplification Rule of Inference
maxOf = x	maxOf ← x
maxOf  ≥ x ^ maxOf  ≥ y	x > y ^ maxOf = x      (by above 2 statements)
	∴ q is true: maxOf  ≥ x ^ maxOf  ≥ y

Proof of false (else) case: ¬(x > y)

true ^ ¬(x > y)	¬(x > y) true on execution of else
¬(x > y)	Simplification Rule of Inference
maxOf = y	maxOf ← y
y ≥ x	¬(x > y) → x ≤ y → y ≥ x
maxOf ≥ x ^ maxOf  ≥ y	y ≥ x ^ maxOf = y     (by above 2 statements)
	∴ q is true: maxOf  ≥ x ^ maxOf  ≥ y

Question 4.12

-- p:  true procedure abs( x : integer) if  x ≥ 0 then abs ← x       else abs ← -x -- q: abs = x ^ x ≥ 0 ⊕ abs = -x ^ x < 0

Prove the postcondition holds for the if-then-else true (then) case only.

if x ≥ 0 then abs ← x

1. Show true:  abs = x ^ x ≥ 0
    
2. Show false: abs = -x ^ x < 0

   Need only show one false in the ^

   Remember what is true when then is being executed.
    

3. Combine a. and b. using the exclusive or, ⊕

a	b	a ⊕ b
F	F	F
F	T	T
T	F	T
T	T	T

Basics of Induction Review

We determine that:

P(1) = 2 = 2 * 1

P(2) = 2 + 2 = 4 =  2 * 2

P(3) = 2 + 2 + 2 = 6 = 2 * 3

P(4) = 2 + 2 + 2 + 2 = 8 = 2 * 4

So we believe n additions of 2 to be:

P(n) = 2 + 2 + ... + 2 = 2 * n

 

How can we prove?

1. Prove a base case to be true.

   P(1) = 2 = 2 * 1

   P(2) = 2 + 2 = 4 =  2 * 2

   P(3) = 2 + 2 + 2 = 6 = 2 * 3

   P(4) = 2 + 2 + 2 + 2 = 8 = 2 * 4

   We already have. Pick any one of the above.

    

2. Assume our definition correct for some case n.

   P(n) = 2 + 2 + ... + 2 = 2 * n

   We proved correct in the base case: n=1, 2, 3 or 4.

    

3. Prove for case n+1 that

   P(n+1) = 2 * (n+1)
    

4. Use direct proof to show:

   p → q

   P(n) → P(n+1)

   P(n+1)	= 2 + 2 + ... + 2 + 2	Definition: P(n+1) = n+1 additions of 2
   	= P(n)                 + 2	Substitute: 2 + 2 + ... + 2 = P(n)
   	= 2n + 2	Substitute: P(n) = 2n
   	= 2 * (n+1)	P(n) → P(n+1)

We can assume

P(n) = 2 + 2 + ... + 2 = 2 * n

true because we showed some base case true: n = 4:

P(4) = 2 + 2 + 2 + 2 = 8 = 2 * 4

We then proved P(n+1) true for any n+1 case.

P(n) → P(n+1)

Loop Invariants

Invariant means unchanged The loop contains an invariant which describes what remains unchanged when loop executed Permits understanding what the loop does without having to understand (at the same time) how it does it. Can reason about the loop's effect without hand tracing each loop iteration. The loop invariant is always true: before the loop, initialization   at the end of each loop, maintenance   and after the loop completes, termination.

 

Example - Proof of loop invariant

The loop invariant is:

Pk = 2*k ^ k ≤ n

 loop invariant is always true:

1. Base Step: before the loop,	Pk = 2*k ^ k ≤ n Pk = 2  ^  1 ≤ n                  Given pre: 1 ≤ n
2. Induction Hypothesis: Pk Assume hypothesis on execution of: while k < n Pk = 2*k ^ k < n Pk = 2 + 2 + ... + 2   = 2*k 3. Prove: Pk+1 Show at the end of each loop, Pk+1 = 2*(k+1) ^ k+1 ≤ n pre: n ≥ 1 Pn( n ) k ← 1 Pk ← 2 Pk = 2*k ^ k ≤ n while k < n         Pk+1 ← Pk + 2         k ← k + 1         Pk ← Pk+1 Pn ← Pk post: Pn = 2*n	Pk+1 = 2 + 2 + ... + 2 + 2 Definition   = Pk + 2               From algorithm    Pk+1 ← Pk + 2   = 2 * k + 2 Hypothesis     Pk = 2 * k   = 2 * (k+1)         k+1 ≤ n because k < n true to execute: while k < n     ∴ Pk+1 = 2 * (k+1)  ^  (k+1) ≤ n   ∴ Pk = Pk+1                             Pk ← Pk+1
4. and after the loop completes	k = n                                          when loop terminates ∴ Pk = 2*k ^ k = n

The postcondition follows directly from the loop invariant at loop termination.

k = n

∴ P_k = 2*k ^ k = n

∴ P_n = P_k

 

Example - Proof of loop invariant - Factorial

Loop invariants are true:

1. before the loop
2. at the end of each loop
3. when loop terminates

The Factorial loop invariant is:

Pk = k! ^ k ≤ n

pre: n ≥ 1 Pn(n) k ← 1 Pk ← 1 Pk = k! ^ k ≤ n while k < n         Pk+1 ← Pk * k+1         k ← k + 1         Pk ← Pk+1 post: Pn = n!

P_k = k! ^ k ≤ n is always true:

1. Base Step: before the loop	P1 = 1! ^ 1 ≤ n          Given pre: n ≥ 1                                           Pk ← 1
2. Induction Hypothesis: Pk Assume Pk = k! ^ k < n Pk = 1 * 2 * ... * k   = k! 3. Prove: Pk+1 Show at the end of each loop, Pk+1 = (k+1)! ^ (k+1) ≤ n pre: n ≥ 1 Pn(n) k ← 1 Pk ← 1 Pk = k! ^ k ≤ n while k < n         Pk+1 ← Pk * k+1         k ← k + 1         Pk ← Pk+1 post: Pn = n!	Pk+1 = 1 * 2 * ... * k * k+1   = Pk * k+1   = k! * (k+1)   = (k+1)! k+1 ≤ n k < n true to execute: while k < n   k+1 ≤ n ∴ Pk+1 = (k+1)!  ^  (k+1) ≤ n
4. and after the loop completes	k = n ∴ Pk = k!  ^  k = n ∴ Pn = Pk

 

Example proof of loop invariant - Maximum of a sequence

Loop invariant proofs can also be performed by induction.

Note

maxOf(P_k, a_i+1) is maximum of P_k and a_i+1

Use of P_k and P_k+1 not necessary but helpful in thinking about the induction.

The loop invariant is:

∀j: 1 ≤ j ≤ i, aj ≤ Pk ^ i ≤ n

-- Precondition:  ∃a1 procedure Pn( a1, a2, a3, ..., an : integers) Pk ← a1 i ← 1 { invariant ∀j: 1 ≤ j ≤ i, aj ≤ Pk ^ i ≤ n} while  i < n Pk+1 ← maxOf(Pk, ai+1) i ← i + 1 Pk ←  Pk+1 -- Postcondition: ∀j: 1 ≤ j ≤ n, aj ≤ Pk

Show ∀j: 1 ≤ j ≤ i, a_j ≤ P_k ^ i ≤ n is always true

1. Base Step: before the loop,	∀j: 1 ≤ j ≤ 1, aj ≤ Pk                             ∃a1 ^ Pk = a1
2. Induction Hypothesis: Pk Assume (when loop executes) i < n ∀j: 1 ≤ j ≤ i, aj ≤ Pk 3. Prove: Pk+1 Show at the end of each loop: ∀j: 1 ≤ j ≤ i+1, aj ≤ Pk+1 ^ i+1 ≤ n -- Precondition:  ∃a1 procedure Pn( a1, a2, a3, ..., an : integers) Pk ← a1 i ← 1 { invariant ∀j: 1 ≤ j ≤ i, aj ≤ Pk ^ i ≤ n} while  i < n Pk+1 ← maxOf(Pk, ai+1) i ← i + 1 Pk ←  Pk+1 -- Postcondition: ∀j: 1 ≤ j ≤ n, aj ≤ Pk	Note that ∀j: 1 ≤ j ≤ i, aj ≤ Pk = a1 ≤ Pk^ a2 ≤ Pk ^ ... ^ ai ≤ Pk Pk+1 = maxOf(Pk, ai+1) = a1 ≤ Pk+1^ ... ^ ai ≤ Pk+1   ^     ai+1 ≤ Pk+1               because Pk ≤ Pk+1^ ai+1 ≤ Pk+1     i+1 ≤ n i < n true to execute: while k < n   ∀j: 1 ≤ j ≤ i+1, aj ≤ Pk+1  =  a1 ≤ Pk+1^ ... ^ ai ≤ Pk+1   ^    ai+1 ≤ Pk+1 ∴ ∀j: 1 ≤ j ≤ i+1, aj ≤ Pk+1^ i+1 ≤ n
4. and after the loop completes	i = n ∴ ∀j: 1 ≤ j ≤ i = n, aj ≤ Pk

 

Induction Proof of loop invariant - Summation of a sequence

Note

Use of P_k and P_k+1 not necessary but helpful in thinking about the induction.

Question 4.13 

a. What is the postcondition?

b. What is the loop invariant?

-- Precondition:  ∃a1 procedure Pn( a1, a2, a3, ..., an : integers) Pk ← a1 i ← 1 while  i < n Pk+1 ← Pk + ai+1 i ← i + 1 Pk ← Pk+1

Show ∀j: 1 ≤ j ≤ i, ∑a_j = P_k ^ i ≤ n is always true

1. Base Step: before the loop,	c. Base step?
2. Induction Step: Pk at the end of each loop,	d. Show what for Pk+1? e. Assume what?
3. Prove: Pk+1	f. Prove
4. and after the loop completes	i = n ∴ ∀j: 1 ≤ j ≤ i = n, ∑aj = Pk

 

Example - Correctness Proof of loop invariant - Linear Search

The loop invariant is:

∀j: 1 ≤ j < i; aj ≠ x ^ i ≤ n+1

-- pre: ∃x ^ ∃a1 procedure linear search (x: integer,                                         a1, a2, ..., an: integers)        i ← 1 ∀j: 1 ≤ j < i; aj ≠ x ^ i ≤ n+1 while  i ≤ n and x ≠ ai    i  ← i + 1 if i ≤ n then    location  ← i else    location  ← 0 -- post: ∀j: 1 ≤ j ≤ n, aj ≠ x → location = 0 --  XOR ∃k: 1 ≤ k ≤ n, ak = x → location = k

Show ∀j: 1 ≤ j < i; a_j ≠ x ^ i ≤ n+1 is always true

1. Base Step:  Show P1 is true before the loop,	Given: ∃x ^ ∃a1 ∀j: 1 ≤ j < 1; aj ≠ x ^ 1 < n+1 vacuously true since 1 ≤ j < 1 does not exist.
2. Inductive Step: Pk → Pk+1 at the end of each loop, Show Pk+1 ∀j: 1 ≤ j < i+1; aj ≠ x ^ i+1 ≤ n+1 Assume Pk (for loop execution to occur) i ≤ n ∀j: 1 ≤ j < i; aj ≠ x = Pk	∀j: 1 ≤ j < i, aj ≠ x → a1≠ x ^ ...^ ai-1≠ x = Pk Pk+1 = a1≠ x ^ ...^ ai-1≠ x ^ ai≠ x         = Pk ^ ai≠ x         = ∀j: 1 ≤ j < i; aj ≠ x ^ ai≠ x         = ∀j: 1 ≤ j < i+1; aj ≠ x  i+1 ≤ n+1 since i ≤ n for loop execution ∴ ∀j: 1 ≤ j < i+1; aj ≠ x ^ i+1 ≤ n+1
3. and after the loop completes, the following is false i ≤ n and x ≠ ai    and the inverse is true i > n or x = ai    Since mutually exclusive, only one can be true i > n xor x = ai	i > n xor x = ai ∴ ∀j: 1 ≤ j < i; aj ≠ x ^ i ≤ n+1 when i > n ∴ ∀j: 1 ≤ j < i; aj ≠ x ^ i ≤ n+1 when i ≤ n ^ ai = x

Postcondition

∀j: 1 ≤ j ≤ n, a_j ≠ x → location = 0 XOR ∃k: 1 ≤ k ≤ n, a_k = x → location = k

Most of the work has been completed in Step 3. above by proving correctness of the loop invariant.

Because the algorithm includes an if-else condition, we can prove the postcondition is true using the if-else rule of inference:

{test && P} S1 {Q}, { !test && P} S2 {Q}
           {P} if (test) then S1 else S2 {Q}

if i ≤ n then
   location  ← i
else
   location  ← 0

P	i > n xor x = ai                          From Step 3
test	i ≤ n                                          if i ≤ n
S1	location  ← i
S2	location  ← 0
Q	location = i v location = 0

Substituting P, S1, S2, and Q of the if-else conditional, we get:

{i ≤ n && i > n xor x = a_i} location ← i { location = i v location = 0}, {i > n && i > n xor x = a_i} location ← 0 { location = i v location = 0}
           {i > n xor x = a_i} if (i ≤ n) then location ← i else location ← 0 { location = i v location = 0 }

Both S1 and S2 must be proven (the true and false case) to hold for precondition P, producing the same Q postcondition.

true: {i ≤ n && i > n xor x = a_i} location ← i { location = i v location = 0}

false: {i > n && i > n xor x = a_i} location ← 0 { location = i v location = 0}

Proof of true case:

i ≤ n && i > n xor x = ai	i ≤ n given to be true i > n xor x = ai true from loop invariant
i ≤ n	Simplification Rule of Inference
x = ai	From loop invariant ∀j: 1 ≤ j < i; aj ≠ x ^ i ≤ n+1 when i ≤ n ^ ai = x
location ← i	i ≤ n && i > n xor x = ai From loop invariant, i is location where found, so false i > n and true i ≤ n && x = ai

Proof of false case:

i > n && i > n xor x = ai	i > n given to be true i > n xor x = ai true from loop invariant
i > n	Simplification Rule of Inference
x ≠ ai	From loop invariant ∀j: 1 ≤ j < i; aj ≠ x ^ i ≤ n+1 when i > n
location ← 0	i > n && i > n xor x = ai From loop invariant, x ≠ ai, is true so x = ai is false and true i > n && i > n