\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\title{Exam 1 Technique Questions}
\date{June 4, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
The following are Exam 1 technique questions. Of this list, you will be asked to prove a specific few of them on the exam. This will constitute the majority of the points on Exam 1. Therefore, it is highly advised that you know these questions very well. It is not advised that you simply memorize the proof, as there are too many problems here to make that feasible.
You are welcome to study these problems with each other, and use any resources as per the Homework Resource Policy on the syllabus. You may not ask me any questions about them specifically except if you think there is an error or poor phrasing. However, as always, if you feel like you are having difficulties with a concept, you should come to me for help.
\begin{enumerate}
\item Prove the following inequality, where $a,b\in\R$ and $a,b > 0$
\[
4\left(\frac{a}{b}\right) + b \geq \sqrt{16a}
\]
\item Let $x$ be a real number. Suppose that $|x-1| < 1$. Then
\[
|x^2 - 4x + 3 | < 3.
\]
\item Prove or disprove the following propositional formulas; verify with truth tables:
\begin{enumerate}
\item $( (P\oor Q) \to (\neg P \to Q) ) \oand ( P\oor (\neg P \oor \neg Q))$
\item $ (R \oor (P \to Q)) \to (\neg R \to Q) $
\end{enumerate}
\item Prove or disprove the following propositional formulas; verify with truth tables:
\begin{enumerate}
\item $ ( ( Q \oand (P\to \neg Q) ) \to R ) \oor (\neg P)$
\item $ (R \to (Q\oand P)) \to (\neg P \to \neg R)$
\end{enumerate}
\item Suppose the domain of discourse is $\N$ (ie. all quantifiers are natural number quantifiers). Let $P(x)$ be a unary property depending on $x$ and $Q(x,y)$ be a binary property depending on $x$ and $y$. Prove the following:
\[(\A x \st \E y \st P(x) \to Q(x,y)) \bimp (\A x \st P(x) \to \E y \st Q(x,y))\]
\item Suppose that domain of discourse is $\N$ (ie. all quantifiers are natural number quantifiers). Let $P(x,y)$ be a binary property depending only on $x$ and $y$ and $Q(x,y,z)$ be a ternary property depending on $x$, $y$, and $z$. Prove the following:
\[ (\A x \st \E y \st \A z \stt P(x,y)\oand Q(x,y,z)) \bimp (\A x \st \E y \stt P(x,y) \oand (\A z\stt Q(x,y,z) )) \]
\item Consider the following statement. If the statement is true, prove it. If it is false, prove its negation.
\begin{enumerate}
\item $\A x\in\R \stt x^5 > x^2$
\item $\A x\in \R \st (x>0) \to \E y\in \R \st (y^4 = x) \oand (y \leq 0)$
\end{enumerate}
\item Consider the following statement. If the statement is true, prove it. If it is false, prove its negation.
\begin{enumerate}
\item $\E x\in\R \st \A y\in\R \stt x^2 - y^2 > 0$
\item $\A x\in\Z \st \A y\in \Z \st \E z\in\N \stt ((x-y) = z)\oor((y-x)=z)$
\end{enumerate}
\item Fix $f(x) = 2x + 7 $. Prove:
\[
\A a \in \R \st \A \epsilon > 0 \st \E \delta > 0 \st \A b \in \R \stt (|a - b| < \delta) \to ( |f(a) - f(b)| < \epsilon )
\]
\item Define a sequence recursively as follows: $a_0 = 1$ and $a_{n} = 4n + a_{n-1}$ for all $n\in \N$, $n>0$. Prove that $a_n = 2n^2 + 2n + 1$.
\item Prove the following by induction:
\[
\A n\in\N \stt 7^{2n+1}+6 \cdot 2^{2n}\cdot 3^{2n}\mbox{ is divisible by 13}
\]
\item Prove the following for all $n\in\N$, and give and prove the values of $n$ where the inequality is strict.
\[
\sum_{i=1}^n \frac{1}{\sqrt{i}} \geq \sqrt{n}
\]
\item Let $n\in\N$, $n>0$. You play a game on a $n$ by $n$ board where you start on the bottom left square and move one space every turn, either horizontally or vertically. Your goal is to get to the top left square in exactly $2n$ moves. Find and prove for which $n$'s this is possible.
\item Prove or disprove the following; if only one side is a subset of the other then prove it, and give a counterexample for the other direction.
\[
((A \minus B) \cup C)\cap B = ((A\cup C)\minus B)\cup (C\cap B)
\]
\item Prove or disprove the following; if only one side is a subset of the other then prove it, and give a counterexample for the other direction.
\[
((A \minus B) \minus C) = (A \minus (B\cap C))
\]
\item Prove or disprove the following; if only one side is a subset of the other then prove it, and give a counterexample for the other direction.
\[
\set{ x \in \R \mid x^2 - 4 > 0 } = \set{ x\in \R \mid x < -2 } \cup \set{ x\in \R \mid x > 2}
\]
\item Recall for $n\in\N$, we have $n! = n\cdot (n-1) \cdot (n-2) \cdot \cdots \cdot 2 \cdot 1$. Give and prove necessary and sufficient conditions for a natural number $n$ to be in the following set:
\[
\set{ n\in \N \mid 2^n < n! }
\]
\item Let $n,m$ be natural numbers and for each $i\in\N$ let $A_i$ be a family of sets. Prove or disprove the following; if it is true in one direction, and false in the other, prove the direction for which is it true, and show the other direction is false:
\[
\bigcup_{i\in [n]\minus[m]} A_i \; = \; \left(\bigcup_{i\in [n]} A_i \right) \minus \left( \bigcup_{i\in[m]} A_i \right)
\]
\item Let $A_1$ and $A_2$ be families of sets. Prove or disprove the following; if it is true in one direction, and false in the other, prove the direction for which is it true, and show the other direction is false:
\[
\bigcap_{i\in A_1 \cup A_2} i \;=\; \left(\bigcap_{i\in A_1} i\right) \cup \left(\bigcap_{i\in A_2} i\right)
\]
\item Give a concise formula for the following set, and prove your formula.
\[
\bigcup_{j\in[n]} [j]
\]
\end{enumerate}
\end{document}