\documentclass[boldsans]{article}
\usepackage{ccfonts,amsmath,amssymb,fullpage}
\title{CSC236, Fall 2012\\
Assignment 1}
\renewcommand{\today}{~}
\begin{document}
\maketitle

These problems aim to give you some practice writing proofs of facts
from different domains, using induction.  Unless you find them easy,
you should start working on them early, and be sure to talk them over
with your instructor and teaching assistant.

Submit your solutions as a PDF file called \texttt{a1.pdf}.
You must generate the PDF from a word processor, or LaTeX --- no
scanned handwritten work will be accepted.
\begin{enumerate}

\item A \textbf{ternary tree} is a tree where each node has no more
  than 3 children, and the \textbf{height} of a tree is defined as the
  number of nodes in the longest path%
  \footnote{Some mathematicians
    define tree \textbf{height} to be the number of edges in a longest
    path.}
  % 
  from the root to any leaf.  Use Complete Induction to prove that if a%
\footnote{non-empty --- the claim is false for the empty tree}
%
  ternary tree has height $n$, it has no more than $3^n-2$ nodes.

\item Exponential growth is, typically, faster than polynomial
  growth, so you should expect that beyond the first few natural
  numbers $n^3+n < 3^n$.  Determine what the ``first few'' natural
  numbers are, and prove that this inequality holds for all other
  natural numbers, using Mathematical Induction.  

\item A set of 3 elements has exactly one subset of size 3 (we'll call
  it a 3-subset), namely itself.  Experiment until you find a formula
  for the number of 3-subsets that a set of $n+3$ elements has, then
  use Mathematical Induction to prove that your formula works for any
  natural number $n$.  You may use, without proof, that a set with
  $n+2$ elements has $[(n+2)(n+1)]/2$ subsets of size 2.

\item Use Complete Induction or Mathematical Induction%
  \footnote{Several other proof techniques will also work}
%
  to prove that any binary string that begins and ends with the same
  bit has an even number of occurrences of substrings from $\{01,10\}$,
  e.g. $010$ has two: $01$ and $10$.  You may find it useful to
  combine this claim with a similar claim about binary strings that
  begin and end with different bits, and then prove the combined
  claims simultaneously.




\end{enumerate}
\end{document}
