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

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 4}{Due Fri March 28, 2025}

%\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.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{} 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{} 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{} 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}

\newpage
\item{} For the identity below,
\begin{enumerate}
	\item Give a combinatorial proof by constructing a set that both sides count.
	\item Use the Binomial Theorem to prove that both sides arise as the coefficient of $x^n$ in the expansion of $(1+3x+x^2)^n$.  Hint: if you are having trouble generating the LHS with the Binomial Theorem, try to apply your combinatorial argument from (a) in the algebraic context.  What plays the role of $j$ in the combinatorial argument?  What is the corresponding mechanism in the algebraic context?
\[ \sum_{j\ge 0} \binom{n}{j}\binom{2j}{j} = \sum_{k\ge 0} \binom{n}{2k}\binom{2k}{k} 3^{n-2k} \]
\end{enumerate}


\item A gambler and a casino play a game with $n$ blue balls and $n+1$ red balls.  The gambler starts with one unit of money (infinitely divisible).  At each round, the gambler bets part of his money (possibly 0), and the casino selects a ball (knowing the amount of the gambler's bet).  If the ball is blue, then the gambler loses the bet; if it is red, then the gambler gains that amount.  The selected ball is discarded.  The gambler wants to maximize his money after all the balls are used, while the casino wants to minimize that.  If both play optimally, how much does the gambler have at the end?  (Hint: Try small cases.  Solve a more general problem.)



\end{enumerate}
\end{document}
