\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}{Theorem}
\newtheorem{pf}{Proof}

\begin{document}
\begin{center}

{\Huge{Proofs}}\\
take three
\end{center}


\begin{enumerate}

\item  Determine if the following proof is valid or not.  \\If not valid, highlight the fallacies/error in logic.


\begin{thm}Every set of lines in the plane, no two of which are parallel, meet in a common point.
\end{thm}

\begin{pf}
Certainly two lines that are not parallel meet in a common point.

Assume a collection of $k$ lines, no two of which are parallel, meet at a common point.  We will show that a collection of $k+1$ lines, no two of which are parallel, will also meet at a common point.

Consider the set of $k+1$ distinct lines in the plane.  By our hypothesis, the first $k$ of these lines meet in a common point $p_1$.  Similarly the last $k$ of these lines meet in a common point $p_2$.  We will show that $p_1$ and $p_2$ must be the same point.  

If $p_1$ and $p_2$ were different points, all lines containing both of them must be the same line because two points determine a line.  This contradicts our assumption that all these lines are distinct.  Thus, $p_1$ and $p_2$ are the same point.  We conclude that the point $p_1=p_2$ lies on all $k+1$ lines, thus our $k+1$ distinct lines meet at a common point.
\end{pf}

\item Prove that $\displaystyle{\sum_{i=1}^n i\cdot i!=(n+1)!-1}$ for all positive integers $n$.

\vfill

\newpage
\item Prove the following recursive algorithm computes $a^n$, where $a$ is a nonzero real number and $n$ is a nonnegative integer.

\begin{algorithm}[H]
procedure power (a,n)\\
\KwData{$a:$ nonzero real number, $n:$ nonnegative integer}
 %initialization\;
 \eIf{$n=0$} 
 {
  	return 1
} 
{
	return $a\cdot \text{power}(a, n-1)$
  }
 \caption{Recursive powers of a}
\end{algorithm}

\vfill

\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 of 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 and the family of trees one step ``above" the basis step tree.
%\item Draw the family of trees one step ``above" the basis step tree.
%\vspace{1.5in}
\item Draw the family of trees two steps ``above" the basis step tree.
\vspace{1.2in}
\item Let $h(T)$ be the height of a tree.  \\
We define $h(\cdot)=0$, and $h(T_1T_2)=1+\max\{h(T_1), h(T_2)\}$.\\
Find the height of the trees in (b).
\end{enumerate} 

%\item Let $T$ be a binary tree, and $n(T)$ be the number of vertices in $T$.  Use induction to prove if $T$ is a full binary tree, then $n(T)\geq 2h(T)+1$.
\vfill


\end{enumerate}
\end{document}
