
\problemdata     
{S01-PS8-2}           
{Generating functions}              
{} 		
{F98-PS8, S01-PS8}
{S01 Karger}





\begin{problem}


Suppose that $f(x)$ is the generating function for the sequence $a_0,
a_1, a_2, \ldots$.  Find generating functions for the following
sequences.

\begin{problemparts}
\problempart $< 0, 0, 0, a_0, a_1, a_2, \ldots >$

\solution{
\begin{eqnarray*}
a_0 x^3 + a_1 x^4 + a_2 x^5 + \ldots
        & = &   x^3 \cdot (a_0 + a_1 x + a_2 x^2 + \ldots) \\
        & = &   x^3 f(x)
\end{eqnarray*}
}

\problempart $< a_0, a_1 + 1, a_2 + 2, a_3 + 3, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + (a_1 + 1) x + (a_2 + 2) x^2 + (a_3 + 3) x^3 + \ldots}
\hspace{1in} \\
        & = &   (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)
                + (0 + 1 x + 2 x^2 + 3 x^3 + \ldots) \\
        & = &   f(x) + \frac{x}{(1 - x)^2}
\end{eqnarray*}
}

\problempart $< a_0, 0, a_1, 0, a_2, 0, a_3, 0, \ldots >$

\solution{
\begin{eqnarray*}
a_0 + a_1 x^2 + a_2 x^4 + a_3 x^6 + \ldots
        & = &   f(x^2)
\end{eqnarray*}
}

\problempart $< a_0, -a_1, a_2, -a_3, a_4, \ldots >$

\solution{
\begin{eqnarray*}
a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 - \ldots
        & = &   f(-x)
\end{eqnarray*}
}

\problempart $< a_0, 0, a_2, 0, a_4, 0, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + a_2 x^2 + a_4 x^4 + a^6 x^6 + \ldots}
\hspace{1in} \\
        & = &   \frac{1}{2} (
                (a_0 - a_1 x + a_2 x^2 - a_3 x^3 + \ldots) \\
        &   & \mbox{} + (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)) \\
        & = &   \frac{1}{2}(f(-x) + f(x))
\end{eqnarray*}
}

\end{problemparts}

\end{problem}
