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

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

\textbf{Thursday 10th November 2016.}

\end{center}

\subsubsection*{Problem 1}
By counting in two ways, prove that $n^2 = 2\binom{n}{2}+n$ for all $n \ge 0$.

\subsubsection*{Problem 2}
By counting in two ways, prove that $\sum_{i=0}^n \binom{i}{k} = \binom{n+1}{k+1}$ for all $k,n \ge 0$.

\subsubsection*{Problem 3}
By counting in two ways, prove that $\sum_{i=1}^n (i-1)(n-i) = \binom{n}{3}$ for all $n \ge 1$.

\subsubsection*{Problem 4}
Prove that the set of all natural numbers, the set of all even natural numbers, and the set of all odd natural 
numbers all have the same cardinality.

\subsubsection*{Problem 5}
Construct an explicit bijection from the open interval $(0,1)$ to the interval $(0,1]$.

\subsubsection*{Problem 6}
A function $f : \mathbb{Z} \to \mathbb{Z}$ is \textit{periodic} if there exists a positive integer $k$ such that 
$f(x+k)=f(x)$ for all $x \in \mathbb{Z}$. Prove that the set of all periodic functions $\mathbb{Z} \to \mathbb{Z}$ is countable.

\subsubsection*{Problem 7}
\begin{enumerate}[(a)]
\item A subset $A$ of $\mathbb{R}$ has the property that, given $\varepsilon > 0$ and $x \in \mathbb{R}$, there exist 
$a,b \in \mathbb{R}$ with $a \in A$ and $b \not \in A$, such that $|x-a|<\varepsilon$ and $|x-b|<\varepsilon$. Can $A$ 
be countable? Can $A$ be uncountable?
\item A subset $B$ of $\mathbb{R}$ has the property that, given $b \in B$, there exists $\varepsilon > 0$ such that 
if \newline $0<|b-x|<\varepsilon$ for some $x \in \mathbb{R}$, then $x \not \in B$. Is $B$ countable?
\end{enumerate}

[\textit{Source: Cambridge Mathematical Tripos Part IA 2010 Exam Paper 4 Question 8.}]

\subsubsection*{Bonus Problem - (2 points)} By counting in two ways, prove that 
$\binom{\binom{n}{2}}{2}=3 (\binom{n}{4} + \binom{n}{3})$
for all $n \ge 3$.

\end{document}
