\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Rosen \S6.4 through Example 15, \S6.1, then the
remainder of \S6.4}

\begin{document}
\problemset{10}

\begin{problem}
Rosen \S6.4, Exercise 14.  (Describe a closed form for the generating
function and indicate which coefficient is the answer to the problem.  You
need \emph{not} calculate the numerical value of this coefficient.)

\solution{
GF for giving action figures to one child is $1+x +x^2+ x^3$, so the GF
for giving figures to 5 children is
\[
G(x) \eqdef \paren{1+x +x^2+ x^3}^5.
\]
The coefficient of $x^{12}$ in the series for $G(x)$ is the number of ways
to give 12 figures to the children.

Another way to write the generating function is
\[
G(x) = \paren{\frac{1-x^4}{1-x}}^5.
\]
Using the Binomial Theorem to expand the numerator yields
\begin{equation}\label{nh}
G(x) = \frac{1}{(1-x)^5} - \frac{5x^4}{(1-x)^5} + \frac{10x^8}{(1-x)^5}
    - \frac{10x^{12}}{(1-x)^5} + \frac{\text{higher-order terms\dots}}{(1-x)^5}.
\end{equation}
The coefficient of $x^{12}$ in the series for $G(x)$ is the sum of the
coefficients of $x^{12}$ in the different series for each of the first
four summands in~\eqref{nh}.  Since the coefficient of $x^n$ in the series
for $1/(1-x)^5$ is $\binom{n+4}{4}$, these four coefficients of $x^{12}$
sum to
\[
\binom{12+4}{4}-5\binom{8+4}{4} + 10\binom{4+4}{4} -10 \binom{0+4}{4} =
1820 -2475 + 700 -10 = 35.
\]
}

\end{problem}


\begin{problem}
Rosen \S6.4, Exercise 29(c).  (Describe a closed form for the generating
function and indicate which coefficient is the answer to the problem.  You
need \emph{not} calculate the numerical value of this coefficient.)

\solution{
GF for number of ways to make $\$n$ change using one or more $\$d$ bills
is
\[
x^d+x^{2d}+x^{3d}+\cdots
\]
So the GF for making $\$n$ change using one or more bills of denominations
$\$5, \$10, \$20, \$50$ is
\[
(x^5+x^{10}+x^{15}+\cdots)(x^{10}+x^{20}+x^{30}+\cdots)(x^{20}+x^{40}+x^{60}+\cdots)(x^{50}+x^{100}+x^{150}+\cdots),
\]
and the coefficient of $x^{100}$ is the desired quantity.

It's easy to figure out the very small number of ways to make change for
\$100 directly, but let's see how we could reason using the above product.

The lowest degree term in this product is
$x^{5}x^{10}x^{20}x^{50}=x^{85}$.  Selecting a term of degree $\geq 40$
from the third series in the product will yield a term $x^n$ for $n \ge
105$, so only the first, $x^{20}$, term can contribute to a term of degree
100 in the product.  Likewise only the first, $x^{50}$, term in the fourth
series can contribute to a term of degree 100 in the product.  Similarly,
for the second series, only the first two terms, $x^{10}$ and $x^{20}$,
can contribute.

So there are only two possible ways to select terms from the last three
series to get a term of degree 100 in the product.  Since the terms chosen
from the last three series determine the which term, if any, from the
first series must be chosen to yield $x^{100}$ in the product, we conclude
that there are at most two ways to obtain $x^{100}$ as a term in the
product.  It's easy to see that there are in fact two ways that work:
$x^{20}x^{10}x^{20}x^{50}$ and $x^{10}x^{20}x^{20}x^{50}$.  So the
coefficient of $x^{100}$ is 2, which means there are exactly two ways to
make change for \$100 according to these rules.

We could also note that
\[
x^d+x^{2d}+x^{3d}+x^{4d}\cdots = x^d(1+x^d+(x^d)^2+(x^d)^3\cdots)=
\frac{x^d}{1-x^d},
\]
so
\begin{equation}\label{x5}
\frac{x^5}{1-x^5} \frac{x^{10}}{1-x^{10}} \frac{x^{20}}{1-x^{20}} \frac{x^{50}}{1-x^{50}}
=  \frac{x^{85}}{(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})}
\end{equation}
is a closed form for the generating function.  But this closed form does
not appear to lead directly to a solution.}

\iffalse
\footnote{
Letting $y=x^5$, we can express the righthand side of~\eqref{x5} as
\begin{align}
\lefteqn{\frac{y^{17}}{(1-y)(1-y^2)(1-y^4)(1-y^{10})}}&\\
 =& \frac{y^{17}}{(1-y)(1-y)(1+y)(1-y^2)(1+y^2)(1-y^5)(1+y^5)}\\
 =& \frac{y^{17}}{(1-y)(1-y)(1+y)(1-y)(1+y)(1+y^2)(1-y^5)(1+y^5)}\\
 =& \frac{y^{17}}{(1-y)^3(1+y)^2(1+y^2)(1-y^5)(1+y^5)}.
\end{align}

Does this lead anywhere?}
\fi


\end{problem}


\begin{problem}
\bparts
\ppart Rosen \S6.1, Exercise 34(a),(b).

\solution{
Call a ternary string with at least two consecutive matching digits a
\emph{good} string.  Let $a_n$ be the number of good strings of length
$n$.  Call the other $3^n-a_n$ strings of length $n$ the \emph{bad}
strings.

Now for $n\ge 2$, a good string of length $n$ consists of (1) a good
string of length $n-1$ followed by any digit, or else (2) a bad string of
length $n-1$ followed by a digit that matches the last symbol of the bad
string.  (Note that there is such a last symbol because $n-1 \ge 1$.)
There are $3a_{n-1}$ strings of type (1) and $3^{n-1}-a_{n-1}$ strings of type
(2), and these two types of strings are disjoint.  So
\[
a_n = 3a_{n-1}+3^{n-1}-a_{n-1} = 2a_{n-1} + 3^{n-1}.
\]
Also, a good string must have at least two digits, so $a_0=a_1=0$.
}

\ppart Derive a closed form for the generating function of the sequence
defined by this recurrence.

\solution{For $n\ge 1$, the coefficient of $x^n$ in the
series expansion of 
$2xG(x)$ is $2a_{n-1}$, and the coefficient of $x^n$ in
\[
x+3x^2+3^2x^3+\cdots+3^{n-1}x^n+\cdots =
x(1+3x+(3x)^2+\cdots+(3x)^{n-1}+\cdots) = \frac{x}{1-3x}
\]
is obviously $3^{n-1}$.  So in the series for $G(x) - 2xG(x) - x/(1-3x)$,
all the coefficients of $x^n$ for $n\ge 2$ are zero.  This leaves
\[
G(x) - 2xG(x) - \frac{x}{1-3x} = (a_0+a_1x)-2a_0x - x = -x.
\]
So
\[
G(x) = \frac{-x}{1-2x} + \frac{x}{(1-3x)(1-2x)}
\]
}

\ppart Find real numbers $A$ and $B$ such that this generating
function equals $A/(1-2x) + B/(1-3x)$.

\solution{Assuming
\[
\frac{-x}{1-2x} + \frac{x}{(1-3x)(1-2x)} = \frac{A}{1-2x} +
\frac{B}{1-3x},
\]
we have 
\[
-x(1-3x) + x = A(1-3x) + B(1-2x).
\]
So letting $x=1/2$, we conclude that $3/4=A(-1/2)$ so $A=-3/2$.  Letting
$x=1/3$, we conclude that $1/3=B(1/3)$, so $B=1$.
}

\ppart Use the previous results to write a closed form for the $n$th term
in the sequence when $n \ge 2$.

\solution{
The coefficient of $x^n$ in the series for $1/(1-3x)$ is $3^n$ and for
$1/(1-2x)$ is $2^n$.  So
\[
a_n = A2^n +B3^n = 3^n - 32^{n-1} = 3(3^{n-1} - 2^{n-1}).
\]
}

\eparts

\end{problem}

\end{document}




