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


%%% Environments %%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{define}{Definition}
\newtheorem{remark}[define]{Remark}
\newtheorem{example}{Example}
\newtheorem{question}{Question}
\newtheorem{algorithm}{Algorithm}

\numberwithin{equation}{section}

%%% 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 Winter 2019 \ -  \ {\bf Problem Set 3}}

% Put your name and section here.
{\large due February 1}
\end{center}


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

	\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 each touchdown, and three points for each 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 Using induction, prove that if $A$ is a finite set with $|A| = n$ then $|\mathcal{P}(A)| = 2^n$.

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

	\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 For each positive integer $n$, let $T_n$ count the number of ways to tile a $2 \times n$ rectangle using $2 \times 1$ tiles.  Prove for each positive integer $n$ that $T_n = f_{n+1}$, the $(n+1)$th Fibonacci number.

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

\end{enumerate}
\end{document}


