Proof Techniques
Class notes
Proof Of Correctness
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.
Chapter 1 Induction  Recursion
1.1 Introduction
Définition 1
A sequence
S is a list of objects, enumerated in some order:
S(1),S(2),S(3),...,S(k),...
A sequence can be defined by giving the value of S(k), for all
k.
Exemple 1
S(k):=2^{k} defines the sequence: 2,4,8,16,32,...
Imagine instead that I give you the following recipe:

(a) S(1):=1.
 (b) If k>1, then S(k):=S(k1)+k.
Can you compute S(2)? S(3) ? S(4) ?
Could you compute any S(k), where k>0.
Proposition 1
The sequence S(k) is fully and uniquely defined by (a) and (b).
Définition 2
We say that S is defined recursively
by (a) and (b).

(a) is the base case
 (b) is the induction step
Exemple 2
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
of steps.
Exemple 3
Define S(k) by S(1):=4.
Problem: how to compute S(2) ?
Exemple 4
Define S(k) by S(k):=2S(k1)
Problem: both the following sequences satisfies this definition!

1,2,4,8,16,...
 3,6,12,24,48,...
Exemple 5
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
Problem 1
Let S be the sequence defined by:

S(1)=1
 S(k):=S(k1)+2^{k1}
Goal: compute S(60)

S(1) 
= 
1 
= 
S(2) 
= 
1+2 
= 
S(3) 
= 

= 
S(4) 
= 

= 
·
·
· 
·
·
· 
·
·
· 
·
·
· 
·
·
· 
S(k) 
= 
1+···+2^{k} 
= 

Conjecture 1
S(60)=
The formula S(k)=2^{k}1 is called a closed form formula
for S(k).
It allows to compute S(k) easily, without computing all the previous
values S(1),S(2),... S(k1).
So, how to prove this conjecture ?

Introduce some notation

Let P(k) be the predicate: S(k)=2^{k}1.
For any positive integer k, P(k) is either true or false.
 Look at examples

Exercice 1
Try the following:

Prove P(1),P(2),P(3)
 Assume that P(27) is true. Can you prove that P(28) is true
?
Now, can you prove P(60)?
1.2.1 First principle of mathematical induction:
Théorème 1
First principle of mathematical induction
Let P(k) be a predicate. If:
(a) P(1) is true
(b) For any k>1, P(k1) true implies P(k) true
Then: P(k) is true for all k>=1.
Définition 3
P is the inductive hypothesis.
(a) is the base case.
(b) is the induction step.
Exemple 6
Consider the sequence S defined as above by:
(a) S(1):=1.
(b) S(k):=S(k)+2^{k1}.
Let's prove that for all k, S(k)=2^{k}1.
Proof.
Let P(k) be the predicate S(k)=2^{k}1.

Base case:
S(1)=1=2^{1}1. So, P(1) is true.
 Induction step:
Let k>1 be an integer, and assume P(k1) is true: S(k1)=2^{k1}1.
Then, S(k)=S(k1)+2^{k1}=2^{k1}1+2^{k1}=2^{k}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)=2^{k1}.
Exercice 2
Let S(k):=1+3+5+···+(2k1). Find a closed form formula for S(k).
Exercice 3
Prove that k!>2^{k} for any k>=4.
Exercice 4
Prove that for any integer k, 2^{2k}1 is divisible by 3.
Exercice 5
Prove that a+ar+ar^{2}+···+ar^{n}=aar^{n}/1r.
Exercice 6
Find a closed form formula for S(k):=1^{4}+2^{4}+··· k^{4}.
Hint: the difficulty is to find a suggestion. What tool could you
use for this?
Exercice 7
The chess board problem.
1.2.2 Other forms of induction:
Exemple 7
Define the sequence F(n) by:
F(1):=1
F(2):=1
F(k)=F(k1)+F(k2), for all k>2.
Exercice 8
Can you compute F(3),F(4),F(5)?
This sequence is the famous and useful Fibonacci sequence.
Problem 2
To compute F(k), you not only need F(k1), but also F(k2).
So that does not fit into the previous induction scheme.
That's fine, because to compute F(k), you only need to know the
values of F(r) for r<k.
Théorème 2
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.
Exemple 8
Any integer is a product of prime integers
Exemple 9
The coin problem
We did not prove that the first (or the second) principle of induction
were valid.
Let's just give an idea of the proof:
Théorème 3
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.
Problem 3
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:

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.
Then, you can solve by induction any problem in your family.
Exemple 10
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(k1) and F(k2)
Exemple 11
Inductive definition of well formed formulas from formal logic
<basic proposition>: A  B  C  ...
<binary connective>: /\  \/  >  <
 <>
<wff>: <basic proposition>  <wff>'  (<wff>)  <wff> <binary
connective> <wff>
This kind of inductive description is called *BNF* (Backus Naur
form).
Exemple 12
Recursive proof of a property of wff
Théorème 4
If a wff contains n propositions (counted with repetition: in A\/ A,
there are two propositions), then it contains n1 binary connectives.
Exemple 13
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
Begin
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 Q_{1}/\ Q_{2} Then
Return Evaluation(Q_{1}, C)and Evaluation(Q_{2}, C);
... // Other binary operators
Else
Error P is not a wff;
End;
Remarque 1
There are programming languages that are particularly well adapted
to write this kind of algorithms. Actually, the real program would
almost look like the pseudocode. See for example CAML
ftp://ftp.inria.fr/lang/camllight/.
Exemple 14
Bijection between words of parenthesis and forests
1.4 Conclusion
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 Techniques
Class notes
Proof Of Correctness
Induction, Recursion /
CSM MACS358 /
Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:16 2007