\documentclass[11pt]{article}

\usepackage{homework,amssymb}


\begin{document}

\dotitle{3}{Wednesday, September 12}


\begin{list1}

\item Read through section 1.2 of van Dalen.
  
\item \addstar Write down explicit definitions of the functions $f$
  and $g$, where
\begin{list2} 
\item $f$ is defined recursively by $f(0)=0$, $f(n+1) = 3 +
f(n)$, and 
\item $g$ is defined recursively by $g(0)=1$, $g(n+1)=(n+1)^2 g(n)$.
  (Hint: use ``factorial'' notation: $m! = 1 \times 2 \times \ldots
  \times m$.)
\end{list2}

\item Write down an explicit definition of the function $h$,
  where $h(0) = 0$ and $h(n+1) = 3 \cdot h(n) + 1$. (Hint: compare to
  the sequence $1, 3, 9, 27, 81, \ldots$)
  
\item \addstar Suppose $g$ is a function from $\Bbb N$ to $\Bbb
  N$. Write down a recursive definition of the function $f(n)$,
  defined by $f(n) = \sum_{i=0}^n g(i)$.

\item Do problem 1 on page 30 of the Enderton handout.

\item \addcirc Do problem 3 on page 30 of the Enderton handout.
  
\item \addstar Suppose, as Section 2.2 of the notes, we are given a
  set $U$, a subset $B \subseteq U$, and some functions $f_1, \ldots,
  f_k$. Say a set is {\em inductive} if it contains $B$ and is closed
  under the $f$'s, and let $C^*$ be the intersection of all the
  inductive subsets of $U$. Show $C^*$ is inductive.
  
\item \addstar Define the set of ``babble-strings'' inductively, as
  follows:
\begin{myitemize}
\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{myitemize}
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''. Is
the set of babble-strings freely generated?

\end{list1}

\bigskip


\end{document}