\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xcolor}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge 21-128 and 15-151 problem sheet 3}

Solutions to the following seven exercises and optional bonus problem are to be submitted through 
blackboard by 8:30AM on

\textbf{Thursday 22nd September 2016.}

There are also some practice problems, not to be turned in, for those seeking more practice
and also for review prior to the exam.

\end{center}


\subsubsection*{Problem 1}
Using induction---and without using the formulae for $\sum i$ and $\sum i^2$---prove that
$$\sum_{i=0}^n i(i+1) = \frac{n(n+1)(n+2)}{3} \text{ for all } n \in \mathbb{N}$$


\subsubsection*{Problem 2}
Prove that
$$\sum_{i=1}^n \frac{1}{(3i-2)(3i+1)} = \frac{n}{3n+1}$$
for all $n \in \mathbb{N^{+}}$.


\subsubsection*{Problem 3}
For integers $n \geq 2$ find and prove a formula for $$\prod_{i=2}^n (1 - \frac{(-1)^i}{i}).$$


\subsubsection*{Problem 4}
Starting with a single stack of 100 coins, two players take alternate turns; in each turn, a player removes 
1, 2, 3 or 4 coins from the stack. The player who removes the last coin wins.
Prove that the second player has a strategy to win regardless of what strategy the first player uses.
(Hint: prove something more general)


\subsubsection*{Problem 5}
Determine the set of all natural numbers that can be expressed as $3m + 10n$ for natural numbers $m$ and $n$.


\subsubsection*{Problem 6}
Let $\langle a_n \rangle_{n \in \mathbb{N}}$ be a sequence satisfying
$$a_n = 2a_{n-1} + 3a_{n-2} \text{ for all } n \ge 2$$
\begin{enumerate}[(a)]
\item Given that $a_0,a_1$ are odd, prove that $a_n$ is odd for all $n \in \mathbb{N}$.
\item Given that $a_0=a_1=1$, prove that $a_n = \frac{1}{2} \left( 3^{n} - (-1)^{n+1} \right)$ for all 
$n \in \mathbb{N}$.
\end{enumerate}


\subsubsection*{Problem 7}
Let $\langle f_n \rangle_{n \in \mathbb{N}}$ be the sequence satisfying
$f_0 = 0$, $f_1 = 1$ and 
$$f_n = f_{n-1} + f_{n-2} \text{ for all } n \ge 2.$$
Show, by induction, that $f^2_n + f^2_{n+1} = f_{2n+1}$ and
$f^2_{n+2} - f^2_n = f_{2n+2}$ for every $n \in \mathbb{N}$.


\subsubsection*{Bonus Problem  (2 points)}
On the island of Perfect Reasoning, $k > 0$ people dress unfashionably. 
Clive Newstead arrives on a boat, somewhat distressed at the stereotypical 
unfashionability of the logically adept, and announces, ``At least one of you is dressed 
unfashionably. No unfashionably dressed person realizes that they are dressed 
unfashionably, but everyone else on the island realizes it. In $n$ days from now 
if you have concluded that your apparel is unfashionable, you will come to the beach 
at noon that day to denounce your apparel." The islanders gather at noon every day 
thereafter. When will the unfashionable apparel be denounced, and how will the 
wearers reason?


\subsubsection*{Extra Problem 1}
Let $P(n)$ be a mathematical statement depending on an integer $n$. Suppose that:
\begin{enumerate}[(i)] \vspace{-10pt}
\item $P(0)$ is true; and
\item Given $n \in \mathbb{Z}$, if $P(n)$ is true, then at least one of $P(n+1)$ or $P(n-1)$ is true.
\end{enumerate}
For which $n \in \mathbb{Z}$ must $P(n)$ be true?


\subsubsection*{Extra Problem 2}
Let $n$ be a positive integer. For each sum below, write it in summation notation 
and find and prove a formula in terms of $n$:
\begin{enumerate}[(a)]
\item $3 + 7 + 11 + \cdots + (4n-1)$;
\item $1 + 5 + 9 + \cdots + (4n+1)$;
\item $-1 + 2 - 3 + 4 - \cdots - (2n-1) + 2n$;
\item $1 - 3 + 5 - 7 + \cdots + (4n-3) - (4n-1)$.
\end{enumerate}


\subsubsection*{Extra Problem 3}
Let $a \in \mathbb{R}$ with $a \ne 0$. Find the flaw in the following `proof' that $a^n=1$ for all $n \ge 0$:
\begin{quote}
We prove that $a^n=1$ for all $n \ge 0$ by induction on $n$.
\begin{itemize}
\item \textbf{Basis step.} $a^0=1$ since any (nonzero) real number raised to the power $0$ is equal to $1$.
\item \textbf{Induction step.} Let $n \in \mathbb{N}$ and assume the induction hypothesis. Then
$$a^{n+1} = \frac{a^n \cdot a^n}{a^{n-1}} = \frac{1 \cdot 1}{1} = 1$$
\end{itemize}
By induction, $a^n=1$ for all $n \ge 0$. \qed
\end{quote}


\end{document}
