Proof Of Correctness
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.
Chapter 1 Induction - Recursion
sequence S is a list of objects, enumerated in some order:
A sequence can be defined by giving the value of S(k), for all
S(k):=2k defines the sequence: 2,4,8,16,32,...
Imagine instead that I give you the following recipe:
Can you compute S(2)? S(3) ? S(4) ?
- (b) If k>1, then S(k):=S(k-1)+k.
Could you compute any S(k), where k>0.
The sequence S(k) is fully and uniquely defined by (a) and (b).
We say that S is defined
recursively by (a) and (b).
(a) is the base case
- (b) is the induction step
The stair and the baby.
This is the idea of recursion (or induction), which is very useful
in maths and computer science.
It allows to reduce an infinite process to a finite (small) number
Define S(k) by S(1):=4.
Problem: how to compute S(2) ?
Define S(k) by S(k):=2S(k-1)
Problem: both the following sequences satisfies this definition!
Proof that any integer is even.
Pitfall: Both base case and induction step are necessary !
You need to know how to start, and you need to know how to continue.
1.2 Proofs by induction
Let S be the sequence defined by:
Goal: compute S(60)
The formula S(k)=2k-1 is called a closed form formula
It allows to compute S(k) easily, without computing all the previous
values S(1),S(2),... S(k-1).
So, how to prove this conjecture ?
Introduce some notation
Let P(k) be the predicate: S(k)=2k-1.
For any positive integer k, P(k) is either true or false.
- Look at examples
Try the following:
Now, can you prove P(60)?
- Assume that P(27) is true. Can you prove that P(28) is true
1.2.1 First principle of mathematical induction:
First principle of mathematical induction
Let P(k) be a predicate. If:
(a) P(1) is true
(b) For any k>1, P(k-1) true implies P(k) true
Then: P(k) is true for all k>=1.
P is the inductive hypothesis.
(a) is the base case.
(b) is the induction step.
Consider the sequence S defined as above by:
Let's prove that for all k, S(k)=2k-1.
Let P(k) be the predicate S(k)=2k-1.
S(1)=1=21-1. So, P(1) is true.
- Induction step:
Let k>1 be an integer, and assume P(k-1) is true: S(k-1)=2k-1-1.
So, P(k) is also true.
Conclusion: by the first principle of mathematical induction,
P(k) is true for all k>=1, i.e. S(k)=2k-1.
Let S(k):=1+3+5+···+(2k-1). Find a closed form formula for S(k).
Prove that k!>2k for any k>=4.
Prove that for any integer k, 22k-1 is divisible by 3.
Prove that a+ar+ar2+···+arn=a-arn/1-r.
Find a closed form formula for S(k):=14+24+··· k4.
Hint: the difficulty is to find a suggestion. What tool could you
use for this?
The chess board problem.
1.2.2 Other forms of induction:
Define the sequence F(n) by:
F(k)=F(k-1)+F(k-2), for all k>2.
Can you compute F(3),F(4),F(5)?
This sequence is the famous and useful Fibonacci sequence.
To compute F(k), you not only need F(k-1), but also F(k-2).
That's fine, because to compute F(k), you only need to know the
values of F(r) for r<k.
So that does not fit into the previous induction scheme.
Second principle of Mathematical induction:
Let P(k) be a predicate. If
(a) P(1) is true,
(b) For any k>1, [ P(r) true for any r, 1<= r<k ]
implies P(k) true,
then: P(k) is true for all k>=1.
Any integer is a product of prime integers
The coin problem
We did not prove that the first (or the second) principle of induction
Let's just give an idea of the proof:
The three following principles are in fact equivalent:
the first principle of induction
- (b) the second principle of induction
- (c) the principle of well ordering:
every non empty collection of positive integers has a smallest member.
Is the principle of well ordering valid for Z ? R ? C
1.3 Other uses of induction
Induction is a much more general problem solving principle.
If you have a family of problems such that:
Then, you can solve by induction any problem in your family.
There is some measure of the size of a problem
- You can solve the smallest problems
- You can breakup each bigger problems in one (or several) strictly
smaller cases, and build from it a solution for the big problem.
Problem: computation of F(k).
Measure of the problem: k.
Value of F(1) is known.
F(k) can be computed from the values of F(k-1) and F(k-2)
Inductive definition of well formed formulas from formal logic
This kind of inductive description is called *BNF* (Backus Naur
<basic proposition>: A | B | C | ...
<binary connective>: /\ | \/ | -> | <-
<wff>: <basic proposition> | <wff>' | (<wff>) | <wff> <binary
Recursive proof of a property of wff
If a wff contains n propositions (counted with repetition: in A\/ A,
there are two propositions), then it contains n-1 binary connectives.
Recursive algorithm for the computation of the value of a wff:
bool function Evaluation(P, C)
// Precondition: P is a wff, C is the context, i.e.
// the truth values of all the basic propositions.
// Postcondition: returns the truth value of P in the // context C
If P is a proposition (say A) Then
Return the truth value of A;
ElseIf P is of the form (Q) Then
Return Evaluation(Q, C);
ElseIf P is of the form Q' Then
Return not Evaluation(Q,C);
ElseIf P is of the form Q1/\ Q2 Then
Return Evaluation(Q1, C)and Evaluation(Q2, C);
... // Other binary operators
Error P is not a wff;
There are programming languages that are particularly well adapted
to write this kind of algorithms. Actually, the real program would
almost look like the pseudo-code. See for example CAML ftp://ftp.inria.fr/lang/caml-light/
Bijection between words of parenthesis and forests
Induction is a fundamental technique for solving problems, in particular
in computer science.
It's the mathematical formalization of the divide and conquer approach.
Proof Of Correctness
Induction, Recursion /
CSM MACS-358 /
Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:16 2007