\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}Solution:\quad 
\color{red} #1
\end{quote}
}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}(#1)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

\begin{document}
\title{Math 301: Homework 2}
\author{Mary Radcliffe}
\date{due 19 Sept 2016}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Use generating functions to find a closed form for $a_n$ for each of the following recurrence relations.
\begin{itemize}
\item $a_{n+1}=\alpha a_n+\beta$ for $n\geq 0$, $a_0=0$.
\item $a_{n+2}=2a_{n+1}-a_n$ for $n\geq 0$, $a_0=0$, $a_1=1$
\end{itemize}

\item Merge sorting is an algorithm for sorting a list $S$ of numbers. It works as follows:
\begin{enumerate}
\item If $S$ contains just one element, it is sorted.
\item If $S$ contains $n>1$ elements, choose some $k<n$. Divide the list into two parts, one having $k$ elements and one having $n-k$ elements. Recursively apply a merge sort to each part.
\item Once every part is sorted, merge the parts by comparing successive elements. 
\end{enumerate}

For example, if we had two sorted parts $\{1, 2, 5, 7\}$ and $\{3, 6, 8\}$, our final step would look as follows: Compare $1, 3$, and take $1$ to be first. Compare $2, 3$, and take $2$ next. Compare $5, 3$, and take $3$ next. This continues until all elements from both sets have been added to a new, totally sorted array. 

Given a set $S$ containing $2^k$ elements, define $m_k$ to be the maximum number of comparisons that must be made to perform a merge sort on $S$, in which each time we divide the list into two parts, they are equal in size (this is actually the optimum procedure). That is to say, $m_k$ is an approximation of the longest running time of a merge sort on a set of $2^k$ elements. Find a recurrence relation for $m_k$, and solve it.



\item For even $n$, let $e_n$ be the number of permutations with all cycles even, $o_n$ the number of permutations with all cycles odd, and $p_n=n!$ the total number of permutations. Let $E(x), O(x)$, and $P(x)$ denote the corresponding exponential generating functions. Prove the following:
\begin{enumerate}
\item $P(t)=(1-t^2)^{-1}$
\item $E(t)=(1-t^2)^{-1/2}$
\item $E(t)O(t)=P(t)$
\item $e_n=o_n$ for all even $n$.
\end{enumerate}


\end{enumerate}

\end{document}