Linear Recurrence Relations with Constant Coefficients

Comp.145  January 1997  Dr. A.J. Mestel

A sequence {u_{n}} for n = 0, 1, … may be defined recursively in terms of previous terms, so that for some integer k > 0 and some function f, u_{n} = f(u_{n−1}, u_{n−2}, … u_{n−k}) for n ⩾ k. Such an equation is called a recurrence relation. The set of all possible solutions to it is called its general solution, which involves k arbitrary constants. If the initial values u_{0}, u_{1}, … u_{k−1} are supplied, repeated use of the recurrence relation enables u_{n} to be found for every n, and hence the solution is determined uniquely. The order of the recurrence relation is the value of k, i.e. the number of preceding terms required to find u_{n}. The recurrence relation is called homogeneous if a possible solution is u_{n} = 0 for every n. A homogeneous recurrence relation is linear if the function f is linear in the u_{n}, i.e. f = a_{n−1}u_{n−1} + … a_{n−k}u_{n−k} where the coefficients a_{i} do not depend on u_{n}. We shall be particularly interested in the case where the coefficients a_{i} are constant, that is they do not vary with n. Thus, for example

(a) u_{n} = u_{n−1}^{2} + 1 is non-linear, inhomogeneous and first order.

(b) u_{n} = u_{n−1} + u_{n−2} is linear, homogeneous and second order.

(c) u_{n+3} = nu_{n+1} + u_{n} is linear, homogeneous, third order, with non-constant coefficients.

Solving homogeneous equations with constant coefficients

(a) First order: The equation can be written u_{n} = au_{n−1} for some constant a. Clearly, the solution is u_{n} = a^{n}u_{0}, or u_{n} = αa^{n} is the general solution, where α is an arbitrary constant. If we know one of the u_{n}, say u_{0}, then we can find the value of α and determine the unique solution.

(b) Second order: For arbitrary a and b, consider u_{n} = au_{n−1} + bu_{n−2}. We seek a solution u_{n} = αλ^{n}, for constants α and λ. We find

αλ^{n} = aαλ^{n−1} + bαλ^{n−2} or λ^{2} − aλ − b = 0 .

Note that n has disappeared, leaving us with a quadratic equation with two roots λ_{1} and λ_{2}, which we assume are different. We have thus found two sets of solutions u_{n} = α_{1}λ_{1}^{n} and u_{n} = α_{2}λ_{2}^{n}. Since the problem is linear, we may combine these two, to obtain the general solution u_{n} = α_{1}λ_{1}^{n} + α_{2}λ_{2}^{n}. If we know two conditions on the u_{n}, say u_{0} and u_{1} known, then we can find the constants α_{1} and α_{2} and hence find the unique solution.

(c) Second order with repeated roots: If a and b are such that λ_{1} = λ_{2}, it turns out that u_{n} = nλ_{1}^{n} is a solution to the recurrence relation. In this case, the general solution can be written u_{n} = (α + βn)λ_{1}^{n}, for arbitrary α and β.

(d) k^{th} order: The substitution u_{n} = λ^{n} leads to a k^{th} order polynomial in λ which has k roots. If these are distinct, the general solution is u_{n} = α_{1}λ_{1}^{n} + α_{2}λ_{2}^{n} … + α_{k}λ_{k}^{n}. We need k conditions to determine the solution uniquely. If multiple roots appear, something similar to case (c) occurs. For example, if λ_{1} = λ_{2} = λ_{3} but all the other roots are different, the general solution is

u_{n} = (α_{1} + β_{1}n + γ_{1}n^{2})λ_{1}^{n} + α_{4}λ_{4}^{n} + … + α_{k}λ_{k}^{n} .

Inhomogeneous Equations: Finding particular solutions

Consider the problem u_{n} − au_{n−1} = 1. We see that u_{n} = 1/(1 − a) for all n is a solution, provided a ≠ 1 Suppose now that v_{n} is a solution to the homogeneous equation, so that v_{n} − av_{n−1} = 0. Then w_{n} ≡ u_{n} + v_{n} solves the inhomogeneous equation, as

w_{n} − aw_{n−1} = (u_{n} + v_{n}) − a(u_{n−1} + v_{n−1}) = (u_{n} − au_{n−1}) + (v_{n} − av_{n−1}) = 1 .

This idea generalises to the important result: The general solution of an inhomogeneous linear equation is the sum of any particular solution to that equation and the general solution to the corresponding homogeneous equation.

We need therefore seek only one solution of the inhomogeneous equation. Rational guesswork is usually the best way of finding these. The following rules should be followed:

(a) If the inhomogeneous part of the equation (which we henceforth call the RHS) is a polynomial in n, try for u_{n} a general polynomial of the same order.

(b) If the RHS is a power, say t^{n} for constant t, try u_{n} = At^{n}.

(c) If the RHS is the product of a polynomial and a power, e.g. (n^{2} + n + 1)t^{n}, try the same sort of combination u_{n} = (An^{2} + Bn + C)t^{n}.

(d) If the RHS is the sum of two or more terms of the above form, treat them separately. E.g. if the RHS is n^{2}t^{n} + n − 1, try u_{n} = (An^{2} + Bn + C)t^{n} + (Dn + E).

(e) If something goes wrong, this is usually because the natural thing to try is itself part of the general solution to the homogeneous equation. Try multiplying it by n. The earlier example u_{n} − au_{n−1} = 1 has the general solution u_{n} = αa^{n} + 1/(1 − a) unless a = 1, when the homogeneous equation u_{n} − u_{n−1} = 0 has solution u_{n} = α1^{n} = α. As u_{n} = constant is the solution to the homogeneous equation, it is no use trying it as a particular inhomogeneous solution. Instead, try multiplying by n, so that u_{n} = An. Then An−A(n−1) = 1 so A = 1 gives a particular solution. The general solution is u_{n} = α+n.

Example: We found that T_{n}, the number of floating point operations necessary to calculate an n × n determinant using row operations, obeyed the recurrence relation T_{n} − T_{n−1} = n^{2} − n + 2. The homogeneous equation T_{n} = T_{n−1} has the solution T_{n} = α. For the particular solution, the RHS is a quadratic in n and so we would usually try T_{n} = An^{2} + Bn + C. However, T_{n} = C solves the homogeneous equation, so instead we multiply by n and try T_{n} = An^{3} + Bn^{2} + Cn. Then T_{n} − T_{n−1} =

An^{3} +Bn^{2} +Cn−A(n−1)^{3} −B(n−1)^{2} −C(n−1) = n^{2}(3A)+n(−3A+2B)+(A−B +C) .

This equals n^{2} − n + 2 if 3A = 1, 3A − 2B = 1 and A − B + C = 2, or A = \frac{1}{3}, B = 0 and C = \frac{5}{3}. The general solution is thus T_{n} = \frac{1}{3}n^{3} + \frac{5}{3}n + α. Now a 2 × 2 determinant needs two multiplications, so 2 = T_{2} = \frac{8}{3} + \frac{10}{3} + α, or α = −4 and T_{n} = \frac{1}{3}n^{3} + \frac{5}{3}n − 4.