CHAPTER 1 Induction - Recursion

1.1. Introduction

Définition. 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. 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. The sequence S(k) is fully and uniquely defined by (a) and (b). Définition. We say that S is defined recursively by (a) and (b).

• (a) is the base case

• (b) is the induction step Exemple. 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. Define S(k) by S(1) := 4. Problem: how to compute S(2) ? Exemple. 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. 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.2.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. 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. 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. P is the inductive hypothesis.

(a) is the base case.

(b) is the induction step. Exemple. 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.

1.2. PROOFS BY INDUCTION 3

(1) Base case:

S(1) = 1 = 2^{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^{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^{2} + ⋯ + ar^{n} = \frac{a−ar^{n}}{1−r}. 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. 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 1.2.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. 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. Any integer is a product of prime integers Exemple. 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. 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 1.2.3. Is the principle of well ordering valid for ℤ ? ℝ ? ℂ ?

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. 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. 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. Recursive proof of a property of wff

Théorème. If a wff contains n propositions (counted with repetition: in A ∨ A, there are two propositions), then it contains n − 1 binary connectives.

Exemple. 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. 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. 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.