\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
            
\input{preamble.tex}

\begin{document}

\homework{3: More Generating Functions}{Due Friday, Week 4}

In this HW set, there are \textbf{five} problems.  Pick \textbf{three} of them to solve!  If you solve more than three, only your \textbf{first three problems} will be graded.  \href{https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=video&cd=1&ved=0CB4QtwIwAA&url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DUbw5N8iVDHI&ei=jM4xVdCcN4q1oQTVw4GwBA&usg=AFQjCNE8omPCQ8xtqWtF21xDxED0eN226w&sig2=60I8Ja4TKTax-GaRn38e6w}{Choose wisely.}
 
\begin{enumerate}
\item For any $n$, let $o_n$ denote the number of ways to write $n$ as an unordered sum of \textbf{odd} natural numbers:\ for example, $o_7 = 5$, because
\begin{align*}
1+1+1+1+1+1+1, 1+1+1+1+3, 1+3+3,1+1+5,7
\end{align*}
are all of the ways to write $7$ as a sum of odd natural numbers.  Similarly, let $d_n$ denote the number of ways to write $n$ as an unordered sum of \textbf{distinct} natural numbers:\ for example, $d_7 = 5$, as
\begin{align*}
1+2+4, 1+6, 2+5, 3+4, 7
\end{align*}
are all of the ways to write 7 as a sum of distinct natural numbers.  

In the example above, $o_7 = d_7 = 5$.  Prove that this wasn't a coincidence: that is, show that $o_n = d_n$ for every $n \geq 1$.

\item This problem consists of a very strange way to answer the following problem: in the expression $(\sqrt{2} + \sqrt{3})^{2014}$, can you determine the first few digits after the decimal place without using a calculator?
\begin{enumerate}
\item First, show that for any $n$, there are integers $a_n, b_n$ such that $(\sqrt{2} + \sqrt{3})^{2n} = a_n + b_n\sqrt{6}$.
\item Now, show that the sequences $a_n, b_n$ satisfy the recurrence relations
\begin{align*}
a_n &= 5a_{n-1} + 12b_{n-1}, \\
b_n &= 2a_{n-1} + 5b_{n-1}.
\end{align*}
\item If $A(x)$ denotes the generating function for the $\{a_n\}_{n=0}^\infty$ sequence, find a closed form for $A(x)$. Use this to prove that $a_n$ has the closed form
\begin{align*}
a_n = \frac{1}{2} \left( (5+2\sqrt{6})^n + (5-2\sqrt{6})^n\right).
\end{align*}
\item Using the above plus our knowledge that $a_n + b_n\sqrt{6} = (\sqrt{2} + \sqrt{3})^{2n} = (5+ 2\sqrt{6})^n$, prove that
\begin{align*}
a_n = b_n\sqrt{6} + (5-2\sqrt{6})^n.
\end{align*}
Use this fact to find the first (say) three digits after the decimal place for $(\sqrt{2} + \sqrt{3})^{2014}$ without using a calculator.
\end{enumerate}

\item The \textbf{Stirling numbers of the second kind} are defined as follows: for any natural numbers $n, k$, let $\stirling{n}{k}$ denote the number of ways to write the set $\{1,2,\ldots n\}$ as the union of $k$ disjoint nonempty subsets. For instance, $\stirling{3}{2} = 3$, as there are precisely three ways to write $\{1,2,3\}$ as a union of two disjoint nonempty sets:\ $\{1,2\} \cup \{3\}, \{1,3\} \cup \{2\}, \{2,3\} \cup \{1\}$.

We can use the sieve method to find a very nice formula for these numbers, as follows. Take $n$ labeled balls and consider the process of placing these balls into $k$ labeled boxes.  Let $\Omega$ denote the $k^n$ many ways of placing these balls into boxes.  Finally, for any $1 \leq i\leq k$, let $p_i$ denote the property that box $i$ is empty, and let $P = \{p_1, \ldots p_k\}$ be the collection of all of these properties.
\begin{enumerate}
\item  Prove that $k! \cdot \stirling{n}{k}$ is just the number of elements of $\Omega$ that satisfy no properties.
\item If $S$ is any subset of our properties and $A(S)$ denotes the number of elements of $\Omega$ that satisfy all of the properties in $S$ (and maybe more), show that $A(S) = (k-|S|)^n$.  
\item  In class, we defined $n_r = \sum_{S \subseteq P: |S| = r} A(S).$  Use (b) to find a formula for $n_r$ in terms of $k, n, r$
\item Use the $N(x-1) = E(x)$ trick to prove the following formula for the Stirling numbers:
\begin{align*}
\sum_{r=0}^\infty \binom{k}{r}(k-r)^n(-1)^r = k! \cdot \stirling{n}{k}.
\end{align*}
\end{enumerate}

\item In class, we proved that if $ A(x) = \sum_{n=0}^\infty a_nx^n$ was a generating function such that $ A(x) = \frac{1}{(1-x)^2},$ then $a_n = n+1$ for every $n$.

On the third quiz, we looked at a generating function $ B(x) = \sum_{n=0}^\infty b_nx^n$ such that $ B(x) = \frac{1}{(1-x)^3}.$  If you successfully completed this quiz problem, then you likely proved that $   b_n = \frac{(n+1)(n+2)}{2} = \binom{n+2}{2}$ for all $n$.

Generalize this as follows:\ for any natural number $k$, let $C(x) = \sum_{n=0}^\infty c_nx^n$ be a generating function such that $C(x) = \frac{1}{(1-x)^k}$.  Prove that $c_n = \binom{n+k-1}{k-1}$ for all $n$.


\item We close with one last example of the sieve method.  For any natural number $n$, let $\Omega$ denote the collection of all subsets of size $n$ from $\{1,2,\ldots 2n\}$.  For any $1 \leq i \leq n$, let $p_i$ denote the property that one of these given subsets does \textbf{not} contain the number $i$, and let $P = \{p_1, \ldots p_n\}$ denote the collection of these $n$ properties.  (Notice that our properties are only concerned with whether our subsets contain elements from $\{1, \ldots n\}$, and don't care about the other $\{n+1, \ldots 2n\}$ elements.)

\begin{enumerate}
\item Show that $A(S)$ is $\binom{2n-|S|}{n}.$
\item Show that $n_r = \binom{n}{r}\binom{2n-r}{n}$.
\item Finally, use the sieve method to show that for any $n$, we have the identity
\begin{align*}
1 = \sum_{r=0}^\infty \binom{n}{r} \binom{2n-r}{n}(-1)^r.
\end{align*}
\end{enumerate}
\end{enumerate}

\end{document}