Massachusetts Institute of Technology Handout 14 6.042J/18.062J: Mathematics for Computer Science March 21, 1995 Professors Mauricio Karchmer and Ron Rivest

Quiz 1 Solutions

Problem 1-1. Discover and prove a formula for ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )^{n}.

Conjecture: ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )^{n} = ( \begin{matrix}1 & n \\ 0 & 1 \end{matrix} ).

Proof. By induction on n.

Base Case: That the conjecture is true for n = 1 is obvious.

Inductive Step: Assume that the conjecture is true for n = k, k ≥ 1, i.e. assume that

( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )^{k} = ( \begin{matrix}1 & k \\ 0 & 1 \end{matrix} )

Now:

( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )^{k+1} = ( \begin{matrix}1 & k \\ 0 & 1 \end{matrix} ) ∗ ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} )
= ( \begin{matrix}1 & k + 1 \\ 0 & 1 \end{matrix} )

And this implies that the conjecture is true for n = k + 1. Thus, by induction, the conjecture is true for all n ≥ 1.

Problem 1-2. Prove that the following two sequences are equal:

u_{0} = 2
u_{n+1} = u_{n}^{2} − u_{n} + 1

v_{0} = 2
v_{n+1} = 1 + v_{0}v_{1} ⋯ v_{n}

Proof. By strong induction on n.

Base cases: When n = 0, u_{n} = v_{n}, by definition. When n = 1 then we have u_{n} = v_{n} = 3.

Inductive Step: Assume that the sequences agree up to the kth member, i.e. assume that u_{n} = v_{n}, ∀n, 0 ≤ n ≤ k where k ≥ 1. Now:

u_{k+1} = u_{k}^{2} − u_{k} + 1
= v_{k}^{2} − v_{k} + 1 (by the inductive hypothesis)
= v_{k}(v_{k} − 1) + 1
= v_{k}(v_{0} … v_{k−1}) + 1 (by the defininition for v_{k} and the fact that k ≥ 1)
= v_{0} … v_{k} + 1
= v_{k+1}

This implies that the sequences agree up to the k + 1st element. Thus, by induction, u_{n} = v_{n}, ∀n ≥ 0, i.e. the sequences are equal. (Note that when we used the formula for v we assumed that k is at least 1. In other words k+1 is at least 2. So we can’t use this step to go from n = 0 to n = 1. That’s why we had to show that u_{1} = v_{1} as a base case. In fact unless u_{0} = v_{0} = 0 or u_{0} = v_{0} = 2 the sequences aren’t the same)

Problem 1-3. For a function f : A ↦ B and a subset C ⊆ A, define f(C) = {b | f(a) = b for some a ∈ C}. Prove that if f is a 1-1(an injection), then f(C ∩ D) = f(C) ∩ f(D) for every C, D ⊆ A.

Proof. To prove this theorem we need to show the following two containments:

1. f(C ∩ D) ⊆ f(C) ∩ f(D). This is true for all functions not just injections. Let y ∈ f(C ∩ D). We know there must exist x ∈ C ∩ D such that f(x) = y. Since x ∈ C ∩ D, x is an element of C and also an element of D. Thus y ∈ f(C) and y ∈ f(D) which implies that y ∈ f(C) ∩ f(D).

2. f(C) ∩ f(D) ⊆ f(C ∩ D). To prove this we need f to be 1-1. Let y ∈ f(C) ∩ f(D). We know there exist x ∈ C and z ∈ D such that f(x) = f(z) = y. But since f is 1-1, x = z and so x ∈ C ∩ D. Thus y ∈ f(C ∩ D).

Problem 1-4. Define the poset ({1, 2, 3, 4, 5}^{2}, ≺) where (a, b) ≺ (c, d) iff a ≤ c and b ≤ d.

(a) Give an antichain which is as long as possible. The antichain is {(5, 1), (4, 2), (3, 3), (2, 4), (1, 5)}.

(b) Prove that the above antichain is the largest. Proof. The proof is by contradiction. Say we had a larger antichain. Consider the first component of all of the elements of this antichain. They are all integers from 1 to 5. If we had more than 5 elements in the antichain, there must be two elements with the same first component (pigeonhole principle). But then these elements are comparable violating the fact we have an antichain. Contradiction. Hence we could not have had an antichain with more than 5 elements.

(An alternate proof would be to show that the poset has a chain cover with no more than 5 elements. Then Dilworth’s theorem would guarantee us that the largest antichain has at most 5 elements too.)

Problem 1-5. The complement of an undirected graph G = (V, E) is the graph G^{c} = (V, E^{c}). That is, G^{c} contains exactly those edges that are not in G. Prove that if G is not connected then G^{c} is.

Proof. Suppose G = (V, E) is not connected. Then G can be divided into nonempty disjoint connected components G_{1}, G_{2}, … G_{k} (where k > 1). Consider any two vertices a, b in V. Let’s show that they are connected by a path in G^{c}.

Case 1 a and b are in different connected components of G. Then there is no edge in E connecting a and b. Thus E^{c} contains an edge connecting a and b.

Case 2 a and b are in the same connected component of G. Let c be a vertex in a different connected component. By case 1, a and c are connected, as are b and c. Thus a and b are connected through c.

Thus G^{c} contains a path from a to b, for any pair of vertices a, b in V. Thus G^{c} is connected.

Problem 1-6. Give an explicit bijection between ℝ and (0, ∞), where (0, ∞) is the set {x ∈ ℝ | x > 0}.

Here is a function that produces a bijective map. f(x) = e^{x}. It is 1-1 since x < y implies that e^{x} < e^{y}. It’s onto since for any z > 0, e^{ln z} = z.