Solutions To Assignment 7

Solutions to Assignment 7

Problems:

1) Use induction to prove that n2 + n is even for all (positive) integers n (this is easy enough to prove directly, but please be sure to use induction to prove the statement to get practice with PMI).

Solution: Let P(n) be the statement " n2 + n is even". We need to show that P(1) is true, and that P(k) ? P(k+1) is true. P(1) is quick to check, since 12 + 1 = 1 + 1 = 2, which is even. Now, suppose that k2 + k is even, i.e., that k2 + k = 2j for some integer j. Then (k+1)2 + (k+1) = k2 + 2k + 1 + k + 1 = k2 + 3k + 2 = k2 + k + 2k + 2 = 2j + 2(k+1) is also even. Thus, by the Principle of Mathematical Induction, P(n) is true for all positive integers n.

Note that (k+1)2 + (k+1) = (k+2)(k+1) is automatically even, because one of the two integers k+1 and k+2 must be even, but if we use that reasoning we are not using PMI.

2) Do problem 3.2.5 on page 62

Solution: For positive integers m and n, we say that "m divides n" if n = km for some positive integer k. (Equivalently, we can also say that "n is a multiple of m".)

Let P(n) be the statement "6 divides n3 - n". P(1) is trivial, since 13 - 1 = 0, and every positive integer divides 0. (Technically, we've only defined "divides" for positive integers, so we could make the basis case P(2). P(2) checks out, since 23 - 2 = 8 - 2 = 6 is divisible by 6.) Now suppose that 6 divides k3 - k, i.e., that k3 - k = 6j for some positive integer j. Then (k+1)3 - (k+1) = k3 + 3k2 + 3k + 1 - k - 1 = 6j + 3k2 + 3k = 6j + 3(k2 + k). by the previous problem, k2 + k is even, so k2 + k = 2s, for some positive integer s. Thus (k+1)3 - (k+1) = 6j + 3(2s) = 6j + 6s = 6(j+s), which is divisible by 6. Thus, by the Principle of Mathematical Induction, P(n) is true for all positive integers n.

3) Let Cn be the nth set in the construction of the Cantor set. So C0 = [0,1], C1 = [0, 1/3] U [2/3, 1], etc., and the Cantor set C is the intersection of all of the Cn as n ranges from 0 to infinity. Use PMI to show that |Cn| = (2/3)n.

Solution: Let P(n) be the statement that |Cn| = (2/3)n. P(0) is true by construction, since |C0| = 1 = (2/3)0. Now, suppose that |Ck| = (2/3)k. Since Ck+1 is formed from Ck by removing the open middle one-third of each of the intervals that makes up Ck, we have that |Ck+1| = (2/3) |Ck|. But then, by the induction hypothesis, |Ck+1| = (2/3) (2/3)k = (2/3)k+1, and we are done.

4) Use PMI to prove that the sum of the first n squares (e.g. 12 + 22 + ... + n2) is equal to n(n+1)(2n+1)/6.

Solution: Let P(n) be the statement that 12 + 22 + ... + n2 = n(n+1)(2n+1)/6. P(1) is true, since 1(1+1)(2+1)/6 = 6/6 = 1 = 12. Now, suppose that 12 + 22 + ... + k2 = k(k+1)(2k+1)/6. But then 12 + 22 + ... + k2 + (k+1) 2 = (12 + 22 + ... + k2) + (k+1) 2 = k(k+1)(2k+1)/6 + (k+1) 2 = (k(k+1)(2k+1) + 6(k+1) 2)/6 = (2k3 + 3k2 + k + 6k2 + 12k + 6)/6 = (2k3 + 9k2 + 13k + 6)/6 = (k+1)(k+2)(2k+3)/6 = (k+1)((k+1)+1)(2(k+1)+1)/6, and we are done.

5) A final, nastier PMI question (nastier in terms of the algebra!) - use PMI to prove that the sum of the first n cubes is [n(n+1)/2]2 (note that since n(n+1)/2 equals 1 + 2 + ... + n, then this also shows that the sum of the first n cubes equals (1 + 2 +... + n)2, a somewhat surprising result).

Solution: Let P(n) be the statement that 13 + 23 + ... + n3 = [n(n+1)/2]2. P(1) is true, since [1(1+1)/2] 2 = 12 = 1 = 13. Now, suppose that 13 + 23 + ... + k3 = [k(k+1)/2]2. But then 13 + 23 + ... + k3 + (k+1) 3 = (13 + 23 + ... + k3) + (k+1) 3 = [k(k+1)/2]2+ (k+1) 3 = (k2(k+1)2 + 4(k+1) 3)/4 = (k4 + 2k3 + k2 + 4k3 + 12k2 + 12k + 4)/4 = (k4 + 6k3 + 13k2 + 12k + 4)/4 = (k+1) 2 (k+2) 2/4 = [(k+1)((k+1)+1)/2]2, and we are done.

6) Prove that every positive integer can be written as the sum of distinct powers of 2 using the principle of complete induction (i.e. problem 3.3.2 on page 63)

Solution: Let P(n) be the statement "n can be written as the sum of distinct powers of 2". P(1) is true, since 1 = 20. Now, suppose that P(j) is true for every positive integer j, where 1 ￡ j ￡ k, i.e., that we can write j = 2p1 + 2 p2 + 2 p3 + ... + 2 pt, where the powers pi satisfy p1 < p2 < p3 < ... < pt. Now consider k + 1. We have two cases.

Case 1: k + 1 is even. Then k + 1 = 2j, for some 1 ￡ j ￡ k, and so, by the (complete) induction hypothesis, k + 1 = 2(2p1 + 2 p2 + 2 p3 + ... + 2 pt) = 2p1+1 + 2 p2+1 + 2 p3+1 + ... + 2 pt+1, where the powers are still distinct.

Case 2: k + 1 is odd. Then k is even, and by the induction hypothesis, we can write k = 2p1 + 2 p2 + 2 p3 + ... + 2 pt, where 1 ￡ p1 < p2 < p3 < ... < pt. (Here all the powers are at least 1, since k is even.) But then k + 1 = 1 + 2p1 + 2 p2 + 2 p3 + ... + 2 pt = 20 + 2p1 + 2 p2 + 2 p3 + ... + 2 pt, and all the powers are distinct.

Thus we have P(1) and P(1) L P(2) L ... L P(k) ? P(k+1). So by the Principle of Complete Mathematical Induction, P(n) is true for all positive integers n.

7) Next we turn to when things can go wrong with PMI. First critique this next proof (i.e. again, is it a valid proof? are there holes in the logic? be sure to explain your answer carefully). Theorem: For every nonnegative integer n, sin(n) + cos(n) = 2n. Proof: We prove this by mathematical induction.

Base case: for n= 0, sin(0) = 0 and cos(0) = 1, so sin(0) + cos(0) = 1 = 20.

Induction step: assume that sin(n) + cos(n) = 2n for some value of n. By substituting the expression n+1 for the variable n, we get sin(n+1) + cos(n+1) = 2n+1, as desired. Thus by the principle of mathematical induction the proof is complete.

Solution: This statement is clearly false, since sin(n) and cos(n) are both between -1 and 1 for all n. The induction step is the problem - rather than showing (or trying to show) that P(n) ? P(n+1), the author merely assumed P(n) and then stated P(n+1).

8) And finally, figure out what is wrong with the example of PMI shown in Example 3.3.4 on page 63 - be sure to explain your answer carefully, i.e. don't just write that the example is wrong - that's pretty obvious from the erroneous conclusion!

Solution: The problem is again with the induction step, but this time it is a bit more subtle. In fact, the statement P(k) ? P(k+1) is true for all k at least 2, but it fails for k = 1. The author's justification for the induction step relies on P(2) (considering the 1st and the (k+1)st rabbit as a group of two), but P(2) is false!