\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 3}
\author{Mary Radcliffe}
\date{due 23 Sept 2015}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Let $a_n$ be the number of paths of length $n$ from $(0, 0)$ using steps of the form $(1, 0)$, $(0, 1)$, or $(-1, 0)$ and never intersecting themselves. (Note: these are different from our previous lattice paths in that we can take horizontal steps either left or right). Use a linear recurrence relation to find a closed form for $a_n$.

\item Find an ordinary generating function 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 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}