Much of our motivation for solving recurrence equations comes from an analogous problem in continuous mathematics—differential equations. You don't need to have studied these beasts before in order to understand what we will do in the remainder of this chapter, but if you have, the motivation for how we tackle the problems will be clearer. As their name suggests, differential equations involve derivatives, which we will denote using “operator” notation by \(Df\) instead of the Leibniz notation \(df/dx\). In our notation, the second derivative is \(D^2 f\), the third is \(D^3 f\), and so on. Consider the following example.
Example9.6
Solve the equation \begin{equation*} Df = 3f \end{equation*} if \(f(0) = 2\).
With differential equations, we apply the differential operator \(D\) to differentiable (usually infinitely differentiable) functions. For recurrence equations, we consider the vector space \(V\) whose elements are functions from the set \(\ints\) of integers to the set \(\complexes\) of complex numbers. We then consider a function \(A:V\longrightarrow V\), called the advancement operator, and defined by \(A f(n) = f(n+1)\). (By various tricks and sleight of hand, we can extend a sequence \(\{a_n\colon n\geq n_0\}\) to be a function whose domain is all of \(\ints\), so this technique will apply to our problems.) More generally, \(A^p f(n)= f(n+p)\) when \(p\) is a positive integer.
Example9.7
Let \(f\in V\) be defined by \(f(n)=7n-9\). Then we apply the advancement operator polynomial \(3A^2-5A+4\) to \(f\) with \(n=0\) as follows: \begin{equation*} (3A^2-5A+4)f(0)=3f(2) - 5f(1) +4f(0)= 3(5)-5(-2)+4(-9)=-11. \end{equation*}
As an analogue of Example 9.6, consider the following simple example involving the advancement operator.
Example9.8
Suppose that the sequence \(\{s_n\colon n\geq 0\}\) satisfies \(s_0 = 3\) and \(s_{n+1} = 2s_{n}\) for \(n\geq 1\). Find an explicit formula for \(s_n\).
Before moving on to develop general methods for solving advancement operator equations, let's say a word about why we keep talking in terms of operators and mentioned that we can view any sequence as a function with domain \(\ints\). If you've studied any linear algebra, you probably remember learning that the set of all infinitely-differentiable functions on the real line form a vector space and that differentiation is a linear operator on those functions. Our analogy to differential equations holds up just fine here, and functions from \(\ints\) to \(\complexes\) form a vector space and \(A\) is a linear operator on that space. We won't dwell on the technical aspects of this, and no knowledge of linear algebra is required to understand our development of techniques to solve recurrence equations. However, if you're interested in more placing everything we do on rigorous footing, we discuss this further in Section 9.5.