\textbox{
{\small
\begin{center}
{\Large {\textbf {Short Guide to Solving Linear Recurrences}}}
\end{center}

A \textit{linear recurrence} is an equation
%
\[
\underbrace{f(n) = a_1 f(n-1) + a_2 f(n-2) + \ldots + a_d f(n-d)}_{\text{homogeneous part}} \underbrace{+ g(n)}_{\text{inhomogeneous part}}
\]
%
together with boundary conditions such as $f(0) = b_0$, $f(1) = b_1$,
etc.

\begin{enumerate}

\item Find the roots of the \textit{characteristic equation}:
%
\[
x^n = a_1 x^{n-1} + a_2 x^{n-2} + \ldots + a_k
\]

\item Write down the \textit{homogeneous solution}.  Each root generates one
term and the homogeneous solution is the sum of these terms.  A
nonrepeated root $r$ generates the term $c_r r^n$, where $c_r$ is a
constant to be determined later.  A root $r$ with multiplicity $k$
generates the terms:
%
\[
c_{r_1} r^n, \quad c_{r_2} n r^n, \quad c_{r_3} n^2 r^n, \quad \ldots,
\quad c_{r_k} n^{k-1} r^n
\]
%
where $c_{r_1}, \ldots, c_{r_k}$ are constants to be determined later.

\item Find a \textit{particular solution}.  This is a solution to the
full recurrence that need not be consistent with the boundary
conditions.  Use guess and verify.  If $g(n)$ is a polynomial, try a
polynomial of the same degree, then a polynomial of degree one higher,
then two higher, etc.  For example, if $g(n) = n$, then try $f(n) = b
n + c$ and then $f(n) = a n^2 + b n + c$.  If $g(n)$ is an
exponential, such as $3^n$, then first guess that $f(n) = c3^n$.
Failing that, try $f(n) = b n 3^n + c 3^n$ and then $a n^2 3^n + b n
3^n + c 3^n$, etc.

\item Form the \textit{general solution}, which is the sum of the
homogeneous solution and the particular solution.  Here is a typical
general solution:
%
\[
f(n) = \underbrace{c 2^n + d (-1)^n}_{\text{homogeneous solution}} +
       \underbrace{3n + 1}_{\text{particular solution}}
\]

\item Substitute the boundary conditions into the general solution.  Each boundary condition gives a linear equation in the unknown constants.  For example,
substituting $f(1) = 2$ into the general solution above gives:
%
\begin{align*}
2 & = c \cdot 2^1 + d \cdot (-1)^1 + 3 \cdot 1 + 1 \\
\implies \quad -2 & = 2c - d
\end{align*}
%
Determine the values of these constants by solving the resulting
system of linear equations.
\end{enumerate}
}
}
