AC Linear Recurrence Equations

Skip to main content

\(\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}{\text{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Section 9.2 Linear Recurrence Equations

What do all of the examples of the previous section have in common? The end result that we were able to achieve is a linear recurrence, which tells us how we can compute the \(n^\text{th}\) term of a sequence given some number of previous values (and perhaps also depending nonrecursively on \(n\) as well, as in the last example). More precisely a recurrence equation is said to be linear when it has the following form

\begin{equation*} c_0a_{n+k}+ c_1a_{n+k-1} + c_2a_{n+k-2} + \dots+c_ka_{n} = g(n), \end{equation*}

where \(k\ge1\) is an integer, \(c_0,c_1,\dots,c_k\) are constants with \(c_0,c_k\neq0\text{,}\) and \(g:\ints\rightarrow\reals\) is a function. (What we have just defined may more properly be called a linear recurrence equation with constant coefficients, since we require the \(c_i\) to be constants and prohibit them from depending on \(n\text{.}\) We will avoid this additional descriptor, instead choosing to speak of linear recurrence equations with nonconstant coefficients in case we allow the \(c_i\) to be functions of \(n\text{.}\)) A linear equation is homogeneous if the function \(g(n)\) on the right hand side is the zero function. For example, the Fibonacci sequence satisfies the homogeneous linear recurrence equation

\begin{equation*} a_{n+2} - a_{n+1} - a_n = 0. \end{equation*}

Note that in this example, \(k=2\text{,}\) \(c_0=1\) and \(c_k=-1\text{.}\)

As a second example, the sequence in Example 9.4 satisfies the homogeneous linear recurrence equation

\begin{equation*} t_{n+2} - 3t_{n+1} + t_n = 0. \end{equation*}

Again, \(k=2\) with \(c_0=c_k=1\text{.}\)

On the other hand, the sequence \(r_n\) defined in Subsection 9.1.3 satisfies the nonhomogeneous linear recurrence equation

\begin{equation*} r_{n+1} - r_{n} = n+1. \end{equation*}

In this case, \(k=1\text{,}\) \(c_0=1\) and \(c_k=-1\) .

Our immediate goal is to develop techniques for solving linear recurrence equations of both homogeneous and nonhomogeneous types. We will be able to fully resolve the question of solving homogeneous linear recurrence equations and discuss a sort of “guess-and-test” method that can be used to tackle the more tricky nonhomogeneous type.