\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 15: Solving Non-Homogeneous Relations}

{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi 10.3

\bigskip

\begin{definition}
If $\color{red} f(n) \ne 0$, a recurrence relation of the form 
\begin{itemize}
\item[(1)] $a x_n + b x_{n-1} = {\color{red} f(n)} \qquad a \ne 0, b \ne 0$
\item[(2)] $a x_n + b x_{n-1} + c x_{n-2} = {\color{red} f(n)} \qquad a \ne 0, c \ne 0$
\end{itemize}
\vspace{.2cm}
is called a \textbf{non-homogeneneous} recurrence relation. \\
The {\bf associated homogeneous relation} is obtained by setting $f$ to be 0
\begin{itemize}
\item[(1)] $a x_n + b x_{n-1} = 0$
\item[(2)] $a x_n + b x_{n-1} + c x_{n-2} = 0$
\end{itemize}
\end{definition}

\vspace{2cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{definition}
\begin{itemize}
\item A \textbf{particular solution}
is a single sequence $x_n^{(p)}$ satisfying a recurrence 
without consideration of the initial condition.
\item The \textbf{general solution} to a recurrence is the set of 
all sequences $x_n$ satisfying it (without consideration of the initial condition)
%\item[$\bullet$] A \textbf{unique solution} is the unique answer to a 
%recurrence with given initial conditions.
\end{itemize}
\end{definition}


\begin{theorem}
The general solution to a non-homogeneous recurrence is given by \textbf{one particular solution}, $x_n^{(p)}$, plus the \textbf{general solution} to the associated homogeneous equation, $x_n^{(h)}$. That is, the solution has the form
$$x_n = x_n^{(p)} + x_n^{(h)}.$$
\end{theorem}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 1 \ $x_n = 6 x_{n-1} + 3^n$ for $n>1$ and $x_0=7$.

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2 \ $x_n - 4 x_{n-1} + 3 x_{n-2} = \frac{2^n}{4}$  and $x_0 = 5, x_0 = 6.$

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

To find a particular solution to a non-homogeneous recurrence of the form
\[ a x_n + b x_{n-1} = f(n) \qquad n \ge 1 \]
\[ a x_n + b x_{n-1} + c x_{n-2} = f(n) \qquad n \ge 2 \]

\begin{itemize}
\item[(1)] Exponential functions $f(n) = k r^n$
\begin{itemize}
\item[(a)] If $r$ is not a root of the char. poly. of the homog. recurrence then look for a particular solution of the form $x_n^{(p)} = Cr^n$.
\item[(b)] If $r$ is a root of multiplicity $m$ then look for a particular solution of the form $x_n^{(p)} = C n^{m} r^n$
\end{itemize}

\item[(2)] Power functions $f(n) = k n^d$
\begin{itemize}
\item[(a)] Look for a solution of the form $x_n^{(p)} = a_d n^d + a_{d-1} n^{d-1} \ldots + a_1 n + a_0$
\item[(b)] If $n^t$, for some $t\le d$, is a solution to the homogeneous equation then multiply the trial solution $x_n^{(p)}$ by the smallest power of $n$, say $n^s$, for which no summand of $n^sf(n)$ is a solution of the homog. relation.
\end{itemize}
\end{itemize}

\noindent
See Grimaldi page 479-481 for examples on how to determine the form of $x_n^{(p)}$.
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame} 

Example 3. \ Find a particular solution to $x_n -3 x_{n-1} +2 x_{n-2} = 4n.$

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame} 
Example 3 (continued).

\vspace{12cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame} 
Extra space.

\vspace{12cm}
\end{frame}
