# Chapter 4 Mathematical Induction

Modified

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Rosen text Web site learning resources, requires registration.

http://highered.mcgraw-hill.com/classware/selfstudy.do?isbn=0072880082 - Extra examples with solutions, self-assessments, interactive problems and other supplementary material.

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 or more cases (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 already 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)

Assumed 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 = 21

P(2) = 2 * 2 = 4 = 22

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

Want to show n multiplications of 2 to be:

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

How can we prove?

1. Prove a base case.

P(1) = 2 = 21

P(2) = 2 * 2 = 4 = 22

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

2. Assume hypothesis true for some case n.

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

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

3. Prove true for case n+1 that

P(n+1) = 2n+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 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)

Assumed true

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

Showed some base case true: n = 3:

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

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

Want to show 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 and what do we assume true for 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) = 2n+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 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 trueP(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

Prove: P(n) = 1 + 2 + 3 + ... + n = n(n+1)/2             for every integer n ≥ 1

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(k) = 1 + 2 + 3 + ... + k = k(k+1)/2

Define P(k) = 1 + 2 + 3 + ... + k = k(k+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 assumed true:

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

Prove: P(k+1)

Definition:   P(k+1) = 1 + 2 + 3 + ... + k + (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 + 22 + ... + 2n = 20 + 21 + 22 + ... + 2n = 2n+1 - 1

P(0) = 1 = 20 = 20+1 - 1 = 21 - 1  = 1

P(1) = 1 + 2 = 20 + 21 = 21+1 - 1 = 22 - 1 =3

Question 4.3.1   What are:

P(2) = ?

P(4) = ?

P(k) = ?

Base Step: P(1)

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

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

Induction Hypothesis: P(k)

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

Prove: P(k+1)

 P(k+1) = 20 + 21 + 22 + ... + 2k + 2k+1 Prove = 2k+1+1 - 1 = 2k+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. What is P(3) = ?

4. Base step?

P(1) =

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

6. P(k + 1) = 2 + 4 + 6 +…+ 2k +    ?                   Definition

7. 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)

k = 1 then:
12 = 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)

 P(k+1) = 12+22+32+ … +k2 + (k+1)2 Prove = (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 = n2

 P(n) = 1 + 3 + 5 + ... + 2n - 1 = n2
 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*2n = 2n+1

2/2 * 1/2n = 2/2*2n = 2/2n+1

*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)

 P(k+1) =  1 * 2 * 3 * ... * k * (k+1) Prove = 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 1

Induction Hypothesis: P(k)

FACTORIAL(k) = FACTORIAL(k-1) * k = k!

Prove: P(k+1) = (k+1)!

FACTORIAL(k+1) = FACTORIAL((k+1)-1) * (k+1)                     k+1 > 1 so the algorithm else return 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) FACTORIAL(k) = k! Induction Hypothesis = (k + 1)! Definition: n! = (n-1)! * n

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 2n subsets.

P(n) = 2n

For n=0, there are 20 = 1 subsets.

S = ∅

Subsets are: ∅

For n=2, there are 22 subsets.

S = {b, c}

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

For n=3, there are 22+22 = 23 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 2n subsets.

Base step

20 = 1 so P(0) is true for ∅

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

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

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

P(k+1) = 2k+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:

______    __    __
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 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): 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 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 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 4.8 Why is P(4) the base?

n = 3 then:
23 = 9 > 6 = 3!

Inductive Hypothesis: P(k)

By P(k) for k≥4:

2k < k!

Prove:  P(k+1)

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

2k+1 < (k+1)!

 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 n5 - n

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

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

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

P(n)        5 divides n5 - n

Base Step:

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

Question 4.9    Why is P(0) base?

Induction Hypothesis: P(k)

5 divides k5 - k

Prove: P(k+1)

5 divides (k + 1)5 - (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) = k5 - k 5 divides 5(k4 + 2k3 +2k2 + k) 5 divides P(k+1) = (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

Prove that 2+2+...+2 = 2*n

The loop invariant is:

 Pk = 2*k ^ k ≤ 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

Hand tracing shows loop invariant is always true when n = 4

 n k Pk Pk = 2*k ^ k ≤ n Invariant 4 1 2 Pk = 2  ^  1 ≤ 4 true Before loop k ← 1Pk ← 2 4 1 2 Pk = 2  ^  1 ≤ 4 true while 1 < 4 4 2 4 Pk = 2+2  ^  2 ≤ 4 true while 2 < 4 4 3 6 Pk = 2+2+2  ^  3 ≤ 4 true while 3 < 4 4 4 8 Pk = 2+2+2+2  ^  4 ≤ 4 true while 4 < 4 4 4 8 Pk = 8  ^  4 ≤ 4 true Termination
 Pk = 2*k ^ k ≤ n

Prove loop invariant is always true:

1. Base Step:     P1

Before the loop executes

while k < n

 Pk = 2*k ^ k ≤ n
Pk = 2  ^  1 ≤ n                  Precondition 1 ≤ n
k ← 1
Pk 2
2. Induction Hypothesis:     Pk
 Pk = 2 + 2 + ... + 2  = 2*k

Assume invariant true on loop execution

while k < n

 Pk = 2*k ^ k ≤ 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

3. Prove:       Pk+1

 Pk = 2 + 2 + ... + 2  = 2*k

Show at the end of each loop,

Pk+1 = 2*(k+1) ^ k+1 ≤ n

 Pk+1 = Pk + 2 From algorithm    Pk+1 ← Pk + 2 = 2 * k + 2 Induction 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

 Pk = 2*k ^ k ≤ n

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

Pk = 2*k ^ k n

Pn ← Pk

∴ Pn = 2*n

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!

Pk = 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(Pk, ai+1) is maximum of Pk and ai+1

Use of Pk and Pk+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, aj ≤ Pk ^ 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 Pk and Pk+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, ∑aj = Pk ^ 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; aj ≠ 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 = PkPk+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, aj ≠ x → location = 0 XOR ∃k: 1 ≤ k ≤ n, ak = 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 = ai} location ← i { location = i v location = 0}, {i > n && i > n xor x = ai} location ← 0 { location = i v location = 0}
{i > n xor x = ai} 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 = ai} location ← i { location = i v location = 0}

false: {i > n && i > n xor x = ai} 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