


\begin{problem}
\problemdata     
{S01-PS8-1}           
{Generating functions}              
{} 		
{F98-PS8, S01-PS8}
{S01 Karger}





Find generating functions for the following
sequences.

\begin{problemparts}

\problempart $< 0, 0, 1, 1, 1, 1, 1, \ldots >$

\solution{
\begin{eqnarray*}
x^2 + x^3 + x^4 + x^5 + x^6 + \ldots
        & = &   x^2 \cdot (1 + x + x^2 + x^3 + x^4 + \ldots) \\
        & = &   \frac{x^2}{1-x}
\end{eqnarray*}
}

\problempart $< 0, 2, 4, 6, 8, 10, \ldots >$

\solution{
\begin{eqnarray*}
0 + 2 x +  4 x^2 + 6 x^3 + 8 x^4 + \ldots
        & = &   2x \cdot (0 + 1 + 2 x + 3 x^2 + 4 x^3 \ldots) \\
        & = &   2x \cdot \frac{d}{dx} \ (1 + x + x^2 + x^3 + x^4 + \ldots) \\
        & = &   2x \cdot \frac{d}{dx} \ \left(\frac{1}{1-x} \right)\\
        & = &   \frac{2x}{(1-x)^2}
\end{eqnarray*}
}

\problempart $< 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
1 + x^3 + x^6 + x^{9} + x^{12} + \dots  & = &   \frac{1}{1 - x^3}
\end{eqnarray*}
}

\problempart $< 2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \ldots  >$

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

\problempart $< -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{-1 + x^2 - x^3 + x^5 - x^6 + x^8 - \ldots}
\hspace{1in} \\
        & = & (x^2 + x^5 + x^8 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
        & = & x^2 (1 + x^3 + x^6 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
        & = & (x^2 - 1) \cdot (1 + x^3 + x^6 + \ldots) \\
        & = & \frac{x^2 - 1}{1 - x^3}
\end{eqnarray*}
}

\end{problemparts}

\end{problem}
