Exam 2 Solutions

November 22, 2000

Problem 1 [25 points] Summations

Find the closed form for each of the expressions listed below. Give your answer in simplified form.

(a) (10 points): ∑_{i=x}^{y} 2i + 1

Solution:

(y + 1)^{2} − x^{2}.

Grading standard:

3 points for knowing to break up the sum (as in ∑_{0}^{y} − ∑_{0}^{x−1}) 2 points for getting the limits right when breaking up OR 3 points for rearranging the limits (for instance as in sum_{0}^{y−x}) 2 points for simplifying correctly to an arithmetic sum 2 points for applying the arithmetic sum correctly 2 points for getting the algebra right 1 point for giving a simplified answer.

There are 2 methods I’d expect to see; these correspond to the first two point categories and the second two point categories. (Give points only for the first pair of categories or the second, not both).

Students should get at least 9 points if their answer is right. An example of an answer that would be right but worth only 9 points would be

y(y + 1) + y + 1 − x(x − 1) − x.

(b) (15 points): ∑_{i=0}^{∞} ∑_{j=1}^{n} (\frac{j}{j+2})^{i}

Solution:

\frac{1}{4}n^{2} + \frac{5}{4}n or \frac{n(n+5)}{4} or \frac{n^{2}+5n}{4}

Grading standard:

3 point for reordering the summations 5 points for correctly applying the formula for an infinite geometric series 2 points for correctly applying the arithmetic series formula 3 points for getting all the algebra right 2 points for simplifying Once again, correct answers should get at least 13 points, and then only 13 if the answer is BADLY unsimplified. An answer like

n + \frac{n(n + 1)}{4}

should get 14 points. Any of the given answers should get all 15 points.

Problem 2 [10 points] Bounding Infinite Sums

Using the Integral Method, give an upper bound for

∑_{i=1}^{n} \frac{3}{i^{10}}

Solution: Since f(k) = \frac{3}{i^{10}} is monotonically decreasing for x > 1, we have:

∑_{i=1}^{n} \frac{3}{i^{10}} = 1 + ∑_{i=2}^{n} \frac{3}{i^{10}}
≤ 1 + ∫_{1}^{n} \frac{3}{x^{10}} dx
= 1 + 3 ∫_{1}^{n} \frac{1}{x^{10}} dx
= 1 + 3 [\frac{−1}{9x^{9}} ]_{1}^{n}
= 1 + [\frac{−1}{3x^{9}} ]_{1}^{n}
= 1 − \frac{1}{3n^{9}} + \frac{1}{3}
= \frac{4}{3} − \frac{1}{3n^{9}}

Hence, ∑_{i=1}^{n} \frac{3}{x^{10}} ≤ \frac{4}{3} − \frac{1}{3n^{9}} .

Grading Standard: Similar to problem 5 on pset 6. -10 for not using the Integral method with wrong answer -7 for both limits incorrect on the integral -4 for one limit incorrect on the integral -2 for making algebraic mistakes -6 for using the Integral method but not being tight (for example, first saying 3/i^{10} < 3/i^{2} and using the integral method from there)

Problem 3 [25 points] Asymptotic Notation

Determine which of the eight choices below best describes each function’s asymptotic behavior. No proofs are necessary. (5 points each)

θ(n) θ(n!) θ(n log n) θ(n^{2}) θ(1) θ(2^{n}) 2^{θ(n)} None of the above

Grading Standard: Give no partial credit, except on part (d) if they answer 2^{θ(n)} instead of θ(2^{n}). Give 2 points partial credit for this answer (the function given IS 2^{θ(n)} but this is not the best answer.)

(a) g(n) = n + ln n + (ln n)^{2}.

Solution: θ(n)

(b) h(n) = \frac{n^{2}+2n−3}{n^{2}−1}

Solution: θ(1)

(c) j(n) = ∑_{i=0}^{n} 2^{2i+1}

Solution: 2^{θ(n)}

(d) k(n) = (2 + sin(n))2^{n+sin(n)}.

Solution: θ(2^{n})

(e) f(n) = ln((n^{2})!).

Solution: None of the above.

Problem 4 [35 points] 3-coloring Grid Graphs

In Exam 1, we proved that an m by n grid graph is always 2-colorable. Thus, it must be 3-colorable. However, with 3 colors, we suddenly get a lot of choices for how to color the graph. In this problem we will solve the question “How many ways are there to 3-color a 3 by n grid graph?”

(Recall that a 3-coloring of a graph is an assignment of one of three colors to each vertex in the graph such that if two vertices are connected by an edge, they must have different colors. We consider two 3-colorings different if any vertex is colored differently between the two.)

(a) (8 points) Suppose we want to color the graph by first coloring the first n−1 columns, then choosing a coloring for the last column. However, the number of ways we can color the last column is dependent on which coloring we choose. There are two cases to consider.

In the first case, the vertices (n − 1, 1) and (n − 1, 3) are the same color.

In the second case, the vertices (n − 1, 1), (n − 1, 2), and (n − 1, 3) are all different colors.

1. How many ways can we color the last column in the first case? 5

2. Of the ways to color the last column in the first case, how many use three different colors? 2

3. How many ways can we color the last column in the second case? 4

4. Of the ways to color the last column in the second case, how many use three different colors? 2

Grading: 2 points for each part, no partial credit.

(b) (10 points) Let A_{n} be the number of ways to 3-color a 3 by n grid graph such that the last column is colored with only 2 colors. Let B_{n} be the number of ways to 3-color a 3 by n grid graph such that the last column is colored with three different colors.

Formulate a system of recurrence relations for A_{n} and B_{n}, and give the initial values A_{1} and B_{1}.

Solution:

A_{n} = 3A_{n−1} + 2B_{n−1}.

B_{n} = 2A_{n−1} + 2B_{n−1}.

A_{1} = B_{1} = 6.

Grading:

1 point for each of the two initial conditions. 2 points for having a system in the right form. 2 points for each coefficient of A_{n−1}. 1 point for each coefficient of B_{n−1}.

(c) (7 points) Suppose that

A_{n} = xc_{1}^{n} + yc_{2}^{n}
B_{n} = xd_{1}c_{1}^{n} + yd_{2}c_{2}^{n}

is the solution to the recurrence relation you found in part (b). Find the number of ways to 3-color a 3 by n grid graph in terms of c_{1}, c_{2}, d_{1}, d_{2}, and n and no other variables.

Solution:

A_{n} + B_{n} = (\frac{−6 + 6d_{2}}{(d_{2} − d_{1})c_{1}} ) (1 + d_{1})c_{1}^{n} + (\frac{6 − 6d_{1}}{(d_{2} − d_{1})c_{2}} ) (1 + d_{2})c_{2}^{n}

Grading:

2 points for solving for x correctly (\frac{6d_{2}−6}{(d_{2}−d_{1})c_{1}} ) 2 points for solving for y correctly (\frac{6−6d_{1}}{(d_{2}−d_{1})c_{2}} ) 2 points for giving a final answer by adding A_{n} and B_{n}. 1 point for combining c_{1}^{n} and c_{2}^{n} terms in the final answer.

(d) (10 points) Find c_{1}, c_{2}, d_{1}, and d_{2} such that

A_{n} = xc_{1}^{n} + yc_{2}^{n}
B_{n} = xd_{1}c_{1}^{n} + yd_{2}c_{2}^{n}

is the general form for the system of recurrence relations you found in part (b).

Solution:

This gives two solutions, c_{1} = \frac{5+\sqrt{17}}{2}, d_{1} = \frac{−1+\sqrt{17}}{4} and c_{2} = \frac{5−\sqrt{17}}{2}, d_{2} = \frac{−1−\sqrt{17}}{4}.

Grading:

3 points for using A_{n} = c^{n}, B_{n} = dc^{n} to find answers for c and d 1 point for using B_{n} = c^{n}, A_{n} = dc^{n}, et cetera. 4 points for getting solutions for c and d. 2 points for correctly indicating c_{1}, c_{2}, d_{1}, d_{2}.

Problem 5 [15 points] Nonhomogenous Recurrence

Give a closed-form solution to the following nonhomogenous recurrence relation,

G_{n} = 2G_{n−2} + 2^{n−1}

such that G_{0} = 1 and G_{1} = 2.

Solution:

G_{n} = 2^{n}.

Grading:

2 points for identifying the homogenous part. 3 points finding the general form of the solution to the homogenous part. 3 points for guessing a2^{n} or the like for the particular solution. 2 points for solving for a. 5 points for finishing their solution.

If they didn’t use this method to find their answer, use this standard instead.

10 points for giving 2^{n} as an answer. 5 points for giving correct reasoning to support their answer.

So, if they just write out the first several terms and then write 2^{n} as their answer, they should get 10 points. If they do this and then prove that 2^{n} works, give them full credit.

Problem 6 [21 points] A Strange Set

Define the function fp(x) = x − ⌊x⌋. (fp stands for “fractional part.”) Recall that ⌊x⌋ is the greatest integer less than or equal to x. So, ⌊8.2⌋ = 8 and ⌊−2.3⌋ = −3. Let h = \sqrt{37}

Let S = {n ∈ ℤ | n ≠ 0 ∧ fp(nh) < 0.01}.

Use the pigeonhole principle to prove that S is nonempty. Other methods will not get credit.

Grading:

4 (mercy) points for appearing to understand the question. 4 points for correct “pigeons” (fp(nh) for each n ≠ 0 ∈ ℤ. 4 points for correct “pigeonholes” (ranges of size .01). 2 points for subtracting two pigeons to get an element in S. 1 points for correctly dealing with which of the elements to subtract from which. 4 points for proving their element is such that fp(nh) < 0.01. 2 points for proving their element is such that n ≠ 0.

The first 4 points are designed to give to people who wrote stuff that wasn’t the start of a proof but showed some understanding of the problem (ie, understanding the set S, the function fp, et cetera). This way, if someone struggles with the problem but doesn’t solve it, they get more credit than someone who doesn’t even try.

The 4 points for getting the ”pigeons” right go to not only what the pigeons *are* but also how to assign them to pigeonholes. Thus, for instance, saying each nonzero integer is a pigeon is only worth part of the credit. Saying fp(nh) for each nonzero integer n are the pigeons makes it clear that we should use this value to choose the pigeonhole and so this is worth full credit.

Problem 7 [45 points] Rearranging the Alphabet

For this problem you do not need to evaluate an expression fully: you may leave it in terms of binomial coefficients, powers of numbers, factorials, and so on. For this problem we consider the alphabet to consist only of capital letters.

(a) (15 points) How many different strings are there of 10 letters such that no letter is used more than once?

Solution: \frac{26!}{16!}

Grading:

5 points for determining to use a permutation formula. 5 points for determining to use a formula that doesn’t allow repetitions. 5 points for correctly applying whatever formula they used.

If you can’t tell what formula they used AND they applied whatever formula it was incorrectly, just give them the first 5 points if they aren’t using binomial coefficients, or no points if they are.

(b) (15 points) How many ways can you rearrange the alphabet (using each letter only once) so that none of the words “TEST,” “EXAM,” and “STUDY” appear as consecutive letters in your arrangement?

Solution: 26! − 23! − 22! + 19!.

Grading:

3 points for attempting to use inclusion/exclusion. 2 points for setting up inclusion/exclusion correctly. 2 points for using permutations without repetitions for the terms. 1 points for getting the 26! term correct*. 1 points for noticing that “TEST” can never appear. 2 points for getting the 23! term correct. 2 points for getting the 22! term correct. 2 points for getting the 19! term correct.

* If they didn’t subtract from 26! they should lose the points for both getting the 26! term and for setting up inclusion/exclusion correctly.

(c) (15 points) How many ways are there to choose a collection of 30 letters such that none of the words “EXAM,” “STUDY,” and “TEST” can be formed using the letters in the collection?

Solution:

\binom{55}{30} − 2\binom{51}{26} − \binom{50}{25} + 2\binom{48}{23} + \binom{46}{21} − \binom{45}{20}.

Grading:

3 points for realizing we need to use inclusion/exclusion and setting it up. 5 points for using combinations with repetitions to come up with the terms. 3 points for using the formula correctly. 3 points for getting the size correct on each of the three two-set intersections. 2 points for getting the size correct on the 3-set intersection.

What I mean by getting the size correct is that they understand the intersection issues (ie, that the ‘E’ in EXAM and TEST need not be in the collection twice).

Problem 8 [24 points] Finite and Infinite Sets

For each of the following sets, state whether it is finite, countably infinite, or uncountably infinite. If it is finite, give its size. If it is countably infinite, give an injective function from the given set to ℕ. If it is uncountable, give a brief argument.

(a) (6 points) R = P({2^{−i} | i ∈ ℕ})

Solution:

Uncountable.

Grading:

2 points for saying ”Uncountable.” 1 point for any argument with major holes or small errors in it. 2 points for any argument with holes in it. 3 points for any argument with minor holes, or calling on results that

are correct but never done in class or in the texts. 4 points for any correct, complete argument.

(b) (6 points) S = P(ℕ) ∩ P({2^{−i} | i ∈ ℕ})

Solution:

Finite; 2

Grading:

2 point for saying ”finite.” 2 points for giving 1 as the size (forgetting the empty set) 4 points for giving 2 as the size.

(c) (6 points) T, the set of all finite sets of prime numbers.

Solution:

Countable. Map a set S ∈ T to the number ∏_{p∈S} p.

Grading:

2 points for saying ”countable.” 1 point for any argument with major holes or small errors in it. 2 points for any argument with holes in it. 3 points for any argument with minor holes, or calling on results that

are correct but never done in class or in the texts. 4 points for any correct, complete argument.

Take off 1 point if their argument doesn’t involve a way to count the set T.

(d) (6 points) U, the set of all equivalence classes of the equivalence relation {(x, y) | x, y ∈ ℝ and x − y ∈ ℚ}

Solution:

Uncountable.

Grading:

2 points for saying ”uncountable” 1 point for arguing that there is a different class for every Real number. 2 points for setting up some incorrect diagonalization argument. 4 points for any correct argument.