\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 8    *
%**************


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

\begin{problemparts}

\problempart $< 0, 0, 1, 1, 1, 1, 1, \ldots >$

\solution{
\begin{eqnarray*}
x^2 + x^3 + x^4 + x^5 + x^6 + \ldots
	& = &	x^2 \cdot (1 + x + x^2 + x^3 + x^4 + \ldots) \\
	& = &	\frac{x^2}{1-x}
\end{eqnarray*}
}

\problempart $< 0, 2, 4, 6, 8, 10, \ldots >$

\solution{
\begin{eqnarray*}
0 + 2 x +  4 x^2 + 6 x^3 + 8 x^4 + \ldots
	& = &	2x \cdot (0 + 1 + 2 x + 3 x^2 + 4 x^3 \ldots) \\
	& = &   2x \cdot \frac{d}{dx} \ (1 + x + x^2 + x^3 + x^4 + \ldots) \\
	& = & 	2x \cdot \frac{d}{dx} \ \left(\frac{1}{1-x} \right)\\
	& = &	\frac{2x}{(1-x)^2}
\end{eqnarray*}
}

\problempart $< 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
1 + x^3 + x^6 + x^{9} + x^{12} + \dots	& = &	\frac{1}{1 - x^3}
\end{eqnarray*}
}

\problempart $< 2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \ldots  >$

\solution{
\begin{eqnarray*}
\lefteqn{2^0 + 2^1 x + 2^2 x^2 + 2^3 x^3 + 2^4 x^4 + \ldots}
\hspace{1in} \\
	& = &	(2x)^0 + (2x)^1 + (2x)^2 + (2x)^3 + (2x)^4 + \ldots \\
	& = &	\frac{1}{1 - 2x}
\end{eqnarray*}
}

\problempart $< -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{-1 + x^2 - x^3 + x^5 - x^6 + x^8 - \ldots}
\hspace{1in} \\
	& = & (x^2 + x^5 + x^8 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
	& = & x^2 (1 + x^3 + x^6 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
	& = & (x^2 - 1) \cdot (1 + x^3 + x^6 + \ldots) \\
	& = & \frac{x^2 - 1}{1 - x^3}
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} Suppose that $f(x)$ is the generating
function for the sequence $a_0, a_1, a_2, \ldots$.  Find generating
functions for the following sequences.

\begin{problemparts}
\problempart $< 0, 0, 0, a_0, a_1, a_2, \ldots >$

\solution{
\begin{eqnarray*}
a_0 x^3 + a_1 x^4 + a_2 x^5 + \ldots
	& = &	x^3 \cdot (a_0 + a_1 x + a_2 x^2 + \ldots) \\
	& = &	x^3 f(x)
\end{eqnarray*}
}

\problempart $< a_0, a_1 + 1, a_2 + 2, a_3 + 3, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + (a_1 + 1) x + (a_2 + 2) x^2 + (a_3 + 3) x^3 + \ldots}
\hspace{1in} \\
	& = &	(a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)
		+ (0 + 1 x + 2 x^2 + 3 x^3 + \ldots) \\
	& = &	f(x) + \frac{x}{(1 - x)^2}
\end{eqnarray*}
}

\problempart $< a_0, 0, a_1, 0, a_2, 0, a_3, 0, \ldots >$

\solution{
\begin{eqnarray*}
a_0 + a_1 x^2 + a_2 x^4 + a_3 x^6 + \ldots
	& = &	f(x^2)
\end{eqnarray*}
}

\problempart $< a_0, -a_1, a_2, -a_3, a_4, \ldots >$

\solution{
\begin{eqnarray*}
a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 - \ldots
	& = &	f(-x)
\end{eqnarray*}
}

\problempart $< a_0, 0, a_2, 0, a_4, 0, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + a_2 x^2 + a_4 x^4 + a^6 x^6 + \ldots}
\hspace{1in} \\
	& = &	\frac{1}{2} (
		(a_0 - a_1 x + a_2 x^2 - a_3 x^3 + \ldots) \\
	&   & \mbox{} + (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)) \\
	& = &	\frac{1}{2}(f(-x) + f(x))
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} For each of the following generating
functions, find a closed-form expression for the coefficient of $x^n$.

\begin{problemparts}
\problempart
\[
\frac{5 - 11x}{4x^2 - 5x + 1}
\]

\solution{We will use the partial fractions method.  The roots of the
denominator are $x = 1$ and $x = \frac{1}{4}$.  Therefore, we look for
a partial fractions expansion of the form

\begin{eqnarray*}
\frac{5 - 11x}{(1-x)(1-4x)}	& = &	\frac{A}{1 - x} + \frac{B}{1 - 4x}.
\end{eqnarray*}

Multiplying by the denominators gives:

\begin{eqnarray*}
5 - 11x	& = &	A (1 - 4x) + B (1 - x)
\end{eqnarray*}

Setting $x = 1$ gives $A = 2$, and setting $x = \frac{1}{4}$ gives $B
= 3$.  Therefore, we can rewrite the generation function as

\begin{eqnarray*}
\frac{5 - 11x}{4x^2 - 5x + 1}
	& = &	\frac{2}{1 - x} + \frac{3}{1 - 4x} \\
	& = &	2 (1 + x + x^2 + x^3 + \ldots) + \\
	&   &	3 (1 + 4x + 4^2 x^2 + 4^3 x^3 + \ldots)
\end{eqnarray*}

Therefore, the coefficient of $x^n$ is $3 \cdot 4^n + 2$.
}

\problempart
\[
\frac{2x}{(1-x)^3}
\]

\solution{ The partial fractions expansion of the above expression is
itself.  Therefore, we take successive derivatives.  One helpful
observation is that the sequence generated by this function is
equivalent to doubling and shifting the sequence generated by $f(x) =
1/(1-x)^3$.  Therefore, we only need to find the sequence
generated by $f(x)$, which involves easier derivatives.

\begin{eqnarray*}
f(x)	& = &	\frac{1}{(1-x)^3} \\
f'(x)	& = &	\frac{3}{(1-x)^4} \\
f''(x)	& = &	\frac{3 \cdot 4}{(1-x)^5} \\
f'''(x)	& = &	\frac{3 \cdot 4 \cdot 5}{(1-x)^6} \\
\\
\ldots & \ldots & \ldots \\
\\
f^{(n)}(x)	& = &	\frac{(n+2)!}{2} \cdot \frac{1}{(1-x)^{n+3}}
\end{eqnarray*}

The coefficient of $x^n$ in $f(x)$ is equal to $f^{(n)}(0)/n!$, which
is $(n+1)(n+2)/2$.  Therefore, the coefficient of $x^n$ in the
original generating function is $n(n+1)$.
}

\end{problemparts}

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

\problem {\bf (15 points)} In this problem, we use generating functions
to compute the number of $m$ bit strings with a multiple of three 1's.
For example, if $m = 4$, then there are five such strings:

\[
\begin{array}{ccccc}
0000 &\quad&	1110	&\quad&	1101 \\
1011 &\quad&	0111		\\
\end{array}
\]

\begin{problemparts}
\problempart Use summation notation and binomial coefficients to
describe the number of $m$-bit strings with a multiple of three 1's.

\solution{
\[
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
\]
}
\end{problemparts}

The following fact will be useful in evaluating this sum.  Let $z_1 =
1$, $z_2 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i$, and $z_3 =
-\frac{1}{2} - \frac{\sqrt{3}}{2} i$.  The expression
$\frac{1}{3}(z_1^k + z_2^k + z_3^k)$ is then equal to 1 if $k$ is a
multiple of 3 and is equal to 0 otherwise.

\begin{problemparts}
\problempart Left $f(x)$ be a generating function for the series $<
a_0, a_1, a_2, \ldots >$.  Give a closed-form expression for the
following sum.

\[
\sum_{i=0}^{\infty} a_{3i}
\]

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\infty} a_{3i}
	& = &	\sum_{k=0}^{\infty} a_k \cdot \frac{z_1^k+z_2^k+z_3^k}{3}\\
	& = &	\frac{1}{3} \cdot \left(
		\sum_{k=0}^{\infty} a_k z_1^k +
		\sum_{k=0}^{\infty} a_k z_2^k +
		\sum_{k=0}^{\infty} a_k z_3^k
		\right) \\
	& = &	\frac{f(z_1) + f(z_2) + f(z_3)}{3}
\end{eqnarray*}
}

\problempart Recall that $f(x) = (1 + x)^m$ is the generating function
for binomial coefficients; that is, for $0 \leq k \leq m$, the
coefficient of $x^k$ is $\binom{m}{k}$, and for $k > m$, the
coefficient of $x^k$ is zero.  Combine this fact and the two preceding
problem parts to obtain a closed-form expression for the number of
$m$-bit strings with a multiple of three 1's.

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
	& = &	\frac{1}{3}((1 + z_1)^m + (1 + z_2)^m + (1 + z_3)^m) \\
	& = &	\frac{1}{3}\left(
		2^m +
		\left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
		\left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
		\right)
\end{eqnarray*}
}

\problempart Use DeMoivre's formula, restated below, to eliminate
complex numbers from your solution.

\begin{eqnarray*}
(\cos \theta + i \sin \theta)^n & = & \cos(n \theta) + i \sin(n \theta)
\end{eqnarray*}

\solution{
\begin{eqnarray*}
\lefteqn{\frac{1}{3}\left(2^m +
		\left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
		\left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
		\right)}
\hspace{1in} \\
	& = &	\frac{1}{3}\left(2^m +
		\left( \cos \frac{\pi}{3} + i \sin \frac{\pi}{3} \right)^m +
		\left( \cos \frac{\pi}{3} - i \sin \frac{\pi}{3} \right)^m
		\right) \\
	& = &	\frac{1}{3}\left(2^m +
		\cos \frac{m \pi}{3} + i \sin \frac{m \pi}{3} +
	   	\cos \frac{m \pi}{3} - i \sin \frac{m \pi}{3} \right) \\
	& = &	\frac{1}{3}\left(2^m + 2 \cos \frac{m \pi}{3} \right)
\end{eqnarray*}

For example, the number of 4-bit strings with a multiple of three ones
is equal to

\begin{eqnarray*}
\frac{1}{3}\left(2^4 + 2 \cos \frac{4 \pi}{3} \right)
	& = &	\frac{1}{3}\left(16 + 2 \cdot \left(-\frac{1}{2}\right)
		\right) \\
	& = &	5
\end{eqnarray*}
 }

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems
%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



