\documentclass[12pt]{article}

%Packages Used%
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsfonts,setspace}
\usepackage{fullpage}
\usepackage[pdftex,pagebackref,hypertexnames=false, colorlinks, citecolor=black, linkcolor=blue, urlcolor=red]{hyperref}
\usepackage{comment}
\usepackage{enumitem}
\usepackage[margin=1in]{geometry}


\setlength{\abovedisplayskip}{3mm}
\setlength{\belowdisplayskip}{3mm}
\setlength{\abovedisplayshortskip}{0mm}
\setlength{\belowdisplayshortskip}{2mm}
\setlength{\baselineskip}{12pt}
\setlength{\normalbaselineskip}{12pt}

\newcommand{\blank}{\underline{~~~~~~~~~}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\cP}{\mathcal{P}}

\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bzero}{\mathbf{0}}
\DeclareMathOperator{\Nul}{Nul}
\DeclareMathOperator{\Mod}{mod}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Ind}{Ind}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\tr}{tr}

\renewcommand{\And}{\wedge}
\newcommand{\Or}{\vee}
\newcommand{\Implies}{\Rightarrow}
\newcommand{\Not}{\sim}



\normalbaselines
\pagestyle{empty}
\raggedbottom
\begin{document}


\begin{center}
{
Math 2106-D, Foundations of Mathematical Proof \\
SAMPLE EXAM 2
}
\end{center}

\begin{enumerate}
\vfill
\item Show that if $r$ is a real number not equal to $1$, then for every $n\geq0$, we have 
\[
r^0+r^1+\ldots+r^n=\frac{1-r^{n+1}}{1-r}
.
\]
\vfill
\item For any real number $a$, let $I_a$ be the interval $[a,a+1)$. Describe an equivalence relation $R$ on $\mathbb R$ whose equivalence classes are exactly the sets $I_a$ for all $a\in\mathbb Z$ (be sure to prove that the relation you write down actually is an equivalence relation).
\vfill
\item For any $n\in\mathbb N$, a {\it partition} of $n$ is a representation of $n$ as a sum of a non-inreasing sequence of natural numbers. For example, the partitions of $4$ are 
\[
4,\quad3+1,\quad2+2,\quad2+1+1,\quad1+1+1+1
.
\]
Let $p(n)$ denote the number of partitions of $n$. For example, as there are $5$ partitions of $4$, we have $p(4)=5$. The number of partitions of $n$ grows very rapidly. Show that this is true by showing that for all $n\geq2$, we have
\[
p(n)\geq2^{\lfloor\sqrt n\rfloor}
,
\]
where $\lfloor x\rfloor$ is the {\it floor function} which takes any real number $x$ to the greatest integer less than or equal to $x$. For instance, $\lfloor\pi\rfloor=\lfloor3.9999\rfloor=\lfloor3\rfloor=3$. (Hint: Construct a surjection from the set of partitions of $n$ to the power set of $\{1,2,\ldots\lfloor\sqrt n\rfloor\}$.)
\vfill
\item 
Define a relation $R$ on $\mathbb N$ by declaring that $xRy$ if and only if $x=y\alpha^2$ for some $\alpha\in\mathbb Q$. Show that $R$ is  an equivalence relation. Show that each equivalence class has the same cardinality as $\mathbb N$. 
\vfill
\item
Given a function $f\colon A\rightarrow B$ and subsets $Y,Z\subseteq B$, show that $f^{-1}(Y\cap Z)=f^{-1}(Y)\cap f^{-1}(Z)$. (Recall that $f^{-1}(Y)$ for a general function means the preimage of $Y$, even when there is no inverse function $f^{-1}$. In the case when $f$ is a bijection, then the preimage of $Y$ is equal to the image of $Y$ under $f^{-1}$, also denoted by $f^{-1}(Y)$).
\vfill
\end{enumerate}

\end{document}




 





