Complete Induction We need to look at more general forms of induction, at least briefly. Theorem (complete induction): (An E N.(Ax < n.Px)->Pn) -> (Ax E N.Px) Proof: By induction as usual. Suppose that (Ak E N.(Ax < k.Px)->Pk) is true. We prove (An E N.(Ax <= n.Px)) by induction (notice that this implies (An.Pn)). Basis step: Since (Ax < 0.Px) is vacuously true, P0 must be true by the hypothesis (Ak E N.(Ax < k.Px)->Pk), and this implies (Ax <= 0.Px), completing the proof of the basis step. Induction Step: Suppose that (Ax <= n.Px) (this is our inductive hypothesis). We want to show that (Ax <= n+1.Px). If x <= n+1, we either have x <= n, in which case Px follows by application of the inductive hypothesis, or x = n+1. So all that remains is to prove P(n+1). By ind hyp again, we have (Ax < n+1.Px) (since x < n+1 <-> x <= n) from which our hypothesis (Ak E N.(Ax < k.Px)->Pk), instantiated with k = n+1, allows us to deduce P(n+1). So we have shown (Ax <= n+1.Px) as desired, completing the proof by induction of (An E N.(Ax <= n.Px)), from which (An E N.Pn) follows immediately. An Example Complete induction is often used when functions defined by more general forms of recursion are used. For example, complete induction is often used when the Fibonacci numbers are involved. I'll do an example which Grantham also does in his book, deriving a formula for the Fibonacci numbers, but we will also do a little motivation! The Fibonacci numbers have the following recursive definition: F(0) = 0 F(1) = 1 F(n+2) = F(n) + F(n+1) The first few terms are 0,1,1,2,3,5,8... (the 0 is only there because we start indexing at 0). They belong to a whole family of sequences G satisfying G(n+2) = G(n) + G(n+1) For example, the ``Lucas numbers'' are often studied (I'll start their indexing at 1): 1,3,4,7,11,18... Here are some rather obvious facts about these sequences: Any sequence of this kind is determined by its first two elements. Suppose G and H are both sequences of this kind; then G+H is also a sequence of this kind. So is cG where c is a constant. Now comes the ``trick'': Suppose we could find a real number x such that 1+x = x^2; then the sequence 1,x,x^2,x^3... would belong to this family, because x^n + x^(n+1) = x^n*(1+x) = x^n*x^2 = x^(n+2). Of course we can find such a number x -- we can use the quadratic formula to find two of them! x^2-x-1 = 0 has roots (1 +/- sqrt(1+4))/2 by the quadratic formula; the two roots are x_1 = (1+sqrt(5))/2 and x_2 = (1-sqrt(5))/2. Now we can use this to develop a formula for the Fibonacci sequence (or for any sequence of this family). Suppose that F(n) = c_1*x_1^n + c_2*x_2^n. We have F(0) = c_1*1 + c_2*1 = 0 so c_2 = -c_1. We have F(1) = c_1*x_1 + c_2*x_2 = c_1*x_1 - c_1*x_2 = c_1*(x_1-x_2) = c_1*sqrt(5) = 1, so c_1 = 1/sqrt(5) and c_2 = -1/sqrt(5), and we obtain the formula F(n) = (x_1^n - x_2^n)/sqrt(5). The context in which you see this formula is the much more mysterious Exercise: Prove by complete induction that F(n) = (x_1^n - x_2^n)/sqrt(5) for each n (where x_1 and x_2 are defined as above). Proof: Suppose for a fixed n that this statement is true for every smaller value of n. We show that it is true for n as well. Case 1: n = 0 (x_1^0 - x_2^0)/sqrt(5) = (1-1)/sqrt(5) = 0 = F(0) Case 2: n = 1 (x_1^1 - x_2^1)/sqrt(5) = sqrt(5)/sqrt(5) = 1 as desired Case 3: n > 1 We have by the hypothesis of our complete induction that F(n-1) = (x_1^(n-1) - x_2^(n-1))/sqrt(5) and F(n-2) = (x_1^(n-2) - x_2^(n-2))/sqrt(5). We can then compute F(n) = F(n-1) + F(n-2) = (x_1^(n-1) - x_2^(n-1))/sqrt(5) + (x_1^(n-2) - x_2^(n-2))/sqrt(5) = ((x_1^(n-1)+x_1^(n-2))-(x_2^(n-1)+x_2^(n-2)))/sqrt(5) = ((x_1^(n-2)*(1+x_1))-(x_2^(n-2)*(1+x_2)) = (by algebraic facts about x_1 and x_2 already shown above) ((x_1^(n-2)*x_1^2)-(x_2^(n-2)*x_2^2) = (x_1^n - x_2^n)/sqrt(5) as desired, completing the proof. The fact that we need special cases for n=0 and n=1 has to do with the special form of the definition of the Fibonacci numbers (we could also develop a special ``Fibonacci induction'' which looks like standard induction except that there are two basis steps and the induction step uses the two previous values, but the more powerful generalization to complete induction is more generally useful). This is where we stopped on May 2.