Accelerated Proofs and Problem Solving

MATH08071

Results you can use:   In this exam you may use facts from the reading we covered in Liebeck, from the Week 10 lecture notes, and statements included in the assignments.

To use them, you have the following options:

● If it is a named theorem  (e.g.   the Fundamental Theorem of Arithmetic,  or the Completeness  Axiom  for  Real  numbers)  you  can  simply  state  the  name  of the theorem.

● Give the exact reference in Liebeck  (not just the number,  but e.g.   Proposition 19.2)/Lecture notes/assignments

● State the result you are using (make sure you include all hypotheses) and say that it can be found in Liebeck/Lecture notes/assignments

(1) Recall the PPS Writing Standards:

(E) English language.

(N) Introduce notation.

(S) Begin solution with a statement of results.

(T) Be thorough.

(M) Indicate what method of proof you are using.                (G)  Clearly indicate where you have left a gap in the proof. (R)  Give references where you need them.

(C) Finish with a concluding remark.

The following statement is given to prove as an assignment:

(The Archimedean Property) Prove that for positive real numbers a, b, there exists a natural number n such that na > b.

For each boxed number in the proof below, identify the PPS Writing Standard that is not being met and give a brief explanation how it is not met.  Then add some words or sentences to improve the proof so it meets the PPS Writing Standards. Use the shorthands for the Writing Standards recalled above.

there exists a natural number k such that k > α _ 1.  The properties of arithmetic now yield k + 1 > α, contradicting the choice of α as an upper bound. Thus N has no upper bound. In particular  is not an upper bound. Hence n >   4       .

[15 marks]

(2) For the following examples, writing down an example is sufficient, you need not prove that your example satisfies the desired properties. Write down an example for

(a) three distinct complex numbers that are not real, but whose product is real. (b) three distinct irrational numbers whose sum is rational.

[Please turn over]

(c) an equivalence relation on the set {1, 2, 3, 4} that has three equivalence classes. Give your answer in a diagram such as the one below, where a ~ sign in the ith row and jth column means that i ~ j .

(d) sets A and B such that p(A × B) contains 16 elements.

(e) a nonzero real number x such that x <  .

(f) a monotone sequence that is not convergent.

(g) a set of irrational numbers whose greatest lower bound is rational. (h) a permutation of order 12 in S12 .

(i) a positive integer that ends in 2 and has exactly four divisors.

(j) a real cubic (degree three) polynomial p(x) such that the function on R defined

by sending x to p(x) is not bijective.

[10 marks]

(3) Let n be a natural number and let a = 38n + 23, b = 10n + 6.

(a)  Show that gcd(a, b) = 1.

(b) Find k, l, such that gcd(a, b) = ka + lb.

[4 marks] [3 marks]

(4)  Consider the sequence (an ) defined by a1   = 0, a2   = 3 and an   = an − 1  + 2an −2  for n > 2. Show that for each n > 1 we have an  = 2n − 1 + (_1)n .                    [6 marks]

(5) Let A = {1, . . . , n} and f e Sn  a permutation. We define a relation on A by letting x ~ y if there is k e Z such that fk (x) = y .

(a)  Show that ~ is an equivalence relation.                                              [3 marks]

(b) Let n = 5 and f = (12)(34) in cycle notation. What is the equivalence class of

1? Explain.                                                                                           [3 marks]

(c) Let n = 5 and f  =  (12)(34) in cycle notation.  Write down the partition of {1, 2, 3, 4, 5} whose elements consist of the equivalence classes.          [2 marks]

(6) For the following statements,  determine, whether they are True or False.   If the statement is true, provide a proof. If the statement is false, provide a counterexample together with a proof that it is a counterexample.

[Please turn over]

(a) If k 三 c  (mod m) and k 三 c  (mod n), then k 三 c  (mod mn). (b)  f : N × N → N, f (a, b) = ab(a + b)/2 is onto.

[4 marks] [4 marks]

(c) If p is a prime and a is an integer not divisible by p, then a((p − 1)2 ) 三 1 (mod

p2 ).

[4 marks]

(7) For the following statements,  determine, whether they are True or False.   If the statement is true, provide a proof. If the statement is false, provide a counterexample together with a proof that it is a counterexample.

(a) The cube root of 6 is irrational.                                                           [4 marks]

(b) There exists a function from {1, 2, 3, 4, 5} to {1, 2, 3, 4, 5, 6, 7, 8} that is 1-1.

[4 marks]

(c)  Given two dice with sides numbered from 1 to 6, the number of ways that the sum of the two dice is n equals the number of ways that the sum of the two dice

is 14 _ n.

[4 marks]

(8) Let S = , 2+(n(−)1)亢   I n e N、. Here N does not include 0.

(a) Find the least upper bound of S .

(b) Find the largest lower bound of S .

(c) Find a sequence in S converging to the least upper bound of S .

[1 mark] [1 mark] [2 marks]

(d) Find a sequence in S converging largest lower bound of S.  Give a proof that your sequence is converging.                                                                [4 marks]

(9) Theorem: Let p1 , . . . , pn  be distinct prime numbers and let a be an integer that is not divisible by any of the pi ’s. Then,

a(p1 − 1)...(p亢−1)  三 1  (mod p1 . . . pn ).

(a) Prove the theorem stated above.                                                         [8 marks]

(b)  Give an example for n = 3 where the statement fails if we omit the hypothesis

that the primes are distinct.                                                                  [1 mark]

(10) Let x be any real number greater than 1. Define a sequence (an ) recursively by a1  = x and an+1  = 3a(x)亢(2)   + 23(a)亢   for n > 1.

(a)  Show that an  > x1/3 for all n. Note: You may use the 3-term AM-GM inequality:

if a, b and c are real numbers, then (abc)1/3  < 1/3(a + b + c).            [4 marks]

(b)  Show that an  is decreasing.

[3 marks]

(c)  Show that an  converges.

(d) Find the limit of an  and prove that it is the limit.

[2 marks] [4 marks]