Proof Of Correctness
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.

Induction, Recursion

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(k-1)+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(k-1)

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(k-1)+2^k-1

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(k-1).

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(k-1) 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^k-1.

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. So, P(1) is true.
Induction step:

Let k>1 be an integer, and assume P(k-1) is true: S(k-1)=2^k-1-1.

Then, S(k)=S(k-1)+2^k-1=2^k-1-1+2^k-1=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^k-1.

Exercice 2 Let S(k):=1+3+5+···+(2k-1). 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²+···+arⁿ=a-arⁿ/1-r.

Exercice 6 Find a closed form formula for S(k):=1⁴+2⁴+··· k⁴.

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(k-1)+F(k-2), 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(k-1), but also F(k-2).

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(k-1) and F(k-2)

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 n-1 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₁/\ Q₂ Then Return Evaluation(Q₁, C)and Evaluation(Q₂, 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 pseudo-code. See for example CAML ftp://ftp.inria.fr/lang/caml-light/.

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 MACS-358 / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:16 2007