\documentclass[11pt]{article}

\usepackage{homework}


\begin{document}

\dotitle{2}{Wednesday, September 5}

Note that a star ($\star$) next to a problem means that you are
required to turn in a written solution. A circle ($\circ$) next to a
problem means that this problem is for your edification and
entertainment. You should do the remaining problems; though you do not
have to turn in written solutions, they are fair game for the exams.

\bigskip

\begin{list1}

\item Read section 1.1 of the van Dalen text (and section 1.2 if you
have time).

\item Use the least element principle to prove the induction
  principle, and vice-versa.

\item \addstar Prove by induction that $\sum_{i=0}^n 2^i =
  2^{n+1}-1$. Keep in mind that $\sum_{i=0}^n 2^i$ is an abbrevation
  for $2^0 + 2^1 + 2^2 + \ldots + 2^n$.

\item \addcirc Can you find a formula for $\sum_{i=0}^n i^2$?
  
\item Prove by induction that whenever $n \geq 4$, $n! >
  2^n$.  Recall that $n!$, read ``$n$ factorial,'' is defined to be $n
  \cdot (n-1) \cdot \ldots \cdot 1$.

\item \addstar Prove by induction that whenever $n \geq 5$, $2^n > n^2$.
  
\item \addstar A ``binary string of length $n$'' is a sequence of $n$
  0's and 1's; for example, $011101$ is a binary string of length 6.
  Prove by induction that for every $n$ there are $2^n$ binary strings
  of length $n$. How many binary strings are there having length {\em
    at most} $n$?

\item \addstar Prove that there are $2^n$ subsets of a set having $n$
  elements. (Hint: you can use the preceding problem.)
  
\item Let ``HiLo'' be the following children's game: Player 1 picks a
  natural number between 1 and $M$ (inclusive), and Player 2 tries to
  guess it. After each incorrect guess, Player 1 responds ``higher''
  or ``lower.'' Assuming Player 2 has $n$ guesses, what is the largest
  value of $M$ for which there is an algorithm that guarantees
  success?  Describe the algorithm, and use induction to prove that it
  works.

\item \addcirc Show that the algorithm you gave in response to the
previous question is optimal, i.e.\ for larger values of $M$ there
will be numbers for which the algorithm fails to determine the correct
number after $n$ guesses.

\item Use the least element principle to prove that all numbers are
  interesting.

\end{list1}

\bigskip

\end{document}