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) = = · · · · · · · · · · · · · · · k S(k) = 1+···+2 = 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. 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=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 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 r1, [ P(r) true for any r, 1<= r=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: - 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 : A | B | C | ... : /\ | \/ | -> | <- | <-> : | ' | () | 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_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 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. ----------------------------------------------------------------------- This document was translated from LaTeX by HeVeA (http://pauillac.inria.fr/~maranget/hevea/index.html).