\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 4}{Due \emph{Friday}, March 22, 2013}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item{}[CM 2.2.4] Let $a_n = 3a_{n-1} - 2a_{n-2} + 1$ for $n\ge 2$ with $(a_0, a_1) = (2, 4)$.  Find a simple formula for $a_n$ first using the characteristic equation method, and again using generating functions.

\item{}[CM 2.2.13] Let $a_n$ be the number of $n$-tuples in $[4]^n$ that have at least one $1$ and have no $2$ appearing before the first $1$ (note that $\seq{a}$ begins $0, 1, 6, \ldots$).  Obtain and solve a recurrence for $\seq{a}$.  Give a direct counting argument (without using summations) to prove the resulting simple formula.

\item{}[CM 2.2.31] A row of $n$ lightbulbs must be turned on; initially, they are all off.  Bulb 1 can be turned on or off at any time.  For $i>1$, bulb $i$ can be turned on or off only when bulb $i-1$ is on and all earlier bulbs are off.  Let $a_n$ be the number of steps needed to turn on all the lights; note that $\seq{a}$ begins $(0, 1, 2, 5, 10, 21, \ldots)$.  Let $b_n$ be the number of steps needed to turn on bulb $n$ for the first time.
\begin{enumerate}
	\item Find a recurrence for $\seq{b}$ and solve it.
	\item Use $\seq{b}$ to find a recurrence for $\seq{a}$.
	\item Solve the recurrence for $\seq{a}$.
\end{enumerate}

\item{}[CM 2.2.33] Let $a_n$ be the number of words of length $n$ of the alphabet $\{0, 1, 2\}$ such that $1$ and $2$ are never adjacent.
\begin{enumerate}
	\item Obtain a second-order recurrence relation for $\seq{a}$.  (\emph{Hint}: An easy approach is first find a recurrence having no fixed order.  There is also a direct (more difficult) combinatorial argument.)
	\item Solve for $a_n$.
\end{enumerate}

\item{}[CM 2.3.13] In class, we argued that $n! \sim k\sqrt{n} (n/e)^n$ for some constant $k$.  Here, we show that $k = \sqrt{2\pi}$, completing the derivation of Stirling's formula.
\begin{enumerate}
	\item Let $I_m = \int_0^{\pi/2} (\sin x)^m\:dx$ for $m\in \N_0$.  Compute $I_m$.  \emph{Hint:} Integrate by parts for $m\ge 2$.  Set $u = (\sin x)^{m-1}$ and $dv = (\sin x)\:dx$.  Try small $m$ first if needed.
	\item Show directly from the definition of $I_m$ that $I_{2n-1} \ge I_{2n} \ge I_{2n+1}$.  Use this to prove the \textbf{Wallis product}:
\[ \frac{\pi}{2} = \lim_{n\to\infty} \frac{2^{4n}(n!)^4}{[(2n)!]^2(2n+1)} \]
	\item Use the Wallis product to compute $k=\sqrt{2\pi}$.
\end{enumerate}

\item{}[CM 3.1.\{3,15\}] Generating Functions.
\begin{enumerate}
	\item A child wants to buy candy.  Four types of candy have prices two cents, one cent, two cents, and five cents per piece, respectively.  Build the enumerator by total cost for the number of ways to spend money.  Express the enumerator in the form $1/f(x)$, where $f(x)$ is a finite product of polynomials.

	\item Let $a_n$ be the number of ways to pick a nonnegative integer $r$, roll one six-sided die $r$ times, and obtain a list of outcomes with sum $n$.  (Caution: $r$ is not fixed; for example,  $(a_0,a_1,a_2,a_3) = (1,1,2,4)$.)  Express the generating function for $\seq{a}$ as the ratio of two polynomials that each have at most three terms.  Obtain a recurrence for $\seq{a}$ directly from the generating function.  Give a combinatorial argument for the recurrence.  
\end{enumerate}

\end{enumerate}
\end{document}
