\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 problem sheet 3
}

Solutions to starred (*) exercises are due at the beginning of recitation on

\textbf{Thursday 24th September 2015}

Please submit answers to separate questions on separate sheets of paper.

\end{center}

\subsubsection*{Problem 1 --- 3.4 *}
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*{Problem 2 --- 3.7}
Prove that $2n-8 < n^2 - 8n + 17$ for all $n \in \mathbb{N}$.

\subsubsection*{Problem 3 --- 3.14}
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*{Problem 4 --- 3.17 *}
Using induction---and without using the formulae for $\sum i$ and $\sum i^2$---prove that
$$\sum_{i=1}^n i(i+1) = \frac{n(n+1)(n+2)}{3} \text{ for all } n \in \mathbb{N}$$

\subsubsection*{Problem 5 --- 3.23}
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}

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

\subsubsection*{Problem 7 --- 3.33 *}
Given $n \in \mathbb{N}$, let $A_n$ be the set of intervals $[a,b] \subseteq \mathbb{R}$, where $a,b \in \mathbb{N}$ and $1 \le a \le b \le n$. Find a simple formula for the number of elements of $A_n$ for each $n \in \mathbb{N}$.

\textit{Note: this is a re-worded but equivalent form of Problem 3.33 on Page 73 of the textbook.}

\subsubsection*{Problem 8 --- 3.44 *}
Determine the set of all natural numbers that can be expressed as the sum of some nonnegative number of $3$s and some nonnegative number of $10$s.

\subsubsection*{Problem 9 --- 3.56 *}
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 3$$
\begin{enumerate}[(a)]
\item Given that $a_1,a_2$ are odd, prove that $a_n$ is odd for all $n \in \mathbb{N}$.
\item Given that $a_1=a_2=1$, prove that $a_n = \frac{1}{2} \left( 3^{n-1} - (-1)^n \right)$ for all $n \in \mathbb{N}$.
\end{enumerate}

\subsubsection*{Problem 10 --- 3.62}
Two players alternately name dates. On each move, a player can increase the month or the day of the month, but not both. The starting position is January 1, and the player who names December 31 wins. According to the rules, the first player can start by naming some day in January after the first, or the first of some month after January.

An example play is as follows:
\begin{center}
Jan 5, Mar 5, Mar 15, Apr 15, Apr 25, Nov 25, Nov 30, Dec 30, Dec 31
\end{center}
Derive a winning strategy for the first player.

\subsubsection*{Problem 11 *}
Let $P(n)$ be a mathematical statement depending on an integer $n$. Suppose that:
\begin{enumerate}[(i)] \vspace{-10pt}
\item $P(1)$ is true; and
\item Given $n \in \mathbb{N}$, if $P(n)$ is true, then $P(2n)$ is true; and
\item Given $n \in \mathbb{N}$ with $n>1$, if $P(n)$ is true, then $P(n-1)$ is true.
\end{enumerate}
Prove that $P(n)$ is true for all $n \in \mathbb{N}$.

Deduce, given $n \in \mathbb{N}$ and nonnegative real numbers $a_1, a_2, \dots, a_n$, that
$$\frac{1}{n} \sum_{i=1}^n a_i \ge \sqrt[n]{\prod_{i=1}^n a_i}$$
\textbf{Hint:} In step (iii), let $\displaystyle a_n = \frac{1}{n-1} \sum_{i=1}^{n-1} a_i$ and apply $P(n)$.
\end{document}