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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{16}{April 8, 2005}

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

\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{.5in}]{
\[
2 + 3x + 5x^2
\]
}

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

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

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

\solution[\vspace{0.5in}]{
\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.5in}]{
\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.5in}]{
\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.5in}]{
\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}
Find a closed-form generating function for the sequence
%
\[
(t_0, t_1, t_2, \ldots)
\]
%
where $t_n$ is the number of different ways to compose a bag of $n$
donuts subject to the following restrictions.
                                                                                
\bparts
                                                                                
\ppart All the donuts are chocolate and there are at least 3.
                                                                                
\solution[\vspace{1in}]{
\[
\frac{x^3}{1-x}
\]
}
                                                                                
\ppart All the donuts are glazed and there are at most 4.
                                                                                
\solution[\vspace{1in}]{
\[
\frac{1-x^5}{1-x}
\]
}
                                                                                
\ppart All the donuts are coconut and there are exactly 2.
                                                                                
\solution[\vspace{1in}]{
\[
x^2
\]
}

\ppart All the donuts are plain and the number is a multiple of 4.
                                                                                
\solution[\vspace{1in}]{\[
\frac{1}{1-x^4}
\]}
                                                                                
\ppart The donuts must be chocolate, glazed, coconut, or plan and:
                                                                                
\begin{itemize}
\item There must be at least 3 are chocolate donuts.
\item There must be at most 4 glazed.
\item There must be exactly 2 coconut.
\item There must be a multiple of 4 plain.
\end{itemize}
                                                                                
\solution[\vspace{1in}]{
\[
\frac{x^3}{1-x} \frac{1-x^5}{1-x}x^2 \frac{1}{1-x^4}
    = \frac{x^5(1+x^2+x^3+x^4)}{(1-x)(1-x^4)}
\]
}
                                                                                
\eparts
                                                                                
\end{problem}

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

\newpage

\begin{problem}[20 points]
A previous problem set introduced us to the Catalan numbers:
$C_0,C_1,C_2,\dots$, where the $n$-th of them equals the number of
balanced strings that can be built with $2n$ paretheses. Here is a
list of the first several of them:
\[
\begin{array}{c|ccccccccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline
C_n & 1 & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & 4862 & 16796 & 58786 & 208012
\end{array}
\]
Then, in lecture we were all amazed to see that the decimal expansion
of the irrational number $500000 - 1000 \sqrt{249999}$ 
\[
1.000001000002000005000014000042000132000429001430004862016796058786208012\dots
\]
``encodes'' these numbers! Now, there are many reasons why one may
want to turn to religion, but this revelation is probably not a good
one. Let's explain why. 

\bparts

\ppart Let $p_n$ be the number of balanced strings containing $n$
\texttt{(}'s.  Explain why the following recurrence holds:
\begin{align*}
p_0	& = 	1, & \text{(the empty string)}\\
p_n	& = 	\sum_{k=1}^{n} p_{k-1} \cdot p_{n-k},  & \text{for }n \geq 1.
\end{align*}

\solution[\vspace{1in}]{Note that every nonempty balanced string consists of a sequence
of one or more balanced strings.  The first balanced string in the
sequence must begin with a \texttt{(} and end with a ``matching''
\texttt{)}.  That is, any balanced string, $r_n$, with $n \geq 1$
\texttt{(}'s consists of a balanced string, $s_{k-1}$, enclosed in
brackets and containing $k-1$ \texttt{(}'s, followed by a balanced string,
$t_{n-k}$, with $n-k$ \texttt{(}'s:
\[
r_n = \texttt{(}s_{k-1} \texttt{)} \text{ followed by } t_{n-k}
\]
where $1 \leq k \leq n$.  This observation leads directly to the
recurrence.}

\ppart Now consider the generating function for the number of balanced strings:
\[
P(x)  =  p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots.
\]
Prove that
\[
P(x)  =  x P(x)^2 + 1.
\]

\solution[\vspace{1in}]{We can verify this equation using the recurrence relation.

\begin{eqnarray*}
x P(x)^2 + 1
	& = &	x (p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots)^2 + 1 \\
	& = &	x (p_0^2 + (p_0 p_1 + p_1 p_ 0) x + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^2 + \cdots) + 1 \\
	& = &	1 + p_0^2 x + (p_0 p_1 + p_1 p_ 0) x^2 + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^3 + \cdots \\
	& = &	1 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots \\
	& = &	P(x)
\end{eqnarray*}
}

\ppart Find a closed-form expression for the generating function $P(x)$.

\solution[\vspace{1in}]{
Given that $P(x) = x P(x)^2 + 1$, the quadratic formula implies that
\[
P(x) =  \frac{1 \pm \sqrt{1 - 4 x}}{2x}.
\]

If $x$ is small, then $P(x)$ should be about $p_0 = 1$.  Therefore,
the correct choice of sign is

\begin{eqnarray*}
P(x)	& = & \frac{1 - \sqrt{1 - 4 x}}{2x}.
\end{eqnarray*}
}

\ppart Show that $P(1/1000000) = 500000 - 1000 \sqrt{249999}$.

\solution[\vspace{1in}]{
\begin{eqnarray*}
P(1/1000000)
	& = &	\frac{1 - \sqrt{1 - 4/1000000}}{2/1000000} \\
	& = &	500000 - 500000 \sqrt{\frac{249999}{250000}} \\
	& = &	500000 - 1000 \sqrt{249999}
\end{eqnarray*}
}

\ppart Explain why the digits of this irrational number encode these
successive numbers of balanced strings.

\solution[\vspace{1in}]{Suppose that we symbolically carry out the
substitution done in the preceding problem part.

\begin{eqnarray*}
P(x)		& = &	p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \cdots \\
P(10^{-6})	& = &	p_0 + p_1 10^{-6} + p_2 10^{-12}
				+ p_3 10^{-18} + \cdots
\end{eqnarray*}

Thus, $p_0$ appears in the units position, $p_1$ appears in the
millionths position, $p_2$ appears in the trillionths position, and so
forth.
}

\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}
