Recursion and Recurrence Relations

Instructions: You can type the answers into this document, type them into a separate document, or handwrite the answers and scan them in(.doc, .docx or .pdf files are preferred). No matter which option you choose, each answer must be clearly labeled with the number of the question you are answering and I must be able to read and understand your answers. Please show all work. No credit will be given if work is not shown. The number of points for each of the 8 problems is shown in parentheses.

  1. (4) Find the next four terms of the recursively-defined sequence:

, for all integers

,

  1. (7) Let be defined by the formula, for all integers. Prove by induction that this sequence is a solution to the recurrence relation , for all integers where a0 = -1.
  1. (4) f(a) = . Express this polynomial in a recursively.
  1. (4) The producity of a worker at a scrapbook sticker company increased as an Arithmetic Sequence (Progression) over a period of 7 days. That is, on day n she produced an = a1 + (n – 1)d stickers. If a7 = 160 and d = 10 what is the total number of stickers she produced over the period of 7 days?
  1. (6) Tom decided to do an exercise involving the Fibonacci and Geometric sequences. He will be pouring liquid into a container. For the first 10 days he will pour in liters of liquid corresponding to the Fibonacci sequence, starting with 1 liter on the first day and 1 liter on the second day. He will use day 10 as the first day of his Geometric sequence and for the next 3 days he will increase the number of liters he pours in by 10% of the previous day. How many liters will he pour into the container on day 13? Note that you are not asked for the total liters poured in, just what is poured in on a particular day.
  1. (7) Which of the following are second-order linear homogeneous recurrence relations with constant coefficients? Place “yes” against all that are. If anyone is not give a reason.

a.

b.

c.

d.

e.

f.

g.

  1. (9) Find a closed form expression that is a solution to the sequence defined by the following recurrence relation and initial conditions (use the method of characteristic equation):

, for all integers ; , .

  1. (9) Find a solution for the following recurrence relation and initial conditions (use the method of characteristic equation):

, for all integers ; , .