Some answers and variations from questions in Book

Some Problems from Section 2.3 P 124:
  1. Question 12: How many 0's at the end of 100! ?
    Well each 0 corresponds to a power of 10 = 2*5 in the sense that there are k zeroes iff both 2^k and 5^k divide 100! = 100 * 99 * ...
    There are 50 even numbers so certainly 2^{50} divides, let's focus on the power for 5.
    We've got 5, 10, 15, ... which is 20 powers of 5, and 25, 50, 75, 100 each contribute one extra. So we know 5^{24} divides 100!.
    The important thing is to show that now larger power will divide.
    This is the same as showing that 5 does not divide
    100! / (5^{24}) = 100/25 * 99 * ... * 96 * (95/5) * 94 * ... * (50/25) * ... * 6 * (5/5) * 4 * 3 * 2 * 1
    Remember that if gcd(a,b)=1 and a | b*c, then a | c. Let a = 5 and assume that a divides this big product 100!/5^{24}. Go through the numbers one by one, noting that gcd(a,100/25) = gcd(a,99) = ... to deduce the contradiction that a must divide 1. Obviously it does not so the assumption that a divides the product must be incorrect.
    A quicker way is to note that 5 is prime and we have the theorem that if a prime divides a product of numbers it must actually divide one of the numbers. Therefore 5 does not divide
    100/25 * 99 * ... * 96 * (95/5) * 94 * ... * (50/25) * ... * 6 * (5/5) * 4 * 3 * 2 * 1
  2. Question 24: (a) 2^{min(2,5)} * 3^{min(3,3)} * 5^{min(5,2)} = 2^2 * 3^3 * 5^2
    (b) 2^1 * 3^1 * 5^0 * 7^0 * 11^1 * 13^0 * 17^0
  3. Question 27: (b) compute -97 mod 11 . -9 * 11 is -99 and -97 is -99 + 2, hence -97 = 2 (mod 11).
    (c) 155 mod 19 = (155 - 190) mod 19 = (-35) mod 19 = (-35 + 38) mod 19 = 3.
    (d) -221 mod 23 = (-221 + 230 ) mod 23 = 9
  4. Question 33: Prove that if n|m and a=b (mod m), then a=b (mod n).
    Easy, assume a = b (mod m), hence a - b = k*m for some k. Now we have that n|m, hence m = s*n for some s. Then a - b = k*(s*n) = (k*s)*n. This means that a-b is a multiple of n which is equivalent to a = b (mod n).
  5. Question 36: If a = b (mod m), then gcd(a,m) = gcd(b,m).
    Lots of ways to do this. One is remember in the proof of the Euclidean algorithm: if r = q*s + c, then gcd(r,s) = gcd(s,c).
    Apply that here, we know that a = b + q*m for some q (since a=b (mod m)).
Now some from P88.
  1. Question 12: x log(x) is O(x^2) but x^2 is not O(x log(x)).
    We know that x is O(x) and log(x) is O(x), hence x * log(x) is O(x * x), by the Theorem stating f1 is O(g1) and f2 is O(g2) implies that f1 * f2 is O(g1 * g2).
    Directly from the definition we show x^2 is not O(x log(x)) by contradiction.
    Assume that there is some C and k so that
    |x^2| < C * | x log(x) | for all x > k.
    Can assume that k is large enough so that everything is positive so we get
    x^2 < C * x * log(x) allowing cancelling (if x> 0)
    x< C * log(x) for all x > k. Well we could actually stop here by saying that this would mean that the definition of x is O(log(x)) appears to be satisfied but we've been told to assume that x is not O(log(x)).
  2. I forgot to prove in class that x is not O((log x)^2).
    Well if x< C * (log x)^2 for all x > k, take logs of both sides:
    log(x) < log(C) + 2 log(log(x)) for all x> k.
    Take really big x of the form 2^y (for y> k, we get x> k)
    log(x) = log(2^y) = y < log(C) + 2 log(log(x)) = log(C) + 2 log(y) for all y> k
    But we know y < log(C) + 2 log(y) does not hold for all y> k, for any k and C, since y is not O(log(y)).
  3. Question 20: (a) (n^3 + n^2 log n)(log n + 1) + (17 log n + 19)(n^3 + 2)
    is O(n^3 log n). If we expand this out we get a sum of terms of the form n^i * (log n)^j. If i < 3, then it doesn't matter what j is we still have a term which is O(n^3). While looking it over we see that if i = 3, then j is never more than 1. So a sum of terms, each of which is O(n^3 log n), is itself O(n^3 log n).
  4. Question 41 and 42: Prove that O(n log n) = O(log n!).
    We did in class that n! < n^n, hence log n! < log n^n = n log n.
    This gives log n! is O(n log n). The other direction is harder.
    Note that n! > (n/2)^(n/2) -- For convenience let's assume that n is an even number (otherwise you work with floor(n/2)).
    Therefore log n! > log( (n/2)^(n/2) ) = (n/2) log (n/2) = (n/2) log n - (n/2) log 2.
    It is easy to see that n log n is O((n/2) log n - (n/2) log 2 ) and the above inequality shows that (n/2) log n - (n/2) log 2 is O(log n!).
    Therefore n log n is O(log n!).
Finally some from Page 78
  1. Question 4: find a_0,..., a_4 in the cases:
    (a) 2^{-n}: a_0 = 1, a_1 = 1/2, a_2 = 1/4, a_3 = 1/8
    (b) 3: a_0 = 3, a_1 = 3, a_2 = 3, a_3 = 3
    (c) 7+4^n: a_0=8, a_1=11, a_2=23, a_3=71
    (d) 2^n + (-2)^n: a_0=2, a_1 = 2+1/2, a_2= 4+1/4, a_3=8+1/8
  2. Question 6: Find SIGMA_{j in S} with S={1,3,5,7} for each sequence:
    (a) a_j=j: SIGMA_{j in S} j = 1+3+5+7
    (b) a_j=j^2: SIGMA_{j in S} j^2 = 1+9+25+49
    (c) a_j=1/j: SIGMA_{j in S} 1/j = 1+ 1/3 + 1/5 + 1/7
    (d) a_j=1: SIGMA_{j in S} 1 = 1+1+1+1 = 4.
  3. Question 11: SIGMA_{j =1 to n} (a_j - a_{j-1})
    = (a_2-a_1) + (a_3-a_2) + ... + (a_n - a_{n-1}) So we just cancel terms
    leaving the only that do not cancel: a_n - a_1
  4. Question 8: Evaluate the sums for j from 0 to 8:
    (a) 1+(-1)^j: for j even this is 2, for j odd it is 0. So for j from 0 to 8
    2 + 0 + 2 + 0 + 2 + 0 + 2 + 0 + 2 = 10
    (b) 3^j- 2^j: SIGMA(3^j-2^j) = SIGMA 3^j - SIGMA2^j =
    (3^9-1)/2 - (2^9-1)
    (c) 2*3^j+3*2^j: = 2 *SIGMA 3^j + 3 * SIGMA 2^j= 2*(3^9-1)/2 + 3 *(2^9-1).
    (d) 2^{j+1} - 2^j: Use question 11.
  5. We want a procedure/algorithm which will list all the rational numbers between 0 and 1 (in a sense this is what "countable" means)
    As the book suggests let's first think of one that lists all those p/q in reduced form such that p+q = n. Then we do an outer loop which makes n go from 1 to infinity.
    Procedure list some(n: an integer)
    for q :=1 to n
    begin
    p:= n-q
    if (p< q and gcd(p,q)=1) then PRINT(p/q)
    end

    Now
    Procedure rational list (no input)
    n:=1
    while n> 0
    begin
    Call list some(n)
    n:= n+1
    end