Massachusetts Institute of Technology Handout 10 6.042J/18.062J: Mathematics for Computer Science September 19, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 2 Solutions

Self-study: Read: Rosen, Discrete Mathematics and Its Applications, Section 2.3 up to p. 122 Self-study problems: (not to be handed in) Rosen, Section 2.3, exercises 1, 5, 7, 9, 11, 15, 29, 31, 33, 35, 37

Note: The self-study reading covers basic mathematical topics that we will not explicitly cover in lecture. We recommend that you read them and discuss any topics that are unclear to you with your TA during the weekly tutorial. The self-study problems are intended for you to get some practice with the mathematical topics covered by the self-study readings. The weekly mini-quiz will be based on that week’s self-study reading and/or problems.

—————————————————————————– Reading: Velleman, How to Prove It, Chapter 2; Sections 3.3, 6.1-6.4 Rosen, Sections 1.1, 3.1-3.3

Problem 1

(a) Rosen 1.3, 24 (c), (d), (e)

Solutions: Using the transformations on page 33 of Rosen, de Morgan’s laws, and the fact that ¬¬x = x: c. ∀y(¬Q(y) ∨ ∃xR(x, y)) d. ∀y(∀x¬R(x, y) ∧ ∃x¬S(x, y) e. ∀y(∃x∀z¬T (x, y, z) ∧ ∀x∃z¬U(x, y, z)

(b) Rosen 1.3, 34

Solutions: a. ∀x(P (x) ⟶ ¬S(x)) b. ∀x(R(x) ⟶ S(x)) c. ∀x(Q(x) ⟶ P (x)) d. ∀x(Q(x) ⟶ ¬R(x)) e. Yes. Combine c and a to get (1): ∀x(Q(x) ⟶ ¬S(x)). Then, take the contrapositive of b to get (2): ∀x(¬S(x) ⟶ ¬R(x)). Finally, combine (1) and (2) to get ∀x(Q(x) ⟶ ¬R(x)), which is statement d. Hence d follows from a, b, and c.

(c) Rosen 1.3, 52

Solution: ∀ϵ ∈ ℝ^{+}∃N ∈ ℕ^{+}∀n ∈ ℕ^{+}(n > N ⟶ |a_{n} − L| < ϵ)

Problem 2

(a) Give a formal reason for each starred line in the following structured proof. Refer to previous steps wherever you think that will be helpful in understanding your proof.

Given: ∀x∀y[P (x) ∨ Q(y)] Prove: (∀xP (x)) ∨ (∀yQ(y))

1. Assume ¬∀xP (x) 2(*). ∃x¬P (x) Negation of universal quantifier 3(*). Choose x_{0} such that ¬P (x_{0}). Existential Instantiation 4(*). ∀y(P (x_{0}) ∨ Q(y)) Universal Instantiation of hypothesis

5. ∀yQ(y)

1. Pick an arbitrary y_{0}

2(*). P (x_{0}) ∨ Q(y_{0}) Universal Instantiation, using 4.

3(*). Q(y_{0}) Propositional reasoning, using 5.2. and 3. 4(*). QED (∀yQ(y)) Universal Generalization

6(*). QED ((∀xP (x)) ∨ (∀yQ(y))) Propositional reasoning, using 5. (B ⟶ A ∨ B)

(b) Write your own structured proof of the other direction, complete with reasons:

Given: (∀xP (x)) ∨ (∀yQ(y)) Prove: ∀x∀y[P (x) ∨ Q(y)] Solution:

1. First, we will prove (∀xP (x)) ⟶ ∀x∀y[P (x) ∨ Q(y)] 1. Assume ∀xP (x)

2. To prove 1, use 1.1 to prove ∀x∀y[P (x) ∨ Q(y)] 1. Pick an arbitrary x_{0}, y_{0}

2. P (x_{0}) Universal Instantiation, from 1.1.

3. P (x_{0}) ∨ Q(y_{0}) Propositional reasoning, from 1.2.2 4. QED Universal Generalization

3. QED Implication

2. Next, prove (∀yQ(y)) ⟶ ∀x∀y[P (x) ∨ Q(y)] Similar argument to the one for 1.

3. Combine 1 and 2 to get [(∀xP (x)) ∨ (∀yQ(y))] ⟶ [∀x∀y[P (x) ∨ Q(y)]] Cases

4. QED Modus ponens, from 3. and “Given”.

Problem 3 Rosen 3.2, exercise 16.

Solution: The proof is by induction. Let P (n) be the proposition that 1 · 2 · 3 + 2 · 3 · 4 + … + n(n + 1)(n + 2) = \frac{n(n+1)(n+2)(n+3)}{4}. Base case: n = 1.1 · 2 · 3 = 6; \frac{1(2)(3)(4)}{4} = 6. Inductive step: By our inductive hypothesis, 1 · 2 · 3 + … + n(n + 1)(n + 2) = \frac{n(n+1)(n+2)(n+3)}{4}. Adding (n + 1)(n + 2)(n + 3) yields

1 · 2 · 3 + … + n(n + 1)(n + 2) + (n + 1)(n + 2)(n + 3)

= \frac{n(n + 1)(n + 2)(n + 3)}{4} + (n + 1)(n + 2)(n + 3)
= \frac{n(n + 1)(n + 2)(n + 3)}{4} + \frac{4(n + 1)(n + 2)(n + 3)}{4}
= \frac{(n + 4)(n + 1)(n + 2)(n + 3)}{4}

Hence P (n) ⟶ P (n + 1). QED.

Problem 4 Velleman 6.1, problem 7

Solution: The proof is by induction. Let P(n) be the proposition that 64|9^{n} − 8n − 1. Base case: n = 1. 9^{n} − 8n − 1 = 9 − 8 − 1 = 0. 64|0. Inductive step: We must prove that 64|9^{n+1} − 8(n + 1) − 1.

9^{n+1} − 8(n + 1) − 1 = 9^{n+1} − 8n − 9
= 9(9^{n} − 1) − 8n
= 9(9^{n} − 1) − 72n + 64n
= 9(9^{n} − 8n − 1) + 64n

Clearly, 64|64n, and we know 64|9^{n} − 8n − 1 from the inductive hypothesis. Hence

64|9^{n+1} − 8(n + 1) − 1.

So P (n) ⟶ P (n + 1). QED.

Problem 5 Velleman 6.2, problem 6

Solution: The proof is by induction. Let P(n) be the proposition that any equilateral triangle, that is cut into 4^{n} congruent equilateral triangles with one corner removed, can be tiled using tiles composed of three of the smaller congruent triangles. Base case: n = 1. With one corner removed, a single tile can be used to cover the remaining area. Inductive step: Consider a triangle, called T, cut into 4^{n+1} congruent equilateral triangles. We can think of this triangle as being cut into four smaller equilateral triangles, which are each then cut into 4^{n} equilateral triangles. Remove the top corner of T. We know that we can tile the triangle that contains the removed corner by the inductive hypothesis. Note that the remaining area contains three triangles, who have corners that meet in the same place; namely, the bottom of T, directly below the removed corner. If we consider each of these triangles with the touching corners removed, then the inductive hypothesis says that we can tile each one separately. To complete the Figure 1: Figure 1: The original triangle T. Dark lines indicate borders of the four smaller triangles; light lines indicate borders of the 4^{n} triangles that the smaller triangles are cut into. The black triangle is the removed corner; the gray triangles indicate the corners that are removed from the smaller triangles in order to apply the inductive hypothesis, which are then covered by a single tile.

tiling, simply use a single tile to cover the three adjacent removed corners. See Figure 1.

Problem 6

(a) What is the smallest natural number h such that towers of all heights greater than or equal to h can be built out of blocks of height 5, 6, and 9?

Solution: 14.

(b) Prove that h is the smallest such number.

Solution: This question has two parts: prove that h satisfies the requirement, and prove that no smaller number also satisfies the requirement. The first part is asked in part c. To prove the second part, we show that a tower of height 13 cannot be made with our given blocks, via a case analysis. Observe that if there were a way to build a tower of height 13, then this tower could have at most two blocks of heights 5 or 6. If there were more blocks of these heights, then the tower would be too long. Similarly, any valid solution can have at most one block of height 9. We can enumerate all the possible configurations consisting of at most two blocks of height 5 or 6, and at most one block at height 9, and check that none of them add up to thirteen. We can actually eliminate many of these cases.

Hence no natural number equal to or less than 13 satisfies the given requirements. Therefore, if 14 does satisfy the requirements, it must be the smallest such number.

(c) Prove that all heights h or greater can be built of of blocks of height 5, 6, and 9.

Solution: The proof is by strong induction. Let P(n) be the proposition that all natural numbers, starting with our smallest base case, going up to and including n, can be formed by adding 5, 6, and 9.

Base cases: 14 is formed by 5+9.

15 is formed by 6+9 (or 5+5+5). 16 is formed by 5+5+6. 17 is formed by 5+6+6. 18 is formed by 9+9 (or 6+6+6).

Inductive step: Assume P(n) to prove P(n+1). Note that we have proved P(n) true for five consecutive base cases. Hence, by our inductive hypothesis, we can always create a tower of height n+1-5. We can then simply add a block of height 5 to that tower, creating a tower of height n+1. P(n) ⟶ P(n+1). QED.

Problem 7 Velleman 6.4, problem 5 (a) (d) Note: By convention, the book considers F_{1} to be 1, F_{2} to be 1, F_{3} to be 2, and so on. In other places, you may see F_{0} = 1, F_{1} = 1, F_{2} = 2, etc.

Solutions:

(a) The proof is by induction. Let P (n) be the proposition that ∑_{i=0}^{n} F_{i} = F_{n+2} − 1. Base case: n = 1.

∑_{i=0}^{1} F_{i} = F_{0} + F_{1}
= F_{1}
= 1
= 2 − 1
= F_{3} − 1
= F_{1+2} − 1

Inductive step: We must prove ∑_{i=0}^{n+1} F_{i} = F_{n+3} − 1.

∑_{i=0}^{n+1} F_{i} = ∑_{i=0}^{n} F_{i} + F_{n+1}
= F_{n+2} − 1 + F_{n+1} by the inductive hypothesis
= F_{n+3} − 1 by the definition of F_{n}

P (n) ⟶ P (n + 1). QED.

(d) We can construct the following table:

n F_{n} ∑_{i=0}^{n} F_{2i}
1 1 1
2 1 4
3 2 12
4 3 33
5 5
6 8
7 13
8 21
9 34

Hmm. It looks like ∑_{i=0}^{n} F_{2i} might be F_{2n+1} − 1. So let’s take a crack at proving that.

The proof is by induction. Let P (n) be the proposition that ∑_{i=0}^{n} F_{2i} = F_{2n+1} − 1. Base case: n = 1.

∑_{i=0}^{n} F_{2i} = F_{0} + F_{2}
= F_{2}
= 1
= 2 − 1
= F_{3} − 1

Inductive step: We must prove ∑_{i=0}^{n+1} F_{2i} = F_{2n+3} − 1.

∑_{i=0}^{n+1} F_{2i} = ∑_{i=0}^{n} F_{2i} + F_{2n+2}
= F_{2n+1} − 1 + F_{2n+2} by the inductive hypothesis
= F_{2n+3} − 1 by the definition of F_{n}

P (n) ⟶ P (n + 1). QED.