MATH1061 / 7861 Assignment 3 Semester 2/2020
Due Monday 19 October at 1pm on blackboard.
Marks will be deducted for sloppy working. Clearly state your assumptions and conclusions, and
justify all steps in your work.
The marked question 5 is required for MATH7861 students only. However, MATH1061 students are encouraged to try this also!
Q1 Letf:Z12→Z12 bedefinedbyf(n)=3n+1(mod12),andletg:Q→Qbedefinedby g(q) = q3 + 1.
(a) Is f one-to-one? (b) Is g one-to-one?
(c) Is f onto? (d) Is g onto?
Prove all of your answers correct.
Q2 Recall the Fibonacci sequence defined by F0 = 0, F1 = 1 and Fn = Fn−1 +Fn−2 for n ≥ 2.
(a) Prove that, for any integers a and b, gcd(a, b) = gcd(a, a + b).
(b) Using induction, prove that gcd(Fn, Fn−1) = 1 for all n ≥ 1.
(10 marks)
Q3 Let S = {(a,b)|a,b ∈ Z and b ̸= 0}. That is, S is the set of all pairs of integers where the second entry is non-zero.
Now define the relation ρ on S where (a,b)ρ(x,y) if and only if ay = bx.
Prove that ρ is an equivalence relation.
Note: This is how you construct the rationals! The set Q is precisely the set of equivalence classes of ρ.
(10 marks)
Q4 LetX andY beanynon-emptysets,letf: X→Y beanyfunctionfromX toY,andlet A, B ⊆ X be any subsets of X .
(a) Is it always true that f(A ∪ B) = f(A) ∪ f(B)? If so, give a proof. If not, give a counterexample.
(b) Is it always true that f(A ∩ B) = f(A) ∩ f(B)? If so, give a proof. If not, give a counterexample.
(8 marks)
Q5 [MATH7861 only]
Again recall the Fibonacci sequence F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for n ≥ 2. Now defineanewsequenceG0,G1,…byG0=0,G1=1andGn=3Gn−1−Gn−2 forn≥2. Provethat Gn =F2n forall n≥0.
(10 marks)
(12 marks)