Massachusetts Institute of Technology Handout 43 6.042J/18.062J: Mathematics for Computer Science October 30, 1998 Professors Nancy Lynch and Srinivas Devadas

Practice Quiz Solutions

Problem 1. Use induction to prove that

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

whenever n is a natural number.

Use induction to prove our proposition, P(n),

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

whenever n is a natural number. Base Case: n = 0 The left side is an empty sum, so 0 = (\frac{0·1}{2})^{2} = 0. Inductive Step: Show that P (n) → P (n + 1). By the inductive hypothesis, we assume that

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

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

And our hypothesis is proved.

Problem 2. Why can’t you find an integer x for which

384 · x = 1 (mod 566)?

This is equivalent to finding an integer x such that there is some integer y for which 384 · x + 566 · y = 1. Since 384 and 566 are even, the LHS must be even, so no integers can give equality to 1.

Problem 3. Prove the set identity

((A − B) ∪ (B − A))^{c} = (A^{c} ∪ B) ∩ (A ∪ B^{c})

Using the definition of set difference, both of De Morgan’s Laws, and the commutativity of union (in that order):

((A − B) ∪ (B − A))^{c} = ((A ∩ B^{c}) ∪ (B ∩ A^{c}))^{c} = (A ∩ B^{c})^{c} ∩ (B ∩ A^{c})^{c}

= (A^{c} ∪ B) ∩ (B^{c} ∪ A)
= (A^{c} ∪ B) ∩ (A ∪ B^{c})

Alternatively, one can use the definitions of the operations. We need to prove x is in the LHS if and only if it is in the RHS.

x ∈ ((A − B) ∪ (B − A))^{c} means that x ∉ (A − B) ∪ (B − A). This means that x ∉ A − B and x ∉ B − A.

So consider cases. If x ∈ A, then certainly x ∈ A ∪ B^{c}. Furthermore, since by assumption x ∉ A − B, we must have x ∈ B. Thus, x ∈ B ∪ A^{c}. Putting these together shows x ∈ (A∪B^{c})∩(B∪^{c}). Now consider the other case. If x ∉ A, meaning x ∈ A^{c}, then certainly x ∈ A^{c} ∪ B. Also, (since x ∉ B − A), we must have x ∉ B. That is, x ∈ B^{c}. Therefore, x ∈ B^{c} ∪ A. Thus, x ∈ (A^{c} ∪ B) ∩ (B^{c} ∪ A).

This proves one direction; the other is similar (but you have to include it in the real quiz!).

Problem 4. Use the following tables to describe the properties of the various functions. Write yes or no in each box. Don’t give proofs (it’d be too hard to squeeze them into the boxes). Pay careful attention to the specified domains and ranges.

• f : ℕ → ℕ, f(x) = 5x.

• g : ℝ^{+} → ℕ, g(x) = ⌊x⌋.

• h : ℝ → ℝ^{+}, h(x) = e^{x}.

Give an inverse if one exists (under the given domain and range).

function  injective surjective inverse
f(x) = 5x  yes  no  none
g(x) = ⌊x⌋  no  yes  none
h(x) = e^{x}  yes  yes  ln(x)

Problem 5. Consider the following algorithm, which takes natural numbers a and b, with b > 0, and returns an ordered pair of natural numbers.

Algorithm Div(a, b)

if (a < b)

return (0, a) else

(q, r) ←Div(a − b, b) return (q + 1, r)

(a) Prove Div terminates in at most a + 1 steps.

We model the algorithm as a state machine with state (q, r). The initial state is (a, b). Termination occurs when the termination condition (a < b) is reached. We define the derived variable f(q, r) = q. It is seen that f is non-negative. Furthermore, f is decreasing because then next value of q at each step is a − b, where by “step” I mean a recursive call to Div. Therefore, termination occurs in at most a steps (+1 for the last iteration).

(b) Prove that Div returns the quotient and remainder of a on division by b.

Recall that the quotient and remainder of a on division by b are defined to be the unique integers q and r such that a = qb + r and 0 ≤ r < b. These integers must exist by the Division Algorithm. We use strong induction on a. Base case: a < b. Then Div immediately returns (0, a). Since a = 0 · b + a and 0 ≤ a < b, these are the quotient and remainder of a on division by b. Inductive step: a ≥ b. Then 0 ≤ a − b < a. In this case, there is a recursive call Div(a − b, b). By the IH, this recursive call returns the quotient and remainder of a − b on division by b. So a − b = qb + r and 0 ≤ r < b. Then a = (q + 1)b + r and 0 ≤ r < b. So q + 1 and r are the quotient and remainder of a on division by b, and these are returned by Div.

Problem 6. David is located at position (1, 0) on the two-dimensional (ℤ × ℤ) x-y plane. His house is located at the origin. David wants to go home. But it is windy, and each time David takes a one-unit step east or west, he also gets blown a one-unit step north or south (he can pick which).

\begin{aligned}& y \\ x \end{aligned}

(a) On the grid above, mark with X’s all the points that David can reach in one step. Mark with O’s the points that David can reach in two steps. (The axes labeled x and y intersect at David’s house.)

(b) Give an informal explanation for why David can never get home.

David starts off with the sum of his coordinates (1 + 0 = 1) odd. Every time he moves, the parity of each coordinate changes, so the sum of his coordinates remains odd. Since the sum of the coordinates of his home (0 + 0 = 0) is even, he can never reach it.

(c) Describe a state machine that represents David’s motion, and list its transitions.

We introduce state variables x, y ∈ ℤ. We designate exactly one start state: the one for which x = 1 and y = 0. The transitions are (x, y) → (x ± 1, y ± 1).

(d) Prove that David can never get home.

We use the following invariant: x + y is odd for all reachable states. This is true for the start state (0 + 1 = 1). For each transition, the sum is modified either by 0, −2, or 2. Thus each transition increases x + y by an even amount preserving the invariant. Since x+y is even for the state corresponding to home, it is not a reachable state of our state machine. Thus David can never get home.

Problem 7. Consider the following algorithm that takes an array (list) A[1 … n] of numbers such that A[1] < A[2] < ⋯ < A[n], and a number q, and is supposed to find q if it is present in the list.

Find(A, n, q)

i ← 1 j ← n + 1 While (j − i > 1)

choose some k with i < k < j if A[k] ≤ q i ← k

else

j ← k Return i

(a) prove this function terminates

Define a state machine whose state is (i, j) and the initial state is (1, n + 1). Define the derived variable f(i, j) = j − i. Note that at each step we choose a k such that i < k < j, and either set j = k or i = k. Therefore f is decreasing. Furthermore f is non-negative since j > i. We conclude that the algorithm terminates in at most n + 1 − 1 = n steps.

Now suppose that q = A[r] for some r.

(b) State an invariant of the while loop relating i, j, and r. The invariant should be “obviously provable by induction” but you need not prove it.

Our invariant is i ≤ r < j.

(c) Assuming the invariant, prove that Find returns r.

When the loop terminates, j − i ≤ 1 (from j ≤ i + 1). Also, the invariant still holds. So i ≤ r < j ≤ i + 1. Since i and r are integers, i = r. Since i is then returned, Find returns r.

Problem 8. An infinite sequence of natural numbers a_{1}, a_{2}, a_{3}, … is defined in such a way that a_{1} = 14, a_{2} = 35, and each later a_{i}, i ≥ 3, is obtained using one of the following rules:

Rule A Choose any two preceding elements of the sequence and define a_{i} to be their sum.

Rule B Choose any number k ≥ 1 of preceding elements of the sequence,and define a_{i} to be their product divided by 7^{k−1}.

Use the well-ordering principle to prove that every element in the sequence is a multiple of 7. (Hint: In case you have forgotten, the well-ordering principle says that every nonempty set of naturals has a smallest element.)

Proof. Let S = {all elements in the sequence that are not multiples of 7 }. Assume that S is nonempty. Then, by well-ordering, it has a smallest element a_{n}. If a_{n} is obtained by rule A, then a_{n} = a_{i} + a_{j} for some a_{i} and a_{j} smaller than a_{n}. But then a_{i} and a_{j} are multiples of 7 therefore a_{n} has to be a multiple of 7 also. If a_{n} is obtained by rule B, then there are k smaller elements in the sequence ,that are multiples of 7, so we can write them in the form a_{k} = 7n_{k}. a_{n} is the product of the a_{k} divided by 7^{k−1}. Then we can write

a_{n} = (∏_{i=1}^{k}(7n_{i}))/7^{k−1} = 7(∏_{i=1}^{k} n_{i})

Therefore a_{n} is also a multiple of 7.

Problem 9. Prove that among any set of 150 natural numbers, there must be three numbers, a, b, and c, such that all the pairwise differences, a − b, a − c, b − c, b − a, c − a, c − b, are multiples of 70.

Proof. Use Pigeonhole. Pigeons The 150 numbers. Holes The natural numbers mod 70. There is some hole with ⌈\frac{150}{70}⌉ = 3 pigeons, that is, three numbers a, b, c that are equivalent modulo 70. Then their differences are equivalent to 0 modulo 70, therefore they are divisible by 70.

Problem 10. For each of the following sets, either use diagonalization to prove that the set is uncountable, or else use dove-tailing or another technique to show that the set is countable. (If an answer to one part of the question follows from an answer you have already given to another part, then you need only indicate this – you don’t need to give a direct proof of the part that follows.)

(a) The set E of all the even natural numbers.

This set is countable. The function f(n) = 2n is a bijection from ℕto E.

(b) The set of all subsets of E.

This set is uncountable. Suppose, for the purposes of contradiction, that it is countable and let A_{1}, A_{2}, … be an ordering of the subsets. Note that then there is a bijection from E to the set of subsets of E that sends the natural number 2i to the set A_{i}. Let S be the subset of E defined by S = {2i ∈ E|2i ∉ A_{i}}. Let n be the integer to which S corresponds under the established bijection. Note that if 2n is in S, then it is not in E which is a contradiction. If it is not in S, then 2n should be in S by the definition of S, so we also have a contradiction. We conclude that the set of subsets of E is uncountable.

(c) The set of all finite subsets of E.

Let S_{i} = The set of all subsets of E with i elements. Each of the S_{i} is countable and the set under question is the countable union of all the S_{i}, therefore it is countable.

(d) The set of all even-size finite subsets of E.

This set is countable, being a subset of the set in part (c).

Problem 11. Give tight (Θ) bounds for

∑_{i=1}^{n} \frac{1}{\sqrt{i}}

You do not need to prove your answer formally, but you should show how you derived it.

We use the integration method for bounding summations.

∫_{1}^{n} \frac{1}{\sqrt{x}}dx ≤ ∑_{i=1}^{n} \frac{1}{\sqrt{i}} ≤ 1 + ∫_{1}^{n} \frac{1}{\sqrt{x}}dx
2x^{\frac{1}{2}} |_{1}^{n} ≤ ∑_{i=1}^{n} \frac{1}{\sqrt{i}} ≤ 1 + 2x^{\frac{1}{2}} |_{1}^{n}
2\sqrt{n} − 2 ≤ ∑_{i=1}^{n} \frac{1}{\sqrt{i}} ≤ 2\sqrt{n} − 1

That is

∑_{i=1}^{n} \frac{1}{\sqrt{i}} = Θ(\sqrt{n}).

Problem 12. For each of the following pairs of functions f(n) and g(n), fill in the blank with O, Ω, Θ, o or ω, depending on whether f(n) = O(g(n)), f(n) = Ω(g(n)), f(n) = Θ(g(n)), f(n) = o(g(n)) or f(n) = ω(g(n)). If there is more than one relation between f(n) and g(n), write only the strongest one (a relation X is stronger than another relation Y if X implies Y but the converse does not hold). The first line is an example solution. Note: lg n = log_{2} n.

2n = Θ (n)
lg(n^{3}) = Θ (lg n)
n! =  ω  (4^{n})
2^{log_{3} n} =  o  (n^{2})
∑_{i=1}^{n} 1/i =  ω  (1)
n^{4.01} =  ω  (n^{4} lg n)
∑_{i=n}^{∞} 1/i^{2} =  o  (1)
\binom{n}{10} = Θ (n^{10})
8^{lg n} = Θ (n^{3})

Problem 13. Find asymptotic bounds for the following recurrences. You may assume that T (n) = Θ(1) for n ≤ 1 in each part.

(a) T (n) = 2T (⌊n/2⌋) + Θ(n)

h(n) = ⌊n/2⌋ − n/2. 2(\frac{1}{2})^{p} = 1 ⇒ p = 1. Hence we have that

T (n) = Θ(x(1 + ∫_{1}^{x} \frac{u du}{u^{2}})) = Θ(x(1 + ln x)) = Θ(x ln x)

(b) T (n) = 4T (⌊n/2 + \sqrt{n}⌋) + Θ(n^{2})

h(n) = ⌊n/2 + \sqrt{n}⌋ − n/2. 4(\frac{1}{2})^{p} = 1 ⇒ p = 2. Hence we have that

T (n) = Θ(x^{2}(1 + ∫_{1}^{x} \frac{u^{2} du}{u^{3}})) = Θ(x^{2}(1 + ln x)) = Θ(x^{2} ln x)

(c) T (n) = T (⌈n/3⌉) + 2T (⌊n/4⌋) + Θ(n)

We rewrite the recurrence as T (n) = T (n/3+(⌈n/3⌉−n/3))+2T (n/4+(⌊n/4⌋− n/4)) + Θ(n). By taking logs on both sides of (\frac{1}{3})^{p} + 2(\frac{1}{4})^{p} = 1 and simplifying, we get p = \frac{ln 2}{ln 12} < 1. Hence we have that

T (n) = Θ(x^{p}(1 + ∫_{1}^{x} \frac{u du}{u^{p+1}} )) = Θ(x^{p}(1 + x^{1−p})) = Θ(x)

Problem 14. In the following problem there is no direct connection between the two parts.

(a) Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of one month and six new pairs of rabbits at the age of two months and every month afterwards. None of the rabbits ever die or leave the island. Find a recurrence relation for the number of pairs of rabbits on the island n months after one newborn pair is left on the island. Do not solve the recurrence relation.

Let N(t) be the number of pairs of rabbits after t months. Then N(0) = 1, N(1) = 3, and we have that, for t ≥ 2:

N(t) = 7N(t − 2) + 3(N(t − 1) − N(t − 2)) = 3N(t − 1) + 4N(t − 2)

(b) Solve the following inhomogeneous recurrence relation:

f(n) = 6f(n − 1) − 9f(n − 2) + 2^{n}, n ≥ 2

The initial conditions are f(0) = 5, f(1) = 26. The characteristic equation r^{2} − 6r + 9 has a repeated root α = 3. Hence the homogeneous solution has the form f_{h}(n) = A3^{n} + Bn3^{n}, for some constants A and B. To find a particular solution, we try f_{p}(n) = K2^{n}. Plugging into the difference equation gives: K2^{n} = 6K2^{n−1} − 9K2^{n−2} + 2^{n} ⇒ K = \frac{6K}{2} − \frac{9K}{4} + 1 ⇒ 4K = 12K − 9K + 4 ⇒ K = 4

Hence the complete solution has the form f(n) = A3^{n} + Bn3^{n} + 2^{n+2}. We now use the initial conditions to solve for A and B: f(0) = 5 = A + 4 ⇒ A = 1 f(1) = 26 = 3 + 3B + 8 ⇒ B = 5

Hence the solution is f(n) = 3^{n} + 5n3^{n} + 4 · 2^{n}, n ≥ 2.