Description

Assistant: Gizem Su¨ngu¨ Student Id:
Course Policy: Read all the instructions below carefully before you start working on the assignment, and before you make a submission.
• It is not a group homework. Do not share your answers to anyone in any circumstance. Any cheating means at least -100 for both sides.
• Do not take any information from Internet.
• No late homework will be accepted.
• For any questions about the homework, send an email to gizemsungu@gtu.edu.tr
• The homeworks (both latex and pdf files in a zip file) will be submitted into the course page of Moodle.
• The latex, pdf and zip files of the homeworks should be saved as ”Name Surname StudentId”.{tex, pdf, zip}.
• If the answers of the homeworks have only calculations without any formula or any explanation -when needed- will get zero.
• Writing the homeworks on Latex is strongly suggested. However, hand-written paper is still accepted IFF hand writing of the student is clear and understandable to read, and the paper is well-organized. Otherwise, the assistant cannot grade the student’s homework.
Problem 1 (15+15=30 points)
Consider the nonhomogeneous linear recurrence relation an = 3an−1 + 2n .
(a) Show that whether an = −2n+1 is a solution of the given recurrence relation or not. Show your work step by step. (Solution)
(b) Find the solution with a0 = 1.
(Solution)
Problem 2 (35 points)
Solve the recurrence relation f(n) = 4f(n-1) – 4f(n-2) + n2 for f(0) = 2 and f(1) = 5.
(Solution)
Problem 3 (20+15 = 35 points)
Consider the linear homogeneous recurrence relation an = 2an−1 – 2an−2. (a) Find the characteristic roots of the recurrence relation.
(Solution)
(b) Find the solution of the recurrence relation with a0 = 1 and a1 = 2. (Solution)
1