CSE191 Assignment 8 Answer Key Fall 2013 ----------------------------------------------------------------------------- (1) For all n, let P(n) == 1^3 + 2^3 + ... + n^3 = (n(n+1)/2)^2. (a) P(1) then states 1^3 = (1(1+1)/2)^2 (b) This reduces to 1 = (2/2)^2 = 1, so the base case P(1) is true. (c) Given n >= 2, the inductive hypothesis is the statement P(n-1). This states that 1^3 + 2^3 + ... + (n-1)^3 = ((n-1)(n-1+1)/2)^2 = ((n-1)n/2)^2. (d) In the inductive step, the goal is to prove P(n), which is given above. (e) Borrow the assumed IH. Let A(n) stand for the LHS of the equation. Then IH P(n-1) states that A(n-1) = ((n-1)n/2)^2. Unrolling the sum, have: A(n) = A(n-1) + n3 = ((n-1)n/2)^2 + n^3, using IH to substitute. = (1/4)(n^2 - n)^2 + n^3, using a little algebra, = (1/4)(n^4 - 2n^3 + n^2) + n^3 = (1/4)n^4 - (1/2)n^3 + (1/4)n^2 + n^3 = (1/4)n^4 - (1/2)n^3 + n^3 + (1/4)n^2 = (1/4)n^4 + (1/2)n^3 + (1/4)n^2 = (1/4)(n^4 + 2n^3 + n^2) = (1/4)(n^2 + n)^2 = (n(n+1)/2)^2, giving A(n) = (n(n+1)/2)^2, which is the statement P(n). (f) Technically this allows us only to redeem P(n-1) --> P(n). Since n is general, we've proved (\forall n >= 2)[P(n-1) --> P(n)]. However, together with the base case P(1), the formal principle of induction allows one to deduce (\forall n)P(n), which is what we wanted. (So yes, the sum of the first n cubes is always a perfect square!) (2) Prove (\forall n > 1)P(n), where P(n) states that the sum of k2^k from k=1 to k=n equals exactly (n-1)2^{n+1} + 2. Basis (n=1): P(1) states that \sum_{k=1}^1 (k*2^k) = (1-1)*2^2 + 2. Well the LHS (left-hand side) is just 1*2^1 = 2, while the RHS is 0*4 + 2 = 2. So it checks out. Ind (n >= 2): Let any n >= 2 be given. Assume (IH) P(n-1), which expresses that \sum_{k=1}^{n-1} k2^k = (n-1-1)2^{n-1+1} + 2, which = (n-2)2^n + 2. Goal: show P(n). Do it: \sum_{k=1}^n k2^k = n2^n + \sum_{k=1}^{n-1} k2^k, = n2^n + (n-2)2^n + 2 (by IH P(n-1)) = n2^n + n2^n - 2*2^n + 2 = 2n2^n - 2^{n+1} + 2 = n2^{n+1} - 2^{n+1} + 2 = (n-1)2^{n+1} + 2. Therefore P(n) holds, and (\forall n >= 1)P(n) follows by induction.[] Footnote: this is a more-precise version of the MergeSort example covered in Monday's lecture, though still only for exact powers of 2. If you put N = 2^n, then the answer (n-1)2^{n+1} + 2 equals (log_2 N - 1)2N + 2 = N*log_2(N) + 2, which has "slack" in the addition term and otherwise makes the constant C in my lecture equal to 1. (3) Prove (\forall n > 1)P(n), where P(n) states n! < n^n. (a,b) Basis (n=2): P(2) states 2! < 2^2. LHS = 2, RHS = 4, and 2 < 4: True. (c,d) Induction (n>=3): Assume (IH) the stmt P(n-1) == (n-1)! < (n-1)^(n-1). Goal: Show P(n). Letting A(n) stand for n!, IH is A(n-1) < (n-1)^(n-1). (e,f) Then: A(n) = A(n-1)*n < [(n-1)^(n-1)]*n < [n^(n-1)]*n because we made the power base bigger = n^n. So A(n) < n^n, which means n! < n^n, as needed to be proved. Note that P(1) says 1! < 11 which is "1 > 1" which is false, and P(0) says 0! < 00, which also gives 1 on both sides and is false. Thus we really need to use n=2 as the basis. Footnote: the three above answers "morph" from the text's style to mine. Note how mine is efficient once you get it---indeed the first line even saves having to say what P(n) expresses again in the induction step. The whole thing is goal-oriented. (4) Prove (\forall n>=1)P(n), where P(n) == 3 divides A(n) =def n^3 + 2n. Basis (n=1): A(1) = 13 + 2*1 = 3, and 3 divides 3, so P(1) holds. Indiction (n>=2): Assume (IH) the statement P(n-1) == 3 divides A(n-1). Goal: show P(n). Now by assumption, 3 divides (n-1)3 + 2(n-1). So (\exists k)[3k = A(n-1)]. Then A(n) = n3 + 2n = (n-1)3 + 3n2 - 3n + 1 + 2n = (n-1)3 + 3n2 - 3n + 2(n-1) + 3 = (n-1)3 + 2(n-1) + 3n2 - 3n + 3 = 3k + 3n2 - 3n + 3 by IH = a multiple of 3, since every coefficient is 3. This 3 divides A(n), which is the statement P(n) we needed to show. The case n=0 says that 3 divides 0. This is OK: 0 = 3*0, and indeed 0 always counts as a multiple of a number, since it is congruent to 0 mod that number. So P(0) could be used as the base case. Finally, since A(n) = n^3 + 2n has only odd powers of n, A(-n) = -A(n), so you always get negative multiples of 3, which is fine. So the predicate actually does hold for all integers n. (5) Prove (\forall n)P(n), where P(n) == for any sets A_1,...,A_n and B, (A_1 - B) n (A_2 - B) n ... n (A_n - B) = (A_1 n A_2 n ... n A_n) - B. [Notation note: I don't mind using "n" for intersection since it suggests AND. In lecture I've written "set-minus" as \ rather than - like in the text. Either is fine.] Basis (n=1): P(1) states (A_1 - B) = A_1 - B, since an intersection of one item is just the item. But hey, let's see if the next case feels less trivial: Extra Basis (n=2): P(2) states (A_1 - B) n (A_2 - B) = (A_1 n A_2) - B. Let's use the fact that A - B = A n (~B). So the left-hand side becomes (A_1 n (~B)) n (A_2 n (~B)). By associativity and commutativity of intersection, this equals A_1 n A_2 n (~B) n (~B). Then by (~B) n (~B) = ~B, you get (A_1 n A_2) n (~B), which equals (A_1 n A_2) - B. So P(2) holds. Induction (n >= 3): Assume (IH) P(n-1), which states (A_1 - B) n ... n (A_{n-1} - B) = (A_1 n ... n A_{n-1}) - B. Now (A_1 - B) n (A_2 - B) n ... n (A_n - B) = [(A_1 - B) n (A_2 - B) n ... n (A_{n-1} - B)] n (A_n - B) = [(A_1 n ... A_{n-1}) - B] n (A_n - B) by IH P(n-1) = (E - B) n (A_n - B) where E = (A_1 n ... A_{n-1}) = (E n A_n) - B by the "extra" base case P(2!) = (A_1 n A_2 n ... n A_n) - B substituting back. Thus the proof did use more than P(1). This is tricky to see, but an important "pattern"---and the horse-of-another-color example shows it can be tricky. However, I must admit this particular example is pretty obvious, and could even be done using more "......" rather than induction. Indeed this is crisply shown by doing it in logic. In logic terms, P(n) expresses that for all x: x \in (A_1 - B) n (A_2 - B) n ... n (A_n - B) <==> x \in (A_1 n A_2 n ... n A_n) - B The LHS is <==> (\forall i) (x \in A_i & x \notin B) <==> [(\forall i) x \in A_i] & x \notin B [since B does not involve i] which gives the logical form of the RHS. Done with no fuss, no induction. (6) Prove (\forall n >= 18)P(n), where P(n) == (\exists a,b >= 0)[n = 4a+7b]. (a) Base cases: 18 = 4*1 + 7*2 19 = 4*3 + 7*1 20 = 4*5 + 7*0 21 = 4*0 + 7*3 (Note that the base cases used every mult. of 7) (b) Induction (n >= 22): Assume (IH) "for all m, 18 <= m < n, P(m)", where P(m) == "for some natural numbers c,d >= 0, m = 4c + 7d." (c) Goal: Prove P(n). Instead of the full strong-induction IH, it turns out we only need P(m) for the value m = n-4. Since n >= 22 here, m >= 18, so m is "in bounds". Thus we may apply P(m) confidently. (d) By IH P(n-4), there exist c,d >= 0 such that n-4 = 4c + 7d. Then take a = c+1, b = d. Then n = 4c + 4 + 7d = 4(c+1) + 7d = 4a + 7b, as was to be proven. (e) Thus (\forall n >= 18)P(n) follows by the principle of strong induction.