\documentclass[12pt]{amsart}
% Call packages that allow you to invoke certain mathematical symbols.
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=0.9in]{geometry}
\usepackage{cases}
% Set the title, author, and date information.
% Formally begin the document and make the title.
\begin{document}
\noindent \textbf{Math 315 - Fall 2017 \\
Homework 3} \\
Due October 2, 2017 \vspace{-4mm}\\
\noindent \small \textit{Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics.}\\\vspace{1mm} \hfill---
John Stillwell
\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in:}
\vspace{5mm}
\bigskip
\begin{enumerate}
\item \textbf{Quick Proofs:} (None need be longer than one or two sentences)
\begin{enumerate}
\item Prove that for all integers $n>1$ the inequality $2^n\leq \binom{2n}{n}$ holds.
\item Prove that for all positive integers $n$, the number $\binom{2n}{n}$ is even.
\item Prove that for all integers $n>k\geq 2$ the inequality $k^n\leq \binom{kn}{n}$ holds.
\end{enumerate}
\bigskip
\item Prove, by a combinatorial argument, that for all $n>1$ the number $\binom{3n}{n,n,n}$ is divisible by 6.
\bigskip
\item Find (and prove) a closed formula for $S(n,2)$ if $n\geq 2$.
\bigskip
\item Let $a_n$ denote the number of compositions of $n$ into parts that are larger than $1$. Give a formula for $a_n$ using $a_{n-1}$ and $a_{n-2}$.
\bigskip
\item We want to select as many subsets of $\{1, 2, 3, \dots, n\}$ as possible without selecting two subsets where one subset contains
the other. Prove that we can select at least $2^n/n$ subsets that do this.
\end{enumerate}
\end{document}