\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}


\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\operatorname{Var}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\PP}{\mathcal{P}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}

\title{\sc Math 2100 -- Homework 3}
\author{
	Fall 2022\\[10pt]
	due Wednesday, \textbf{October 19}, at the start of class\\[10pt]
	Sections 2.1, 2.2, 2.3, 2.4
}
\date{}
\begin{document}
\maketitle

\begin{center} 
	\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}

\textbf{Instructions:} This assignment is due at the \emph{beginning} of class. Please write the questions in the correct order. Explain all reasoning.

\begin{enumerate}	
	\item Decide if the following statement is true or false. If it's true, prove it. If it's false, provide a counterexample.
	\begin{center}
		If $x$, $y$, and $z$ are integers and if $x$ divides $y$ and $x$ divides $z$, then $x^2$ divides $yz$.		
	\end{center}

	\item Decide if the following statement is true or false. If it's true, prove it. If it's false, provide a counterexample.
	\begin{center}
		If $x$, $y$, and $z$ are integers and if $x$ divides $z$ and $y$ divides $z$, then $xy$ divides $z$.		
	\end{center}

	\item Decide if the following statement is true or false. If it's true, prove it. If it's false, provide a counterexample.
	\begin{center}
		If $n$ is a positive even integer, then $3^n+1$ is divisible by $5$.
	\end{center}
	
	\item Decide if the following statement is true or false. If it's true, prove it. If it's false, provide a counterexample.
	\begin{center}
		If $n$ is a positive even integer, then $n^3 + 2n$ is divisible by $4$.
	\end{center}
	
	\item Decide if the following statement is true or false. If it's true, prove it. If it's false, provide a counterexample.
	\begin{center}
		If $m$ is a positive odd integer, then $m^2 - 1$ is divisible by $8$.
	\end{center}
	
	\item Prove that if $3$ divides $4^{n-1}-1$ then $3$ divides $4^n-1$.
	
	\item Prove that no perfect square can have the form $3n + 2$ for an integer n.	

	\item Prove that for all positive integers $n$,
	\[
		\ds\sum_{k=0}^n (k \cdot k!) = (n+1)! - 1.
	\]
		
	\item Prove that for all positive integers $n \geq 2$, the number $2^{3n}-1$ is not prime. (Hint: do some experimenting to figure out a more specific fact about how the numbers $2^{3n}-1$ factor, and then use induction to prove that fact.)

	\item Prove that for all positive integers $n \geq 4$,
	\[
		n! > 2^n.
	\]

\end{enumerate}
\end{document}

