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:
 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 a_{0}, …, a_{5}.
 3 points each; total = 9 points.
 p. 456: 4a, b
 You have to show that a certain nonrecursively–defined
sequence is a solution of a
certain recurrence relation.
To do this, just substitute the nonrecursive formula for
a_{n} 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
 pp. 457–458: 6a–c, e–f, h (i.e., omit d and g)
 Hint:
Compute a few (say, 3–5) values of a_{n}
and look for a pattern that will enable you to define
a_{n} in terms of previous values a_{n–1}
(and, perhaps, n).
 3 points each; total = 18 points
 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
 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:
 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.
 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.html20090409