\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm} 
\usepackage{color}
\usepackage{verbatim}

%%% Margins %%%
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\oddsidemargin}{-20pt}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4ex}

%%% Macros %%%
% Some macros to get you started
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\im}{im}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}




\begin{document}

\pagestyle{empty}

\begin{center}
{\large MATH 108 Fall 2019 \ -  \ {\bf Problem Set 3}}

% Put your name and section here.
{\large due October 18}
\end{center}


\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item For each postive integer $k$, let $A_k = \{x \in \RR \mid 0 < x < 1/k\}$.  Prove that
	 \[ \bigcap_{k=1}^\infty A_k = \emptyset. \]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Using induction, prove that for all positive integers $n$,
	 \begin{enumerate}
	  \item $n^3-n$ is divisible by 3.
	  \item $8^n - 1$ is divisible by 7.
	  \item $\sum_{k = 1}^n k^3 = \frac{n^2(n+1)^2}{4}$.
	  \item $n! = 1 + \sum_{k=1}^{n-1} k \cdot k!$.
     \end{enumerate}
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item In American football, a team can score seven points for a touchdown, and three points for a field goal (ignore safeties, two-point conversions, etc).  Prove that every integer score larger than 11 is possible.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $P$ be the set of prime numbers.  Prove that
	 \[ \bigcup_{p \in P} p\ZZ = \ZZ \setminus \{-1,1\}. \]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Use the Well-Ordering Principle of the natural numbers to prove that every positive rational number $x$ can be expressed as a fraction $x = a/b$ where $a$ and $b$ are postive integers with no common factor.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item The Fibonacci sequence is an infinite sequence of integers $(f_0, f_1, f_2, f_3, \ldots)$ defined as follows.  The first two numbers are $f_0 = 0$ and $f_1 = 1$.  For all $n \geq 2$, define $f_n$ to be the sum of the previous two numbers,
	 \[ f_n = f_{n-1} + f_{n-2}. \]
    Use induction to prove that for all nonnegative integers $n$,
     \[ f_n = \frac{\varphi^n - \psi^n}{\varphi - \psi}, \]
    where $\varphi = (1+\sqrt{5})/2$ and $\psi = (1-\sqrt{5})/2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Nim is a two-player game involving piles of coins. The players alternate taking turns, and on each turn the player chooses a nonempty pile and chooses a positive number of coins to remove from that pile.  This continues until there are no coins left.  In this version of Nim, whoever takes the last coin loses, and the game starts with two piles, each with $n$ coins.  Prove by induction that for all $n \geq 2$, the second player has a winning strategy, i.e. they can always win no matter what the first player does.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{enumerate}
\end{document}


