\documentclass [12pt] {article}


\usepackage{graphicx, amsmath, amsthm}
\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{Quiz 4}
\end{center}
\vskip .5in
\normalsize

\noindent{Show \emph{all} your work. No credit is given without reasonable supporting work. There are \emph{two} sides to this quiz and all logic symbols make use of the textbook notation.}

\begin{enumerate}
\item $[2]$ The ``structure" of induction requires two steps.  Name the two steps.
\vspace{.5in}


\item $[3]$ (\S5.1 Example 15)  Determine if the following proof is valid or not.  If valid, identify the proof method(s) used.  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}

\vspace{1in}


\item$[3]$ Explain how inductions works as you would to a colleague who ``doesn't believe" in induction.



\newpage	
\item $[6]$ (\S5.2 \#10) Assume that a chocolate bar consists of $n$ squares arranged in a rectangular pattern.  The entire bar, a smaller rectangular piece of the bar, can be broken along a vertical of a horizontal line separating the squares.  Assume that only one piece can be broken at a time.  Prove you will need $n-1$ breaks to break the bar into $n$ separate squares. 
\vfill

\item $[6]$  (\S5.1 \#7) Prove that $\displaystyle{3+3\cdot 5 +3\cdot 5^2+3\cdot 5^3+\cdots +3\cdot 5^n=\frac{3(5^{n+1}-1)}{4}}$ whenever $n$ is a nonnegative integer.
\vfill


\end{enumerate}
\end{document}
