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

\frametitle{Lecture 21: Solving Recurrences using Generating Functions}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\bigskip

Grimaldi 10.4
\vspace{5mm}

Given $a_0$, the recurrence $a_n = 3a_{n-1} + 1$ defines a sequence
$$
a_0, a_1, a_2, \dots, a_n, \dots
$$
which in turn defines the generating function
$$
A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n + \dots 
$$
If we find a rational form for $A(x)$, that is
$$
A(x) = \frac{p(x)}{q(x)}
$$
for polynomials $p(x)$ and $q(x)$, then we can use partial fractions
to get a formula for $a_n = [x^n] A(x)$.

\vspace{5mm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 1.  Solve $a_n - 3 a_{n-1} = n$ for $n \ge 1$ and $a_0 = 1$. \\
The recurrence relation represents an infinite set of equations.

\vspace{2cm}
Multiply equation ($k$) be $x^k$ we get
\vspace{2cm}

Adding all equations up gives
\vspace{3cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Now plug in $a_0$ and isolate $A(x)$.
\vspace{3cm}


Now we do a PDF and get a formula for $a_n$.
\vspace{5cm}


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

Example 2.  Consider the sequence defined by $a_0=0, a_1=1$ and 
\medskip

\quad $a_n-5a_{n-1}+6a_{n-2}=0$ {for} $n\ge 2.$

\medskip
Find a rational expression for $A(x) = \sum_{n=0}^{\infty} a_n x^n.$
\vspace{12cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2 (cont.)
\vspace{12cm}
\end{frame}

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

Method.

\medskip
Let $a_0,a_1,a_2, \dots $ be a sequence satisfying a recurrence
$$ c_n a_n + c_{n-1} a_{n-1} + \dots + c_k a_{n-k} = f(n).$$
Let $A(x) = a_0 + a_1 x + a_2 x^2 + \dots $ \\
\begin{itemize}
\item[(1)] Multiply the recurrence by $x^k, x^{k+1}, \dots$ and sum both sides
           to infinity.
\item[(2)] Rewrite the infinite sums on the LHS in terms of $A(x)$ and 
           the sum on the RHS as a rational function.
\item[(3)] Isolate $A(x)$ and use partial fractions to calculate $a_n = [x^n] A(x)$.
\end{itemize}


\end{frame}

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

Problem.  Consider the sequence defined by
\medskip

\quad $ a_0 = 2, a_1 = 3$ and $a_n - 4 a_{n-1} + 4a_{n-2} = 2^n$ for $n\ge 2.$

\medskip
Solve the recurrence using a generating function.

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Problem (cont.)

\vspace{12cm}

\end{frame}

