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

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

, for all integers
,




2. Let be defined by the formula , for all integers . Show that this sequence is a solution to the recurrence relation , for all integers where a0 = 1. (Show means “prove in general”. Showing that it works for a few terms is not a proof.)




3. Show that the sequence 2, 3, 4, 5, ..., , defined for , is a solution to the recurrence relation:
t_0=2,t_1=3
t_k=2t_(k-1)-t_(k-2), for all integers .

(Show means “prove in general”. Showing that it works for a few terms is not a proof.)


4. Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induciton:
, for all integers


5. A worker at a scrapbook sticker company is promised a bonus if she can increase her productivity by 2 pages of stickers per day every day for a period of 30 days. If on day 0 she produces 170 pages of stickers, how many pages of stickers must she produce on day 30 to qualify for the bonus?


6. Which of the following are second-order linear homogeneous recurrence relations with constant coefficients? Circle all that apply and explain each answer.

a.

b.

c.

d.

e.

f.

g.



7. Find an explicit formula for the sequence that is a solution the following recurrence relation and initial conditions (use the method of characteristic equation):

, for all integers
,



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

, for all integers
,


9. Connecting math to programming

Choose one from the three following projects (if you have experience writing computer programs, please do the first one or second one– otherwise, do the third one).

The Towers of Hanoi problem dates back to the late 1800s. Here is a description of the problem, taken from Wikipedia (http://en.wikipedia.org/wiki/Tower_of_Hanoi):

The game consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
No disk may be placed on top of a smaller disk.



Write a computer program that simulates the game for 8 disks and shows step by step how to move the disks to get to the solution. You can use any programming language you want. If you choose a language other than C, C++, Visual Basic or Java, I may not be able to help you if you run into problems.

Deliverables: By the due date, please turn in the code file and screen shots that show how the program runs. Think of this as showing your “boss” how your program works without running it for him/her in person. It’s your job to convince me that your program works and to explain how it works. It’s not my job to figure out how it works.

Factorial - Write a program that does the following: Given a positive integer n as input, return the factorial of n, which is n(n-1)(n-2)1. Compute the result recursively, without using any loops.

Deliverables: By the due date, please turn in the code file and screen shots that show how the program runs. Think of this as showing your “boss” how your program works without running it for him/her in person. It’s your job to convince me that your program works and to explain how it works. It’s not my job to figure out how it works.


c. Write a two to three page paper, 12pt font, double-spaced, that explains how what we learned in Chapter 8 about recursion is pertinent to computer science. This should be written at the college level (no spelling or grammar issues) and be as detailed as possible. Turn in your paper as a separate file from the rest of the exam and make sure it is in .doc, .docx, .rtf, or .pdf format. No other formats will be accepted.