## Intro. To Discrete Structures Homework #7

** **

**Problem 1 Fill in blanks [10 points]**

- A second-order linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form _____ for all integers
*k*≥ _____, where _____. - Given a recurrence relation of the formfor all integers, the characteristic equation of the relation is _____.
- If a sequenceis defined by a second-order linear homogeneous recurrence relation with constant coefficients and the characteristic equation for the relation has two distinct rootsand(which could be complex numbers), then the sequence is given by an explicit formula of the form _____.
- If a sequenceis defined by a second-order linear homogeneous recurrence relation with constant coefficients and the characteristic equation for the relation has only a single root, then the sequence is given by an explicit formula of the form _____.

** **

**Problem 2 [15 points]**

Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence.

for all integers

** **

**Problem 3 [15 points]**

Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence.

for all integers

** **

**Problem 4 [15 points]**

Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence.

for all integers

** **

**Problem 5 [15 points]**

for all integers

** **

**Problem 6 [15 points]**

for all integers

** **

**Problem 7 [15 points]**

for all integers