\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\title{Assignment 3}
\date{Friday June 1, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{A Few More Puzzles}
This section has absolutely no pre-requisites. Below are two fun geometric-like problems. These are intended to be fairly straightforward, and aren't to be taken too seriously. Although you should be able to figure them out on your own there are hints provided on the last page. Try not to look at the hints until you're no longer having fun thinking about the problems. If you think of a solution that doesn't seem to use the hints I provide, don't worry; there's lots of ways to do these.
While writing the proof, don't think about rigor necessarily. Think about what would be enough to convince you. To test whether you were successful in this goal, you should do these problems early during the week, and look over your answer several days later; did you convince yourself?
\begin{prob} \label{triangle}
Consider the following picture:
\begin{center}
\begin{tabular}{c c c c c c}
$\bullet$ \\
$\bullet$ & $\bullet$ & \\
$\vdots$&$\vdots$&$\ddots$ \\
$\bullet$ & $\bullet$ & $\ldots$ & $\bullet$ \\
$\bullet$ & $\bullet$ & $\ldots$ & $\bullet$ & $\bullet$ \\
$\bullet$ & $\bullet$ & $\ldots$ & $\bullet$ & $\bullet$ & $\bullet$ \\
$\underbrace{\phantom{\bullet}}_{n}$ & $\underbrace{\phantom{\bullet}}_{n-1}$ & $\ldots$ & $\underbrace{\phantom{\bullet}}_{3}$ & $\underbrace{\phantom{\bullet}}_{2}$ & $\underbrace{\phantom{\bullet}}_{1}$
\end{tabular}
\end{center}
How many dots are there? Give a proof why using only the geometry of the picture.
\end{prob}
\begin{prob} \label{square}
Let $n$ be a natural number. Prove that the area of a square with side length $(n+1)$ minus a square with side length $n$ is the $n$th odd number. Do not use algebra or induction, only geometry.
\end{prob}
\section{More Proofs}
This section is intended for you to do Tuesday May 29th. Here we will do some basic proofs (as we did on the last homework).
\begin{prob}
Fix $f(x) = 2x + 1$, and a real number $a$. With particular emphasis on the form of the proof, prove:
\[
\A \epsilon > 0 \st \E \delta > 0 \st \A b\in \R \stt 0\leq |a - b| < \delta \to |f(a) - f(b)| < \epsilon
\]
You just proved that the function $f(x) = 2x+1$ is continuous.
\textit{Hint: When you are looking for $\delta$, do some algebraic scratch work. Remember $\delta$ is allowed to depend on $\epsilon$.}
\end{prob}
\begin{prob}
Prove, using mathematical induction, that the sum of the first $n$ natural numbers is the arithmetic mean of $n^2$ and $n$.
\end{prob}
\section{Induction}
This section is intended for you to do on Wednesday May 30th. Here we will practice proofs by induction on the natural numbers. Pay special attention to the form of your proof, especially your variables as well as the exact phrasing of your assumptions.
\begin{prob}
Let $a_n$ be a sequence, $n\in \N$, defined by recursion: $a_0 = a_1 = $ and $a_n = n^2 + a_{n-2}$. Prove that for every $n$
\[
a_n = \frac{n^3+3n^2+2n+3+3(-1)^n}{6}
\]
\end{prob}
\section{Sets}
This section is intended for you to do on Thursday May 31st. Here we will enforce some basic notions of sets, gaining intuition on what a set is, and basic operations on sets.
\begin{prob}
We denote that set of the first $n$ natural numbers as $[n]$. That is,
\[
[n] = \s{1,2,3,\ldots,n}
\]
For this problem, let $E$ denote the even integers. Calculate the following sets:
\begin{itemize}
\item $\N \cap [n]$
\item $\N \cap E$
\item $[5]\cup \s{1,3,9,15}$
\item $[5]\cap E$
\item $[2] \cup E$.
\item $[2]\cup[5]$
\item $[2]\cap[5]$
\end{itemize}
\end{prob}
\begin{prob}
The empty set is a difficult concepts for students. Here is a long list of expressions. Decide for each one whether they are true or false.
\begin{enumerate}
\item $\emptyset \sbs \emptyset$
\item $\emptyset \sbs \s{\emptyset}$
\item $\s{\emptyset} \sbs \emptyset$
\item $\s{\emptyset} \sbs \s{\emptyset}$
\item $\s{\s{\emptyset}} = \s{\emptyset}$
\end{enumerate}
\end{prob}
\begin{prob}
This is a preview question. We will talk about this question in detail on class Friday. Recall that $A\sbs B$ is short-hand for the formula $\A x \st x\in A \to x\in B$.
\begin{enumerate}
\item What are the first and last lines of a direct proof of $A\sbs B$?
\item Recall that, by definition, $x\in A\cup B$ if and only if $x\in A$ or $x\in B$. Write down the definition of $x\in A\cap B$.
\item Prove that $A\cap B \sbs A$.
\end{enumerate}
\end{prob}
\section{Hints}
\begin{itemize}
\item For problem \ref{triangle}, try thinking of a $(n+1)$ by $(n+1)$ square of dots; where does the picture I drew fit in?
\item For problem \ref{square}, try drawing the dot picture, as I did for the triangle. Pictorially, what is the difference between the $(n+1)$ by $(n+1)$ square the the $n$ by $n$ square?
\end{itemize}
\end{document}