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

\frametitle{Lecture 20 Rational Generating Functions continued.}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{2cm}
Grimaldi 9.2 Calculation Techniques

\vspace{2cm}
\vspace{2cm}

\end{frame}

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

\subsubsection{General Form}
\medskip

\noindent
We have been working with the two basic GF's
\begin{align*}
\frac{1}{1-x}  &=      1 + x + x^2 + x^3 + \cdots =  \sum_{n=0}^{\infty} x^n   \\
\frac{1}{(1-x)^2}       &=      1 + 2x + 3x^2 + 4x^3 + \cdots = \sum_{n=0}^{\infty} (n+1) x^n
\end{align*}

\noindent
We already proved the more general generating function:
\[ \frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} {n + k - 1 \choose n} x^n \]

\noindent
Combining this formula with {\bf substitution} allows us to determine the coefficients of any rational function of the form $$\frac{p(x)}{ (ax+b)^k }.$$

\bigskip
\noindent 
On page 422 the textbook uses a natural generalization of binomial coefficients,
called the \emph{extended binomial theorem} to get these coefficients.
We will use substitutions instead.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 1.  For $\ds A(x) = \frac{x}{(1-x)^2}$ find $[x^n]( A(x) )$.


\vspace{3.5cm}

Example 2.  Find the coefficient of $x^5$ of $\ds A(x) = \frac{1}{(1-2x)^7}$

\vspace{4cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Partial Fractions}

Question: How can we deterine the coefficients of GFs of the form
$$ \frac{p(x)}{ax^2+bx+c}  ~~{\rm and}~~ \frac{p(x)}{ax^3+bx^2+cx+d} ~~{\rm etc}? $$

\bigskip
If $ax^2+bx+c=a(x-\alpha)(x-\beta)$ and $\alpha \ne \beta$ solve
$$ \frac{1}{(x-\alpha)(x-\beta)} = \frac{A}{x-\alpha} + \frac{B}{x-\beta}$$
for $A,B$.  If $ax^3+bx^2+cx+d=a(x-\alpha)(x-\beta)(x-\gamma)$ 
and $\alpha \ne \beta \ne \gamma$ solve
$$ \frac{1}{(x-\alpha)(x-\beta)(x-\gamma)}
   = \frac{A}{x-\alpha} + \frac{B}{x-\beta} + \frac{C}{x-\gamma}$$
for $A,B,C$.  If $ax^3+bx^2+cx+d=a(x-\alpha)(x-\beta)^2$ and $\alpha \ne \beta$ solve
$$ \frac{1}{(x-\alpha)(x-\beta)^2}
   = \frac{A}{x-\alpha} + \frac{B}{x-\beta} + \frac{C}{(x-\beta)^2}$$
for $A,B,C$.  Then use the formula for $1/(1-x)^k$ with substitutions.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 1.  Find the coefficient of $x^n$ of $\ds C(x) = \frac{3x}{x^2-3x+2}$.
% Use C(x) = 3x/(x-2)(x-1) = A/(x-2) + B/(x-1)
%     3x = A(x-1)+B(x-2) = (A+B)x -A-2B ==> A+B=3, A+2B=0 ==> -B=3, B=-3, A=6
%   C(x) = 6/(x-2) - 3/(x-1) = -6/(2-x) + 3/(1-x) = -3/(1-x/2) + 3/(1-x)
% [x^n] C(x) = -3 / 2^n + 3
%
% Alternative
%     3x = A(x-1)+B(x-2)
% x=1  3 = 0 - B ==> B = -1
% x=2  6 = A + 0 ==> A = 6
\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2.  Find values for $A,B,C$ so that the expression below is true.
%then use this to determine $[x^n]D(x)$.
\[ D(x) = \frac{1}{(x-3)(x-2)^2} = \frac{A}{x-3} + \frac{B}{x-2} + \frac{C}{(x-2)^2} \]

\vspace{10cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Series Division}

\medskip
To find the series for the quotient 
$$
C(x) = \frac{A(x)}{B(x)} = \frac{a_0 + a_1 x + a_2 x^2+ \cdots}
                                {b_0 + b_1 x + b_2 x^2+ \cdots}
$$
let $C(x) = c_0 + c_1 x + c_2 x^2 + \cdots$ and write $A(x) = B(x) C(x)$ so that

{ \color{blue}
$$ 
   (a_0 + a_1 x + a_2 x^2 + \cdots)
 = (b_0 + b_1 x + b_2 x^2 + \cdots) (c_0 + c_1 x + c_2 x^2 + \cdots)
$$
}

In this equation the $a_i$ and $b_i$ are known coefficients, the $c_i$ are unknown. \\
Equating coefficients in $x^i$ for $i=0,1,2,\cdots$ and solving for $c_i$ we obtain

\bigskip
\begin{tabular}{l l}
$[x^0]$  &  $\ds a_0 = b_0 c_0 \implies c_0 = a_0 / b_0 \color{dred} \implies b_0 \ne 0$ \\
$[x^1]$  &  $\ds a_1 = b_0 c_1 + b_1 c_0 \implies c_1 = ( a_1-b_1 c_0 ) /  b_0$ \\
$[x^2]$  &  $\ds a_2 = b_0 c_2 + b_1 c_1 + b_2 c_0
                  \implies c_2 = ( a_2-b_1 c_1 - b_2 c_0 ) / b_0 $ \\
$\dots$  & \\
$[x^n]$  &  $\ds a_n = b_0 c_n + b_1 c_{n-1} + \dots + b_n c_0
           \implies c_n = ( a_n - b_1 c_{n-1} - \dots - b_n c_0 ) / b_0 $
\end{tabular}

\vspace{2cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 1.  Let $A(x) = (1+x)/(1-x)^2 = (1+x)/(1-2x+x^2)$.
Find the coefficients of $A(x)$ up to $x^3$ using series division.

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2.  Find a recurrence for the coefficients of $x/(1-x-x^2)$ using series division.

\vspace{7.5cm}
Exercise. Find the series for $(1+x)/(1-3x+3x^2-x^3)$ to $x^4$ using series
division and determine a recurrence for the $n$th coefficient.
% Exercise  Find x/(1-x-x^2-x^3)  and look up OEIS 
\end{frame}

