Previous: Proof TechniquesProof Techniques Up: Class notesClass notes Next: Proof Of CorrectnessProof 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:

A sequence can be defined by giving the value of S(k), for all k.
Exemple 1   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) ?

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

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: Goal: compute S(60)

S(1) = 1 =
S(2) = 1+2 =
S(3) =   =
S(4) =   =
S(k) = 1+···+2k =

Conjecture 1   S(60)=

The formula S(k)=2k-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)=2k-1.

For any positive integer k, P(k) is either true or false.

Look at examples
Exercice 1   Try the following:
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

Let's prove that for all k, S(k)=2

Proof. Let P(k) be the predicate S(k)=2
  1. Base case:

    1-1. So, P(1) is true.

  2. Induction step:

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

    Then, S(k)=S(k-1)+2

    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

Exercice 2   Let S(k):=1+3+5+···+(2k-1). Find a closed form formula for S(k).

Exercice 3   Prove that k!>2k for any k>=4.

Exercice 4   Prove that for any integer k, 22k-1 is divisible by 3.

Exercice 5   Prove that a+ar+ar2+···+arn=a-arn/1-r.

Exercice 6   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?

Exercice 7   The chess board problem.

1.2.2  Other forms of induction:

Exemple 7   Define the sequence F(n) by:



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:
  1. the first principle of induction
  2. (b) the second principle of induction
  3. (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: 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(PC)

// 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(QC);

  ElseIf P is of the form Q' Then

    Return not Evaluation(Q,C);

  ElseIf P is of the form Q
1/\ Q2 Then

    Return Evaluation(Q
1C)and Evaluation(Q2C);

  ... // Other binary operators


    Error P is not a wff;

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

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.
Valid HTML 4.0! Previous: Proof TechniquesProof Techniques Up: Class notesClass notes Next: Proof Of CorrectnessProof Of Correctness
Induction, Recursion / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:16 2007