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

\frametitle{Lecture 18 \ Calculating with Generating Functions}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi 9.2

\vspace{10cm}
\end{frame}


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

\begin{definition}[ Generating Function ]

Let  $a_0,a_1,a_2,a_3,\dots$ be a sequence of real numbers (or integers).
The function 
$$ 
  A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i 
$$
is called the {\bf generating function} for the sequence.
\end{definition}

Note: we are interested in the coefficients of $A(x)$ not the values of $A(x)$.


All polynomials may be viewed as generating functions.

\medskip

Example 1
% f(x) = 1+3x+3x^2+1
% A(x) = 1+3x+3x^2+x^4+\dots $  a_0=a_3=1, a_1=a_2=3, a_4=a_5=...=0.

\vspace{3cm}
\end{frame}

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

Example 2.  How many ways can we make 30 cents from nickels, dimes and quarters?

\vspace{4cm}

Example 3.  How many integer solutions does $x_1 + x_2 + x_3 = n$ have if $x_i \ge 0$?

\vspace{4cm}

\end{frame}

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

\begin{definition} [ Arithmetic for Generating Functions ]
Let $A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots$ \\
and $B(x) = b_0 + b_1 x + b_2 x^2 + b_3 x^3 + \dots$ and $c$ be a constant.  Then 

\begin{itemize}
\item[(1)] Sum: \ 
$\ds A(x) + B(x) = (a_0+b_0) + (a_1+b_1) x + \dots = \sum_{n=0}^{\infty} (a_n+b_n) x^n.$

\item[(2)] Scalar product: \ 
$ \ds c A(x) = c a_0 + c a_1 x + \dots = \sum_{n=0}^{\infty} (c a_n) x^n.$

\item[(3)] Product:  
$\ds A(x) \cdot B(x) = (a_0 b_0) + (a_0 b_1 + a_1 b_0)x + \dots = 
   \sum_{n=0}^{\infty} \left ( \sum_{k=0}^{n} a_k b_{n-k} \right ) x^n.$


\item[(4)] Derivative: \ 
$\ds A'(x) = a_1 + 2a_2 x + 3a_3 x^2 + \dots = \sum_{n=1}^{\infty} (n a_n) x^{n-1}.$
\end{itemize}
\end{definition}

\vspace{1.5cm}
\end{frame}

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

\bigskip
Example.  Let $A(x) = 1+x+x^2+x^3+ \dots$ and $B(x) = 2+2x+2x^2+2x^3 + \dots$.


\bigskip

$
2A(x)+B(x) =
$

\vspace{2cm}
$
A(x) \cdot B(x) = 
$

\vspace{2cm}
$
A'(x) = 
$

\vspace{4cm}
\end{frame}


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

What about inverses?  Let $x$ be a real number. \\
The number 1 has the property $1 \cdot x = x$ for all $x$. [identity] \\
If $x$ is non-zero it has an inverse $1/x$ so that $x \cdot \frac{1}{x} = 1$. [inverses]

\vspace{3cm}
%\medskip
%Let $A(x) = \sum_{n=0}^{\infty} a_n x^n$ be a generating function. \\
%Then $1 \cdot A(x) = \sum_{n=0}^{\infty} (1 a_n) x^n = A(x)$. \\
%If $A(x) \cdot B(x) = 1$ we say $B(x)$ is the inverse of $A(x)$ and write $B(x)=1/A(x)$.

Example 1 \ Let $A(x) = 1+x+x^2+ \dots$ and $B(x) = 1-x$. \\
Verify that $A(x) \cdot B(x) =1 $ and conclude that $A(x) = 1/B(x) = 1/(1-x)$.

\vspace{3cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2.  Find the inverse of $(1-x)^k$.

Let $a_n$ be the number of integer solutions of $x_1 + x_2 + \dots + x_k = n $ where $x_i \ge 0$.


% Using selection with repetition is $a_n = C(n+k-1,n)$.
% Consider $A(x) = (1+x+x^2+\dots+x^n+\dots)^k = 1/(1-x)^k$.
% The number of solutions is $[x^n] A(x)$.
% Thus $[x^n] A(x) = C(n+k-1,n)$ so $A(x) = \sum_{n=0}^{\infty} C(n+k-1,n) x^n$.

\vspace{10cm}

\end{frame}

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

Example 3 \ Let $C(x) = 1 + 2x + 4x^2 + 8x^3 + \dots $ and
$N(x) = 1 + x^5 + x^{10} + x^{15} + \dots $ (the GF for nickels). \\
Using $2x C(x)$ and $x^5 N(x)$ find the inverse of $C(x)$ and $N(x)$.

%2x C(x) = 2x + 4x^2 + 8x^3 + \dots = C(x) - 1 so 2x C(x) = C(x) - 1
%so C(x) = 1/(1-2x) and C^(-1) = 1-2x.


%Then x^5 N(x) = x^5 + x^10 + \dots = N(x) - 1 so N(x) = 1/(1-x^5)
% Thus N^(-1) = 1-x^5.

%C(x) = A(2x) = 1/(1-2x) and N(x) = A(x^5) = 1/(1-x^5).
\vspace{7.5cm}
Express $C(x)$ and $N(x)$ in terms of $A(x) = 1 + x + x^2 + x^3 + \dots  = 1/(1-x)$.
\end{frame}
