COMP250: Induction proofs.
Jérôme Waldispühl School of Computer Science
McGill University
Based on slides from (Langer,2012), (CRLS, 2009) & (Sora,2015)
Outline
• Induction proofs o Introduction o Definition
o Examples
• Loop invariants o Definition
o Example (Insertion sort)
o Analogy with induction proofs o Example (Merge sort)
forany n≥2, n2 ≥2n ?
f(x) = x2
g(x) = 2x
forany n≥5, n2 ≤2n ?
g(x) = 2x
f(x) = x2
Motivation How to prove these?
foranyn≥1, 1+2+3+4+!+n=n⋅(n+1) 2
foranyn≥1, 1+3+5+7+!+(2⋅n−1)=n2 foranyn≥5, n2 ≤2n
And in general, any statement of the form:
“for all n≥n0 , P(n)” where P(n) is some proposition.
Mathematical induction
Many statement of the form “for all n≥n0 , P(n)” can be proven with a logical argument call mathematical induction.
The proof has two components:
• Base case: P(n0)
• Induction step: for any n≥n0 , if P(n) then P(n+1)
n0
0
1
2
3
4
5
…
k
k+1
…
Principle
n0
0
1
2
3
4
5
…
k
k+1
…
Implies
etc.
0
1
2
3
4
5
…
k
k+1
…
Claim: foranyn≥1, Proof:
1+2+3+4+!+n= n⋅(n+1) 2
Example 1
• Basecase: n=1 1=1⋅2 2
• Induction step:
foranyk≥1, if 1+2+3+4+!+k=k⋅(k+1)
2
then 1+2+3+4+!+k+(k+1)= (k+1)⋅(k+2) 2
Example 1
Assume 1+2+3+4+!+k=k⋅(k+1) 2
then 1+2+3+4+!+k+(k+1) = k⋅(k+1)+(k+1)
2
= k⋅(k+1)+2⋅(k+1)
2
= (k+2)⋅(k+1)
2
Induction hypothesis
Summary Base case: P(1)
Induction step: for any k≥1, if P(k) then P(k+1) Thus for all n≥1, P(n) ☐
Example 2
Claim: foranyn≥1, 1+3+5+7+!+(2⋅n−1)=n2 Proof:
• Base case:
• Induction step:
n=1 1=12
foranyk≥1, if 1+3+5+7+!+(2⋅k−1)=k2 then 1+3+5+7+!+(2⋅(k+1)−1)=(k+1)2
Example 2
Assume 1+3+5+7+!+(2⋅k−1)=k2
then 1+3+5+7+!+(2⋅k−1)+(2⋅(k+1)−1)
=k2 +2⋅(k+1)−1 =k2 +2⋅k+1 =(k+1)2
Induction hypothesis
Example 3
g(x) = 2x
f(x) = 2x+1
Example 3
Claim: foranyn≥3, 2⋅n+1<2n Proof:
• Base case:
• Induction step:
n=3 2⋅3+1=7<23 =8
foranyk≥3, if 2⋅k+1<2k then 2⋅(k+1)+1<2k+1
Example 3
Assume 2⋅k+1<2k then 2⋅(k+1)+1
=2⋅k+2+1 <2k +2
Induction hypothesis
≤2k +2k =2k+1
fork≥1
Stronger than we need, but that works!
Example 4
g(x) = 2x
f(x) = x2
Example 4
Claim: foranyn≥5, n2 ≤2n Proof:
• Basecase: n=5 25≤32 • Induction step:
foranyk≥5, if k2≤2n then (k +1)2 ≤ 2k+1
Example 4
Assume k2 ≤2k then (k+1)2
=k2 +2⋅k+1 ≤2k +2⋅k+1
≤2k +2k =2k+1
Induction hypothesis From previous example
Example 5
Fibonacci sequence:
Fib0 = 0 base case
Fib1 = 1 base case
Fibn = Fibn-1 + Fibn-2 for n > 1 recursive case
Claim: For all n≥0, Fibn<2n
Base case: Fib0=0<20=1, Fib1=1<21=2
Q: Why should we check both Fib0 and Fib1?
Induction step: for any i≤k, if Fibi<2i then Fibk+1<2k+1
Assume that for all i ≤ k, Fibi < 2i
Then Fibk+1 = Fibk + Fibk-1 < 2k + 2k-1
≤ 2k + 2k = 2k+1
(Note variation of induction hypothesis)
Induction hypothesis (x2)
fork≥1
Example 5
Proving the correctness of an algorithm
LOOP INVARIANTS
Algorithm specification
• Analgorithmisdescribedby: – Input data
– Output data
– Preconditions: specifies restrictions on input data – Postconditions: specifies what is the result
• Example:BinarySearch
– Input data: a:array of integer; x:integer; – Output data: index:integer;
– Precondition: a is sorted in ascending order
– Postcondition: index of x if x is in a, and -1 otherwise.
Correctness of an algorithm
An algorithm is correct if:
– for any correct input data:
• it stops and
• it produces correct output.
– Correct input data: satisfies precondition
– Correct output data: satisfies postcondition
Problem: Proving the correctness of an algorithm may be complicated when the latter is repetitive or contains loop instructions.
How to prove the correctness of an algorithm?
• Recursive algorithm ⇒ Induction proofs • Iterative algorithm (loops) ⇒ ???
Loop invariant
A loop invariant is a loop property that hold before and after each iteration of a loop.
Insertion sort
fori ← 1tolength(A)-1 j←i
while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j←j-1
end while
end for
(Seen in previous lecture)
Insertion sort
1
3
5
6
2
4
n elements New element
already sorted
to sort
1
2
3
5
6
4
n+1 elements sorted
Loop invariant The array A[0…i-1] is fully sorted.
1
3
5
6
2
4
A[0…i-1]
i
Initialization
Just before the first iteration (i = 1), the sub-array A[0 … i−1] is the single element A[0], which is the element originally in A[0], and it is trivially sorted.
1
3
5
6
2
4
i=1
Maintenance
1
3
5
6
2
4
Iteration i
n elements already sorted
i
1
2
3
5
6
4
Iteration i+1
n+1 elements sorted
i+1
Note: To be precise, we would need to state and prove a loop invariant for the “inner’’ while loop.
Termination
The outer for loop ends when i ≥ length(A) and increment by 1 at each iteration starting from 1.
Therefore, i = length(A).
Plugging length(A) in for i−1 in the loop invariant, the subarray A[0 … length(A)-1] consists of the elements originally in A[0 … length(A)-1] but in sorted order.
A[0 … length(A)-1] contains length(A) elements (i.e. all initial elements!) and no element is duplicated/deleted.
In other words, the entire array is sorted.
Proof using loop invariants
We must show:
1. Initialization: It is true prior to the first iteration of
the loop.
2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
Analogy to induction proofs Using loop invariants is like mathematical induction.
• You prove a base case and an inductive step.
• Showing that the invariant holds before the first iteration is
like the base case.
• Showing that the invariant holds from iteration to iteration is like the inductive step.
• The termination part differs from classical mathematical induction. Here, we stop the “induction’’ when the loop terminates instead of using it infinitely.
We can show the three parts in any order.
MERGE-SORT(A,p,r) if p < r then
q=(p+r)/2
p
qr
Merge Sort
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)
Precondition:
Array A has at least 1 element between indexes p and r (p≤r)
Postcondition:
The elements between indexes p and r are sorted
Merge Sort (Merge method)
• MERGE-SORT calls a function MERGE(A,p,q,r) to merge the sorted subarrays of A into a single sorted one
• The proof of MERGE can be done separately, using loop invariants
MERGE (A,p,q,r)
Precondition: A is an array and p, q, and r are indices into the array such that p <= q < r. The subarrays A[p.. q] and A[q +1.. r] are sorted
Postcondition: The subarray A[p..r] is sorted
Procedure Merge
Input: Array containing sorted subarrays A[p..q] and A[q+1..r].
Output: Merged sorted subarray in A[p..r].
Merge(A, p, q, r) 1 n1¬q–p+1 2 n2 ¬ r – q
3
4
5
6
7 8 9 10 11 12 13 14 15 16
for i ¬ 1 to n1
do L[i] ¬ A[p + i – 1]
forj¬1ton2
do R[j] ¬ A[q + j]
L[n1+1] ¬ ¥ R[n2+1] ¬ ¥ i¬1
j¬1 fork¬ptor
do if L[i] £ R[j] then A[k] ¬ L[i]
i¬i+1 else A[k] ¬ R[j]
j¬j+1
A
Merge/combine – Example
...
1
6
8
9
26
32
42
43
...
L
R
6
8
26
32
¥
1
9
42
43
¥
Idea: The lists L and R are already sorted.
Correctness proof for Merge
• Loop Invariant: The array A[p,k] stored the (k-p+1) smallest
elements of L and R sorted in increasing order.
• Initialization: k = p
– Acontainsasingleelement(whichistrivially“sorted”) – A[p]isthesmallestelementofLandR
• Maintenance:
– Assume that Merge satisfy the loop invariant property until k.
– (k-p+1)smallestelementsofLandRarealreadysortedinA.
– NextvaluetobeinsertedisthesmallestoneremaininginLandR.
– ThisvalueislargerthanthosepreviouslyinsertedinA.
– Loopinvariantpropertysatisfiedfork+1.
• Termination Step:
– Mergeterminateswhenk=r,thuswhenr-p+1elementshavebeen inserted in A ⇒ All elements are sorted.
Correctness proof for Merge Sort
• Recursive property: Elements in A[p,r] are be sorted.
• BaseCase:p=r
– Acontainsasingleelement(whichistrivially“sorted”)
• Inductive Hypothesis:
– Assume that MergeSort correctly sorts n=1, 2, ..., k elements
• Inductive Step:
– ShowthatMergeSortcorrectlysortsn=k+1elements.
• Termination Step:
– MergeSortterminateandallelementsaresorted.
Note: Merge Sort is a recursive algorithm. We already proved that the Merge procedure is correct. Here, we complete the proof of correctness of the main method using induction.
Inductive step
• Inductive Hypothesis:
– AssumeMergeSortcorrectlysortsn=1,...,kelements
• Inductive Step:
– Show that MergeSort correctly sorts n = k + 1 elements.
• Proof:
– First recursive call n1=q-p+1=(k+1)/2 ≤ k
=> subarray A[p .. q] is sorted
– Second recursive call n2=r-q=(k+1)/2 ≤ k
=> subarray A[q+1 .. r] is sorted
– A, p q, r fulfill now the precondition of Merge
– The post-condition of Merge guarantees that the array
A[p .. r] is sorted => post-condition of MergeSort satisfied.
Termination Step
We have to find a quantity that decreases with every recursive call: the length of the subarray of A to be sorted MergeSort.
At each recursive call of MergeSort, the length of the subarray is strictly decreasing.
When MergeSort is called on an array of size ≤ 1 (i.e. the base case), the algorithm terminates without making additional recursive calls.
Calling MergeSort(A,0,n) returns a fully sorted array.