Description
Question 1 (30 pts)
Use generating functions to solve the following recurrence relation;
an = 3an−1 + 4an−2, n ≥ 2
where a0 = a1 = 1. Any solution that does not use generating functions would not gain partial credits.
Question 2 (30 pts)
a)
Find the generating function (in closed form) for the sequence < 2, 5, 11, 29, 83, 245, · · · >. Show all
the steps clearly. (15 pts)
b)
Find the sequence corresponding to the generating function; (15 pts)
G(x) = 7 − 9x
1 − 3x + 2x
2
Question 3 (20 pts)
a)
The relation R is defined on as Z follows;
aRb iff there exists a right triangle that has the edges a, b, n where n ∈ Z
Is R an equivalence relation? If it is an equivalence relation what is the equivalence class of 3?
1
b)
The relation R is defined on as R follows;
(x1, y1)R(x2, y2) iff 2×1 + y1 = 2×2 + y2
Is R an equivalence relation? If it is an equivalence relation what is the equivalence class of (1, −2)?
What does it represent in the Cartesian coordinate system?
Question 4 (20 pts)
R = {(a, b)|a divides b} is a relation defined on A = {2, 5, 10, 18, 60}.
a) Draw the Hasse diagram of R.
b) What is the matrix representation for R?
c) What is the matrix representation for Rs, where Rs is the symmetric closure of R. List all pairs
(x, y) where (x, y) ∈ Rs ∧ (x, y) ∈/ R.
d) You are allowed to remove a single element in A and add another element. Is it possible to create
a total ordering that includes all elements of A. What if you are allowed to remove two elements
and add one? Which elements would you remove and add to create such total ordering?
Each item is worth 5 pts. Note that partial points may not be given to the items.
Regulations
1. You have to write your answers to the provided sections of the template answer file given.
Handwritten solutions will not be accepted.
2. Late Submission: Not allowed!
3. Cheating: We have zero tolerance policy for cheating. People involved in cheating will
be punished according to the university regulations.
4. Submit a single PDF file named eXXXXXXX.pdf (7-digit student number).
5. You may ask your questions in the course forum or by sending a mail to ”mduymus@ceng.metu.edu.tr”.
2