\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section9.3Advancement Operators

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\).

Solution

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\).

Solution

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.

Subsection9.3.1Constant Coefficient Equations

It is easy to see that a linear recurrence equation can be conveniently rewritten using a polynomial \(p(A)\) of the advancement operator: \begin{equation} p(A)f=(c_0A^{k}+ c_1A^{k-1} + c_2A^{k-2} + \dots+c_k)f = g. \label{eqn_advance}\tag{9.3.1}\end{equation} In (9.3.1), we intend that \(k\ge1\) is an integer, \(g\) is a fixed vector (function) from \(V\), and \(c_0,c_1,\dots, c_k\) are constants with \(c_0,c_k\neq0\). Note that since \(c_0\neq0\), we can divide both sides by \(c_0\), i.e., we may in fact assume that \(c_0=1\) whenever convenient to do so.

Subsection9.3.2Roots and Factors

The polynomial \(p(A)\) can be analyzed like any other polynomial. It has roots and factors, and although these may be difficult to determine, we know they exist. In fact, if the degree of \(p(A)\) is \(k\), we know that over the field of complex numbers, \(p(A)\) has \(k\) roots, counting multiplicities. Note that since we assume that \(c_k\neq0\), all the roots of the polynomial \(p\) are non-zero.

Subsection9.3.3What's Special About Zero?

Why have we limited our attention to recurrence equations of the form \(p(A)f = g\) where the constant term in \(p\) is non-zero? Let's consider the alternative for a moment. Suppose that the constant term of \(p\) is zero and that \(0\) is a root of \(p\) of multiplicity \(m\). Then \(p(A) = A^mq(A)\) where the constant term of \(q\) is non-zero. And the equation \(p(A)f=g\) can then be written as \(A^mq(A)f=g\). To solve this equation, we consider instead the simpler problem \(q(A)f=g\). Then \(h\) is a solution of the original problem if and only if the function \(h'\) defined by \(h'(n) = h(n+m)\) is a solution to the simpler problem. In other words, solutions to the original problem are just translations of solutions to the smaller one, so we will for the most part continue to focus on advancement operator equations where \(p(A)\) has nonzero constant term, since being able to solve such problems is all we need in order to solve the larger class of problems.

As a special case, consider the equation \(A^m f =g\). This requires \(f(n+m)=g(n)\), i.e., \(f\) is just a translation of \(g\).