# MATA31H3 Study Guide - Natural Number

58 views8 pages
16 Nov 2012
School
Department
Course
UNIVERSITY OF TORONTO SCARBOROUGH
MATA31H3 : Calculus for Mathematical Sciences I
MIDTERM EXAMINATION # 1
October 3, 2012
Duration – 2 hours
Aids: none
NAME (PRINT):
Last/Surname First/Given Name (and nickname)
STUDENT NO: KEY
TUTORIAL:
Tutorial section # Name of TA
Qn. # Value Score
COVER PAGE 5
1 20
2 20
3 15
4 15
5 10
6 15
Total 100
TOTAL:
I understand that any breach of academic integrity is a violation of The Code of Behaviour on Academic Matters. By
signing below, I pledge to abide by the Code.
SIGNATURE:
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 8 pages and 3 million more documents.

Midterm Exam # 1 MATA31H3 page 2 of 8
(1) (20 points) Use induction to prove that
n
X
k=1
4k=4
3(4n1) nN.
[Recall that
n
X
k=1
4kis a fancy way of writing 41+ 42+··· + 4n.]
Proof: By induction.
Let
A=nnN:
n
X
k=1
4k=4
3(4n1)o.
1∈ A, since 4 = 4
3(4 1).
Now, suppose n∈ A. Then from the deﬁnition of A,
n
X
k=1
4k=4
3(4n1).
Adding 4n+1 to both sides yields
n+1
X
k=1
4k=4
3(4n1) + 4n+1
=4n+1 4
3+3·4n+1
3
=4·4n+1 4
3
=4n+2 4
3
=4
3(4n+1 1).
Thus, we see that whenever n∈ A, we must have n+ 1 A as well. By induction,
we conclude that A=N, which is precisely what is claimed.
continued on page 3
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 8 pages and 3 million more documents.

Midterm Exam # 1 MATA31H3 page 3 of 8
(2) (20 points) Prove that 56∈ Q.
There are (at least!) two different approaches:
Proof 1: Suppose 5Q. Then aZand bNsuch that a
bis fully reduced,
and 5 = a
b.
Squaring both sides and simplifying shows that
()a2= 5b2.
In particular, a2is a multiple of 5. It follows (see Lemma below) that ais a multiple
of 5. So, we can write a= 5kfor some kZ. Plugging this back into () and
simplifying yields
b2= 5k2.
Exactly as above, this implies that bis a multiple of 5. Thus, both aand bmust be
multiples of 5. But this contradicts our assumption that a
bis fully reduced!
Lemma: Suppose aZ, and a2is a multiple of 5. Then ais also a multiple of 5.
Proof. Let kbe the smallest integer such that 5k > a. (Such an integer exists by the
Well-Ordering Property of N.) This implies that 5(k1) a, since otherwise, k
wouldn’t be minimal. So, we have
5k5a < 5k.
This means that
a= 5kr,
where r= 1,2,3,4,or 5. Moving things around and squaring both sides, we see
that
r2=a210kr + 25k2.
Note that the entire right hand side is a multiple of 5, since a2is a multiple of 5 by
hypothesis, and 10kr and 25k2are clearly multiples of 5. We thus conclude that r2
must be a multiple of 5. There are only ﬁve possible values of r, and it’s easy to
check that the only one of these for which r2is a multiple of 5 is r= 5. Thus, we
conclude that a= 5k5, which is a multiple of 5 as claimed.
—————————-
—————————-
Proof 2: Let A={nN:n5Z}. If A=, then we’re done.
Suppose instead that A 6=. By the Well-Ordering Property of N,Amust have
some least element; call it a. I now claim that
(*) a(52) ∈ A.
Since a(52) < a, this would contradict the minimality of a.
So, why is (*) true? First, note that a(52) Z, since a5Zand 2aZ. Next,
since a(52) >0, we deduce that it is actually a natural number. Finally, we
have
a(52) ·5=5a2a5Z.
Thus, (*) is true. This contradicts the minimality of a; it follows that Amust be
empty after all.
continued on page 4
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 8 pages and 3 million more documents.

## Document Summary

Please read the following statement and sign below: I understand that any breach of academic integrity is a violation of the code of behaviour on academic matters. By signing below, i pledge to abide by the code. Mata31h3 page 2 of 8 (1) (20 points) use induction to prove that n(cid:88) k=1. 4k is a fancy way of writing 41 + 42 + + 4n. ] n(cid:88) k=1. Thus, we see that whenever n a, we must have n + 1 a as well. By induction, we conclude that a = n, which is precisely what is claimed. (cid:3) (cid:110) n n : n(cid:88) Then from the de nition of a, k=1 k=1. Adding 4n+1 to both sides yields n+1(cid:88) k=1 n(cid:88) Midterm exam # 1 (2) (20 points) prove that. Then a z and b n such that a is fully reduced, Squaring both sides and simplifying shows that a2 = 5b2. In particular, a2 is a multiple of 5.