Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
174 lines (116 sloc) 12.5 KB
\input{HEADER.tex}
\lhead{Introduction to Proofs}
\title{ARML Lecture: Introduction to Proofs}
\begin{document}
\begin{center}
\HRule \\[0.4cm]
{ \huge \bfseries ARML: Introduction to Proofs}\\[0.4cm] % Title of your document
\HRule \\[1.5cm]
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{Authors}\\
Justin \textsc{Stevens} \newline
\end{flushleft}
\end{minipage}
~
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
Spring 2014
\end{flushright}
\end{minipage}\\[0.5cm]
\end{center}
\section{Direct Proofs}
\begin{exmp} Prove that if $x$ is even and $y$ is odd, then $x+y$ is odd. \end{exmp}
\begin{proof}
If $x$ is even, then $x=2m$ for some integer $m$. If $y$ is even, then $y=2k+1$ for some integer $k$. Therefore $$x+y=2m+2k+1=2(m+k)+1$$ which is odd. \end{proof}
\begin{prob} Prove that if $x$ is odd and $y$ is odd, then $x+y$ is even. \end{prob}
\begin{exmp} Prove that if $x$ is even, then $x^2$ is even. \end{exmp}
\begin{proof} Set $x=2m$. Therefore, $$x^2=4m^2=2(2m^2),$$ which is clearly even. \end{proof}
\begin{exmp}[Generalization] Prove that if $x$ is even, then $x^n$ is even. \end{exmp}
\begin{proof} Set $x=2m$. Therefore, $$x^n=\left(2m\right)^n=2^n\times m^n=2\left(2^{n-1}\times m^n\right),$$ which is even. \end{proof}
\begin{prob} Prove that if $x$ is odd, then $x^2$ is odd. \end{prob}
\begin{exmp} Prove that for integers $a,b,c$, if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$. \end{exmp}
\begin{case} Notice that $2$ divides $6$ and $6$ divides $18$. This problem says that $2$ divides $18$. \end{case}
\begin{proof} Notice that $a\mid b$ means that "a divides b" and "b is a multiple of a". $a\mid b$ implies that $b=ka$ for some integer $k$. Similarly, $b$ divides $c$ implies that $c=mb$ for some integer $m$. Therefore $$c=mb=m\left(ka\right)=mk\left(a\right)$$
Therefore, $a\mid c$. \end{proof}
\subsection{Proof by cases}
Notice in all of the above problems, we are given a statement and asked to prove something with the statement. Sometimes, we are just given a statement and a condition, and are asked to prove something with the condition. In some cases, this condition may not be sufficient to proving the probelm statement. For example, we may be given that $x$ is an integer, however, this may not be enough to prove the problem statement. In this case, then we must divide the problem into \textbf{cases}. These cases would be the case when $x$ is odd and when $x$ is even. If we can prove the problem statement holds for when $x$ is odd and for when $x$ is even, then the problem statement holds for all integers $x$.
\begin{exmp} Prove that for all integers $x$, that $x^2+x$ is even. \end{exmp}
\begin{proof}
Using the fact that $x$ is an integer is not enough to prove that $x^2+x$ is even. Therefore, we divide this problem into the case when $x$ is even and when $x$ is odd.
\textbf{Case 1:} $x$ is even. Therefore, $x=2m$ for some integer $m$ and therefore $$x^2+x=4m^2+2m=2(2m^2+m),$$ which is clearly even.
\textbf{Case 2:} $x$ is odd. Therefore, $x=2k+1$ for some integer $k$ and therefore $$x^2+x=(4k^2+4k+1)+(2k+1)=4k^2+6k+2=2(2k^2+3k+1),$$ which is clearly even.
Since $x$ must be even or odd, in both cases, $x^2+x$ is even. \end{proof}
\begin{exmp} Prove that if $n$ is an integer, then $1+\left(-1\right)^n\left(2n-1\right)$ is a multiple of $4$. \end{exmp}
\begin{proof}
We start by testing a few cases:
$$\begin{tabular}{l | r}
n & $1+(-1)^n\left(2n-1\right)$ \\ \hline
1 & 0 \\
2 & 4 \\
3 & -4 \\
4 & 8 \\
5 & -8 \\
6 & 12 \\
7 & -12 \\
\end{tabular}$$
\textbf{Case 1:} $n$ is even. Therefore, $n=2m$ for some integer $m$. Then, \begin{eqnarray*} 1+\left(-1\right)^n\left(2n-1\right)&=&1+\left(-1\right)^{2m}\left(2\times 2m-1\right) \\ &=& 1+1\left(2\times 2m-1\right)=1+4m-1=4m \end{eqnarray*}
Which is a multiple of $4$.
\textbf{Case 2:} $n$ is odd. Therefore, $n=2k+1$ for some integer $k$. Then, \begin{eqnarray*} 1+\left(-1\right)^{2k+1}\left(2\times \left(2k+1\right)-1\right) &=& 1-1\left(4k+2-1\right) \\ &=& 1-1\left(4k+1\right)=1-4k-1=-4k \end{eqnarray*}
Which is a multiple of $4$.
\end{proof}
\begin{exmp} Prove that the sum of two integers with opposite parity (meaning that one number is even and the other is odd) sum to an odd integer. \end{exmp}
\begin{proof}
Let $x$ and $y$ be these two integers with opposite parody. We wish to prove that $x+y$ is even.
\textbf{Case 1:} $x$ is even and $y$ is odd. Let $x=2a$ for some integer $a$ and $y=2b+1$ for some integer $b$. Then $x+y=2a+2b+1=2(a+b)+1$ which is odd.
\textbf{Case 2:} $x$ is odd and $y$ is even. Let $x=2a+1$ for some integer $a$ and $y=2b$ for some integer $b$. Then $x+y=2a+1+2b=2(a+b)+1$ whih is odd. \end{proof}
Notice that the two cases are essentially identical. No matter which order we sum the even and odd number, the result will always be the same. In this situation where the two cases are identical, we can only do one case. The proof of this would be as follows:
\begin{proof}
Without Loss or Generality (WLOG), let $x$ be even and $y$ be odd. The rest of the proof follows as the same as Case 1 above. \end{proof}
Notice that the reason we could WLOG let $x$ be even and $y$ be odd is because the expression $x+y$ is \textbf{symmetric}. This means that $x+y=y+x$. If the expression was $x^2+y$, then we could not WLOG let $x$ be even and $y$ be odd, because the $x^2+y\neq y^2+x$ when the variables are interchanged. This is very important to remember. If you have any questions on this (as this part is rather confusing), feel free to ask me.
\section{Proof by Contradiction}
The method of proof by contradiction works by assuming the negation of the problem statement, and proving that the negation is false, therefore the problem statement must be true. This is best explained through an example.
\begin{exmp} Prove that if for an integer $a$ that $a^2$ is odd, then $a$ is odd. \end{exmp}
\begin{proof} Assume, for the sake of contradiction, that $a$ is even. However, using the example above in Chapter 1, we have that if $a$ is even, then $a^2$ is even, contradiction. Since $a$ can't be even, this means that $a$ must be odd. \end{proof}
Now that we have a basic understanding of proof by contradiction, we attack some classical problems using this method.
\begin{exmp} Prove that $\sqrt{2}$ is irrational. \end{exmp}
\begin{proof} For a number to be irrational, it cannot be expressable as a fraction. Assume for the sake of contradiction that $$\sqrt{2}=\frac{m}{n},$$ where $\frac{m}{n}$ is a fully reduced fraction. Squaring both sides of this equation results in $$2=\frac{m^2}{n^2}\implies 2n^2=m^2$$
Therefore, since the left hand side of this equation is divisible by $2$, the right hand side must be as well, and therefore $2\mid m$. Therefore, set $m=2m_1$ for some integer $m_1$. Now, $$2n^2=m^2=4m_1^2\implies n^2=2m_1^2$$ Similarly, this implies $2\mid n$ therefore $n=2n_1$ for some integer $n_1$. However, we assumed that $\frac{m}{n}$ was fully reduced, however, $$\frac{m}{n}=\frac{2m_1}{2n_1}=\frac{m_1}{n_1},$$ contradiction. \end{proof}
\begin{exmp} Prove that $x^2+x$ is always even. \end{exmp}
\begin{proof} We can divide this into cases again, however, there is a much simpler method. Notice that $x^2+x=x(x+1)$. Now, assume that $2$ does not divide either $x$ or $x+1$. Since $2$ does not divide $x$, this implies that $x$ is odd, however, then $x+1$ is even, contradiction. Therefore at least one of $x, x+1$ is even, and therefore their product is even. This idea is used in the next problem. \end{proof}
\begin{exmp} Prove that there is an infinite number of primes. \end{exmp}
\begin{proof}[Due to Euclid] Assume there is a finite number of primes. Let $2=p_1<p_2<p_3<\cdots<p_k$ be all of the primes. Then consider the product $$N=p_1p_2\cdots p_k+1$$ Let $p$ be a prime divisor of $N$. Then $p$ cannot be among $p_1, p_2, \cdots, p_k$ because this would imply that $p$ divides both $p_1p_2\cdots p_k$ and $p_1p_2\cdots p_k+1$, hence must divide there difference $1$. Therefore, we have found another prime outside of the set $\{p_1, p_2, \cdots, p_k\}$, contradiction. \end{proof}
This is a really challenging proof and it's OK if you don't understand it at first. Read over this proof several times, and it will become apparent to you.
\begin{exmp} Prove there are no positive integer solutions to $x^2-y^2=1$. \end{exmp}
\begin{proof} Assume for the sake of contradiction that there exists a solution pair $(x,y)$. Then we must have $$\left(x-y\right)\left(x+y\right)=1$$ The divisors of $1$ consist of $1,-1$ therefore since $x-y$ and $x+y$ are divisors of $1$, we must have $x+y, x-y \in \{-1, 1\}$. However, notice that $x+y>0$ so $x+y$ must be $1$, and therefore $x-y$ must be $1$ too (in order to have $x^2-y^2=1$). However, the equations $\begin{cases} x+y=1 \\ x-y=1 \end{cases}$
Gives $y=0, x=1$, of which $y$ is not a positive integer. Therefore we have arrived at a contradiction. \end{proof}
\newpage
\section{A Quick Introduction to Inequalities}
\begin{exmp}[Trivial inequality] Prove that for all real numbers $x$, we have $x^2\ge 0$. \end{exmp}
\begin{proof} We proceed by proof by contradiction, and assume that $x^2<0$ for some $x$. We have three cases to consider: $x$ is greater than $0$, $x$ is equal to $0$, $x$ is less than $0$.
\textbf{Case 1:} $x$ is greater than $0$. In this case, if $x^2<0$ were true, we could divide by $x$ on both sides of the equation (since $x$ is positive) to result in $x<0$, contradiction.
\textbf{Case 2:} $x$ is equal to $0$. In this case, $x^2=0$, therefore $x^2<0$ cannot be true.
\textbf{Case 3:} $x$ is less than $0$. In this case, if $x^2<0$ were true, we could divide by $x$ on both sides of this equation to result in $x>0$ (since $x$ is negative we have to switch the inequality sign). This is an obvious contradiction.
Since all three cases resulted in a contradiction, $x^2\ge 0$ for all real numbers $x$. \end{proof}
\begin{exmp} Prove that for all $a,b$ being real numbers, we have $a^2+b^2\ge 2ab$. \end{exmp}
\begin{soln} Notice that $$a^2+b^2\ge 2ab \iff a^2+b^2-2ab\ge 0$$
Now, $a^2+b^2-2ab=\left(a-b\right)^2$ (prove it!). Since all perfect squares are greater than or equal to $0$, we have $\left(a-b\right)^2=a^2+b^2-2ab\ge 0$. Now the question is how would we write up this proof? The best method for writing a proof for an inequality such as this is \textbf{to work backwards}. This method is illustrated in the following formal proof of this inequality. \end{soln}
\begin{proof} Notice that $\left(a-b\right)^2\ge 0$ since all perfect squares are greater than or equal to $0$. Expanding this equation results in $a^2+b^2-2ab\ge 0$. Adding $2ab$ to both sides of this inequality gives $a^2+b^2\ge 2ab$ as desired. \end{proof}
\section{Exercises for the Reader}
See me if you need a hint on any of these problems, as they are hard!
\begin{prob} Prove that if $a,b,c$ are odd integers, then the quadratic equation $ax^2+bx+c=0$ does not have any integer roots. \end{prob}
\begin{prob} Prove there are no rational number solutions to $x^3+x+1=0$. \textit{HINT:} Use proof by contradiction and assume a root is in the form $\frac{p}{q}$. \end{prob}
\begin{prob} Prove there are no positive integer solutions to $x^2-y^2=10$. \end{prob}
\begin{prob} Prove that if $a$ is an odd integer, then $a^2+3a+5$ is also odd. \end{prob}
\begin{prob} Prove that if $a\mid b$ then $a^2\mid b^2$. \end{prob}
\begin{prob} Prove that $4\ge x(4-x)$. \end{prob}
\begin{prob} If two integers have the same parity, then their sum is even. \end{prob}
\begin{prob} Prove that if $a,b$ are integers, then $a+b\ge 15$ implies that $a\ge 8$ or $b\ge 8$. \end{prob}
\begin{prob} Prove that if $a\mid b$ and $a\mid c$ then prove that $a\mid (b+c)$. \end{prob}
\begin{prob} Prove that if $x$ and $y$ are odd, then $xy$ is odd. \end{prob}
\begin{prob} Prove that if $a\mid b$ then $a\mid (b^5+3b^3+b)$. \end{prob}
\begin{prob} Prove that if $a,b$ are integers, that $a^2-4b\neq 2$. \end{prob}
\begin{prob} Prove that for $a,b$ positive integers greater than $1$, we cannot have both $a\mid b$ and $a\mid b+1$ (this is a lemma we used in the proof that there are an infinite number of primes). \end{prob}
\begin{prob} Prove that $\sqrt[3]{2}$ is irrational. \end{prob}
\begin{prob} Prove that for all integers $x$, that $x^2-x$ is even. \end{prob}
\end{document}