\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcounter{theproblem} \setcounter{theproblem}{1}
\newenvironment{problem}[1][]
{\noindent{{\color{blue}\large\bf
\arabic{theproblem}. #1} \stepcounter{theproblem}\vspace{0.3cm}}\\}
{\vspace{0.5cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}\newpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent{\color{blue}{\Large\bf Homework 2 \hfill 21-127 Concepts of Math \hfill due 09.13.2012}\\
\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Assignment begins here! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\color{blue}\large\bf Name:} % WRITE YOUR NAME HERE
\vspace{0.3cm}\\
\noindent{\color{blue}\large\bf ID:} % WRITE YOUR ANDREW ID HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Section:} % WRITE YOUR RECITATION SECTION HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Collaborators:} % LIST ANYONE YOU WORKED WITH HERE
\vspace{0.3cm}\\
{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
\begin{problem}[The Power of One (10 pts)]
What is wrong with the following ``proof'' of the claim that $a^n=1$ for every non-negative integer $n$?
\begin{quote}
Let $a$ be a nonzero real number.\vspace{0.2cm}\\
Notice that $a^0=1$.\vspace{0.2cm}\\
Also, notice that we can inductively write
\[ a^{k+1}=a^k\cdot a = a^k\cdot\frac{a^k}{a^{k-1}} = 1\cdot \frac{1}{1}= 1\]
since we know all smaller powers of $a$ are equal to 1, by assumption.\vspace{0.2cm}\\
Thus, by an inductive argument, $a^n=1$ for every non-negative integer $n$.
\end{quote}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Feel The Bernoulli (15 pts)]
Let $x$ be an arbitrary and fixed real number such that $x\geq -1$. In this problem, we will prove that
\[ (1+x)^n \geq 1+nx \]
for every natural number $n$. Call this inequality {\large\text{$\heartsuit$}}.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Prove that {\large\text{$\heartsuit$}} holds true when $n=1$.
\item {\bf Suppose} that $\ell$ is some arbitrary and fixed natural number, and {\bf suppose} that {\large\text{$\heartsuit$}} holds true when $n=\ell$.\vspace{0.2cm}\\
Use this assumption to prove that {\large\text{$\heartsuit$}} holds true when $n=\ell+1$, as well.\vspace{0.2cm}\\
{\bf Hint:} If you don't use the assumption that $x\geq -1$, maybe you're missing something \ldots
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[What The $L$? (20 pts)]
Let $n$ be some arbitrary and fixed natural number. Consider a chessboard of size $2^n\times 2^n$.\\(Note: those are {\bf powers} of 2, not multiples of 2!)\vspace{0.2cm}\\
Remove {\bf any} square from the board. Is it possible to tile the remaining squares with $L$-shaped triominoes?\\
(Note: a triomino consists of 3 squares.)\vspace{0.2cm}\\
If your answer is {\sf Yes}, prove it using some relevant technique. (What could this possibly be $\ldots$?)\vspace{0.3cm}\\
If your answer is {\sf No}, provide a counterexample. (That is, find an $n$ such that no {\it possible} way of tiling the board will work.)
\vspace{0.2cm}\\{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Some Sums Sum To Something Too Big (20 pts)]
In this problem, we will prove that the familiar {\bf Harmonic Series}, given by
\[ \sum_{k=1}^\infty \frac{1}{k} = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots \]
is {\bf divergent}; that is, we will prove that the sum of all the terms does not approach a finite limit.\vspace{0.2cm}\\
(Note: Do not worry about the terminology here. Just follow the steps outlined for you and it'll be fine!)\vspace{0.2cm}\\
We claim that the following inequality holds for every natural number $n$:
\[ \sum_{\displaystyle{k=1}}^{\displaystyle{2^n}}\;\frac{1}{k}\; > \frac{n+1}{2} \]
Call this inequality {\Large\text{$\star$}}.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Prove that {\Large\text{$\star$}} holds true when $n=1$.
\item Now, {\bf suppose} that $m$ is some arbitrary and fixed natural number, and {\bf suppose} that {\Large\text{$\star$}} holds true for the value $n=m$.\vspace{0.2cm}\\
Write out what it would mean for {\Large\text{$\star$}} to hold with the value $n=m+1$.
\item Start with the summation you wrote in part {\bf\color{blue}(b)}. Express it in terms of the assumption we made about {\Large\text{$\star$}} in part {\bf\color{blue}(b)}, and apply the assumption to write an {\bf inequality}.
\item Make an observation about the remaining terms in your expression. Specifically, you should be able to write something like
\[ \sum_{\displaystyle{k=2^m+1}}^{\displaystyle{2^{m+1}}}\; \frac{1}{k}\; > \sum_{\displaystyle{k=2^m+1}}^{\displaystyle{2^{m+1}}}\; C \]
where $C$ is some {\bf constant} that {\bf does not depend on $k$}.
\item Use this observation, and the inequality in part {\bf\color{blue}(c)}, to deduce that {\Large\text{$\star$}} also holds for the value $n=m+1$.
\item Think about what this proof has accomplished. Try to explain how the claim we have now proven shows that the Harmonic Series cannot converge to any finite limit.\vspace{0.2cm}\\
{\bf Note:} We really think it will help {\bf you} to put some thought into what you've accomplished with the previous parts of the problem. If you write anything relevant that makes sense, you will get full credit on this part.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Mo' Brendans, Mo' Problems (15 pts)]
In a futuristic society, there are only two different denominations of currency: a coin worth 3 Brendans, and a coin worth 7 Brendans. There is also a nation-wide law that says shopkeepers can only charge prices that can be paid in {\bf exact change} using these two coins.\vspace{0.2cm}\\
For example, we could pay 23 Brendans for a cup of coffee by using three 3 Brendan coins and two 7 Brendan coins. However, we clearly could {\bf not} pay 8 Brendans for a cup of coffee.\vspace{0.2cm}\\
What are {\bf all} of the legal costs that a shopkeeper could charge you for a cup of coffee, and why?\vspace{0.2cm}\\
Be sure to explain why your answers are {\bf all} of the possibilities.\vspace{0.2cm}\\({\bf Hint:} Try a bunch of small values and see what happens.)
\vspace{0.2cm}\\{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Setting Up Sets (20 pts)]
Rewrite the following sentences using the ``set-builder notation'' to define a set. Then, if possible, {\bf write out} all the elements of the set, using set braces; if not possible, explain why not and write out {\bf three} example elements of the set.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Let $A$ be the set of all natural numbers whose squares are less than 39.
\item Let $B$ be the set of all real numbers that are roots of the equation $x^2-3x-10=0$.
\item Let $C$ be the set of pairs of integers whose sum is non-negative.
\item Let $D$ be the set of pairs of real numbers whose first coordinate is positive and whose second coordinate is negative and whose sum is positive.
\item Fix an integer $x$. Let $E_{x}$ be the set of all integers $z$ with the property that we can find an integer $k$ such that $x\cdot k = z$.\vspace{0.2cm}\\
For writing out specific elements, use the case where $x=7$.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\end{document}