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

\frametitle{Lecture 19 \ Rational Generting Functions }
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\bigskip
Grimaldi 9.2

\vspace{1cm}
{\color{blue}
\[ A(x) = 1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x} \]
\[ A'(x) = 1 + 2x + 3x^2 + 4x^3 + \cdots = \frac{1}{(1-x)^2} \]
}

\vspace{2cm}
\end{frame}


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

We have already seen that the generating function
\[ A(x) = 1 + x + x^2 +x^3 + \ldots = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \]
has a compact represenation as the rational function $\frac{1}{1-x}$.
Generating functions which can be compactly represented as
rational functions will be our main subject.

\bigskip

\begin{definition}\index{generating function!rational}
A generating function $A(x) = a_0 + a_1 x + a_2 x^2 + \dots $ is \textbf{rational} if it can be expressed as
\[ A(x) = \frac{p(x)}{q(x)} \]
where $p(x)$ and $q(x)$ are polynomials and $q(x) \ne 0$.
\end{definition}


\bigskip

\noindent
\begin{itemize}
\item[(1)] Given a sequence of numbers express it as a rational GF ?
\item[(2)] Given a rational GF, find the associated sequence (coefficient extraction)
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Two useful generating functions}

\quad $\ds A(x) = 1 + x + x^2 +x^3 + \ldots = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} .$ \\
\quad $\ds A'(x) = 1 + 2x + 3x^2 + \ldots = \sum_{n=0}^{\infty} (n+1) x^n = \frac{1}{(1-x)^2} .$

Using just these two GF's with basic arithmetic operations gives us the ability
to describe many other GF's.

\bigskip
Example 1.  Determine the sequence for the GF

\medskip
$ \ds \frac{x^3-2}{1-x} $

\vspace{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2.  Determine the sequence for the GF

\medskip
$ \ds \frac{2x^2+5}{(1-x)^2} + 7x $

\vspace{10cm}

\end{frame}

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

\begin{definition}[ Substitution ]
Let $A(x) = a_0 + a_1 x + a_2 x^2 + \dots$ be a GF and $c$ be a constant.  Define
$$ A({\color{blue} cx^m}) = a_0 + a_1(cx^m) + a_2(cx^m)^2 + a_3(cx^m)^3 \dots 
           = \sum_{n=0}^{\infty} a_n c^n x^{mn}. $$
\end{definition}

\bigskip
Example 1.  The GF for nickels is $N(x) = 1+x^5+x^{10}+\dots = \sum_{n-0}^{\infty} x^{5n}.$
 \\ Express $N(x)$ as a rational function.

\vspace{8cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2.  What is the GF for $1,-1,1,-1,\dots$ ?

\vspace{4cm}
Example 3.  Express $C(x) = 1-2x+4x^2-8x^3+16x^4-\dots$ as a rational function.
\vspace{4cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 4.  Find a rational GF for the sequence $1,-2,3,-4,5,-6,\dots$ ?
\vspace{4cm}

Example 5.  Express $D(x) = -x + 2x^2 - 3x^3 + 4x^4 - \dots$ as a rational function.
\vspace{4cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
{\bf Finding Coefficients}

\medskip
Using substitution and our two basic GF's $A(x) = 1+x+x^2+ \dots $ and $A'(x)$
we can now determine the coefficients for any GF that has the form
$$ \frac{p(x)}{ax+b} ~~{\rm or}~~ \frac{p(x)}{(ax+b)^2} $$

Problem 1.  Find the coefficient of $x^k$ in the GF

\medskip
$\ds C(x) = \frac{x^2}{2x+3}$

\vspace{6cm}
\end{frame}

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

Problem 2.  Find the coefficient of $x^k$ in the GF

\medskip
$\ds D(x) = \frac{x^2}{(x+2)^2}$ % avoid fractions

\vspace{12cm}
\end{frame}
