%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 11 Recurrence Relations}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi Chapter 10 Recurrence Relations

\bigskip
\bigskip
\bigskip

The Fibonacci sequence $1, 1, 2, 3, 5, 8, \dots$ \ is generated by the {\bf recurrence}
{ \large
$$ \color{blue} f_{n+1} = f_n + f_{n-1} ~~{\rm for}~ n \ge 2$$
}
and {\bf initial values}
{ \large
$$ \color{blue} f_1 = 1, ~ f_2 = 1. $$
}

\vspace{3cm}
\end{frame}

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

Example 2.  Let $b_n$ be the number of binary strings of length $n$ bits.

\vspace{3cm}

{\bf A new way}: To construct a binary string of length $n$ first construct one of length $n-1$ bits.

\vspace{5cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 3. Let $k_n$ be the number of edges in $K_n$ the complete graph on $n$ vertices.

\vspace{12cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition} A {\bf linear} recurrence relation (RR) of {\bf order $k$} with {\bf constant coefficients} for a sequence $a_1,a_2,a_3, \dots$ is an equation of the form
{ \large
$$
c_0 a_n + c_1 a_{n-1} + \dots + c_k a_{n-k} = f(n) ~~ {\rm for}~ n \ge k
$$
}
\noindent
where $c_0,c_1,\dots,c_k$ are constants and $c_0 \ne 0, c_k \ne 0.$
If $f(n)=0$ the RR is said to be {\bf homegeneous}, otherwise it is {\bf non-homogeneous}.
\end{definition}

Examples


\vspace{6cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Note: We can {\bf shift} a RR up or down without changing the solutions.  For example

\bigskip
\begin{tabular}{rcl}
$a_{n+1}$ &=& $2 a_n + n$ \\
$a_{n  }$ &=& $2 a_{n-1} + n-1$ \\
$a_{n+2}$ &=& $2 a_{n+1} + n+1$
\end{tabular}

\bigskip
Initial Values:

\vspace{5cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 4.  Let $S_n$ be the set of all binary strings of length $n$ with the property
that every 1 is followed by a 0 (so 1 cannot be the last bit).

\medskip

\begin{itemize}
\item[(1)] List $S_1, S_2, S_3$.
\item[(2)] Let $c_n = |S_n|$.  Give a recurrence relation for $c_n$.
\end{itemize}

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 5.  Let $D_n$ be the set of all strings of length $n$ 
over the alphabet $\Sigma = \{A,B,C,D\}$ such that every $A$ is followed
by a $C$ and every $B$ is followed by $DD$.

\medskip
\begin{itemize}
\item[(1)] List $D_0, D_1, D_2$.
\item[(2)] Let $d_n = |D_n|$.  Give a recurrence relation for $d_n$.
\end{itemize}

\vspace{12cm}
\end{frame}

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

{Additional space}

\vspace{12cm} 

\end{frame}
