### Exam of November 4, 2010

**1.** Compute the sum: .

**2.** Prove by induction: .

(“For every integer *n* greater than or equal to 1, six divides “.)

**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” is false in certain number systems.)

**4.** Prove that .

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

December 3, 2010 at 8:45 pm

1.Compute the sum: .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 …

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: .(“For every integer

ngreater than or equal to 1, six divides “.)Base CaseLet P(n) denote the proposition .

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 (howmany?Toomany!) confuse theproposition“6|6” (a true statement) with thenumber“6/6” (the integer positive-one) in their writings.)Induction StepNow suppose, for some positive integer

k, that P(k) is known to be true. In other words, fixkand suppose that . This means that for some integera. NowBut 7

a+1 is an integer, so this tells us that . 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 wheneveramod6 = 3 andbmod6 = 2, it is also true thatabmod6 = 0.(Remark: this shows that the “Zero Product Law” is false in certain number systems.)

Proof:Suppose (for some integers

aandb) thatamod6 = 3 andbmod6 = 2. In other words, suppose that integerspandqexist witha = 6p + 3andb = 6q + 2. Thenab=(6

p+ 3) (6q+ 2)=36

pq+12p+ 18q+ 6=6(6

pq+2p+ 3q+ 1).Hence,

ab= 6t+ 0where

t(= 6pq+2p+ 3q+ 1) is an integer. This is the same thing as to say thatabmod6 = 0; we are done.December 3, 2010 at 11:09 pm

4.Prove that .(“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-zerointegers b, d such thatx = a/b

andy = 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

isa 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

greatestrealless than 17.

December 4, 2010 at 1:06 pm

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 .

Hence k mod 7 = 4 (by the definition of “mod”).

Also k = 11 = 2*5 + 1 (and ).

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 ofproofsabout even-and-odd, so it’s really not too much to expect…December 5, 2010 at 9:53 pm

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

December 5, 2010 at 9:54 pm

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

December 7, 2010 at 7:37 pm

right; thanks.

the copy will be corrected at some point

(i’m not logged in).

December 7, 2010 at 8:05 pm

see?

the error turned out to’ve been repeated

(at least once); the dangers of cut-and-paste.