%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 14 Solving first order non-homogeneous RRs}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}

Grimaldi 10.3

\bigskip
\bigskip
\bigskip

\includegraphics[height=2cm]{hanoi.pdf}

\bigskip
\bigskip
Can you move the disks on pole 1 to pole 3 using pole 2 as needed? \\
Rule 1: move one disk at a time.  \\
Rule 2: do not put a disk on top of a smaller disk. \\
Question: how many moves is necessary?

\vspace{1cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{ Solving first order non-homogeneous recurrences }


\bigskip
Consider the non-homogenous recurrence relations
\bigskip
\begin{itemize}
\item[(1)] $a_n + c_1 a_{n-1} = f(n)$ where $c_1 \ne 0$ and $f(n) \ne 0$
\item[(2)] $x_n + c_1 x_{n-1} + c_2 x_{n-2} = f(n)$ where $c_2 \ne 0$ and $f(n) \ne 0$
\end{itemize}
\bigskip

How do we solve them?

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Case (1) $a_n + c_1 a_{n-1} = f(n)$ where $\color{red} c_1 = -1.$ \\

\vspace{4cm}
Example 1.  Solve $a_n - a_{n-1} = 3n^2$ with $a_0=7$.

\vspace{4cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2.  Solve $a_n - 3 a_{n-1} = 5 \cdot 3^n$ with $a_0 = 2.$

\vspace{10cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 3 -- The Towers of Hanoi.

\bigskip

\includegraphics[height=1.5cm]{hanoi.pdf}

\bigskip
Move the disks from pole 1 to pole 3 using pole 2 as needed. \\
Move one disk at a time.  Do not put a bigger disk on top of a smaller one.

\medskip

\begin{itemize} 
\item[(1)] % Move the top $n-1$ disks on pole 1 to pole 2 (using pole 3 as needed).

\medskip

\item[(2)] % Move disk $n$ on pole 1 to pole 3.

\medskip

\item[(3)] % Move the $n-1$ disks on pole 2 to pole 3 (using pole 1 as needed).
\end{itemize}

\bigskip
Let $m_n$ be the {\bf number of moves}. \\
Determine and solve a recurrence relation for $m_n$.

\vspace{3cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 3 -- The Towers of Hanoi (cont.)
\vspace{12cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 4 -- Interest on a loan. \\
Pauline takes out a bank loan for \$$S$ dollars.
She pays bak \$$P$ every month and the bank charges her $r$\% interest
per month.  Let $a_n$ be the amount she owes after $n$ months.
Determine, and solve, a recurrence relation for $a_n$.

\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 4 -- Interest on a loan (cont.)

\vspace{12cm}
\end{frame}
