\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\recitation{16}{November 5, 2004}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The \term{(ordinary) generating function} for a sequence $\seq{a_0, a_1,
a_2, a_3, \dots}$ is the power series:
%
\[
a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Find closed-form generating functions for the following sequences.  Do
not concern yourself with issues of convergence.

\bparts

\ppart $\seq{2, 3, 5, 0, 0, 0 , 0, \ldots}$

\solution[\vspace{0.25in}]{
\[
2 + 3x + 5x^2
\]
}

\ppart $\seq{1, 1, 1, 1,1 ,1, 1, \dots}$

\solution[\vspace{0.25in}]{
\[
1 + x + x^2 + x^3 + \ldots = \frac{1}{1 - x}
\]
}

\ppart $\seq{1, 2, 4, 8, 16, 32, 64, \dots}$

\solution[\vspace{0.25in}]{
\begin{align*}
1 + 2 x + 4 x^2 + 8 x^3 + \ldots
    & = (2x)^0 + (2x)^1 + (2x)^2 + (2x)^3 + \ldots \\
    & = \frac{1}{1 - 2 x}
\end{align*}
}

\ppart $\seq{1, 0, 1, 0, 1, 0, 1, 0, \dots}$

\solution[\vspace{0.25in}]{
\begin{align*}
1 + x^2 + x^4 + x^6 + \ldots
    & = \frac{1}{1 - x^2}
\end{align*}
}

\ppart $\seq{0, 0, 0, 1, 1, 1, 1, 1, \dots}$

\solution[\vspace{0.25in}]{
\begin{align*}
x^3 + x^4 + x^5 + x^6 + \ldots
    & = x^3 (1 + x + x^2 + x^3 + \ldots)
    & = \frac{x^3}{1 - x}
\end{align*}
}

\ppart $\seq{1, 3, 5, 7, 9, 11, \ldots}$

\solution[\vspace{0.25in}]{
\begin{align*}
1 + x + x^2 + x^3 + \ldots & = \frac{1}{1-x} \\
\frac{d}{dx}\ 1 + x + x^2 + x^3 + \ldots & = \frac{d}{dx}\ \frac{1}{1-x} \\
1 + 2 x + 3 x^2 + 4 x^2 + \ldots & = \frac{1}{(1-x)^2} \\
2 + 4 x + 6 x^2 + 8 x^2 + \ldots & = \frac{2}{(1-x)^2} \\
1 + 3 x + 5 x^2 + 7 x^3 + \ldots & = \frac{2}{(1-x)^2} - \frac{1}{1-x} \\
                             & = \frac{1 + x}{(1-x)^2}
\end{align*}
}


\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem}
Suppose that:
%
\begin{align*}
f(x) & = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + \cdots \\
g(x) & = b_0 + b_1 x + b_2 x^2 + b_3 x^3 + b_4 x^4 + \cdots
\end{align*}
%
What sequences do the following functions generate?

\bparts

\ppart $f(x) + g(x)$

\solution[\vspace{1in}]{
\[
(a_0 + b_0) + (a_1 + b_1) x + (a_2 + b_2) x^2 + (a_3 + b_3) x^3 + \ldots
\]
}

\ppart $f(x) \cdot g(x)$

\solution[\vspace{1in}]{
\[
a_0 b_0 + (a_0 b_1 + a_1 b_0) x + (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 + \ldots
+ \left(\sum_{k=0}^n a_k b_{n-k}\right) x^n + \ldots
\]
}

\ppart $f(x) / (1 - x)$

\solution{This is a special case of the preceding problem part where:
%
\begin{align*}
g(x) & = \frac{1}{1 - x} \\
     & = 1 + x + x^2 + x^3 + x^4 + \cdots
\end{align*}
%
and so $b_0 = b_1 = b_2 = \ldots = 1$.  In this case, we have:
%
\[
f(x) \cdot g(x) = a_0 + (a_0 + a_1) x + (a_0 + a_1 + a_2) x^2 + \ldots
+ \left(\sum_{k=0}^n a_k \right) x^n + \ldots
\]
%
Thus, $f(x) / (1 - x)$ is the generating function for sums of prefixes
of the sequence generated by $f$.}

\eparts
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem}
There is a jar containing $n$ different flavors of candy.  I'd like to
pick out a set of $k$ candies.

\bparts

\ppart In how many different ways can this be done?

\solution[\vspace{1.25in}]{There is a bijection with sequences
containing $k$ zeroes (representing candies) and $n - 1$ ones
(separating the different varieties).  The number of such sequences
is:
%
\[
\binom{n + k - 1}{k}
\]
}

\ppart Now let's approach the same problem using generating functions.
Give a closed-form generating function for the sequence $\seq{s_0,
s_1, s_2, s_3, \ldots}$ where $s_k$ is the number of ways to select
$k$ candies when there is only $n = 1$ flavor available.

\solution[\vspace{1.25in}]{
\[
1 + x + x^2 + x^3 + \ldots = \frac{1}{1-x}
\]
}

\ppart Give a closed-form generating function for the sequence
$\seq{t_0, t_1, t_2, t_3, \ldots}$ where $t_k$ is the number of ways
to select $k$ candies when there are $n = 2$ flavors.

\solution[\vspace{1.25in}]{
\[
(1 + x + x^2 + x^3 + \ldots)^2 = \frac{1}{(1-x)^2}
\]
}

\ppart Give a closed-form generating function for the sequence
$\seq{u_0, u_1, u_2, u_3, \ldots}$ where $u_k$ is the number of ways
to select $k$ candies when there are $n$ flavors.

\solution[\vspace{1.25in}]{
\[
\frac{1}{(1-x)^n}
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{problem}
Consider the following recurrence equation:
%
\[
T_n =
\begin{cases}
1 & n = 0 \\
2 & n = 1 \\
2 T_{n-1} + 3 T_{n-2} & (n \geq 2) \\
\end{cases}
\]
%
Let $f(x)$ be a generating function for the sequence $\seq{T_0, T_1,
T_2, T_3, \ldots}$.

\bparts

\ppart Give a generating function in terms
of $f(x)$ for the sequence:
%
\[
\seq{1, \quad 2, \quad 2 T_1 + 3 T_0, \quad 2 T_2 + 3 T_1, \quad 2 T_3 + 3 T_2, \ldots}
\]

\solution[\vspace{1.5in}]{
We can break this down into a linear combination of three sequences:
%
\[
\begin{array}{ccccccccl}
\langle & 1, & 2, & 0, & 0, & 0, & \ldots & \rangle & = 1 + 2x \\
\langle & 0, & T_0, & T_1, & T_2, & T_3, & \ldots & \rangle & = x f(x) \\
\langle & 0, & 0, & T_0, & T_1, & T_2, & \ldots & \rangle & = x^2 f(x) \\
\end{array}
\]
%
In particular, the sequence we want is very nearly generated by $1 +
2x + 2 x f(x) + 3 x^2 f(x)$.  However, the second term is not quite
correct; we're generating $2 + 2 T_0 = 4$ instead of the correct
value, which is $2$.  We correct this by subtracting $2 x$ from the
generating function, which leaves:
%
\[
1 + 2 x f(x) + 3 x^2 f(x)
\]
}

\ppart Form an equation in $f(x)$ and solve to obtain a closed-form
generating function for $f(x)$.

\solution[\vspace{1in}]{The equation
%
\[
f(x) = 1 + 2 x f(x) + 3 x^2 f(x)
\]
%
equates the left sides of all the equations defining the sequence
$T_0, T_1, T_2, \ldots$ with all the right sides.  Solving for $f(x)$
gives the closed-form generating function:
%
\[
f(x) = \frac{1}{1 - 2x - 3x^2}
\]
}

\ppart Expand the closed form for $f(x)$ using partial fractions.

\solution[\vspace{2.in}]{
We can write:
%
\[
1 - 2x - 3x^2 = (1 + x)(1 - 3x)
\]
%
Thus, there exist constants $A$ and $B$ such that:
%
\[
f(x) = \frac{1}{1 - 2x - 3x^2} = \frac{A}{1+x} + \frac{B}{1-3x}
\]
%
Now substituting $x = 0$ and $x = 1$ gives the system of equations:
%
\begin{align*}
1 & = A + B \\
- \frac{1}{4} & = \frac{A}{2} - \frac{B}{2}
\end{align*}
%
Solving the system, we find that $A = 1/4$ and $B = 3/4$.  Therefore,
we have:
%
\[
f(x) = \frac{1/4}{1+x} + \frac{3/4}{1-3x}
\]
}

\ppart Find a closed-form expression for $T_n$ from the partial
fractions expansion.

\solution{Using the formula for the sum of an infinite geometric
series gives:
%
\begin{align*}
f(x)
    & = \frac{1}{4} \left(1 - x + x^2 - x^3 + x^4 - \ldots\right)
        + \frac{3}{4} \left(1 + 3 x + 3^2 x^2 + 3^3 x^3 + 3^4 x^4 + \ldots\right)
\end{align*}
%
Thus, the coefficient of $x^n$ is:
%
\[
T_n = \frac{1}{4} \cdot (-1)^n + \frac{3}{4} \cdot 3^n
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
