Formalizing our approach to recurrence equations

So far, our approach to solving recurrence equations has been based on intuition, and we've not given a lot of explanation for why the solutions we've given have been the general solution. In this section, we endeavor to remedy this. Some familiarity with the language of linear algebra will be useful for the remainder of this section, but it is not essential.

Our techniques for solving recurrence equations have their roots in a fundamentally important concept in mathematics, the notion of a vector space. Recall that a vector spaceTo be more complete, we should say that we are talking about a vector space over the field of real numbers, but in our course, these are the only kind of vector spaces we will consider. For this reason, we just use the short phrase vector space. consists of a set \(V\) of elements called vectors; in addition, there is a binary operation called addition with the sum of vectors \(x\) and \(y\) denoted by \(x+y\); furthermore, there is an operation called scalar multiplication which combines a scalar (real number) \(\alpha\) and a vector \(x\) to form a product denoted \(\alpha x\). These operations satisfy the following properties:

1. \(x+y=y+x\) for every \(x,y,\in V\).

2. \(x+(y+z) = (x+y)+z\), for every \(x,y,z\in V\).

3. There is a vector called zero and denoted \(0\) so that \(x+0=x\) for every \(x\in V\). Note: We are again overloading an operator and using the symbol \(0\) for something other than a number.

4. For every element \(x\in V\), there is an element \(y\in V\), called the additive inverse of \(x\) and denoted \(-x\) so that \(x+(-x)=0\). This property enables us to define subtraction, , \(x-y= x+(-y)\).

5. \(1x=x\) for every \(x\in X\).

6. \(\alpha(\beta x) = (\alpha\beta)x\), for every \(\alpha,\beta\in\reals\) and every \(x\in V\).

7. \(\alpha(x+y)=\alpha x + \alpha y\) for every \(\alpha\in\reals\) and every \(x,y\in V\).

8. \((\alpha +\beta) x = \alpha x + \beta x\), for every \(\alpha,\beta\in\reals\) and every \(x\in V\).

When \(V\) is a vector space, a function \(\phi\colon V\rightarrow V\) is called an linear operator, or just operator for short, when \(\phi(x+y)=\phi(x)+\phi(y)\) and \(\phi(\alpha x)=\alpha\phi(x)\). When \(\phi\colon V\rightarrow V\) is an operator, it is customary to write \(\phi x\) rather than \(\phi(x)\), saving a set of parentheses. The set of all operators over a vector space \(V\) is itself a vector space with addition defined by \((\phi+\rho)x = \phi x +\rho x\) and scalar multiplication by \((\alpha\phi)x=\alpha(\phi x)\).

In this chapter, we focus on the real vector space \(V\) consisting of all functions of the form \(f\colon\ints\rightarrow\reals\). Addition is defined by \((f+g)(n)= f(n)+g(n)\) and scalar multiplication is defined by \((\alpha f)(n)=\alpha(f(n))\).

Here is the basic theorem about solving recurrence equations (stated in terms of advancement operator equations)and while we won't prove the full result, we will provide enough of an outline where it shouldn't be too difficult to fill in the missing details.

The conclusion that the set \(W\) of all solutions is a subspace of \(V\) is immediate, since \[\begin{aligned}\end{aligned}\] What takes a bit of work is to show that \(W\) is a \(k\)-dimensional subspace. But once this is done, then to solve the advancement operator equation given in the form of , it suffices to find a basis for the vector space \(W\). Every solution is just a linear combination of basis vectors. In the next several subsections, we outline how this goal can be achieved.

The development proceeds by induction (surprise!) with the case \(k=1\) being the base case. In this case, we study a simple equation of the form \((c_0A+c_1)f=0\). Dividing by \(c_0\) and rewriting using subtraction rather than addition, it is clear that we are just talking about an equation of the form \((A-r)f=0\) where \(r\neq0\).

Using the preceding two results, we can now provide an outline of the inductive step in the proof of , at least in the case where the polynomial in the advancement operator has distinct roots.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

It is straightforward to modify the proof given in the preceding section to obtain the following result. We leave the details as an exercise.

Combining the results in the preceding sections, we can quickly write the general solution of any homogeneous equation of the form \(p(A)f=0\) provided we can factor the polynomial \(p(A)\). Note that in general, this solution takes us into the field of complex numbers, since the roots of a polynomial with real coefficients are sometimes complex numberswith non-zero imaginary parts.

We close this section with one more example to illustrate how quickly we can read off the general solution of a homogeneous advancement operator equation \(p(A)f=0\), provided that \(p(A)\) is factored.