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\text{.}$