Let's prove that 12^n-1 is divisible by 11 for each n in N. Some practice: n 12^n - 1 As 11 * __ 0 1 - 1 = 0 11 * 0 1 12 - 1 = 11 11 * 1 2 144 - 1 = 143 11 * 13 What we want is an inductive/recursive view of 12^n-1. (By the way: I won't ask you to make a distinction between inductive and recursive, so please don't ask me to :)#). 12^n is inductive, and 12^n - 1 isn't much more trouble: 12^(n+1) - 1 = 12*[(12^n - 1) + 1] - 1 TRICK question: Let a_0 = 1, a_n+1 = 12 * a_n for every n in N. Prove that a_n = 12^n for every n in N. If 12^n - 1 = 11k, then 12^(n+1)-1 = 12*[11k + 1] - 1 = 11*12k + 12 - 1 = 11*12k + 11 = 11*(12k + 1) So it looks like we have the raw material for an inductive proof. Proof ----- For each n in N let P(n) be: 12^n - 1 is divisible by 11. [Question: what is wrong with just letting P(n) = 12^n - 1?] We prove \-/n in N, P(n) by induction. Base Case 12^0 - 1 = 0 = 11 * 0. I.S. Let n in N. Suppose P(n). Then 12^n - 1 = 11k for some k in Z (in fact k in N) by IH. Thus 12^(n+1)-1 = 12*12^n - 1 = 12*[(12^n - 1) + 1] - 1 = 12*[11k + 1] - 1 = 11*12k + 12 - 1 = 11*12k + 11 = 11*(12k + 1) where 12k + 1 in Z since k in Z. Nonzero Base Case ================= Question: for which n in N is n^2 <= 2^n? n n^2 2^n 0 0 1 1 1 2 2 4 4 3 9 8 4 16 16 5 25 32 6 36 64 7 49 128 8 64 256 Looks true for n all n in N except n = 3. 2^n is inductive: multiply by 2, or add 2^n to get next. n^2 not as clear. could force it: (n+1)^2 = (sqrt(n^2) + 1)^2 but this recalculates n and calculates (n+1)^2 from it :(#. alternative: (n+1)^2 = n^2 + 2n + 1 Is adding 2n + 1 to n^2 no more than doubling 2^n / adding 2^n? doubling n^2 / adding n^2? Because n^2 <= 2^n, the first question is logically easier, but does not completely remove the inductive aspect (which is the point of induction: view the question inductively, use the IH and prove a simpler non-inductive question). It requires comparing 2n + 1 to 2^n. We could write a helper proof (I just made up that term for us CS people: it's like a helper method, in mathematics it's called a Lemma, subproof or aside). But let's compare 2n + 1 and n^2. When is 2n + 1 <= n^2? This is like the algebra of O proofs from CSC165: 2n + 1 <= 2n + n, for n >= 1 = 3n <= n^2, for n >= 3 So n >= 3 guarantees it. Note that, unlike our original question about n^2 <= 2^n, we haven't determined all the n for which it works, because we only need enough to do our induction. But note that it can't be true for n = 2 since then combining it with 2^2 <= 2^2 would prove that 3^2 <= 2^3 (which is false!). So now we prove that n^2 <= 2^n for all n in N except n = 3. Proof ----- Note that it's a bit unclear whether we're claiming that n = 3 specifically doesn't work, or that we're only making a claim for n != 3. For n in N let P(n) be: n^2 <= 2^n. We prove that ~P(3) /\ \-/n in N, n!=3 -> P(n). Our table above shows P(0), P(1), P(2) and ~P(3). For n >= 4 we proceed by induction. Base Case (n=4): 4^2 = 16 <= 16 = 2^4. I.S. Let n in N, n >= 4. Suppose P(n). Then (n+1)^2 = n^2 + 2n + 1 <= n^2 + 2n + n, since n >= 1 = n^2 + 3n <= n^2 + n^2, since n >= 3 = 2n^2 <= 2*2^n, by IH = 2^(n+1). Note ---- Notice how the base case and inductive step work together here. The base case is P(4). The smallest case in the I.S. is P(4) -> P(5). So we can `get off the ground'. Reaching farther back ===================== What postage can be made from 4 and 7 cent stamps? I.e. for which n in N are there s and t in N such that n = 4s + 7t? We made a table in class, seemed to think that it can be done for all n >= 18 (and some earlier ones, but not 17). It was noticed that if we can make the postage for n, then we can make it for n + 4 by simply including an extra 4. Since we saw that 18, 19, 20 and 21 can be done, we can get the next four (22, 23, 24, 25) from them, and then so on inductively. For n in N let P(n) be: n = 4s + 7t for some s, t in N. We prove that \-/n in N, n >= 18 -> P(n), by induction. Note: I'm not summarizing what happens before 18. Proof ----- Base Cases (n = 18, 19, 20, 21): 18 = 1*4 + 2*7 19 = 3*4 + 1*7 20 = 5*4 + 0*7 21 = 0*4 + 3*7 I.S. Let n in N, n >= 21. Suppose P(i) for all i with 18 <= i <= n. Then n + 1 = (n - 3) + 4 = (4s + 7t) + 4 for some s, t in N, by IH for i = n - 3, since n >= 21 -> n - 3 >= 18 and also n - 3 <= n. = 4(s+1) + 7t. Since s and t in N, s + 1 and t in N. Notes ----- The base cases cover 18 to 21. The smallest inductive step is [\-/i in N, 18 <= i <= 21 -> P(i)] -> P(21+1) i.e. P(18)/\P(19)/\P(20)/\P(21) -> P(22). So together they start us properly. The IH is assuming everything from the base case up to (but not including) n + 1 in order to prove P(n + 1). This is sometimes called complete or strong induction. But except when studying induction most people don't bother with the name. Similarly there is a name to specify that it is not this kind of induction: weak or simple induction. The proof shows a situation where it's less clear that P is true for the previous case we need, and we made a justification. In previous proofs when we looked at P(n+1) we literally used the string "n+1" and it inspired us to see it in terms of P(n). But to prove [\-/i in N, 18 <= i <= n -> P(i)] -> P(n+1) writing P(n+1) in terms of "n+1" wasn't helpful, especially because it didn't involve P(n). This is typical of strong induction, and so there's a slightly different form more commonly used. We see this in the next proof. Trees ----- What is the maximum number of nodes that a ternary (branching factor 3) tree of height h can have? (From the possible definitions of height we choose: the number of levels.) We conjectured that it's 1 + 3 + 9 + 27 + ... + 3^(h-1). (Almost?) no one remembered the closed formula for the geometric series, so we learned a valuable lesson about the value of proof: it's useful even if we only want to just use the result! Let S = 1 + 3 + ... + 3^(h-1). Then 3S = 3 + ... + 3^(h-1) + 3^h. So 2S = 3^h - 1, so S = (3^h - 1)/2. Both the sum and the closed formula are nice and inductive. What about "the maximum number of nodes in a ternary tree of height h"? Note: as mentioned in class, this example is simple enough for many of you to 'see'. It lets us concentrate on the form. One way to look at building a ternary tree from one/ones of lesser height is by adding leaves to a tree of height one less. But this often doesn't work as well as one might like. Often better is to view a tree of height h > 0 as made up of a root and subtrees of smaller height. In a ternary tree each node has at most three children (by definition of ternary), so the root has at most three subtrees, and each has height <= h - 1 (notice we're not assuming they all have height h - 1!) With this view of ternary trees, we now give a proof. Proof ----- For each h in N let M(h) be the maximum number of nodes in a ternary tree of height h P(h) be: M(h) = (3^h - 1) / 2. [Shall I ask again: what is the key difference between P(h) and M(h)?] We prove \-/h in N, P(h), by induction. [We will not have an explicit base case! We will handle all h in the I.S., assuming all earlier cases.] I.S. Let h in N. Suppose P(i) for all i in N with 0 <= i < h. Let t be a ternary tree of height h. If h = 0, t is the empty tree, so M(0) = 0 = (1 - 1) / 2 = (3^0 - 1)/2 If h > 0, t has a root with three subtrees t1, t2 and t3 of heights h1, h2 and h3, where 0 <= h1,h2,h3 < h. Since tree heights are in N, h1, h2, h3 < h implies h1, h2, h3 <= h - 1. So P(h1), P(h2) and P(h3) by IH. So number of nodes in t_i <= (3^h_i - 1)/2 <= (3^(h-1)-1)/2 So number of nodes in t is 1 for the root plus number in the subtrees <= 1 + 3 * (3^(h-1)-1)/2 = (2 + 3^h - 3)/2 = (3^h - 1) / 2. So M(h) <= (3^h - 1) / 2. Notes ----- For h = 0, 0 <= i < h is vacuous, so we aren't assuming anything when proving P(0) in the I.S. Thus we essentially do a base case inside the I.S. Then for h = 1, we assume P(i) for 0 <= i < 1, i.e. we assume P(0). From it we prove P(1). This is how the induction gets off the ground. The above also shows how to reason about a maximum based on individual elements (i.e. M(h) via an `arbitrary' t of height h). And as mentioned earlier it shows the -> P(n) style (versus the -> P(n+1) style) of I.S.