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