\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\newcommand{\corresp}{\ \longleftrightarrow\ }

\begin{document} 
\inclassproblems{11, Fri.}                    % !! start the paper

%revised from S04 cp13w

\begin{problem}

\bparts 

\ppart\label{tay}  Verify that
\[
\frac{1}{\paren{1-x}^k} = \sum_{n=0}^\infty \binom{n+k-1}{n}x^n.
\]
\hint  Use the fact that if $A(x) = \sum_{n=0}^\infty a_nx^n$, then
\[
a_n = \frac{A^{(n)}(0)}{n!},
\]
where $A^{(n)}$ is the $n$th derivative of $A$.

\solution{
\begin{align*}
\frac{d\paren{1-x}^{-k}}{dx} & = k\paren{1-x}^{-(k+1)}.\\
\frac{d^2\paren{1-x}^{-k}}{(dx)^2} & = \frac{d\, k\paren{1-x}^{-(k+1)}}{dx} = (k+1)k\paren{1-x}^{-(k+2)}\\
\frac{d^3\paren{1-x}^{-k}}{(dx)^3} & = \frac{d\,
  (k+1)k\paren{1-x}^{-(k+2)}}{dx} = (k+2)(k+1)k\paren{1-x}^{-(k+3)}\\
& \vdots\\
\frac{d^n \paren{1-x}^{-k}}{(dx)^n} & = (k+n-1)\cdots(k+2)(k+1)k\paren{1-x}^{-(k+n)}.
\end{align*}

Now suppose $(1-x)^{-k} = A(x)$.  Then by the hint, we have
\begin{align*}
a_n & = \frac{A^{(n)}(0)}{n!}\\
    & = \frac{(k+n-1)\cdots(k+2)(k+1)k\paren{1-0}^{-(k+n)}}{n!}\\
    & = \frac{\dfrac{(n+k-1)!}{(k-1)!}\cdot 1}{n!}\\
    & = \frac{(n+k-1)!}{(k-1)!n!}\\
    & = \binom{n+k+1}{n}
\end{align*}
}

\ppart Let $S(x) \eqdef \sum_{k=1}^{\infty} k^2x^k$.  Explain why
$S(x)/(1-x)$ is the generating function for the sums of squares.  That is,
the coefficient of $x^n$ in the series for $S(x)/(1-x)$ is $\sum_{k=1}^n
k^2$.  

\solution{
\begin{equation}\label{ss}
\paren{\sum_{n=0}^{\infty} a_n x^n}\paren{\sum_{n=0}^{\infty} x^n}
= \sum_{n=0}^{\infty} \paren{\sum_{k=0}^{n} a_k\cdot 1} x^n =
\sum_{n=0}^{\infty} \paren{\sum_{k=0}^{n} a_k} x^n
\end{equation}
by the convolution formula for the product of series.  For $S(x)$, the
coefficient of $x^k$ is $a_k = k^2$, and
\[
S(x)/(1-x) = S(x)\paren{\sum_{n=0}^{\infty} x^n},
\]
so~\eqref{ss} implies that the coefficient of $x^n$ in $S(x)/(1-x)$ is the
sum of the first $n$ squares.}

\ppart  Use the fact that
\[
S(x) =\frac{x(1+x)}{(1-x)^3},
\]
and the previous part to prove that
\[
\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.
\]

\solution{We have
\begin{equation}\label{S4}
\frac{S(x)}{1-x} = \frac{\dfrac{x(1+x)}{(1-x)^3}}{1-x} = \frac{x+x^2}{(1-x)^4}.
\end{equation}
From part~\eqref{tay}, the coefficient of $x^n$ in the series expansion of
$1/(1-x)^4$ is
\[
\binom{n+3}{n}= \frac{(n+1)(n+2)(n+3)}{3!}.
\]
But by~\eqref{S4},
\[
\frac{S(x)}{1-x} = \frac{x}{(1-x)^4} + \frac{x^2}{(1-x)^4},
\]
so the coefficient of $x^n$ is the sum of the $(n-1)$st and $(n-2)$nd
coefficients of $(1-x)^4$, namely,
\[
\frac{n(n+1)(n+2)}{3!}+\frac{(n-1)n(n+1)}{3!}= \frac{n(n+1)(2n+1)}{6}.
\]
}

\ppart (Optional)  How about a formula for the sum of cubes?

\solution{TBA}

\eparts

\end{problem}

\instatements{\newpage}
\begin{problem}
We are interested in generating functions for the number of different ways
to compose a bag of $n$ donuts subject to various restrictions.  For each
of the restrictions in (a)-(e) below, find a closed form for the
corresponding generating function.
                                                                                
\bparts
                                                                                
\ppart All the donuts are chocolate and there are at least 3.
                                                                                
\solution{
\[
\frac{x^3}{1-x}
\]
}
                                                                                
\ppart All the donuts are glazed and there are at most 2.
                                                                                
\solution{
\[
1+x+x^2
\]
}
                                                                                
\ppart All the donuts are coconut and there are exactly 2 or there are none.
                                                                                
\solution{
\[
1+x^2
\]
}

\ppart All the donuts are plain and their number is a multiple of 4.
                                                                                
\solution{\[
\frac{1}{1-x^4}=\frac{1}{(1-x)(1+x)(1+x^2)}
\]}
                                                                                
\ppart The donuts must be chocolate, glazed, coconut, or plain and:
                                                                                
\begin{itemize}
\item there must be at least 3 chocolate donuts, and
\item there must be at most 2 glazed, and
\item there must be exactly 0 or 2 coconut, and
\item there must be a multiple of 4 plain.
\end{itemize}
                                                                                
\solution{
\begin{align*}
\frac{x^3}{1-x}(1+x+x^2)(1+x^2) \frac{1}{1-x^4}
  &  = \frac{x^3(1+x+x^2)(1+x^2)}%
            {(1-x)^2(1+x)(1+x^2)}\\
  & =  \paren{x^3+x^4+x^5}\frac{1}{(1-x)^2(1+x)}
\end{align*}
}
                                                                                
\ppart Find a closed form for the number of ways to select $n$ donuts
subject to the constraints of the previous part.

\solution{
\[
\frac{1}{(1-x)^2(1+x)} = \frac{1/2}{(1-x)^2} + \frac{1/4}{1-x} +
\frac{1/4}{1+x}
\]
so the $n$th coefficient in its generating function is
\[
\frac{n+1}{2} + \frac{1}{4} +\frac{(-1)^n}{4} = \frac{2n+ 3 + (-1)^n}{4}
\]

The number ways to select $n$ donuts is the sum of the $(n-3)$rd,
$(n-4)$th, and $(n-5)$th of these coefficients, namely
\[
\frac{2(n-3) + 2(n-4) +2(n-5)+ 9 +(-1)^{n-3} + (-1)^{n-4} + (-1)^{n-5}}{4}
= \frac{6n - 15 + (-1)^{n-1}}{4}
\]
}
\eparts

                                                                                
\end{problem}



\section*{Appendix}

\subsection*{Products of Series}
Let
\begin{align*}
A(x) & = \sum_{n=0}^{\infty} a_n x^n, &
B(x) & = \sum_{n=0}^{\infty} b_n x^n, &
C(x) & = A(x) \cdot B(x) = \sum_{n=0}^{\infty} c_n x^n.
\end{align*}
Then
\[
c_n = a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2} + \cdots + a_n b_0.
\]

\end{document}
