\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}
\usepackage{textcomp}
\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}

\midterm{}{Due Friday, Week 5, at the start of class}


This midterm has \textbf{two} sections!

\begin{enumerate}
\item \textbf{Non-Collaboration Section}.  This section contains 4 quiz-styled problems, of which you will pick three.   If you attempt more than three, only your first three problems will be graded.  You are allowed to use your notes from class and the online class notes in this section; however, other resources (e.g. the internet, Mathematica, classmates) are off-limits.  You get \textbf{three} hours to complete this section!
\item \textbf{Collaboration Section}.  This section contains 4 homework-styled problems, of which you will pick two.  If you attempt more than two, only your first two problems will be graded.  You are allowed to use your notes from class, online class notes, Wikipedia, textbooks, Mathematica/Wolfram Alpha/etc, and can also collaborate with other people in the class.  As with the HW, you must cite all of your collaborators, and prove any results that you want to use that haven't been proven in class.  Also, all proofs/writeups/etc must be done in your own words.  You get \textbf{nine} hours to complete this section!
\end{enumerate}

The way time limits work is via the honor system, and as follows:\ 
\begin{itemize}
\item On the second page of this midterm, you can find a table for logging start/stop times on your work. 
\item When you start work, write down when you start the problem.
\item When you stop --- i.e., to take a break, or go to sleep, or go for a run --- write down when you stop.
\item Work is somewhat subjective, but can be broadly construed as ``thinking about and/or working on the problems.''  As long as you are being fairly reasonable and ethical here, you are likely doing the right thing!
\end{itemize}

You can send in questions by email or ask them at office hours; I will be a bit more cryptic than normal, but will still be helpful!

Good luck and have fun!
\newpage
\begin{center}
\textbf{Non-Collaboration Section Timesheet}\\
\begin{tabular}{|c|c|}\hline
\qquad\qquad\qquad Time started \qquad\qquad\qquad&\qquad\qquad\qquad Time stopped\qquad\qquad\qquad\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
\end{tabular}
\end{center}

\begin{center}
\textbf{Collaboration Section Timesheet}\\
\begin{tabular}{|c|c|}\hline
\qquad\qquad\qquad Time started \qquad\qquad\qquad&\qquad\qquad\qquad Time stopped\qquad\qquad\qquad\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
&\\\hline
\end{tabular}
\end{center}
\newpage


\section{Non-Collaboration Section}
Do \textbf{three} of the \textbf{four} problems in this section!


\begin{enumerate}
\item Consider the sequence $\displaystyle\{a_n\}_{n=0}^\infty$, defined recursively as follows: $a_0 = 0, a_1 =1$, and 
\begin{align*}
a_n = \left\{ \begin{array}{cc} a_{n/2}, & n \textrm{ is even},\\
a_{\lfloor n/2 \rfloor} + a_{\lceil n/2 \rceil}, & n \textrm{ is odd}. \end{array}\right. 
\end{align*}
For example, because $2$ is even, we have that $a_2 = a_{2/2} = a_1 = 1$.  Similarly, because $3$ is odd, we have that $a_3 = a_{\lfloor 3/2 \rfloor} + a_{\lceil 3/2 \rceil} = a_1 + a_2 = 1+1 = 2$.
\begin{enumerate}
\item Prove that for every $n \in \mathbb{N}$, we have $a_{2^n} = 1$.
\item Prove that for every $n \in \mathbb{N}, k \leq 2^n$, we have the following equality:
\begin{align*}
a_{2^n + k} = a_{2^n - k} + a_k.
\end{align*}  
\end{enumerate}
\item The Pell numbers are defined as follows: $p_0 =0, p_1 = 1$, and $p_n = 2p_{n-1} + p_{n-2}$.  Let $\displaystyle P(x) = \sum_{n=0}^\infty p_nx^n$ denote the generating function for the Pell numbers.
\begin{enumerate}
\item Show that 
\begin{align*}
P(x) = \frac{x}{1-2x-x^2}.
\end{align*}
\item Use this to find a closed form for $p_n$.
\end{enumerate}
\item Call a natural number $n$ ``powerful'' if it is of the form $m^k$ for some $m \in \mathbb{N}, k \geq 2 \in \mathbb{N}$.  How many non-powerful natural numbers are there that are less than 10,000?  (For this problem, you are allowed to use a calculator.)

\item Take any two finite sets $A, B$ such that $A \subseteq B$.  Prove that 
\begin{align*}
\sum_{A \subseteq K \subseteq B} (-1)^{|K \setminus A|} = \left\{ \begin{array}{cc} 1, & A = B, \\ 0, & A \neq B. \end{array}\right.
\end{align*}
\end{enumerate}


\newpage



\section{Collaboration Section}
Do \textbf{two} of the four problems in this section!  Each problem is on its own page.

\begin{enumerate}
\item Great news:\ for your birthday, you got a totally sweet Towers of Hanoi set!

 Bad news:\ in your mathematical joy, when you unwrapped your present you bent the middle peg pretty badly.
\begin{center}
\includegraphics[width=3in]{hanoi2.pdf}
\end{center}
As a result, when you play with your Towers of Hanoi set, you can't really leave pegs on the middle tower for too long.  To help with this, you've came up with a variation on the Towers of Hanoi rules. The normal Towers of Hanoi rules are as follows:
\begin{itemize}
\item Start with $3$ rods $A,B,C$.
\item On rod $A$, place $n$ disks with radii $1, 2, \ldots n$, so that the disk with radius $n$ is on the bottom, the disk with radius $n-1$ is on top of that disk, and so on/so forth.
\item Your goal is to move all of the disks from the far-left rod $A$ to the far-right rod $C$, subject to the following rules:
\begin{itemize}
\item You can move only one disk at a time.
\item Each move consists of taking the top disk off of some rod and placing it on another rod.
\item You cannot place a disk $D_i$  on top of any other disk $D_j$ with radius smaller than $D_i$.
\end{itemize}
\end{itemize}
You've changed the rules above as follows:
\begin{itemize}
\item[--] If you are moving disks from the broken rod $B$, you can move them all as one big stack (instead of one-by-one.)  You still can't place bigger disks on top of smaller disks, but this should hopefully make it so we move disks away from $B$ faster!
\end{itemize}
\begin{enumerate}
\item Let $h_n$ denote the smallest number of moves needed to move all of the disks from $A$ to $C$ in this new game.  (Note: we assume $h_0 = 1$ here for calculational convenience.)  Find a recurrence relation on the $h_n$'s.


\item Use this recurrence relation to find $H(x)$, the generating function for the $\displaystyle\{h_n\}_{n=0}^\infty$ sequence.  (Hint: if you get this part right, you should have $H(x) = \frac{1-x+x^2}{1-2x+x^3}$.)


\item Use this to find a closed form for $h_n$.
\end{enumerate}
\newpage 
\item In class, we used the sieve methods to show that the number of permutations on $\{1, \ldots n\}$ with no fixed points was
\begin{align*}
n! \cdot \sum_{r=0}^n \frac{(-1)^r}{r!}.
\end{align*}
\begin{enumerate}
\item Generalize this:\ show that the number of permutations on $\{1, \ldots n\}$ with $t$ fixed points is 
\begin{align*}
\frac{n!}{t!} \cdot \sum_{r=0}^{n-t} \frac{(-1)^r}{r!}.
\end{align*}
\item Use the above to prove that for every $n \geq 4$, the number of permutations of $\{1, \ldots n\}$ with an even number of fixed points is greater than the number of permutations with an odd number of fixed points.
\end{enumerate}
\newpage
\item Congratulations: you've beat the Elite Four\texttrademark and are now an official Pok\'emon Champion!  Accordingly, you must now spend the next $m$ days battling challengers, one each day, and you have $n$ Pok\'emon.  To start a Pok\'emon battle, you must pick one of your Pok\'emon to lead with.  

Suppose that over these $m$ days, you want to pick each of your $n$ Pok\'emon at least once to lead with.  Let $A(m,n)$ denote the total number of different ways to make these choices.
\begin{enumerate}
\item Use inclusion-exclusion to prove
\begin{align*}
A(m,n) = \sum_{k=0}^n \binom{n}{k} (n-k)^m(-1)^k.
\end{align*}
\item As a corollary of the above, prove that if $m < n$, we have that
\begin{align*}
\sum_{k=0}^n \binom{n}{k} (n-k)^m(-1)^k = 0.
\end{align*}
\end{enumerate} 

\newpage
\item You're writing a poem!  Accordingly, because you're a mathematician, you've decided that you care very, very deeply about the structure of your poem.  Namely, you've decided that your poem will have the following structure:
\begin{itemize}
\item It will consist of $n$ words.   These words will be split into nonempty lines of consecutive words:\ i.e. we could split seven words into (four words + three words), (two words + one word + four words), (seven words), and many other such combinations.
\item In each line, exactly one word is the word ``argyle.''  Any one of the words in a line can be ``argyle.''
\end{itemize}
Let $h_n$ denote the number of such structures (i.e. line breaks + placements of the word ``argyle'' in each line.) For example, $h_3 = 8$, as evidenced by the following structures:
\begin{multicols}{2}
\begin{itemize}
\item \fbox{\phantom{ttesteste}} argyle,\\
argyle
\item argyle \fbox{\phantom{ttesteste}},\\
argyle
\item argyle,\\
\fbox{\phantom{ttesteste}} argyle
\item argyle,\\
argyle \fbox{\phantom{ttesteste}}
\item argyle,\\
argyle,\\
argyle\\
\item argyle \fbox{\phantom{ttesteste}} \fbox{\phantom{ttesteste}}
\item \fbox{\phantom{ttesteste}} argyle \fbox{\phantom{ttesteste}}
\item  \fbox{\phantom{ttesteste}} \fbox{\phantom{ttesteste}} argyle
\end{itemize}
\end{multicols}
We find a closed form for $h_n$ here.  (Assume $h_0 = 1$ for computational convenience.)

\begin{enumerate}
\item Let $w_n$ be the number of ways to take a line with $n$ slots in it and pick one to be the word ``argyle.'' Show that $w_n = n$, and therefore that if $W(x)$ is the generating function for the $w_n$'s, then $W(x) = \frac{x}{(1-x)^2}$.
\item Let $h^{\{1\}}_n$ denote the number of poems on $n$ words with our desired structure, that have exactly one line.  If $H^{\{1\}}(x)$ is the generating function associated to the $h^{\{1\}}_n$'s, show that $H^{\{1\}}(x) = W(x)$.

Similarly, let $h^{\{2\}}_n$ denote the number of poems on $n$ words with our desired structure that have exactly two lines.   If $H^{\{2\}}(x)$ is the generating function associated to the $h^{\{2\}}_n$'s, show that $H^{\{2\}}(x) = (W(x))^2$.
\item Generalize the above:\ let $h^{\{k\}}_n$ denote the number of poems on $n$ words with our desired structure that have exactly $k$ lines.   If $H^{(k)}(x)$ is the generating function associated to the $h^{\{k\}}_n$'s, show that $H^{\{k\}}(x) = (W(x))^k$.
\item Let $H(x)$ be the generating function for our original $h_n$'s.  Show that
\begin{align*}
H(x) = \sum_{k=0}^\infty H^{\{k\}}(x).
\end{align*}
\item Use the above to find a closed form for $H(x)$, and from there find a closed form for $h_n$.  (Hint: if you did this right, you should get $H(x) =1 + \frac{x}{1-3x+x^2}$.)
\end{enumerate}
\end{enumerate}

\newpage



\end{document}