\documentclass[11pt]{article}
\usepackage{hw}

\begin{document}

\dotitle{1}{Thursday 14 September}

Undergraduates are to do only the unstarred problems. Graduate
students should also do the starred problem.

\bigskip

\begin{list1}
  
%\item Prove that there are infinitely many prime numbers.\\
%  (Hint: suppose $p_0, p_1, \ldots, p_k$ is a list of all the primes,
%  and consider the product $q = p_1\cdot p_2 \cdot\ldots\cdot p_k +
%  1$. Show that $q$ is either prime or is divisible by a prime
%  different from any of the $p_i$.)
  
\item Prove by induction that: $$\sum_{i=0}^n 2^i\ =\ 2^{n+1}-1\;.$$
  (Recall that $\sum_{i=0}^n 2^i$ is an abbrevation for $2^0 + 2^1 +
  2^2 + \ldots + 2^n$.)
  
%\item Prove by induction that if $n \geq 4$, then $n! >
%  2^n$.\\
%  (Recall that $n!$, read ``$n$ factorial,'' is defined to be $n \cdot
%  (n-1) \cdot \ldots \cdot 1$.

\item Use the least number principle to prove the induction principle.
 

\item Define the set of ``babble-strings'' inductively, as
  follows:
\begin{itemize}
\item ``ba'' is a babble-string
\item if $s$ is a babble-string, so is ``ab''$\concat s$
\item if $s$ and $t$ are babble-strings, so is $s \concat t$ 
\end{itemize}
Prove by induction that every babble-string has the same number of
$a$'s and $b$'s, and that every babble-string ends with an ``a''.

\item Referring to the previous problem, show that the set $B$ of babble-strings is not freely generated.  Give a different specification of $B$ such that $B$ is freely generated.  Use that specification to define a length function $f:B\to\N$ giving the number of letters in the string.

  
\item Write down explicit definitions of the functions $f$ and $g$,
  defined recursively by:
\begin{list2} 
\item $f(0)=0$, and $f(n+1) = 3 + f(n)$,
\item $g(0)=1$, and $g(n+1)=(n+1)^2 g(n)$.\\
  (Hint: use ``factorial'' notation: $n!= 1\cdot 2\cdot \ldots
  \cdot n$.)
\end{list2}

%\item \addstar Suppose $g$ is a function from $\N$ to $\N$. Write down
%  a recursive definition of the function $f(n)$, defined by $f(n) =
%  \sum_{i=0}^n g(i)$.

\item \addstar Prove by induction that if $n \geq 5$, then $2^n > n^2$.
  
\end{list1}


\end{document}