Mathematics 357 – Combinatorics Discussion 3 – Inhomogeneous Linear Recurrences With Constant Coefficients March 18, 2005

Background

Many of the most common recurrences that we need to solve in combinatorics are linear recurrences with constant coefficients, of the form:

(1)  h_{n} = a_{1}h_{n−1} + a_{2}h_{n−2} + ⋯ + a_{k}h_{n−k} + b(n)

We looked at the case b(n) = 0 (the homogeneous recurrences) last time. Today, we will investigate recurrences with b(n) ≠ 0 in some detail.

Discussion Questions

A) The basis for the treatment of the inhomogeneous case is a fact that is parallel to patterns you have seen in Linear Algebra (and possibly Differential Equations too!). Show that if h_{n}, p_{n} are any two solutions of the same inhomogeneous recurrence (1):

\begin{aligned}h_{n} & = a_{1}h_{n−1} + a_{2}h_{n−2} + ⋯ + a_{k}h_{n−k} + b(n) \\ p_{n} & = a_{1}p_{n−1} + a_{2}p_{n−2} + ⋯ + a_{k}p_{n−k} + b(n) \end{aligned}

then the difference sequence g_{n} = h_{n} − p_{n} is a solution of the homogeneous recurrence

(2)  g_{n} = a_{1}g_{n−1} + a_{2}g_{n−2} + ⋯ + a_{k}g_{n−k}

associated to (1). (Note: the coefficients on the various terms from the sequence are the same, but the b(n) term has been replaced by zero.)

B) Suppose we can find the general solution g_{n} of (2) by the methods we discussed in class last time, and that we know some “particular solution” of (1) like p_{n} above. What does that say about solving (1)? Explain.

To determine “particular solutions”, we will use the following “rules of thumb” based on the form of the function b(n):

• If b(n) = b_{ℓ}n^{ℓ} + ⋯ + b_{1}n + b_{0}, then try a particular solution of the same form

p_{n} = P_{ℓ}n^{ℓ} + ⋯ + P_{1}n + P_{0}

but with undetermined coefficients P_{k}. (Be sure you understand the notation here: p_{n} is the sequence giving the particular solution; P_{k} with the capital letters are the undetermined coefficients that we want to solve for.)

• If b(n) = q^{n}, then try a particular solution p_{n} = P q^{n} (same q, of course!)

Then in both cases, substitute into (1) and try to determine the constants to make j_{n} a solution of (1) for all n.

C) For instance, find a particular solution of

(3)  h_{n} = 6h_{n−1} − 9h_{n−2} + 2n.

Then use that and the solution of the associated homogeneous recurrence to solve (3) with the initial conditions h_{0} = 1, h_{1} = 0.

D) The rules of thumb above do not always “work” (in particular they can fail if the proposed particular solution actually solves the homogeneous equation. Show that this happens, for instance for the recurrence

h_{n} = 5h_{n−1} − 6h_{n−2} + 2^{n}

Find a particular solution in this case of the form p_{n} = P · n2^{n} for some constant P. Then use that and the solution of the associated homogeneous recurrence to solve (3) with the initial conditions h_{0} = 1, h_{1} = 0.

Assignment

Group writeups due in class on Wednesday, March 23.