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: There are two ways of doing this problem. In the first, we re-form the sum so the lower limit is 0 instead of x and apply the arithmetic sum formula.

∑_{i=x}^{y} 2i + 1 = ∑_{i=0}^{y−x} 2(i + x) + 1

= ∑_{i=0}^{y−x} 2i + 2x + 1

= (y − x + 1)(2x + 1) + 2 ∑_{i=0}^{y−x} i

= (y − x + 1)(2x + 1) + 2\frac{(y − x)(y − x + 1)}{2}

= (y − x + 1)(2x + 1 + y − x) = (y − x + 1)(y + x + 1) = ((y + 1) − x)((y + 1) + x)

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

In the second, we express this sum as the difference of two summations, one involving only y and one involving only x.

∑_{i=x}^{y} 2i + 1 = ∑_{i=0}^{y} 2i + 1 − (∑_{0=1}^{x−1} 2i + 1).

Now, since

∑_{i=0}^{n} 2i + 1 = n + 1 + 2\frac{n(n + 1)}{2} = n + 1 + n(n + 1) = n^{2} + 2n + 1 = (n + 1)^{2},

we can evaluate this to

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

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

Solution: First, we reorder the summations to get

∑_{j=1}^{n} ∑_{i=0}^{∞} (\frac{j}{j + 2})^{i} .

We can do this reordering because the value of j never depends on the value of i, we just use every possible pair of values for a nonnegative i and a j between 1 and n. Evaluating the inner summation, which is just an infinite geometric series, we get

∑_{j=1}^{n} \frac{1}{1 − \frac{j}{j+2}}

= ∑_{j=1}^{n} \frac{j + 2}{2}

= n + \frac{1}{2} ∑_{j=1}^{n} j

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

which simplifies to \frac{1}{4}n^{2} + \frac{5}{4}n.

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}} = 3 + ∑_{i=2}^{n} \frac{3}{i^{10}}
≤ 3 + ∫_{1}^{n} \frac{3}{x^{10}} dx
= 3 + 3 ∫_{1}^{n} \frac{1}{x^{10}} dx
= 3 + 3 [\frac{−1}{9x^{9}} ]_{1}^{n}
= 3 + [\frac{−1}{3x^{9}} ]_{1}^{n}
= 3 − \frac{1}{3n^{9}} + \frac{1}{3}
= \frac{10}{3} − \frac{1}{3n^{9}}

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

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

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

Solution:

θ(n)

We know that for sufficiently large n, n > (ln n)^{2} > ln n. (For instance, if n > e^{2} then (ln n)^{2} = 4 < e^{2}.) Thus, for sufficiently large n,

n + ln n + (ln n)^{2} < n + n + n = 3n.

Furthermore, as long as ln n is positive,

n + ln n + (ln n)^{2} > n.

Thus, for all sufficiently large n, n < g(n) < 3n, so g(n) = θ(n).

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

Solution: θ(1) Dividing the top and bottom by n − 1 yields h(n) = \frac{n+3}{n+1}. Now, since the top is greater than the bottom, h(n) > 1 for all n > −1. Furthermore, solving the equation \frac{n+3}{n+1} < 2 yields the solution n > 1. So for all n > 1, h(n) < 2. Thus, for all n > 1, we have 1 < h(n) < 2 so h(n) = θ(1).

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

Solution: 2^{θ(n)} Putting the summation in closed form yields j(n) = 2(4^{n})/3. Now certainly, log_{2} j(n) = log_{2}(2/3) + n log_{2}(4) = θ(n). Thus, j(n) = 2^{θ(n)}. However, as we showed in tutorial, ¬(4^{n} = O(2^{n})) so ¬(j(n) = θ(2^{n})). So 2^{θ(n)} best describes the asymptotic behavior of j(n).

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

Solution: θ(2^{n}) We know that sin n ≥ −1 so k(n) ≥ (2 − 1)2^{n−1} = \frac{1}{2}2^{n}. We also know that sin n ≤ 1 so k(n) ≤ (2 + 1)2^{n+1} = 6 · 2^{n}. Thus, \frac{1}{2}2^{n} ≤ k(n) ≤ 6 · 2^{n}, so k(n) = θ(2^{n}).

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

Solution: None of the above. By Stirling’s approximation, we know that l(n) = θ(n^{2} ln n^{2}) = θ(n^{2} ln n). Now, this grows faster than θ(1), θ(n), θ(n^{2}) and θ(n log n), and slower than θ(n!), θ(2^{n}) and 2^{θ(n)}, so “none of these” is the correct answer.

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

(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.

(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:

Plugging in A_{1} = 6 and B_{1} = 6 we get that xc_{1} = 6 − yc_{2} so 6 = d_{1}(6 − yc_{2}) + yd_{2}c_{2}. Solving for y we get

y = \frac{6 − 6d_{1}}{(d_{2} − d_{1})c_{2}} ,

so

x = \frac{−6 + 6d_{2}}{(d_{2} − d_{1})c_{1}} .

Finally, the number of ways to 3-color a 3 by n grid graph is A_{n} + B_{n} which is just

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}

this can be simplified a bit, to

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

(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:

Let’s guess that for some c ≠ 0 and some d, that A_{n} = c^{n} and B_{n} = dc^{n}. Then, substituting into the recurrence relation yields

c^{n} = 3c^{n−1} + 2dc^{n−1}

and

dc^{n} = 3c^{n−1} + 2dc^{n−1}

Dividing the top equation by c^{n−1} yields c = 3 + 2d. Subsituting this into the bottom equation and gathering terms yields 2d^{2} + d − 2 = 0, so

d = \frac{−1 ± \sqrt{17}}{4}.

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}. This was not required by the question, but for a sense of completeness, using these values and simplifying, the number of ways to 3-color a 3 by n grid graph is

(\frac{9 + 3\sqrt{17}}{2\sqrt{17}}) (\frac{5 + \sqrt{17}}{2})^{n} + (\frac{−9 + 3\sqrt{17}}{2\sqrt{17}}) (\frac{5 − \sqrt{17}}{2})^{n} .

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: First we solve the homogenous part. The characteristic equation is

r^{2} − 2 = 0

so r = ±\sqrt{2} are the solutions. Thus, our general solution is of the form α_{1}\sqrt{2}^{n} + α_{2}(−\sqrt{2})^{n}. For our particular solution, we guess that c2^{n} will work, where c is a constant. Plugging in, this gives us

c2^{n} = 2c2^{n−2} + 2^{n−1}
= c2^{n−1} + 2^{n−1}
2c2^{n−1} = c2^{n−1} + 2^{n−1}
c2^{n−1} = 2^{n−1}
c = 1

So we must now solve for α_{1} and α_{2} such that α_{1} + α_{2} + 2^{0} = α_{1} + α_{2} + 1 = 1 Therefore, α_{2} = −α_{1}. Furthermore,

\sqrt{2}α_{1} + (−\sqrt{2})(−α_{1}) + 2^{1} = 2\sqrt{2}α_{1} + 2 = 2

so α_{1} = α_{2} = 0 are our solutions. So the closed form solution for the recurrence relation is just

G_{n} = 2^{n}.

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.

Solution:

We let fp(nh) be our pigeon (for each n there is one pigeon), and let the pigeonholes be ranges of size .01. So the first pigeonhole would be those n for which the first two digits of fp(nh) after the decimal point are 0 and 0, the secound would have digits 0 and 1, and so on. Since there are infinitely many pigeons and only 100 pigeonholes, by the pigeonhole principle, there must be a pigeonhole with more than one pigeon in it.

Let m and n be two different numbers such that fp(nh) and fp(mh) end up in the same hole. Suppose, without loss of generality, that fp(nh) ≥ fp(mh). Then, fp(nh) − fp(mh) < .01.

Suppose l and m are the digits associated with the pigeonhole both n and m fall into. Then, we can write k = 10l + m and write

nh = \frac{k}{100} + α + ⌊nh⌋ and

mh = \frac{k}{100} + β + ⌊mh⌋ where 0 ≤ β ≤ α < .01

Now, we can subtract these two equations and get

nh − mh = α − β + ⌊nh⌋ − ⌊mh⌋ .

Since α ≥ β we know α − β ≥ 0. Since α < .01 we know α < 1, so α − β < 1. Thus,

nh − mh = α − β + ⌊nh − mh⌋ .

by the definition of the floor function. Thus, α − β = fp(nh − mh) = fp((n − m)h). Since n − m is an integer and is not equal to 0 (since m and n were different numbers), and since 0 ≤ fp((n − m)h) < .01 we know n − m must be an element of S. Thus, S is nonempty.

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:

This is just asking for a permutation of 10 out of 26 objects. Thus, the answer is P (26, 10) = \frac{26!}{(26−10)!} = \frac{26!}{16!}.

(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:

We proceed by using the inclusion/exclusion principle. It makes our job slightly easier that the word “TEST” can never appear in a rearrangement of the alphabet, since “TEST” contains the letter T twice. The number of valid arrangements is equal to A − E − S + B where A is the number of ways we can rearrange the alphabet, E is the number of ways we can rearrange the alphabet so that “EXAM” appears, S is the number of ways we can rearrange the alphabet so that “STUDY” appears, and B is the number of ways we can rearrange the alphabet so that both “EXAM” and “STUDY” appear.

A = 26!, since there are 26! ways of putting 26 distinct elements in order.

E = 23!. since there are 23! ways of ordering 23 objects: the string “EXAM” and the 22 other letters in the alphabet.

S = 22 · 21! = 22! by the same reasoning.

B = 19! by the same reasoning; this time there are two strings, “EXAM” and “STUDY” and 17 letters.

So the final answer is 26! − 23! − 22! + 19!.

(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:

Again, we prooced by inclusion/exclusion. A collection is not an ordered object, and we are obviously allowed to use letters more than once, so we use the formula for combinations with repetitions. Thus, the number of ways to choose a collection of 30 letters is \binom{30+26−1}{30} = \binom{55}{30}.

The number of ways to make a collection of 30 letters with k specified letters is the number of ways to make a collection of 30 − k letters (to which we add the specified letters). Thus, it is \binom{30+26−1−k}{30−k} = \binom{55−k}{30−k}.

Let A be the set of all collections which contain the letters ‘E’, ‘X’, ‘A’, and ‘M’. Let B be the set of all collections which contain the letters ‘S’, ‘T’, ‘U’, ‘D’, and ‘Y’. Let C be the set of all collections which contain the letters ‘S’, ‘E’, and which contains the letter ‘T’ at least twice. What we want is

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Now we note that A ∩ B has 9 fixed letters, A ∩ C and B ∩ C have 7, and A ∩ B ∩ C has 10 fixed letters. (For instance, “EXAM” and “TEST” overlap so we only have to have the ‘E’ once to form both words). Thus,

|A ∪ B ∪ C| = \binom{51}{26} + \binom{50}{25} + \binom{51}{26} − \binom{46}{21} − \binom{48}{23} − \binom{48}{23} + \binom{45}{20}

So our answer is

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

which, if you’re curious, evaluates to about 2.5 quadrillion.

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. Proof by contradiction by the diagonalization method: suppose S_{0}, S_{1}, … is a complete list of all elements of R. Consider the set S = {2^{−i} | 2^{−i} ∉ S_{i}}. Since S is a member of R it must appear in the list somewhere, so assume its number is n. This is a contradiction since 2^{−n} ∈ S ⇔ 2^{−n} ∉ S. Thus, there must not be any such complete list.

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

Solution:

Finite. The only two subsets in common between ℕ and {2^{−i} | i ∈ ℕ} are the subset containing 1 and the empty set. Thus, its size is 2.

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

Solution:

Countable. Each finite set of prime numbers defines a different integer, namely the product of all the numbers in the set. This mapping is injective since the prime factorization of a number is unique. Thus, N can be mapped into the natural numbers, so N is countable. (We can count T by listing the sets that map to integers in ascending order of the integers. So the first element would be ∅, the second would be {2}, and the fifth would be {2, 3}, et cetera).

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

Solution:

Uncountable. Each equivalence class is a countable set: if C were countable we could express R as the cartesian product of two countable sets (namely, the set of equivalence classes and ℚ). But this would make R countable and it is not.