代做CISC102 Winter 2024 Quiz 4: Relations代写C/C++语言

日期：2024-04-10 12:02

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