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

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

• ## (Partial) Contents Page

Vlorbik On Math Ed ('07—'09)
(a good place to start!)