%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 12 Solving First Order Recurrence Relations}

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

\vspace{1cm}

Grimaldi Chapter 10.1

\vspace{1cm}

{\large \color{blue}
$p_n = n \, p_{n-1}$

\medskip
$c_n = (n-1) + c_{n-1}$

\medskip
$h_n = 1 + 2 h_{n-1}$
}

\vspace{3cm}
\end{frame}

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

\input{Bubblesort}

What should we count to determine the cost of the Bubblesort algorithm? \\
We will count the number of comparisons between elements of $A$ in line 6.  \\
Let $c_n$ be the number of comparisons.

\vspace{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
A First Look at Solving Recurrence Relations. \\
How can we solve RRs like
\begin{itemize}
\item[(1)] $b_n = 2b_{n-1}$ for $n \ge 2$ and $b_1=2$.
\item[(1)] $c_n = c_{n-1} + (n-1)$ for $n \ge 2$ and $c_1=0$.
\end{itemize}

\medskip
Example $b_n = 2 b_{n-1}$

\vspace{10cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example $c_n = c_{n-1} + (n-1)$

\vspace{12cm}
\end{frame}


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

\begin{theorem} [ A different way to solve first order RRs ]
Every sequence $x_0, x_1, x_2, \dots$ satisfying the recurrence $x_n = d x_{n-1}$ has
the general solution $x_n = c d^n$ for some constant $c$. (The sequence is a geometric
progression.)
\end{theorem}

Proof (substitution)

\vspace{3cm}

This suggests the following general strategy for solving RRs:
\begin{itemize}
\item[(1)] Find the {\bf general solution} to the RR. This will have one or more constants.
           Note: a RR of order $k$ will has $k$ constants.
\item[(2)] Use the $k$ initial values to determine the constants. This gives a {\bf unique}
           solution.
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example.  Suppose $x_n = 5 x_{n-1}$ and $x_0 = 7$.  First find the general solution
then the unique solution satisfying $x_0 = 7.$

\vspace{3cm}

Exercise 1. Solve $p_n = n p_{n-1}$ where $p_1 = 1$. \\

\vspace{4cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Exercise 2. Solve $x_n = x_{n-1} + An+B$ for $x_1 = C$.
\vspace{12cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\vspace{12cm}

\end{frame}
