\documentclass [12pt] {article}

\usepackage{graphicx, xypic,amsmath,amssymb,epstopdf,amsthm,amsfonts}
\usepackage{algorithm2e}
\usepackage[all]{xy}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\newenvironment{packed_itemize}{
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{itemize}}
\newenvironment{packed_enum}{
\begin{enumerate}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{enumerate}}


\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\newtheorem{thm}{Definition}

\begin{document}
\begin{center}

{\Huge{Recursive Definitions}}\\
\end{center}

\noindent Recall that sequences can be defined by writing a few terms, writing a closed formula, or \emph{recursively}.  That is, the first term(s) are defined explicitly and the $n^{\text{th}}$ term is defined by using only term(s) before it.

\begin{enumerate}

\item Let $f(0)=1$ and $f(n)=-2f(n-1)$ for $n\geq 1$.
\begin{enumerate}
\item Find $f(4)$.
\vfill
\item Find a closed formula for $f(n)$.
\vfill
\end{enumerate}

\item Give a recursive definition for the sequence $\{a_n\}_{n\geq 1}$, where $a_n=4n-2$.
\vspace{.75in}



\begin{thm} Recursive definitions involve two parts (and can be applied to functions, sets, structures, and more):
\begin{enumerate}
\item Bases Step: a specific and initial definition
\item Recursive Step: rule forming new function/set/rule dependent on facts preceding it.
\end{enumerate}

\end{thm}

\item The set of \emph{full binary (and rooted) trees}, where a rooted tree consists of a set of vertices containing a distinguished vertex called the \emph{root}, and eyes connecting these vertices, can be defined recursively by:

\noindent Basis Step: A single vertex $r$ is a full binary (and rooted) tree.\\
\noindent Recursive Step: Suppose that $T_1$ and $T_2$ are disjoint full binary (and rooted) trees, there is a full binary (and rooted) tree, denoted $T_1\cdot T_2$, consisting for a root $r$ together with edges connecting $r$ to the root of the left subtree $T_1$ and $r$ to the root of the right subtree $T_2$. 
\begin{enumerate}
\item Draw the basis step tree.
\item Draw the family of trees one step ``above" the basis step tree.
\vfill
\item Draw the family of trees two steps ``above" the basis step tree.
\vfill
\end{enumerate} 


\newpage
\item Use induction to prove if $T$ is a full binary tree, then $n(T)\leq 2^{h(T)+1}-1$.
\vfill

\begin{algorithm}[H]
 %initialization\;
 int factorial (int n) 
 
 \If{$n==1$}{
  	return 1\;
	}
 \Else{
	return $n*factorial(n-1)$
 }
 \caption{Sort Algorithm}
\end{algorithm}
\item Use induction to prove the above recursively defined program computes the factorial of $n$.

\vfill

\end{enumerate}
\end{document}
