From ecroot@math.gatech.edu Mon Nov 30 14:58:15 2009 Date: Mon, 30 Nov 2009 14:58:15 -0500 (EST) From: Ernie Croot To: Blackili Rudi Milhose Subject: hw 6... Dear Blackili, Here are the problems to grade from HW 6 (go to the course webpage on my homepage, and look where it says ``Homework 6'' -- there are two files that make up this HW): Part 1, #1, 3. Part 2, #2. Grade these problems for accuracy out of 20 points each (for a total of 60 points), and then quickly scan the remaining problems to see that they did them, and assign them a score out of 40 points for those problems. Solutions: Part 1, #1: We have to show that this relation is reflexive, symmetric, and transitive. * Reflexive: Clearly, x ~ x, since using q = 1, which is rational, we have x = q^4 x. * Symmetric: Suppose x ~ y. Then, there exists a non-zero rational q such that x = q^4 y. Now, letting q' = 1/q, we see that it is also a rational number; and, y = (q')^4 x, which means y ~ x. * Transitive: Suppose that x ~ y and y ~ z. Then, there exist non-zero rationals q and r, such that x = q^4 y, and y = r^4 z. So, x = q^4 (r^4 z) = (qr)^4 z, and since qr is a rational number (the product of two non-zero rationals is again rational), this means x ~ z, and we are done. Part 1, #3. Basically, this machine has 3 states, all of which are halt states. Call these states 1, 2 and 3. State 1 is the start state. The diagram should have three edges leading from state 1 to itself, where the edges are labeled A, C and G. There should be an edge from state 1 to state 2 labeled T; and there should be three edges leading from state 2 back to state 1, labeled A, C and G. Finally, there should be an edge leading from state 2 to state 3, labeled T; and there should be three edges leading from state 3 back to state 1, labeled A, C and G. Part 2, #2. The solution to this problem is quite similar to the proof of ``Euler's Theorem'' that I presented in class (which is in the textbook) -- the only difference is that I use polynomials x^(3j)-1, instead of x^(2j) - 1: It is relatively easy to see that the generating function for f(n) is given by F(x) = (1 + x + x^2)(1 + x^2 + x^4)(1 + x^3 + x^6) ... = product_{i=1}^infinity (1 + x^j + x^(2j)). But now, 1 + x^j + x^(2j) = (x^(3j) -1)/(x^j -1), meaning that F(x) can be rewritten as F(x) = ( (x^3 - 1)/(x - 1) ) * ( (x^6 - 1)/(x^2 - 1) ) * ... = product_{j=1}^infinity ( (x^(3j) - 1)/(x^j - 1) ). Now notice that the factors x^(3j) - 1 all cancel with a subset of the denominator polynomials here; and so, after removing those factors, we get F(x) = (1 / (x-1) ) * (1 / (x^2-1) ) * (1 / (x^4-1) ) * ... The terms that are ``missing'' are those of the form 1/(x^(3j) - 1). Expanding these 1/(x^j - 1) = 1 + x^j + x^(2j) + x^(3j) + ..., it should be clear that F(x) is the generating function for g(n) = # of partitions of n where no part is divisible by 3. Equating coefficients for the two different ways of writing F(x), we conclude f(n) = g(n). Q.E.D. Best, Ernie