CISC102 Winter 2024
Quiz 4: Relations Reminders
◦ Answer each question to the best of your abilities, and show all of your work
◦ You may use your notes from class but are prohibited from using external resources.
◦ You must handwrite your solutions. Electronic solutions will automatically receive a 0 Insufficient justification will result in a loss of marks.
Questions
1. (2 marks) Describe in words the following relation, where n is some fixed integer:
R = {(a,b) ∈ Z2 | n|(a − b)}
2. (5 marks) Given the recurrence relation an = f · an − 1 + ℓ with a0 = 2. Let f be the integer corresponding to the first letter of you First name and let ℓ be the integer corresponding to the first letter of your Last name (eg. Selena Gomez would have f = 19 ℓ = 7 since S is the 19th letter of the alphabet and G is the 7th letter.
. Write out the first 5 terms of the sequence.
. Using the repeated substitution method from class, determine a closed form for the recurrence relation.
. Check that your closed form holds for the first 5 terms.
3. (6 marks) Let R be the relation on the set of all bitstrings of length n, where aRb whenever a and b ‘correspond’ at the second position. That is, the second item for a,b is either both 0 or both 1.
(a) Prove that R is an equivalence relation
(b) Determine the equivalence classes of R.
4. (5 marks) Complete the following induction proof by filling in each of the missing areas.
Prove the closed form of this sumation:
Proof.
Base Case: Let n = 0, then the LHS gives
The RHS is . So the base case holds.
Induction Hypothesis: [Fill This Out]
Inductive Step:
Consider
Therefore, we have proved by induction that .
5. (7 marks) Let f : R → R be a function such that
(a) Prove that f is a bijection.
(b) Find f− 1
(c) Find the image of the set S = {−3, 0.5, 5/2, π} under f. That is, find imagef (S).
6. (8 marks) Given the recurrence relation an = 8an−1 −12an −2 with a0 = −2 and a1 = 0. Prove using strong induction that the closed form is
an = 6n − 3 · 2n