\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}\color{red}Solution:\quad 
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Zplus}{\Z^+}

\begin{document}
\title{Math 228: Homework 3}
\author{Mary Radcliffe}
\date{due 22 Sept 2016}
\maketitle

\begin{enumerate}

\item Recall the Fibonacci numbers are defined by the recurrence relation $s_n = s_{n-1}+s_{n-2}$, and $s_0=s_1=1$. Prove the following identities.
\begin{enumerate}
\item $s_2+s_4+\dots+s_{2n} = s_{2n+1}-1$
\item $\sum_{k=0}^n {n\choose k}s_k = s_{2n}$
\item $s_{2n+1} = 3s_{2n-1}-s_{2n-3}$
\end{enumerate}


\item Let $a_n$ be the number of ways to pay $n$ dollars using only $10$ dollar bills, $5$ dollar bills, and $1$ dollar bills. Find a recurrence relation and a set of initial conditions for $a_n$.

\item Find an explicit formula for $a_n$ when $a_n$ is defined by the recurrence relation $a_n=3a_{n-1}-2a_{n-2}$ subject to the initial conditions $a_0=3$ and $a_1=4$.

\item Suppose you go to a party with $n-1$ other people, and each person checks a coat at the coatcheck. The coatcheck worker is lazy, and throws away all the coatcheck tickets, so that when everyone leaves the party, he randomly hands out coats. How many ways can the coats be returned so that nobody receives their own coat back?

You may think of this as a permutation $\pi$ on $[n]$, so person $i$ receives back coat $\pi(i)$, and thus $\pi(i)\neq i$ for every $i$ (that is, nobody gets what their own coat, so every coat is sent to a person to whom it does not belong). Such a permutation is called a {\it derangement} of $[n]$.

Find a recurrence relation on the number of derangements of $[n]$. 

\end{enumerate}

\end{document}