\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}

\input{preamble.tex}

\begin{document}

\homework{1: Basic Counting}{Due Friday, Week 1}

Do \textbf{three} of the \textbf{five} problems below!   Prove all of your claims.  If you've seen some of these problems before, try the ones you have not seen first.


\begin{enumerate}
\item Show that the following equality holds for all $n \in \mathbb{N}$:
\begin{align*}
2^n = \sum_{i=0}^n \binom{n}{i}.
\end{align*}

\item In class, we showed that 
\begin{align*}
\sum_{i=1}^n i = \frac{n(n+1)}{2}
\end{align*}
by creating a $(n+1) \times (n+1)$ square out of dots and counting in two ways.

Using similar methods, try to count $\sum_{i=1}^n i^2$.

\item \textbf{Without} using induction, show that the following equality holds for all $a,b,n \in \mathbb{N}$:
\begin{align*}
(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}.
\end{align*}

\item Show that the following equality holds for all $n \in \mathbb{N}$:
\begin{align*}
\sum_{i=1}^n i \cdot (n-i) = \sum_{i=1}^n \binom{i}{2} = \binom{n+1}{3}.
\end{align*}

\item Call an ordered list of the first $n$ numbers $[n] = \{1,2,3, \ldots n\}$ \textbf{pleasant}\footnote{I made this term up.} if it satisfies the following property:
\begin{itemize}
\item The first element in our list can be any of the numbers in $\{1,2,3,\ldots n\}$.  
\item If $k$ is any element in our list that is not the first element, then at least one of $k+1, k-1$ must have shown up earlier in our list.
\end{itemize}
For example, 
\begin{align*}
(2,3,4,5,6,1)
\end{align*}
is a pleasantly ordered list.  However,
\begin{align*}
(2,3,5,4,6,1)
\end{align*}
is not a pleasantly ordered list: we have 5 in the third position, but we do not have either 4 or 6 occurring earlier in our list.

How many ordered lists are there of $[n]$?  
\end{enumerate}










\end{document}