% 
% hw1.tex
%
%   This is a LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}

\usepackage{amssymb,amsmath,pstricks,framed}
\usepackage{color}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}

% *** GRAPHICS RELATED PACKAGES ***
%

\usepackage[pdftex]{graphicx}
 \graphicspath{{./}}
 \DeclareGraphicsExtensions{.pdf,.jpeg,.png}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Data, Logic, and Computing\\[2ex] 
       \rm\normalsize ECS 17 (Winter 2022)}
\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle
\section*{\underline{Midterm 2: solutions}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1 \emph{(2 questions, 20 points total)}}

\textcolor{blue}{\emph{Let $n$ be an integer. Give a direct proof and an indirect proof of the proposition, if $n$ is odd then $2n^2+5n+2$ is odd}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{itemize}
\item[$p$: ] $n$ is odd
\item[$\lnot p$:] $n$ is even
\item[$q$: ] $2n^2+5n+2$ is odd
\item[$\lnot q$: ] $2n^2 + 5n+2$ is even
\end{itemize}
We use two methods of proof:
\begin{itemize}
\item[a)] Direct proof: we show $p \rightarrow q$ is true.

Let us assume that $p$ is true, i.e. that $n$ is odd. There exists and integer $k$ such that $n=2k+1$. Therefore,
\begin{eqnarray*}
2n^2 + 5n + 2 &=& 2(2k+1)^2 + 5(2k+1) + 2 \\
&=& 8k^2 + 18k + 9 \\
&=& 2(4k^2+9k+4)+1
\end{eqnarray*}
As $k$ is an integer, $4k^2+9k+4$ is an integer which we call $l$. Therefore $2n^2+5n+2=2l+1$, i.e. it is odd.

We have shown that $q$ is true when $p$ is true: the proposition $p\rightarrow q$ is true.

\item[b)] Indirect proof: we show $\lnot q \rightarrow \lnot p$ is true.

Let us assume that $\lnot q$ is true, i.e. that $2n^2+5n+2$ is even. There exists and integer $k$ such that $2n^2+5n+2=2k$. Therefore,
\begin{eqnarray*}
2n^2  +4n + n + 2&=& 2k \\
n &=& 2k - 2n^2 - 4n -2 \\
&=& 2(k-n^2-2n-1) 
\end{eqnarray*}
As $k$ and $n$ are integers, $k-n^2-2n-1$ is an integer which we call $l$. Therefore $n=2l$, i.e. it is even.

We have shown that $\lnot p$ is true when $\lnot q$ is true: the proposition $\lnot q \rightarrow \lnot p$ is true and, by equivalence, $p\rightarrow q$ is true.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $m$ and $n$ be 2 integers. Using the method of proof of your choice, show that if $mn$ is odd, then $m$ is odd and $n$ is odd.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{itemize}
\item[$p$: ] $mn$ is odd
\item[$\lnot p$:] $mn$ is even
\item[$q$: ] $m$ is odd and $n$ is odd
\item[$\lnot q$: ] $m$ is even or $n$ is even
\end{itemize}

We use an indirect proof: we show that $\lnot q \rightarrow \lnot p$ is true.

Let us assume that $\lnot q$ is true, namely that $m$ is even or $n$ is even. We consider two cases:
\begin{itemize}
\item [a)] $m$ is even. There exists an integer $k$ such that $m=2k$. Then,
\begin{eqnarray*}
mn &=& 2kn \\
&=& 2(kn)
\end{eqnarray*}
As $k$ and $n$ are integers, $kn$ is an integer which we call $l$. Therefore $mn=2l$, i.e. it is even.
\item [b)] $n$ is even. There exists an integer $k$ such that $n=2k$. Then,
\begin{eqnarray*}
mn &=& 2km \\
&=& 2(km)
\end{eqnarray*}
As $k$ and $m$ are integers, $km$ is an integer which we call $l$. Therefore $mn=2l$, i.e. it is even.
\end{itemize}
In both cases, we have shown that $mn$ is even. Therefore $\lnot p$ is true when $\lnot q$ is true. the proposition $\lnot q \rightarrow \lnot p$ is true and, by equivalence, $p\rightarrow q$ is true.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $n$ be an integer. Use a proof by contradiction to show that $\frac{6n+1}{2n+4}$ is not an integer.}}

\vspace{0.1in}
Let:

$P$: $\frac{6n+1}{2n+4}$ is not an integer

We use a proof by contradiction. We \textbf{assume} that $P$ is false, i.e. we assume that $\frac{6n+1}{2n+4}$ is an integer. Let us name this integer as $k$. We have:
\begin{eqnarray*}
\frac{6n+1}{2n+4} = k
\end{eqnarray*}
which we rewrite as:
\begin{eqnarray*}
6n+1 = k(2n+4)
\end{eqnarray*}
Let $LHS=6n+1$ and $RHS=k(2n+4)$. Notice that:
\begin{eqnarray*}
LHS = 2(3n)+1
\end{eqnarray*}
Since $n$ is an integer, $3n$ is an integer and therefore $LHS$ is odd. Conversely,
\begin{eqnarray*}
RHS = 2(k(n+2))
\end{eqnarray*}
As $k$ and $n$ are integers, $k(n+2)$ is an integer which we call $l$. Therefore $RHS=2l$, i.e. it is even.

Under the assumption that $P$ is false, we find that $LHS=RHS$ with $LHS$ odd and $RHS$ even. Since an even number cannot be equal to an odd number, we have reached a contradiction.
Therefore the assumption that $P$ is false, is false, i.e. $P$ is true.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $n$ be a natural number (i.e., $n$ is a positive integer different from 0). Use a proof by contradiction to show that if $n$ is a perfect square, then $2n$ is not a perfect square. (A natural number $n$ is a perfect square if and only if there exists an integer $k$ such that $n=k^2$).}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{itemize}
\item[$p$: ] $n$ is a perfect square
\item[$\lnot p$:] $n$ is not a perfect square
\item[$q$: ] $2n$ is not a perfect square
\item[$\lnot q$: ] $2n$ is a perfect square
\end{itemize}

We use a proof by contradiction. We assume that $p \rightarrow q$ is false, i.e. that $p$ is true AND $q$ is false.

Since $p$ is true, $n$ is a perfect square: there exists an integer $k$ such that $n=k^2$.

Since $q$ is false, $2n$ is a perfect square: there exists an integer $l$ such that $2n=l^2$.

Replacing $n$ by $k^2$, we get:
\begin{eqnarray*}
2k^2= l^2
\end{eqnarray*}
As $n$ is non zero, $l$ is not zero. Therefore:
\begin{eqnarray*}
2= \frac{k^2}{l^2}
\end{eqnarray*}
Taking the square root (the numbers are now real),
\begin{eqnarray*}
\sqrt{2}= \frac{|k|}{|l|}
\end{eqnarray*}
As $k$ is an integer, $|k|$ is an integer. Similarly, as $l$ is an integer, $|l|$ is an integer. This would lead to $\sqrt{2}$ is rational: this is a contradiction, as we know that $\sqrt{2}$ is irrational.

Therefore the assumption that $p \rightarrow q$  is false, is false, i.e.  $p \rightarrow q$ is true.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $x$ be a real number. Show that if $x^3+x^2-2x < 0$, then $x < 1$.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{itemize}
\item[$p$: ] $x^3+x^2-2x < 0$
\item[$\lnot p$:] $x^3+x^2-2x \ge 0$
\item[$q$: ] $x<1$
\item[$\lnot q$: ] $x\ge 1$
\end{itemize}

We use an indirect proof, i.e. we prove that $\lnot q \rightarrow \lnot p$ is true. We assume that $\lnot q$ is true, i.e. that $x\ge 1$.

Let $A = x^3+x^2-2x$. Notice that,
\begin{eqnarray*}
A &=& x^3+x^2-2x \\
&=&x(x-1)(x+2)
\end{eqnarray*}
We know that:
\begin{itemize}
\item[i)] $x >0$ since $x\ge 1$
\item[ii)] $x-1\ge 0$ since $x\ge 1$
\item[iii)] $x+2 > 0$ since $x\ge 1$
\end{itemize}
The three terms in $A$ are positive: $A$ is positive. Therefore $\lnot p$ is true.

We have shown that $\lnot p$ is true when $\lnot q$ is true. the proposition $\lnot q \rightarrow \lnot p$ is true and, by equivalence, $p\rightarrow q$ is true.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Prove or disprove that there exits an integer $n$ such that $n^2+3n+2$ is odd.}}

\vspace{0.1in}
Let:

$P:$ There exists an integer $n$ such that $n^2+3n+2$ is odd

\vspace{0.1in}
$P$ is likely to be false. To prove that it is false, we need to show that $\lnot P$ is true, namely that

\vspace{0.1in}
$\lnot P:$ For all integers $n$, $n^2+3n+2$ is even. 

\vspace{0.1in}
We use a proof by case:
\begin{itemize}
\item[case a)] $n$ is even.

There exists an integer $k$ such that $n=2k$. Then,
\begin{eqnarray*}
n^2 + 3n + 2 &=& (2k)^2 + 3(2k) + 2 \\
&=& 4k^2 + 6k + 2 \\
&=& 2(2k^2+3k+1)
\end{eqnarray*}
As $k$ is an integer, $2k^2+3k+1$ is an integer which we call $l$. Therefore $n^2+3n+2=2l$, i.e. it is even.

\item[case b)] $n$ is odd.

There exists an integer $k$ such that $n=2k+1$. Then,
\begin{eqnarray*}
n^2 + 3n + 2 &=& (2k+1)^2 + 3(2k+1) + 2 \\
&=& 4k^2 + 4k+1 + 6k + 3 + 2 \\
&=& 2(2k^2+5k+3)
\end{eqnarray*}
As $k$ is an integer, $2k^2+5k+3$ is an integer which we call $l$. Therefore $n^2+3n+2=2l$, i.e. it is even.
\end{itemize}
In all cases, $n^2 + 3n + 2$ is even.

We have shown that $\lnot P$ is true, therefore the original proposition $P$ is false.

\end{document}