Lesson 6

The above method generalizes to order \(k\) as follows. The characteristic polynomial will have exactly \(k\) roots (which can be complex or repeated). The general solution is a linear combination of \(k\) functions: for a root \(\alpha\) of multiplicity \(t\), the corresponding terms are \[\alpha^{n}, n\alpha^{n}, n^{2}\alpha^{n}, \dotsc, n^{t-1}\alpha^{n} \ .\] (We omit the proof that any such linear combination is a solution to the recurrence relation.) The coefficients for such a linear combination are determined by the initial conditions.

Finally, let us briefly discuss how to handle non-homogeneous linear recurrence relations. While we will not provide a general recipe, we will demonstrate how to guess the solution (and then verify it) for a simple non-homogeneous term \(g(n)\). First, ignore the non-homogeneous part \(g(n)\) and find the solution to the corresponding homogeneous recurrence relation. Then, guess the non-homogeneous addition using the following guidelines:

• If \(g(n)\) is a polynomial (or constant), try adding a polynomial of the same degree, one degree higher, or two degrees higher. For example, if \(g(n)=n\), first try \(bn+c\), then \(an^{2}+bn+c\).


• If \(g(n)=3^{n}\), try \(c3^{n}\), then \((bn+c)3^{n}\), and then \((an^{2}+bn+c)3^{n}\).