\documentclass{article}
\usepackage{amssymb, mathrsfs, enumitem}
\usepackage{tikz-cd}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig, colortbl}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\renewcommand{\today}{}


\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\la}{\Leftarrow}
\newcommand{\ra}{\Rightarrow}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}


\newcommand{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 21 February 2019}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).

\begin{enumerate}

\item Given $n\geq0$, recursively define $n!$ by 
\[0! = 1, \quad, n! = n(n-1)! \hbox{ for }n>0.\]
Prove that for every $n\geq 4$, $2^n<n!$.

\item Prove that for any $n\in\N$, we have\[\sum_{k=1}^n k!k = (n+1)!-1.\]

\item (*) Prove that for any $n\in\N$, 
\[\displaystyle\prod_{i=1}^n(2i-1) = \frac{(2n)!}{2^nn!}.\]

\item Let $a_0, a_1, a_2, a_3, \dots$ be a sequence of real numbers, defined recursively by 
\[a_0=0;\quad a_1=1;\quad a_n=7a_{n-1}-12a_{n-2}\hbox{ for }n\geq 2.\]
Prove that for all $n\geq 0$, we have $a_n=4^n-3^n$.

\item (*) Prove, using induction, that for any odd $n\in\N$, we have $n^2-1$ is divisible by 8. How does the fact that $n$ is odd change the structure of the proof?

\item Suppose we play a game where there are 2 players. The game is as follows:
first, make two nonempty piles of pennies. On each player’s turn, they
may remove as many pennies as they like from one of the piles (but not
0). The player who removes the last penny wins the game.

Prove that if the two piles initially contain the exact same number of
pennies, then the second player can always win the game. Prove that if
the two piles initially contain different numbers of pennies, then the first
player can always win the game.

\item (*) Suppose you have a $2\times n$ playing board, and a supply of $2\times 1$ dominoes. Let $D_n$ denote the number of ways to cover the board with dominoes. For example, it is plain to see that $D_1= 1$ and $D_2=2$.

Determine an expression for the value of $D_n$. Prove that your expression is correct.

\item (*) Show that any $n\in\N$ can be written in the form $n=d_11!+d_22!+\dots+d_rr!$, where each $d_i$ satisfies $0\leq d_i\leq i$.

\item Given an integer $d$, define the set $A_d=\{n\in\N\ | \ n\hbox{ is divisible by }d\}$.
\begin{enumerate}
\item Suppose $p, q$ are distinct primes. Show that $A_p\cap A_q = A_{pq}$.
\item Suppose $a, b$ are integers with $a|b$. Prove that $A_b\subseteq A_a$.
\end{enumerate}

\item (*) Let $X, Y$ be sets in a universe $\Omega$. \begin{enumerate}
\item Prove that $X\subseteq Y$ if and only if $X\cap Y = X$.
\item Prove that $X\subseteq Y$ if and only if $X\cup Y = Y$.
\end{enumerate}
\end{enumerate}
\end{document}