Homework 4
Due Thursday, March 25, 1999
Each of the problems should be solved on a separate sheet of paper to facilitate grading. Limit the solution of each problem to one sheet of paper. Staple all these sheets together! Please don't wait until the last minute to look at the problems.
Do the following exercises in Graham, Knuth, and Patashnik:
Exercise 7-23.
(a) Let
fn = c0, for some constant c0.
Does there necessarily exist a constant coefficient homogeneous recurrence
relation
where an = bn for all n.
If so, prove it, and give d' in terms of d.
If not, give a counter-example.
(b) Let
fn = c0n, for some constant c0.
Does there necessarily exist a constant coefficient homogeneous recurrence
relation
where an = bn for all n.
If so, prove it, and give d' in terms of d.
If not, give a counter-example.
(c) Let
,
for some constant c0.
Does there necessarily exist a constant coefficient homogeneous recurrence
relation
where an = bn for all n.
If so, prove it, and give d' in terms of d.
If not, give a counter-example.