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

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