\documentclass[UTF8, 11pt]{amsart}
\usepackage{hyperref}
\usepackage{amsthm}

\title{MATH 3040: Preliminary Exam \#2, Part II}
\author{}
\date{November 8, 2017}

%----------Theorems----------

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{nondefinition}[theorem]{Non-Definition}
\newtheorem{exercise}[theorem]{Exercise}

\renewcommand{\P}{\mathcal{P}}
\newcommand{\N}{\textbf{N}}
\newcommand{\RR}{\textbf{R}}
\newcommand{\ZZ}{\textbf{Z}}

%Redefine the first level
\renewcommand{\theenumi}{(\alph{enumi})}
\renewcommand{\labelenumi}{\theenumi}

\begin{document}

\maketitle

All answers must be in complete sentences. All assertions must be proven, per the student contract. Remember that this is a writing class, so while correctness and thoroughness are most important, \textit{style} matters as well. 

For this part of the exam, you are free to use any of the allowable resources for the course (e.g. notes, book, your previous homeworks, etc.), but you are \textbf{not allowed to discuss the questions with each other}.

This part of the exam is due on Gradescope by Sunday, November 12.

\bigskip
\noindent
\textbf{1. (Countability of Sets of Numbers)} A real number $a \in \RR$ is said to be \textbf{algebraic} if there a nonzero polynomial
\[
f(x) = a_n x^n + a_{n-1} x^{n-1} + + \cdots + a_1 x + a_0,
\]
where the coefficients $a_i \in \ZZ$ for all $i$, such that $f(a) = 0$. For example, $\beta = \sqrt{2}/2$ is algebraic because it is a root of $2x^2 - 1$. If $a \in \RR$ is not algebraic, we say it is \textbf{transcendental}. Famous examples of a transcendental numbers include the familiar constants $\pi$ and $e$, but it's difficult to show that a number is transcendental.

\begin{enumerate}
  \item{Show that if $a \in \RR$ is transcendental, then $a$ is irrational (i.e. $a$ cannot be expressed as $\frac{p}{q}$ where $p, q \in \ZZ$).}
  
  \item{Use the following lemma to prove that the set of algebraic numbers is countable, but the set of transcendental numbers is uncountable.
  
  \medskip
  \begin{quote}
  \textbf{Lemma A.} A degree-$n$ polynomial with real number coefficients has at most $n$ roots in $\RR$.	
  \end{quote}
}	
\end{enumerate}



\bigskip
\noindent
\textbf{2. (Formula Hunting)} Define $f_0 = 1$. For $n \geq 1$, let $f_n$ be the number of subsets of $[n] = \{1, \dots, n \}$ that do not contain three consecutive numbers. Here are the first few values of $f_n$:
\begin{center}
    \begin{tabular}{cc|l}
    $f_0$   & 1 & by definition \\
    $f_1$   & 2 & all the subsets of $[1]$ \\
    $f_2$   & 4 & all the subsets of $[2]$\\
    $f_3$   & 7 & all eight subsets of $[3]$ except for $\{1,2,3\}$ \\
    $f_4$   & 13 & all sixteen subsets of $[4]$ except for $\{1,2,3\}$, $\{2,3,4\}$, and $\{1,2,3,4\}$ \\
    $f_5$   & 24 & \\
    \end{tabular}
\end{center}

\bigskip
\noindent
Find a recursive formula for $f_n$ and prove that your formula is correct. (Warning: If you use induction, be careful about which form of induction you use!)

\end{document}
