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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document}
\inclassproblems{13, Wed.}


\begin{problem}  \emph{Carried over from Monday, slightly revised.}

\bparts 

\ppart Let $S(x) \eqdef \sum_{k=1}^{\infty} k^2x^k$.  Verify that
\begin{equation}\label{Sx}
S(x) =\frac{x(1+x)}{(1-x)^3}.
\end{equation}

\hint Consider $\frac{d}{dx} \paren{1 + x + x^2 + x^3 + x^4 + \cdots}$.

\solution{
\begin{eqnarray*}
\frac{d}{dx} \paren{1 + x + x^2 + x^3 + x^4 + \cdots}
	& = & \frac{d}{dx}  \paren{\frac{1}{1-x}} \\
1 + 2x + 3x^2 + 4x^3 + \cdots & = & \frac{1}{(1-x)^2} \\
x + 2x^2 + 3x^3 + 4x^4 + \cdots & = & \frac{x}{(1-x)^2} \\
\frac{d}{dx} \paren{x + 2x^2 + 3x^3 + 4x^4 + \cdots} & = & \frac{d}{dx}
	\paren{\frac{x}{(1-x)^2}} \\
1 + 2^2x + 3^2x^2 + 4^2x^3 + \cdots & = &  x \cdot \frac{2}{(1-x)^3} +
	\frac{1}{(1-x)^2} \\
       &=&  \frac{2x}{(1-x)^3} +
	\frac{1-x}{(1-x)^3} \\
      &=& \frac{1+x}{(1-x)^3}\\
x + 2^2x^2 + 3^2x^3 + 4^2x^4 + \cdots & = &  \frac{x(1+x)}{(1-x)^3}
\end{eqnarray*}
So
\[
S(x) = \frac{x(1+x)}{(1-x)^3}.
\]
}

\ppart Explain why $S(x)/(1-x)$ is the generating function for the sum 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{
\[
\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} x^n
\]
as a special case of the convolution formula for the product of series.
So in particular for $S(x)$ with $a_k = k^2$, 
\[
\frac{S(x)}{1-x} = S(x)\paren{\sum_{n=0}^{\infty} x^n}, 
\] 
so the coefficient in of $x^n$ is the sum of the first $n$ squares.
}

\iffalse

\ppart Explain why $1/(1-x)^m$ is the generating function for the number
of sets of $n$ elements, chosen \emph{with repetition} from a set of $m$
elements.  Use this observation to write a closed form for the coefficient
of $x^n$ in the series for this generating function.

\solution{
There can be any number of repetitions of the first element, so the
generating function for the number of ways to pick the first element is
$1+x+x^2+\cdots = 1/(1-x)$.  The generating function for the number of
ways to pick all $m$ elements is the product of these individual
generating functions.  

The coefficient of $x^n$ in this product is the number of sets of $n$
elements chosen with repetition from the set of $m$ elements.  But we know
this is $\binom{m+n-1}{n}$.  That is,
\[
\frac{1}{(1-x)^k}= \sum_{n=0}^{\infty} \binom{m+n-1}{n} x^n.
\]}
\fi


\ppart  Use the previous parts to prove that
\[
\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.
\]

\solution{We have from equation~\eqref{Sx} that
\begin{equation}\label{S4}
\frac{S(x)}{1-x} = \frac{x(1+x)}{(1-x)^4}.
\end{equation}


But we know $1/(1-x)^4$ is the generating function for the number of sets
of $n$ elements, chosen \emph{with repetition} from a set of 4 elements.
So the coefficient of $x^n$ in its series expansion 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)}{(1-x)^4}= \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}.
\]
}

\eparts

\end{problem}

\instatements{\newpage}
\begin{problem}
Define the function $f:\naturals \to \naturals$ recursively by the rules
\begin{align*}
f(0) & = 1,\\
f(1) & = 6,\\
f(n) & = 2f(n-1)+3f(n-2)+4 & \text{ for }n\geq 2.
\end{align*}

\bparts

\ppart Find a closed form for the generating function
\[
G(x) \eqdef f(0) + f(1)x + f(2)x^2 + \cdots + f(n)x^n + \cdots.
\]

\solution{
\[\begin{array}{rclcrcrccr}
         G(x) & = & f(0) & + & f(1)x  & + & f(2)x^2   & + \cdots & + & f(n)x^n  + \cdots\\
       2xG(x) & = &      &   & 2f(0)x & + & 2f(1)x^2  & + \cdots & + & 2f(n-1)x^n + \cdots\\
     3x^2G(x) & = &      &   &        &   & 3f(0)x^2  & + \cdots & + & 3f(n-2)x^n + \cdots\\
\dfrac{4}{1-x} & = & 4    & + & 4x     &   &  4x^2     & + \cdots & + &      4x^n + \cdots
\end{array}\]

So
\begin{align}
G(x) - 2x G(x) - 3x^2 G(x) - \dfrac{4}{1-x} & = f(0)-4 + (f(1)-2f(0)-4)x \notag\\
             & =  1 - 4 + (6 - 2 - 4)x = -3.\notag\\
G(x)(1-2x-3x^2) & = \dfrac{4}{1-x} - 3.\notag\\
G(x) & = \paren{\dfrac{4}{1-x} - 3}/(1-2x-3x^2).\label{G0}
\end{align}
}

\ppart Find a closed form for $f(n)$.  \hint Find numbers $a,b,c,d,e,g$ such that
\[
G(x) = \frac{a}{1+dx} + \frac{b}{1+ex} + \frac{c}{1+gx}.
\]


\solution{
\begin{align}
G(x) & = \paren{\dfrac{4}{1-x} - 3}/(1-2x-3x^2) & \text{by~\eqref{G0}}\notag\\
     & = \paren{\dfrac{4}{1-x} - 3}/((1+x)(1-3x))\notag\\
     & =  \dfrac{4}{(1-x)(1+x)(1-3x)} - \frac{3}{(1+x)(1-3x)}\notag\\
     & =  \dfrac{4- 3(1-x)}{(1-x)(1+x)(1-3x)}.\label{G1}
\end{align}

From~\eqref{G1} and the method of partial fractions, we conclude that
$d,e,g = -1,1,-3$, respectively.  So we want $a,b,c$ such that
\begin{align}
\dfrac{4- 3(1-x)}{(1-x)(1+x)(1-3x)}
           & = \dfrac{a}{1-x} + \dfrac{b}{1+x} + \dfrac{c}{1-3x}\label{G2}\\
4 - 3(1-x) & = a(1+x)(1-3x) + b(1-x)(1-3x) + c(1-x)(1+x).\label{abc}
\end{align}
Setting $x=1$ in~\eqref{abc}, we conclude that $4 = a\cdot 2 \cdot (-2)$,
so
\[
a=-1.
\]
Setting $x=-1$ in~\eqref{abc}, we conclude that $4-3\cdot 2 = b\cdot 2 \cdot 4$, so
\[
b=-\frac{1}{4}.
\]
Setting $x=1/3$ in~\eqref{abc}, we conclude that $4-3(2/3) = c\cdot (2/3)(4/3)$, so
\[
c=\frac{9}{4}.
\]
So from~\eqref{G1} and~\eqref{G2}, we have
\[
G(x) = \frac{-1}{1-x} + \frac{1/4}{1+x} + \frac{9/4}{1-3x}.
\]

Now the coefficient of $x^n$ in $a/(1-x)$ is $a$, the coefficient in
$b/(1+x)$ is $(-1)^nb$ and the coefficient in $c/(1-3x)$ is $3^n c$.  For
$n\geq 2$, the coefficient in $G(x)$ is the sum of these coefficients.  So
\[
f(n) = -1 + \frac{(-1)^n}{4} + \frac{9}{4}3^n = \frac{3^{n+2} + (-1)^n}{4} - 1.
\]
}



\eparts
\end{problem}


\iffalse

\begin{problem}  (Fall97 Q1)

A society of devil-worshipers meets every week in a catacomb to
initiate new members.  Members who have been in the society for two or
more weeks initiate four new members each and members who have been in
the society for only one week initiate one new member each.  On week 0
there is one devil-worshiper.  There are two devil-worshipers on week
1.

Write a recurrence relation for the number of members $D(n)$ in the
society on the $n$th week.

\solution{
The number of devil-worshipers on week $n$ is the number of
devil-worshipers that were around 2 weeks before plus their new
recruits, so $5D(n-2)$, and the number of devil worshipers that were
around only last week, $D(n-2) - D(n-1)$, plus their new recruits.  So
the total number of devil-worshipers on the $n$th week is

$D(n) = 5D(n-2) + 2(D(n-1)-D(n-2)) = 3D(n-2) + 2D(n-1)$

The initial conditions are

$D(0) = 1$

$D(1) = 2$
}
\end{problem}

\fi

\end{document}
