Exam of November 4, 2010

1. Compute the sum: \sum_{i=1}^3 i^3.

2. Prove by induction: (\forall n \in {\Bbb Z}^+)6|(7^n - 1).
(“For every integer n greater than or equal to 1, six divides 7^n - 1“.)

3. Prove that whenever a mod 6 = 3 and b mod 6 = 2, it is also true that ab mod 6 = 0.
(Remark: this shows that the “Zero Product Law” (a \ne 0 \wedge b \ne 0) \rightarrow (ab \ne 0) is false in certain number systems.)

4. Prove that (\forall x, y \in {\Bbb Q})xy \in {\Bbb Q}.
(“The product of any two rational numbers is a rational number”.)

5. Prove by contradiction that there is no greatest Real number less than 17.

6. Prove that there is an odd integer k such that k mod 7 = 4.

Advertisements

  1. 1. Compute the sum: \sum_{i=1}^3 i^3.

    \sum_{i=1}^3 i^3 = 1^3 + 2^3 + 3^3 = 36.

    all but one student got this i think.
    so i should’ve gone a *little* harder.
    the various sum-of-powers formulas
    are proved by induction in the text
    but i required only that this quarter’s
    students *know how* to *expand* a sum.
    there’s a little use of “index” notation…
    stuff like \bigcup_{i=1}^n X_i
    that i wanted to at least look at.
    i’ve complained many times in many
    other courses that there’s far too much
    material in the sections-to-be-“covered”
    to actually require from the students
    one actually gets; that was sure the
    case again here (though i’m not so
    inclined to complain about it… it’s
    almost as if by this level of the game
    it should be *understood*… by student
    and teacher alike… that one will
    throw out great tracts of text so as
    to write passable exams).

    2. Prove by induction: (\forall n \in {\Bbb Z}^+)6|(7^n - 1).
    (“For every integer n greater than or equal to 1, six divides 7^n - 1“.)

    Base Case
    Let P(n) denote the proposition 6|(7^n -1).
    For our base step—P(1)—note that
    6|(7^1 – 1) is true.

    (Because 6|6; this in turn is true because 6=6*1 [and 1 is an integer]. One need not spell this out here; we’ve recently worked some proofs involving the definition of a-divides-b (a | b) though and there was certainly some confusion on the day. Many students (how many? Too many!) confuse the proposition “6|6” (a true statement) with the number “6/6” (the integer positive-one) in their writings.)

    Induction Step
    Now suppose, for some positive integer k, that P(k) is known to be true. In other words, fix k and suppose that 6|(7^k - 1). This means that 7^k -1 = 6a for some integer a. Now

    7^{k+1} - 1=
    7\cdot7^k - 1 =
    7\cdot7^k - 7 + 6=
    7(7^k - 1) + 6=
    7(6a) + 6=
    6(7a + 1)\,.

    But 7a +1 is an integer, so this tells us that 6|(7^{k+1} -1). This is exactly P(k+1), so our induction is complete.

    Only a handful of students produced satisfactory proofs; this is the only problem I’m (essentially) repeating from Exams I and II on an otherwise non-cumulative Exam III (and Final). With luck the homework exercises will have had some effect and I’ll have a much better time grading these.

    3. Prove that whenever a mod 6 = 3 and b mod 6 = 2, it is also true that ab mod 6 = 0.
    (Remark: this shows that the “Zero Product Law” (a \ne 0 \wedge b \ne 0) \rightarrow (ab \ne 0) is false in certain number systems.)

    Proof:
    Suppose (for some integers a and b) that a mod 6 = 3 and b mod 6 = 2. In other words, suppose that integers p and q exist with a = 6p + 3 and b = 6q + 2. Then
    ab =
    (6p + 3) (6q + 2)=
    36pq +12p + 18q + 6=
    6(6pq +2p + 3q + 1).

    Hence,
    ab = 6t + 0
    where t (= 6pq +2p + 3q + 1) is an integer. This is the same thing as to say that ab mod 6 = 0; we are done.

  2. 4. Prove that (\forall x, y \in {\Bbb Q})xy \in {\Bbb Q}.
    (“The product of any two rational numbers is a rational number”.)

    Proof: Let x & y denote rational numbers.
    Then, by the definition of “rational number”, there exist integers a, c, and non-zero integers b, d such that

    x = a/b and y = c/d.

    It follows that xy = (a/b)(c/d) = (ac)/(bd).

    Now note that bd is nonzero (by the “Zero Product Law” for real numbers) and that ac and bd are both integers (by “closure”… the product of integers is an integer).

    So xy satisfies all the properties of a rational number; we are done.

    5. Prove by contradiction that there is no greatest Real number less than 17.

    Suppose there is a greatest Real less than 17; call it M.

    Now consider q= (M+17)/2. We have

    q-M=
    (M+17)/2 – 2M/2=
    (17-M)/2.

    This is a positive number (because 17>M), so
    q-M >0 and
    q > M.

    But also 17-q = 34/2 – (M+17)/2 = (17-M)/2.
    This is still positiive, so 17 > q.
    We have our contradiction: M<q<17.
    M cannot be the greatest real
    less than 17.

  3. 6. Prove that there is an odd integer k such that k mod 7 = 4.

    Let k = 11.

    Then k = 11 = 7*1 + 4; note that 1 \in \Bbb Z.
    Hence k mod 7 = 4 (by the definition of “mod”).

    Also k = 11 = 2*5 + 1 (and 5 \in \Bbb Z).
    So k is odd. Done.

    The commonest mistake was to overlook the need to prove that k is odd… understandable of course. But we’d just been looking at lots of proofs about even-and-odd, so it’s really not too much to expect…

  4. typo in #3. b mod 3 = 2. The “3” is missing.

  5. oops. That’s a missing 6, not a missing 3, sorry.

  6. blag

    right; thanks.
    the copy will be corrected at some point
    (i’m not logged in).

  7. see?

    the error turned out to’ve been repeated
    (at least once); the dangers of cut-and-paste.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: