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

\bigskip 
\bigskip

Grimaldi 10.2


\vspace{1cm}
{ \Large \color{blue}

$ f_{n+1} = f_n + f_{n-1} $ \\

\bigskip

$ a_{n} = a_{n-1} + 2 a_{n-2} $
}

\vspace{3cm}
\end{frame}

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

For constants $a,b,c$ consider a recurrence relation of the form
\begin{equation}
\label{eqn:2nd}
a \, x_n + b \, x_{n-1} + c \, x_{n-2} = 0 \quad \mbox{ for $n \ge 2$}.
\end{equation}

Suppose that $x_n = r^n$ is a solution to equation (\ref{eqn:2nd}).
In this case we have
\begin{equation}
\label{eqn:char-poly}
a r^n + b r^{n-1} + c r^{n-2} = 0 \quad \mbox{ for all $n \ge 2$}.
\end{equation}

\vspace{1cm}

\noindent
Observe that the $n \ge 2$ condition is redundant in equation (\ref{eqn:char-poly}).   If this holds for $n=2$, then it holds for all larger values (multiplying by powers of $r$ gives the other equations).  This reduces us to a familiar equation 

\[ a r^2 + br + c = 0 \]

\noindent
Conclusion: A number $r$ satisfies $ar^2 + br + c = 0$ if and only if $x_n = r^n$ is a solution to our recurrence.  

\end{frame}

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

\begin{definition}
The homogeneous second order linear recurrence relation
\[ a x_n + b x_{n-1} + c x_{n-2} = 0 \] 
has \textbf{characteristic equation}
\[ ar^2 + br + c = 0. \]
\end{definition}

\noindent
The roots of $ar^2+br+c$ are precisely those numbers 
$r$ for which $x_n = r^n$ satisfies the above recurrence. 


\bigskip
Exercise.
Find all real numbers $r$ so that $x_n = r^n$ is a solution to the recurrence
\[ x_n - 5 x_{n-1} + 6 x_{n-2} = 0 \]

\vspace{5cm}
\end{frame}





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

\begin{theorem}[ Linearity ]
Both of the properties below hold for the recurrence relation
\begin{equation}
\label{eqn:lin}
a x_{n} + b x_{n-1} + c x_{n-2} = 0
\end{equation}

\begin{itemize}
\item[(A)] If $x_n = r^n$ is a solution of (\ref{eqn:lin})
then $C r^n$ is a solution to (\ref{eqn:lin}) for any constant $C$.
\item[(B)] If $x_n = s^n$ and $x_n = t^n$ are solutions of (\ref{eqn:lin}) then $s^n+t^n$ 
is a solution.
\end{itemize}
It follows from $(A)$ and $(B)$ that $C s^n + D t^n$ is a solution for any constants $C, D$.
\end{theorem}

\bigskip
Proof:

\vspace{7cm}
\end{frame}

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

Exercise. \ The recurrence relation $$x_n - 5 x_{n-1} + 6 x_{n-2} = 0$$
has the solutions $x_n = 3^n$ and $x_n = 2^n$. Check that $C 2^n + D 3^n$ is a solution.

\vspace{3cm}

How do we determine what $C$ and $D$ are? With two consecutive initial values.
Find the solution with the initial values $ x_0 = 6$ and $x_1 = 13.$

\vspace{3cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{General solutions}

\begin{theorem} \index{recurrence relation!general solution}
Let $a,b,c$ be fixed constants with $a \neq 0$ and consider the recurrence
\begin{equation}
\label{order2again}
a x_n + b x_{n-1} + c x_{n-2} = 0.
\end{equation}
If the characteristic equation, 
\[ ar^2 + br + c =0\]
has two {\bf distinct} real roots, say $r_1$ and $r_2$, then every sequence
satisfying this recurrence has the form 
\begin{equation}
\label{eqn:genlsol}
x_n = C r_1^n + D r_2^n
\end{equation}
where $C$ and $D$ are fixed constants.  Accordingly, we will call equation (\ref{eqn:genlsol}) the \textbf{general solution} to the recurrence.  
\end{theorem}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example. \ The Fibonacci sequence $(f_1, f_2, f_3, \ldots)$ is generated
by the recurrence
%
\[ f_n = f_{n-1} + f_{n-2} \qquad \mbox{ for $n \ge 2$ } \]
%
together with the initial values $f_0 = 0$ and $f_1 = 1$.
\begin{itemize}
\item[(1)] Find the general solution to the above recurrence.
\item[(2)] Find a closed form (a formula in $n$) for the Fibonacci sequence.
\end{itemize}

\vspace{8cm}
\end{frame}

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

Solving $ar^2+br+c=0$ using the quadratic formula we get
$$
r = \frac{-b \pm \sqrt{ \color{red} b^2-4ac }}{2a}
$$
If $\color{red} b^2-4ac=0$ then we have two repeated real roots. \\
If $\color{red} b^2-4ac<0$ we have two complex roots.

\begin{theorem}[ Repeated real roots case ]
Let $a,b,c$ be real constants with $a \ne 0, c \ne 0$ and consider the recurrence
$$ a \, x_n + b\, x_{n-1} + c\, x_{n-2} = 0.$$
If the characteristic polynomial $a r^2 + b r + c$ has a repeated root $r$ then 
every sequence satisfying this recurrence has the form 
\begin{equation}
\label{caserr}
x_n = C r^n + D \, n r^n
\end{equation}
where $C$ and $D$ are constants.  
Equation (\ref{caserr}) is the {\bf general solution} to the recurrence.
\end{theorem}

\end{frame}

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

Example. Solve the following recurrence 
$$x_n -6 x_{n-1} + 9 x_{n-2} = 0  \quad {\rm with} \quad x_0=2, ~x_1 = 3.$$
\vspace{12cm}

\end{frame}
