\newlec

\hdc

Let $n \in \mathbb{Z}$. Consider the following implication.\\[2mm]

\hspace{10mm} If ($\forall x \in \mathbb{R},~x \leq 0~\vee~x+1 > n$), then $n=1$.\\[2mm]

The contrapositive of this implication is

\begin{enumerate}[A)]
\item If $n=1$, then ($\forall x \in \mathbb{R},~x \leq 0~\vee~x+1 > n$).
\item If $n=1$, then ($\exists x \in \mathbb{R},~x > 0~\wedge~x+1 \leq n$).
\item If $n\neq 1$, then ($\exists x \in \mathbb{R},~x \geq 0~\wedge~x+1 < n$).
\item If $n\neq 1$, then ($\forall x \in \mathbb{R},~x \leq 0~\vee~x+1 > n$).
\item None of the above.												
\end{enumerate}
\vskip3em
\soln None of the above (Watch the inequality signs above!).

\ic{This is the 5 minute mark. You will likely want to repoll the students (when I first gave this problem, many of my students got this wrong).}

\newpage

\ic{This is a catch up lecture where if anything form the previous lectures took too long, then you can use this lecture to catch up. The only thing I would do in this lecture is show them sigma notation which I will do first and then give the class a lot of time to do practice problems.}

\textbf{Introduction to Summations}

\ex Tower of Hanoi:

In this modified version of the Tower of Hanoi, we create a tower with levels where each level is a cylinder of height 1 and increasing radius begining with $1$ and increasing by $1$ at each level. Below is a level $4$ Tower of Hanoi
\begin{center}
\includegraphics[scale=0.25]{L12P2.png}
\end{center}
\qn What is the volume of the $4$ level Tower of Hanoi?
\vskip1em 
\soln
\begin{align*}
V_{Tower} &= V_{1} + V_{2} + V_{3} + V_{4}\\
&= \pi(1)^{2}(1) + \pi(2)^{2}(1) + \pi(3)^{2}(1) + \pi(4)^{2}(1)\\
&= \pi + 4\pi + 9\pi + 16\pi\\
&= 30\pi
\end{align*}
\vskip1em
\qn What about computing the volume of the $100$ level Tower of Hanoi?
\vskip1em
\soln
\begin{align*}
V_{Tower} &= V_{1} + V_{2} +  ... + V_{100}\\
&= \pi(1)^{2}(1) + \pi(2)^{2}(1) + ... + \pi(100)^{2}(1)\\
&= \pi + 4\pi + ... + 10000\pi
\end{align*}
\note There are two concerns here. How do we evaluate this last sum? How to we write the above sum nicely and more formally without using dots?
\ic{This is the 10 minute mark.}
\textbf{Sigma and Pi Notation}
\vskip1em
\defn Let $\{a_{1}, ... ,a_{n}\}$ be a sequence of $n$ real numbers. We write
$$
\sum_{i=1}^{n} a_{i} := a_{1} + a_{2} + ... + a_{n}.
$$
We call $i$ the index variable, $1$ is the starting number, $n$ is the upper bound. We can also write
$$
\sum_{x \in S}x
$$
to mean the sum of elements in $S$.
\ic{Make sure you discuss the := symbol.}
Similarly, we define
$$
\prod_{i=1}^{n}a_{i} := a_{1}a_{2}...a_{n} \quad\quad\quad \prod_{x\in S} = \text{ Product of elements in S} 
$$
We make the following conventions when $j > k$ are integers (that is, the start index exceeds the end index)
$$
\sum_{i=j}^{k}a_{i} = \sum_{x \in \emptyset} = 0 
$$
and further,
$$
\prod_{i=j}^{k}a_{i} = \prod_{x \in \emptyset} = 1
$$
\note Sums are linear:
\begin{center}
For $c,j,k \in \mathbb{Z}$,  $\displaystyle \sum_{i=j}^{k}(ca_{i} \pm b_{i}) = c\sum_{i=j}^{k}a_{i}  \pm \sum_{i=j}^{k}b_{i}$
\end{center}
\ex
\begin{enumerate}
\item $\displaystyle \sum_{i=1}^{4}i^{2} = (1)^{2} + (2)^{2} + (3)^{2} + (4)^{2}  = 1 + 4 + 9 + 16 = 30$
\item $\displaystyle \prod_{i=1}^{4}i^{2}  = (1)^{2}(2)^{2}(3)^{2}(4)^{2} = (1)(4)(9)(16)= 576$
\item $\displaystyle \sum_{i=1}^{3.5}i = 1 + 2 + 3 = 6$
\item For $k \in \mathbb{N}$ fixed, $\displaystyle \sum_{i=k}^{2k}1/i = 1/k + 1/(k+1) + ... + 1/(2k)$.
\item So we can write the 100 level tower of Hanoi volume as $\displaystyle \sum_{i=1}^{100}\pi i^{2} = \pi \sum_{i=1}^{100}i^{2} $
\end{enumerate}

\defn We define the factorial notation for $n \geq 0$ an integer by $\displaystyle n! := \prod_{i=1}^{n} i$. Note $0! = 1$.
\vskip1em
\ex $4! = (4)(3)(2)(1) = 24$.
\vskip1em
\note We will see next week how to compute the sum in our volume computation of the 100 level Tower of Hanoi.
\ic{This is the 25-30 minute mark}

\newpage

\hdc
\ic{I suggest letting students work on these and either getting them to write solutions on the board or at least telling you which ones they want to see solved.}
Try some of the following problems:
\begin{itemize}
\item $\min\{a,b\} \leq \frac{a+b}{2}$ for all real numbers $a$ and $b$. 					
\item Let $x$ be real. Then $x^2-x > 0$ if and only if $x \not\in [0,1]$.						
%\item Let $S$ be a set. There is a unique set $T$ such that $S \cap T=S$.						
\item If $r$ is irrational, then $\frac{1}{r}$ is irrational.										
\item There do not exist integers $p$ and $q$ satisfying $p^2-q^2=10$. 						
\item The complete real solution to $x^2+y^2-2y=-1$ is $(x,y)=(0,1)$. 							
\item Let $S$ and $T$ be sets with respect to a universe $U$. Prove that $\overline{S \cap T} \subseteq \overline{S} \cup \overline{T}$. 
\item Let $a, b, c \in \mathbb{Z}$. Prove that if $a \nmid b$ and $a \mid (b + c)$, then $a \nmid c$.
%\item The sum of the first $n$ odd positive integers equals $n^2$.									\hfill \nb{induction}
\end{itemize}

\vskip3em
\ic{Hints in order
\begin{enumerate}
\item Direct proof with cases
\item iff, contrapositive
%\item uniqueness with set equality
\item contrapositive
\item contradiction
\item factor
\item set inclusion
\item contrapositive and elimination.
\end{enumerate}}


\newpage
\soln

\begin{itemize}
\item Let $a,b \in \mathbb{R}$. Without loss of generality, suppose that $a \leq b$. Then $2\min\{a,b\} = 2a < a + b$. Hence  $\min\{a,b\} \leq \frac{a+b}{2}$
\item Let $x$ be real. Then 
\begin{align*}
x^{2} -x > 0 &\Leftrightarrow x(x-1) > 0 \\
&\Leftrightarrow x > 0 \wedge x-1 > 0 \text{ or } x<0 \wedge x-1 < 0\\
&\Leftrightarrow x > 1 \text{ or } x < 0\\
&\Leftrightarrow x \not\in [0,1].
\end{align*}
\item We proceed by the contrapositive. If $\frac{1}{r}$ is rational, say $\frac{1}{r} = \frac{a}{b}$ with $a,b \in \mathbb{Z}$ and $b \neq 0$, then $r = \frac{b}{a} \in \mathbb{Q}$.
\item Assume towards a contradiction that there exists integers $p$ and $q$ satisfying $p^{2} - q^{2} = 10$. Without loss of generality, we may assume that $p,q \geq 0$ since $p^{2} = (-p)^{2}$ so if $(p,q)$ is a solution, then all of $(\pm p, \pm q)$ are solutions. Factoring gives $(p-q)(p+q) = 10$. Since $p+q > 0$, we have that $p-q > 0$. Since $p-q < p+q$, we see that $p-q=1$ and $p+q = 10$ or $p-q = 2$ and $p+q=5$. Adding the two equalities gives $2p = 11$ and $2p = 7$, both of which are a contradiction since $p$ is an integer.
\ic{The previous problem can also be solved by a parity argument.}
\item Isolating and factoring gives $x^{2} + (y-1)^{2} = 0$. Hence $x=0$ and $y=1$.
\item Suppose that $x \in \overline{S \cap T}$. We are required to show that  $x \in \overline{S} \cup \overline{T}$. By definition, $x \in U-(S \cap T)$ and hence $x \in U$ and $x \not\in S \cap T$. Thus, if $x \in T$, then $x \not\in S$ and so $x \in \overline{S}$. Otherwise, $x \not\in T$ and hence $x \in \overline{T}$. Thus, $x \in \overline{S} \cup \overline{T}$.
\item We prove the contrapositive. Suppose that $a \mid c$. Then we need to show that $a \mid b$ or $a \nmid (b+c)$. By elimination, we may assume that $a \mid (b+c)$ (otherwise $a \nmid (b+c)$ and the conclusion is true). Now, $a \mid c$ and $a \mid (b+c)$ and so by Divisibility of Integer Combinations, we have that $a \mid c(-1) + (b+c)(1)$ and hence $a \mid b$. 
\end{itemize}