Computer Science 547 - Discrete Mathematics
Prof. Steven Skiena
Spring 1999

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:

1.

Exercise 7-7.

2.

Exercise 7-21(a).

3.

Exercise 7-23.

4.

Warmup exercises 8:1-6.

5.

Exercise 8-7.

6.

Exercise 8-11.

7.

Exercise 8-15.

8.

Let $a_n = f_{n} + \sum_{i=1}^d c_i a_{n-i}$, $n \geq d$ be a constant coefficient recurrence relation of history d, with specified initial conditions $a_i, 0 \leq i < d$.

(a) Let f_n = c₀, for some constant c₀. Does there necessarily exist a constant coefficient homogeneous recurrence relation $b_n = \sum_{i=1}^{d'} c'_i b_{n-i}$ where a_n = b_n for all n. If so, prove it, and give d' in terms of d. If not, give a counter-example.

(b) Let f_n = c₀ⁿ, for some constant c₀. Does there necessarily exist a constant coefficient homogeneous recurrence relation $b_n = \sum_{i=1}^{d'} c'_i b_{n-i}$ where a_n = b_n for all n. If so, prove it, and give d' in terms of d. If not, give a counter-example.

(c) Let $f_{n} = c_0 \times n!$, for some constant c₀. Does there necessarily exist a constant coefficient homogeneous recurrence relation $b_n = \sum_{i=1}^{d'} c'_i b_{n-i}$ where a_n = b_n for all n. If so, prove it, and give d' in terms of d. If not, give a counter-example.

9.

Use generating functions to solve the recurrence:

A_n = 3 A_n-1 - 2 A_n-2 + 3

where A₀ = A1 = 1.

10.

Use generating functions to solve the recurrence:

where A₀ = 2 and A₁ = -1.