\documentclass[12pt,titlepage]{article}
\usepackage{light}

%\renewcommand{\baselinestretch}{1.5}

\begin{document}
\generic{Things to Know - Compilation of Common Mistakes}{October 8, 2004}

\section{Different Things To Know}
You should know the following symbols and formulas.  Ask your TA if you
are not sure about a symbol or how to derive a formula.
\subsection{Symbols and Notations}
\begin{itemize}
\item Natural numbers : $\mathbb{N}=\set{0,1,2,\dots}$

\item Integers : $\mathbb{Z}=\set{0,1,-1,2,-2,\dots}$

\item Rational numbers or fractions: $\mathbb{Q}=\set{a/b \text{ s.t. } (a,b)\in
\mathbb{Z}\times \mathbb{Z}\ and\ b\neq 0}$

\item Real numbers : $\mathbb{R}=(-\infty , \infty)$

\item Complex numbers: $\mathbb{C}=\set{x+iy \text{ s.t. } x, y \in \mathbb{R}\ and\ i^2=-1}$

\item Positive numbers $\mathbb{N}^+ = \mathbb{Z}^+ = \set{1,2,\dots},\quad
\mathbb{R}^+=(0,\infty)$
% $\mathbb{R}^* = R\\ {0}  : \mathbb{R}^+=[0,\infty) and \mathbb{R}^{+*}=<0,\infty) $

\item If $S$ is a set, then $\size{S}$ is the \emph{size} (also called the
\emph{cardinality}) of $S$.  If $r$ is a real number, then $\size{r}$ is
the \emph{absolute value} of $r$.  If $a$ is a complex number, then
\[
\size{a} = \sqrt{\text{real-part}(a)^2 + \text{complex-part}(a)^2}
\]
is called the \emph{modulus} of $a$.

%, $\mathbb{R}^{*+}=(-\infty,0)$. ??

%NOT YET--ARM
%\item The binomial coefficient: $(_k^n)=\frac{n!}{k!(n-k)!}$.  

\end{itemize}

\subsection{Useful Formulas}
\begin{eqnarray*}
\sum_{k=1}^{n}{k}&=&\frac{n(n+1)}{2}\\
\forall r\neq1\ \sum_{k=0}^{n}{r^k}&=&\frac{1-r^{n+1}}{1-r}%\\
%(a+b)^n\ =\ \sum_{k=0}^{n}{(_k^n)a^kb^{n-k}}\ &=&\ \sum_{k=0}^{n}{\frac{n!}{k!(n-k)!}a^kb^{n-k}}
\end{eqnarray*}

\section{Inaccurate Statements, False Proofs and Solutions}
In the next section, you will see a compilation of inaccurate or false
statements, as well as false proofs.  Make sure that you can
actually find the errors (mistakes or inaccuracies).  Also, make sure you
would be able to provide a correct solution.  Solutions are provided at the
end of the section.

\subsection{Inaccurate Statements and False Proofs}

\begin{enumerate}
\item $a \mid b \implies b=ak$.

\item If $\exists (a,b) \in \mathbb{Z}^2$ such that $a\mid b$ and $b \mid
a$, then $a=b$.

\item $\gcd(a,b)=sa+tb$.

\item $x^2 \ge  0\ \forall x \in \mathbb{R}$.

\item Prove the proposition $Q: \gcd(ka,kb)=k\cdot \gcd(a,b)$.

{\bf Proof}: Since the gcd is the smallest linear combination of a and b,
$\exists (s,t) \in \mathbb{Z}^2$ such that $\gcd(ka,kb)=s(ka)+t(kb)$.
Similarly, $\exists (s,t) \in \mathbb{Z}^2$ such that $\gcd(a,b)=sa+tb$.
Therefore, we have: $\gcd(ka,kb)=s(ka)+t(kb)=k(sa+tb)=k.\gcd(a,b)$.
\item Prove that $\forall (x,y) \in {R^+}^2\ \sqrt{xy} \le (x+y)/2$.

{\bf Proof}: First Try! This is easy, since we have:
\begin{eqnarray*}
\sqrt{xy} &\le& \dfrac{x+y}{2}\\
xy &\le& \dfrac{(x+y)^2}{4}\\
4xy &\le& x^2+2xy+y^2\\
0 &\le& x^2-2xy+y^2\\
0 &\le& (x-y)^2.
\end{eqnarray*}
Since $0 \le (x-y)^2$, we have $\sqrt{xy} \le (x+y)/2$.

\item Prove that $\forall (x,y) \in {R^+}^2\ \sqrt{xy} \le (x+y)/2$.

{\bf Proof}: Second Try! Let's try to be more careful and let's use the obvious true fact that:
\[\forall (x,y) \in \mathbb{R}^2,\  0 \le (x-y)^2.\]
We have: 
\begin{eqnarray*}
\forall (x,y) \in \mathbb{R}^2,,\  0 &\le& (x-y)^2.\\
\implies \forall (x,y) \in \mathbb{R}^2,\  0 &\le& x^2-2xy+y2  \mbox{\ \ \ (since $(x-y)^2=x^2-2xy+y^2$)}\\
\implies \forall (x,y) \in \mathbb{R}^2,\  4xy &\le& x^2+2xy+y2 \mbox{\ \ \ (adding $4xy$ on each side)}\\
\implies \forall (x,y) \in \mathbb{R}^2,\  4xy &\le& (x+y)^2 \mbox{\ \ \ (since
$(x-y)^2=x^2+2xy+y^2$)}\\
\implies \forall (x,y) \in \mathbb{R}^2,\  2\sqrt{xy} &\le& (x+y) \mbox{\ \ \ (taking
he square root on each side)}\\
\forall (x,y) \in \mathbb{R}^2,\ \sqrt{xy} &\le& \frac{x+y}{2} \mbox{\ \ \ (dividing by $2$).}
\end{eqnarray*}

Since we worked with implications, the proof is established.

\item Prove that for $c\neq0$, $a \mid b \iff ca \mid cb$.

{\bf Proof}: We can directly prove the equivalence of both propositions. We have :
$a \mid b$ $\iff \exists k \in \mathbb{Z}$ such that $b=ka$
$\iff \exists k \in \mathbb{Z}$ such that $cb=kca$
$ \iff ca \mid cb$, and the proof is completed.

\item  Prove by induction that for any natural number $n$,
\[ 1+2+\dots +n = \sum_{i=1}^{n} \frac{n(n+1)}{2}\]

{\bf Proof}: first try! We prove by induction. 

Induction Hypothesis: Let $P(n)$ be 
\[\forall n, 1+2+\dots +n = \sum_{i=1}^{n}\frac{n(n+1)}{2}\] 
........

\item Prove that $\forall n\in\mathbb{N}^+\ \frac{2}{n(n+1)(n+2)}=\frac{1}{n}-\frac{2}{n+1}+\frac{1}{n+2}$.

{\bf Proof}: We have: 
\[\forall n\in\mathbb{N}^+\  \frac{1}{n(n+1)}=\frac{1}{n}-\frac{1}{n+1}\ and\ \frac{1}{(n+1)(n+2)}=\frac{1}{n+1}-\frac{1}{n+2}\]
Also, we have the following equality: \[\forall n\in\mathbb{N}^+\  \frac{2}{n(n+1)(n+2)}=\frac{1}{n(n+1)}-\frac{1}{(n+1)(n+2)},\]
Therefore, we can write that 
\begin{eqnarray*}
\forall n\in\mathbb{N}^+\  \frac{2}{n(n+1)(n+2)}\\
\iff \frac{1}{n(n+1)}-\frac{1}{(n+1)(n+2)}\\
\iff \frac{1}{n}-\frac{1}{n+1}-(\frac{1}{n+1}-\frac{1}{n+2})\\
\iff \frac{1}{n}-\frac{2}{n+1}+\frac{1}{n+2},
\end{eqnarray*}
which proves the equality.

\item Prove by induction that for any natural number $n$, 
\[ 1+2+\dots +n = \sum_{i=1}^{n} \frac{n(n+1)}{2}\]

{\bf Proof}: second Try! 
\begin{itemize}
\item We prove by induction.
\item Induction Hypothesis: Let $P(n)$ be 
\[1+2+\dots +n = \sum_{i=1}^{n}\frac{n(n+1)}{2}\] 
\item Base case: we have $0=\frac{0(0+1)}{2},$ so $P(0)$ is true.
\item Inductive step: let's assume that $P(n)$ is true for some natural number $n$. We have: 
\begin{eqnarray*}
P(n+1) = 1+2+\dots+n+(n+1)\\   
\implies P(n+1)=\frac{n(n+1)}{2}+(n+1) \mbox{\ \ \ (since we assume $P(n)$ is true)}\\
\implies P(n+1)=1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}
\end{eqnarray*}
\item Therefore, we have proven by induction that for any natural number $n$, 
\[ 1+2+\dots +n = \sum_{i=1}^{n} \frac{n(n+1)}{2}\]
\end{itemize}
\end{enumerate}

\subsection{Solutions}
\begin{enumerate}
\item You need to specify what $k$ is. The previous statement is
inaccurate and, as a consequence, should be considered as
false. Correct statements are:
\begin{itemize} 
\item $a \mid b \iff b=ak$ for some integer $k$, or 
\item $a \mid b \iff b=ak$ for some $k \in \mathbb{Z}$, or
\item $a \mid b \iff \exists k \in \mathbb{Z}$ such that $b=ak$.
\end{itemize}
Note that you should not use quantifiers on the right side of the
expression you want to quantify.
\item  Don't forget that the case $a=-b$ is possible too. These mistakes are often
resulting from lack of attention. Just be careful. Two correct statements would be:
\begin{itemize} 
\item If $\exists (a,b) \in \mathbb{Z}^2$ such that $a \mid b$ and $b \mid a$, then $a=b$ or $a=-b$, or 
\item If $\exists (a,b) \in N^2$ such that $a \mid b$ and $b \mid a$, then $a=b$.
\end{itemize}
\item Once again, you need to specify what s and t are. Correct statements could
be:
\begin{itemize}
\item $\exists (s,t) \in \mathbb{Z}^2$ such that $\gcd(a,b)=sa+tb$, or 
\item $\gcd(a,b)=sa+tb$ for some integers $s$ and $t$.
\end{itemize}
\item As previously mentioned, you should not use quantifiers on the right side of the expression
you want to quantify. Correct statements should be:
\begin{itemize}
\item $x^2\ge 0$ for all $x \in \mathbb{R}$, or 

\item $x^2\ge 0$ for all real numbers $x$, or 

\item $\forall x \in \mathbb{R},\  x^2\ge 0$.
\end{itemize}
\item There are two mistakes in this proof.
\begin{itemize} 

\item The first one is that the gcd of $a$ and $b$ is not the smallest
linear combination of $a$ and $b$. The gcd of $a$ and $b$ is the smallest
\emph{positive} linear combination of $a$ and $b$. Forgetting
\emph{positive} is inaccurate and, as a consequence, false.

\item The second one is more subtle but as important if not more! 
When writing : 
\begin{itemize}
\item $P1 : \exists (s,t) \in \mathbb{Z}^2$ such that $\gcd(ka,kb)=s(ka)+t(kb)=k(sa+tb)$ and 
\item $P2 : \exists (s,t) \in \mathbb{Z}^2$ such that $\gcd(a,b)=sa+tb$, 
\end{itemize}

the integers $s$ and $t$ in $P1$ \emph{do not} have to be the same as the
integers $s$ and $t$ in $P2$.  \textbf{Make sure you understand this
point!} If you had written $P2$ as $P2 : \exists (p,q) \in \mathbb{Z}^2$
such that $\gcd(a,b)=pa+qb$, this fact would have been more obvious.
Therefore, proving that $\gcd(ka,kb)=k\cdot \gcd(a,b)$ by writing that:
$\gcd(ka,kb)=s(ka)+t(kb)=k(sa+tb)=k\cdot \gcd(a,b)$ is completely wrong!
\end{itemize}

\item The proof is what you could call a \emph{backward proof}. The way the
proof is written does not prove anything! The proof shows that $Q
\implies True$, which does not imply that Q is true! I hope that you
clearly understand this point and that you remember the truth table of
$P\implies Q$: if $P$ is false and $Q$ is true or false,
$P\implies Q$ is always true. Therefore, showing that $Q
\implies True$ does not reveal any information about $Q$. 
The two ways to prove this fact would be directly $True\implies Q$ or
by contradiction $\neg Q \implies False$.
On top of the conceptual mistake, $x$ and $y$ are not quantified: we
don't know what they are; are they natural numbers, fractions, integers, real numbers,
others. A good proof would specify that $(x,y)$ are positive real numbers.

\item Once again, there is a small but important mistake in this
proof. If your proof were correct, this would mean that you would have
proven that $ 1\le -1$ (take $x=-1$ and $y=-1$ for instance). 
So where is the problem then ? In the written proof $x$ and $y$ are
assumed to be real numbers, which means that they could be negative
numbers. But if $x<0$, then $\sqrt{x^2}=-x$. This means that you have
to be careful about what you have to prove. The expression has to be
proven for positive real numbers, so a correct proof should be:
\begin{eqnarray*}
\forall (x,y) \in {\mathbb{R}^+}^2,\  0 &\le& (x-y)^2.\\
\implies \forall (x,y) \in {\mathbb{R}^+}^2,\  0 &\le& x^2-2xy+y2  \mbox{\ \ \ (since $(x-y)^2=x^2-2xy+y^2$)}\\
\implies \forall (x,y) \in {\mathbb{R}^+}^2,\  4xy &\le& x^2+2xy+y2 \mbox{\ \ \ (adding $4xy$ on each side)}\\
\implies \forall (x,y) \in {\mathbb{R}^+}^2,\  4xy &\le& (x+y)^2 \mbox{\ \ \ (since$(x-y)^2=x^2+2xy+y^2$)}\\
\implies \forall (x,y) \in {\mathbb{R}^+}^2,\  2\sqrt{xy} &\le& (x+y) \mbox{\ \ \ (taking
the square root on each side)}\\
\forall (x,y) \in {\mathbb{R}^+}^2,\ \sqrt{xy} &\le& \frac{x+y}{2} \mbox{\ \ \ (dividing by
$2$).}
\end{eqnarray*}

Another way to prove it would be by equivalence:
\begin{eqnarray*}
\forall (x,y) \in {\mathbb{R}^+}^2,\ \sqrt{xy} &\le& \frac{x+y}{2}\\
\iff \forall (x,y) \in (\mathbb{R}^+)^2,\  2\sqrt{xy} &\le& (x+y)\\
\iff \forall (x,y) \in (\mathbb{R}^+)^2,\  4xy &\le& (x+y)^2\\
\iff \forall (x,y) \in (\mathbb{R}^+)^2,\  4xy &\le& x^2+2xy+y2\\
\iff \forall (x,y) \in (\mathbb{R}^+)^2,\  0 &\le& x^2-2xy+y2\\
\forall (x,y) \in (\mathbb{R}^+)^2,\  0 &\le& (x-y)^2.
\end{eqnarray*}

Since we worked by equivalence, and the last proposition is true, the
initial proposition is true. Therefore, we have proven the
proposition.
Working by equivalence is correct has long as you make sure that
everything is really equivalent. 

\item Once again the proof is incorrectly written. The proposition
\[ P1 : \iff \exists k \in \mathbb{Z} \mbox{\ such that\ } b=ka \] 
is not equivalent
to 
\[ P2 : \iff \exists k \in \mathbb{Z} \mbox{\ such that\ } cb=kca\]
unless $c\neq0$ is explicitly written!
You have 
\[\forall c\in \mathbb{R}\ P1 \implies P2,\]
but what you need in this proof is 
\[\forall c\in \mathbb{R}, c\neq 0 \implies \ P1 \iff P2.\]

If the quantifier $\forall c\in \mathbb{R}$ is forgotten in your proof,
the proof becomes false!  A correct proof would be:\\
\begin{eqnarray*}
a \mid b &\iff & \exists k \in \mathbb{Z} \mbox{ such that } b=ka\\
&\iff & \exists k \in \mathbb{Z} \mbox{ s.t. } cb=kca, \mbox{ since } c\neq0\\
&\iff & ca \mid cb,
\end{eqnarray*}

and the proof is completed.

\item The induction hypothesis should be a predicate with $n$ being the free
variable. So it should not contain the quantifier $\forall n$. In other
words, the prove should go as follows:

{\bf Proof}: We prove by induction. 

Induction Hypothesis: Let $P(n)$ be 
\[1+2+\dots +n = \sum_{i=1}^{n}\frac{n(n+1)}{2}.\] 
........

\item The equivalence symbol '$\iff$' should be used to state the equivalence of propositions only. It does not make sense to use '$\iff$' instead of '$=$' in a proof. The proof should go as follow:

{\bf Proof}: We have: 
\[\forall n\in\mathbb{N}^+\  \frac{1}{n(n+1)}=\frac{1}{n}-\frac{1}{n+1}\ and\ \frac{1}{(n+1)(n+2)}=\frac{1}{n+1}-\frac{1}{n+2}\]
Also, we have the following equality: \[\forall n\in\mathbb{N}^+\  \frac{2}{n(n+1)(n+2)}=\frac{1}{n(n+1)}-\frac{1}{(n+1)(n+2)},\]
Therefore, we can write that: 
\begin{eqnarray*}
\forall n\in\mathbb{N}^+\  \frac{2}{n(n+1)(n+2)}=\frac{1}{n(n+1)}-\frac{1}{(n+1)(n+2)}\\
\iff \forall n\in\mathbb{N}^+\  \frac{2}{n(n+1)(n+2)}=\frac{1}{n}-\frac{1}{n+1}-(\frac{1}{n+1}-\frac{1}{n+2})\\
\iff \forall n\in\mathbb{N}^+\  \frac{2}{n(n+1)(n+2)}=\frac{1}{n}-\frac{2}{n+1}+\frac{1}{n+2},
\end{eqnarray*}
which proves the equality.

\item If $P(n)$ is defined as the predicate of the induction proof, $P(n)$ can only be true or false. Therefore, you should not use $P(n)$ in an equality with numbers. In other words, 
\[P(n+1) = 1+2+\dots+n+(n+1)\] does not make any sense. The proof should go as follows:

{\bf Proof}: 
\begin{itemize}
\item We prove by induction.
\item Induction Hypothesis: Let $P(n)$ be 
\[1+2+\dots +n = \sum_{i=1}^{n}\frac{n(n+1)}{2}\] 
Let's call $S(n)$ the following sum: \[S(n)=1+2+\dots+n\].
\item Base case: we have $S(0)=0=\frac{0(0+1)}{2},$ so $P(0)$ is true.
\item Inductive step: let's assume that $P(n)$ is true for some natural number $n$. We have: 
\begin{eqnarray*}
S(n+1) = 1+2+\dots+n+(n+1)\\   
\implies S(n+1)=\frac{n(n+1)}{2}+(n+1) \mbox{\ \ \ (since we assume $P(n)$ is true)}\\
\implies S(n+1)=1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}
\end{eqnarray*}
\item Therefore, we have proven by induction that for any natural number $n$, 
\[ 1+2+\dots +n = \sum_{i=1}^{n} \frac{n(n+1)}{2}\]
\end{itemize}
\end{enumerate}

\end{document}

