# MATA31H3 Study Guide - Natural Number

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:

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.

SIGNATURE:

Midterm Exam # 1 MATA31H3 page 2 of 8

(1) (20 points) Use induction to prove that

n

X

k=1

4k=4

3(4n−1) ∀n∈N.

[Recall that

n

X

k=1

4kis a fancy way of writing 41+ 42+··· + 4n.]

Proof: By induction.

Let

A=nn∈N:

n

X

k=1

4k=4

3(4n−1)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(4n−1).

Adding 4n+1 to both sides yields

n+1

X

k=1

4k=4

3(4n−1) + 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

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 √5∈Q. Then ∃a∈Zand ∃b∈Nsuch 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 k∈Z. 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 a∈Z, 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(k−1) ≤a, since otherwise, k

wouldn’t be minimal. So, we have

5k−5≤a < 5k.

This means that

a= 5k−r,

where r= 1,2,3,4,or 5. Moving things around and squaring both sides, we see

that

r2=a2−10kr + 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= 5k−5, which is a multiple of 5 as claimed.

—————————-

—————————-

Proof 2: Let A={n∈N:n√5∈Z}. 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(√5−2) ∈ A.

Since a(√5−2) < a, this would contradict the minimality of a.

So, why is (*) true? First, note that a(√5−2) ∈Z, since a√5∈Zand 2a∈Z. Next,

since a(√5−2) >0, we deduce that it is actually a natural number. Finally, we

have

a(√5−2) ·√5=5a−2a√5∈Z.

Thus, (*) is true. This contradicts the minimality of a; it follows that Amust be

empty after all.

continued on page 4

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