Here is a method (algorithm) to solve recurrence relations of the following form, without the use of generating functions or z-transforms.
We assume we are given k initial conditions (to enable us to solve uniquely the k’th order equation), and that is of the form
, where is a polynomial of degree .
1. Solve the equation with first (the homogeneous form of the equation).
a) Write down, then factorise the characteristic equation (which arises from setting ).
where are distinct.
b) The homogeneous solution (i.e. that corresponding to ) is
where is a polynomial of degree .
2. Incorporate the term f(n). For j = 1 to J,
- If for all i,
- If for some i,
3. Find for all j and k by substituting into (*).
4. Combine the homogeneous and particular solutions to find the general solution .
5. Use the initial conditions to find in step 1b.
Let us try this out with the following example.
1a) The characteristic equation is found by substituting and setting the right side to 0:
b) The homogeneous solution is then given by .
2. We have . Since 1 is one of the roots of the characteristic polynomial of multiplicity 1, we try a particular solution of the form .
3. Substituting into the original equation:
Matching the constant coefficient of both sides: , so .
4. Combining homogeneous and particular solutions, .
5. Use the initial values to find :
Solving gives . Hence and it can be verified by substitution that this indeed satisfies the recurrence equation with the given initial conditions.
So why does this procedure work? The remainder of this post attempts to provide some insight. It is not intended to be a complete proof, but should provide enough examples for one to be able to generalise and complete the details.
Part A. We start by considering the first order equation
1. By setting this can be converted to an equation of the form , so we are reduced to solving an equation of the original form (+) with .
2. If we can find a solution to for each j, then summing the J solutions will give a solution for . We are reduced further to solving an equation of the form .
3. If we let , becomes
which reduces to . To solve this we have the following lemma which is interesting in its own right.
Lemma 1: Let be a given polynomial of degree d, and a constant. Then there exists a polynomial such that the equation is satisfied.
- If , p has degree d.
- If , p has degree d+1.
For example, has the solution (linear), while has the solution (quadratic).
To prove the lemma, we find the coefficients of p(n) by solving a system of linear equations. The invertibility of the equations comes from the fact that the system is lower triangular with non-zero diagonal entries. This means back-substitution can be used to find the coefficients.
If , matching coefficients of leads to the following system of equations.
For the diagonal entries are non-zero and hence the system of equations may be inverted to solve for the coefficients of p(n).
This time we let (degree d+1) and proceed as in case 1 with set to 1, leading to the following system.
Again the diagonal entries are non-zero, and hence may be solved by back-substitution starting with . This completes the proof of Lemma 1. Note that any constant term can be added to and the result still satisfies .
To tie this with the original 5 steps at the top of the post, the homogeneous solution to is seen to be (easily linked to the characteristic equation ). The two cases in step 2 are equivalent to verifying those of Lemma 1, since we applied the substitution . Then the homogeneous and particular solutions may be added and initial conditions used to determine any remaining coefficients.
The main conclusion of Part A after following the above steps is as follows:
Proposition 1 : The solution of (where q(n) has degree d), is of the form , where is a polynomial whose degree is d if and d+1 if .
Part B: Now we seek to solve the original equation (*). This can be done by successively reducing the order of the left side to reach eventually first order, and then apply the result of Proposition 1.
Let S be the shift operator on sequences, so that S applied to the sequence yields . This is a linear operator in that where and are sequences. We can multiply S by scalars, so that for example , indicating also that S commutes with scalar multiplication. Furthermore, we can also take powers of S, corresponding to successive application of the operator (e.g. ). Finally, we can form linear combinations of these powers, hence polynomials in S. Let I denote the identity operator. Then equation (*) can be written as
The polynomial in S can factorise, as the algebra of polynomials carries over to the shift operator (i.e. the shift operator generates a commutative ring of linear operators), so we may write something like
We can start to see how the roots of the characteristic polynomial in 1a) above play a role.
Suppose we wish to find the general solution to the second order equation . Letting , we find from the above factorisation that . The solution to this is . Then , and from Proposition 1, this has solution .
Consider now the equation . This is equivalent to . Letting , we find that. The solution to this is . Then and from Proposition 1, this has solution (i.e. a different form when there are repeated roots).
This can be generalised to higher orders and the case . We factorise the characteristic polynomial and make first order substitutions with an aim to reduce the order of the recurrence by one each time. Each first order equation is of the form given in Part A and hence may easily be solved by applying Proposition 1.
We will give a final example to illustrate this.
Let . Then , which has solution of the form . Then we have
This has solution of the form . Finally, , which by Proposition 1 has solution of the form
Note that , and are part of the homogeneous solution meaning that they are found only from the initial values and they contribute nothing to the right side of the equation upon substitution. The coefficients and are found by substituting into the original equation and comparing coefficients.
This entire explanation (i.e. Parts A and B) may make better sense after trying more examples. It is nice to have a procedure as outlined in steps 1-5, but more rewarding to see why it works.