Discrete Structures

HW #12

 Last Update: 17 April 2009 Note: or material is highlighted

Reminder: Each HW problem solution should consist of:

• a restatement of the entire problem (you may copy it word for word),
• followed by a complete solution with all intermediate steps shown.

Exercises are from §7.1, pp. 456–460 (recurrence relations) and §7.2, p. 471 (solving linear recurrence relations).

From §7.1:

1. p. 456: 2a, b, e

• You are asked to find the first 6 terms of 3 recursively defined sequences
(i.e., sequences defined in terms of a recurrence relation (the recursive case) and initial conditions (the base case)).

• The first 6 terms would be a0, …, a5.
• 3 points each; total = 9 points.

2. p. 456: 4a, b

• You have to show that a certain non-recursively–defined sequence is a solution of a certain recurrence relation.
To do this, just substitute the non-recursive formula for an into the recursive formula
to show that the recursive formula will then compute the same value that the non–recursive formula computes.

• 3 points each; total = 6 points

3. pp. 457–458: 6a–c, e–f, h (i.e., omit d and g)

• Hint:
Compute a few (say, 3–5) values of an and look for a pattern that will enable you to define an in terms of previous values an–1 (and, perhaps, n).
• 3 points each; total = 18 points

4. p. 457: 10a–c

• This asks you to figure out how much money you will have after investing a certain initial amount in a savings account that earns a certain annual interest.
• Part (c) asks you to figure out how much you'll have after 100 years.
You don't need to compute the actual number if you don't want to; a formula will suffice.
• 3 points each; total = 9 points

5. p. 460: 62a–d

• First read the definitions of "backward difference", "first difference", and "(k+1)st difference" that are given immediately before problem 62 on p. 460.
• Suggestion:
Even though you are only asked to compute the "first difference" of the given sequences, I think you will find it interesting to compute the second, third, etc., differences, too.
Keep going until you either reach 0, 0, 0, … or else go into an infinite loop (this will make more sense to you once you try it).
If you know calculus, compare the derivative of each function in problem 62 with these differences.
• 3 points each; total = 12 points

From § 7.2:

6. p. 471: 2a–g

• You are asked to say which of the given recurrence relations are "linear homogeneous with constant coefficients of degree k".
It will be easiest to give your answer in the form of a chart that gives a "yes", "no", or "not applicable" answer, for each recurrence relation, concerning whether it is linear, whether it is homogeneous (if it is linear), whether it has constant coefficients (if it is linear), and (if applicable) what its degree is.
• 3 points each; total = 21 points.

7. p. 471: 4b, c

• Here, you have to solve the given recurrence relations using the technique of Theorem 1 (as shown in Examples 3 and 4, and in lecture).
• 3 points each; total = 6 points.

Total points = 81

 A = 78–81 A– = 73–77 B+ = 69–72 B = 64–68 B– = 60–63 C+ = 55–59 C = 46–54 C– = 37–45 D+ = 28–36 D = 15–27 F = 0–14

 DUE: AT THE BEGINNING OF LECTURE, FRIDAY, APRIL 24

 REMINDER:NAME, DATE, RECITATION SECTION AT TOP RIGHT OF EACH PAGE;         STAPLE MULTIPLE PAGES

Copyright © 2009 by William J. Rapaport (rapaport@cse.buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/S09/hw12.html-20090409