Solving recurrence relations requires solving a system of linear equations. A system is a set of more than one equation, with more than one unknown variables. If the number of unknowns is greater than the number of equations, then we cannot completely solve the system. If the number of equations equals the number of unknowns, then we have at least the hope, but not the certainty, of being able to solve the system.

A system may not have a solution because the equations are inconsistent:

A system may also be redundant, or linearly dependent:

In this case, the second equation is simply the first equation multiplied by a constant, and so gives us no additional information. This system has an infinite number of solutions: y = 6 - x, but x may have any value at all.

We can attempt to solve any system of n equations in n unknowns. If the system has either of the two pathologies above, it will become apparent during the solution. (If we have more equations than unknowns, then the system is overdetermined and may or may not have a unique solution. The usual procedure is to take a set of n of the equations and solve them, and then check to see if the solution found will also work for the remaining equations.)

In solving a system of equations, we may make any of the following elementary transformations:
    1. The equations may be written down in any order. This obviously does not affect the solution.
    2. Any of the equations may be multiplied or divided by a constant, as long as the quantities on both sides of the equals sign are multiplied or divided by the same constant.
    3. One equation can be added to or subtracted from any of the others; again, providing that the quantities on both sides are added or subtracted in the same way.

These transformations may be applied any number of times, in any order, using any of the equations, without affecting the solution.

The general strategy is to find a series of elementary transformations that allow the equations to be added in such a way that one variable can be eliminated. This tranforms the system of n equations in n unknowns to a system of n-1 equations in n-1 unknowns. This is continued until only a single equation in a single unknown remains. This equation is solved directly, and that value then substituted into one of the earlier equations.

An example will make this clearer. Suppose we have the following system of linear equations:

We wish to find unique values for x and y, if any exist, that satisfy both equations at once.

First, we decide which variable to eliminate. We arbitrarily decide to eliminate y first. We need to multiply or divide one of the equations by a constant so that y has the same coefficient in both equations, with opposite sign. To avoid working with fractions, let's multiply the first equation by -4:

We now add the two equations, simply by adding left sides and adding right sides:

The solution to this sytem of equations is x = 1, y = 2.

Comments. Rather than adding equations, it's also quite acceptable to subtract one equation from another. For example, in the above example, we could have multiplied the first equation by 4 and subtracted. When working these problems by hand, however, it's usually safer to multiply by a negative number if necessary and always add equations. This reduces the risk of getting confused while subtracting numbers of different signs. When programming a computer to solve these systems, of course, such considerations are irrelevant.
    In the general case, when the variables may take on any real value, we also may have to worry about both roundoff effects and ill-conditioning; some systems of equations are very sensitive to errors in calculating their solutions. Small errors in calculations can result in large errors in the answers. But since this is a course in discrete mathematics and not numerical analysis, we're not going to go into much detail on these problems. Just be aware that in the real world of computing, this technique is very frequently used, and such considerations can be very important. But such considerations are matters of computation, not mathematics; if our computers were capable of infinite precision, such considerations would never matter.

Pathologies in linear systems: Let's try working the above pathological examples and see what happens.

First,

Multiplying the first equation by -1 gives us

Adding these equations gives the startling result

Now let's deal with the redundant example:

Multiplying the first equation by -2 gives us

And adding the equations gives us the valid (but hardly informative)

In either case, we can simply start the solution and see if we get such a pathological case. This is because inspecting a system and detecting redundancy or inconsistency is very difficult. For example, is the following system valid, redundant, or inconsistent?

Just by looking, there's almost no way to tell. If we attempt to solve the system, we'll find out. So let's solve it.

We decide that we will first eliminate z. The choice is arbitrary, but we have to start somewhere. Multiply the first equation by 2 and add it to the second:

Now multiply the second equation by -5 and add it to the third:

We have reduced our original system of 3 equations in 3 unknowns to a system of 2 equations in 2 unknowns:

We have reduced our original problem to a simpler version of the same basic problem: solution of a set of equations. So now we solve this smaller set of equations. Multiply the first equation by 2 and add it to the second.

The obvious solution is x = 1. Now we select one of our earlier equations (from the previous step) and substitute. We arbitrarily select Eq. 2:

Now we substitute our values of x and y back into our original equations, again selecting one of the equations arbitrarily:

The system of equations is satisfied by x = 1, y = 1, z = 3.

This method is very general and can be used to solve any system of n linear equations in n unknowns. For large systems, it's much less tedious to use a computer algebra package, or use any of several different matrix methods for solving them. These methods are covered in CS 393, Numerical Analysis and Symbolic Computation.

SI - CS 191 Home Page

Email Brian
 

This page last modified 1/7/2000
Copyleft 2000, Brian K. Hare