\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,latexsym, hyperref}

\begin{document}
\begin{center}
\textbf{Math 3100 Test 01 Key}

Michel Smith

February 16, 2024
\end{center}

Show all your work for each problem, if the work is incomplete or incorrect you may not receive full credit for that problem. Indicate your reasoning, partial credit will be given if the reasoning is correct and only computational errors are made. If you do scratch work, indicate what is scratch work; no credit will be taken off for errors in the scratch work.

\

\noindent
Problem 1. Determine if the following two logic statements are equivalent:
\begin{eqnarray*}
(\sim P) \Rightarrow Q & \mbox{and} & (\sim Q) \Rightarrow P.
\end{eqnarray*}

\begin{proof}  We use the truth tables to answer the question:

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$P$ & $Q$ &  $\sim P$ & $\sim P \Rightarrow Q$ & $\sim Q$ & $\sim Q \rightarrow P$ \\
\hline
$T$ & $T$ &  $F$ & $T$ & $F$ & $T$ \\
$T$ & $F$ &  $F$ & $T$ & $T$ & $T$ \\
$F$ & $T$ &  $T$ & $T$ & $F$ & $T$ \\
$F$ & $F$ &  $T$ & $F$ & $T$ & $F$ \\
\hline
\end{tabular}
\end{center}
Since columns four and six match, it follows that they are equivalent,
\end{proof}

\

\noindent
Problem 2.  Prove two of the following theorems about the integers using the axioms of the integers, make sure to indicate the reason for each step.   However, you may assume the usual rules (axioms) about associativity and commutativity of both multiplication and addition; so you do not have to indicate reasons for using associativity and commutativity .  [If you do all three, I will grade the best two out of three.]

a.  Theorem.  If $a$ is an integer, then $0\cdot a = 0$.
\begin{proof}
Suppose that $a$ is an integer.  Then:

\begin{eqnarray}
 0 \cdot a & = & (0 + 0)\cdot a \\
  & = & 0 \cdot a + 0 \cdot a  \\
 0 \cdot a - 0\cdot a & = & 0 \cdot a + 0 \cdot a  - 0\cdot a \\
 0 & = & 0 \cdot a + 0 \\
 0 & = & 0 \cdot a  \\
 0 \cdot a & = & 0. \nonumber
\end{eqnarray}
Reasoning:

(1) Property of the additive identity;

(2) Distribution axiom;

(3) Adding the additive inverse of $0\cdot a$ to both sides of the equation;

(4) Property of the additive inverse;

(5) Property of the additive identity.
\end{proof}


b.  Theorem.  The additive identity is unique.
\begin{proof}  Suppose that integer $x$ is another additive identity. Then

\begin{eqnarray}
 0 + x & = & x \\
 0 + x & = & 0 \\
 0 & = & x.
\end{eqnarray}

Reasoning:

(6) Property of the additive identity;

(7) By the assumption that $x$ is also an additive identity;

(8) By the transitive property of the equal sign from equations (6) and (7).
\end{proof}

c.  Theorem.  If $a$ is an integer, then $-a = -1\cdot a$.
\begin{proof} Given that $a$ is an integer we have:
\begin{eqnarray}
 a + -1 \cdot a & = & 1 \cdot a + -1 \cdot a \\
  & = & (1 -1) \cdot a \\
  & = & 0 \cdot a \\
  & = & 0 \\
 a + -a & = & 0.
\end{eqnarray}
Therefore:
\begin{eqnarray}
 a + -1 \cdot a & = & a + -a \\
 -a + a + -1 \cdot a & = & -a + a + -a \nonumber \\
0 + -1 \cdot a & = & 0 + -a \\
 -1 \cdot a & = &  -a \\
-a & = &   -1 \cdot a.  \nonumber
\end{eqnarray}
Reasoning:

(10) Distributive axiom;

(11) Property of the additive inverse $-1$;

(12) By the proof of problem 2a (which may be considered a lemma to this problem):

(13) Property of the additive inverse;

(14) Transitive property of the equal sign from equations (12) and (13);

(15) Property of the additive inverse $-a$;

(16) Property of the additive identity.
\end{proof}

\

\noindent
Problem 3.  Prove for each positive integer $n$, that $3|(2n^3+n)$.
\begin{proof}  We prove the statement by induction.  First we verity the statement for $n=1$; for $n=1$ we have $2n^3 + n = 2+1 = 3$ which is divisible by $3$.  Our induction hypothesis is that for the integer $k \ge 1$ there exists an integer $q$ so that $2k^3 + k = 3 q$.  Then for $n=k+1$ we have,
\begin{eqnarray*}
 2(k+1)^3 + k+1 & = & 2(k^3+3k^2+3k +1) + k + 1 \\
   & = & 2k^3+6k^2+6k +2 + k + 1 \\
   & = & 2k^3 + k +6k^2+6k +3  \\
   & = & 3q +6k^2+6k +3  \\
   & = & 3(q +2k^2+2k +1).
\end{eqnarray*}
So the quantity is divisible by $3$ and so we have shown that if the statement is true for $n=k$ then it's true for $n=k+1$ so the statement follows from the induction axiom.
\end{proof}

\

\noindent
Problem 4.  Prove the following identity.
\begin{eqnarray*}
\sum_{i=1}^n i(i+1)  & = &  \frac{n(n+1)(n+2)}3.
\end{eqnarray*}
\begin{proof}
 We prove the statement by induction.  First we verity the statement for $n=1$; for $n=1$ we have:
\begin{eqnarray*}
 Leftside & = & \sum_{i=1}^1 i(i+1)  = 1\cdot( 1 + 1) = 2 \\
Rightside & = & \frac{1 \dot (1+1)(1+2)}3 = \frac{6}3 = 2,
\end{eqnarray*}
which verifies the statement for $n=1$'  Our induction hypothesis is that for the integer $k \ge 1$  we have:
\begin{eqnarray*}
\sum_{i=1}^k i(i+1)  & = &  \frac{k(k+1)(k+2)}3
\end{eqnarray*}
Next consider
\begin{eqnarray*}
\sum_{i=1}^{k+1} i(i+1)  & = &  \sum_{i=1}^k i(i+1)  + (k+1)(k+2) \\
  & = & \frac{k(k+1)(k+2)}3 + (k+1)(k+2) \\
  & = & \frac{k(k+1)(k+2)}3 + \frac{3(k+1)(k+2)}{3} \\
  & = & \frac{(k+1)(k+2)(k+3)}3.  
\end{eqnarray*}
Where the second equation follows from the induction hypothesis and the fourth equation from factoring.  And thus we have shown that if the statement is true for $n=k$ then it's true for $n=k+1$ so the theorem follows from the induction axiom.
\end{proof}

\

\noindent
Problem 5. Prove the following Fibonacci identity.
\begin{eqnarray*}
\sum_{i=1}^n F_{2i-1}  & = &  F_{2n} .
\end{eqnarray*}
\begin{proof}  We prove the statement by induction.  First we verity the statement for $n=1$; for $n=1$ we have:
\begin{eqnarray*}
 Leftside & = & \sum_{i=1}^1 F_{2i-1} = F_1 = 1 \\
Rightside & = & F_{2 \cdot 1} = F_2 = 1,
\end{eqnarray*}
which verifies the statement for $n=1$.  Our induction hypothesis is that for the integer $k \ge 1$  we have:
\begin{eqnarray*}
\sum_{i=1}^k F_{2i-1}  & = &  F_{2k} .
\end{eqnarray*}
Next consider 
\begin{eqnarray*}
\sum_{i=1}^{k+1} F_{2i-1}  & = &  \sum_{i=1}^k F_{2i-1} + F_{2k+1} \\
  & = & F_{2k} +  F_{2k+1} \\
  & = & F_{2k+2} = F_{2(k+1)}.
\end{eqnarray*}
Where the second equation follows from the induction hypothesis.  So we have shown that if the statement is true for $n=k$ then it's true for $n=k+1$ so the theorem follows from the induction axiom.
\end{proof}


\newpage

\noindent
Problem 6.  Suppose that each of $a$ and $b$ is a positive integer.  Let $S$ be the following set:
$$S = \{a-bq \ge 0 | q \ge 0 \}.$$

a.  Prove that if $0 \in S$ then $a|b$.
\begin{proof}  If $0 \in S$ the there exists an integer $q$ so that $a-bq = 0$ then $a = bq$ and so $b|a$.  

Now, I didn't realize (until I started the grading process) that I wrote the conclusion backwards.  It should have said, ``if $0 \in S$ then $b|a$.'' So, since I made the mistake,  everyone will get full credit for this part of problem 6.
\end{proof}


b.  Prove that if $r$ is the least member of $S$, then $r<b$.
\begin{proof} If $r=0$ then clearly, since $b$ is positive, we have $r<b$.  So we may assume that $r>0$.  Suppose then that $r \ge b$.  By the definition of $S$, there is an integer $q$ so that $r=a-bq$.  Then:
\begin{eqnarray*}
r  & \ge & b \\
a-bq & \ge & b \\
a-bq -b & \ge & 0 \\
a-b(q+1) & \ge & 0. 
\end{eqnarray*}
So the integer $a-b(q+1) \in S $. And we claim that this integer is less than $r$ which would contradict our assumption that $r$ is the least integer in $S$, 
\begin{proof}[Proof of Claim.]
\begin{eqnarray*}
0  & < & 1 \\
q+0 & < & q +1 \\
bq & < & b(q+1) \\
-bq & > & - b(q+1) \\
a -bq & > & a - b(q+1) \\
r & > & a - b(q+1).
\end{eqnarray*}
\end{proof} \end{proof}


\

\noindent Extra Credit: Prove the following Fibonacci identity.
\begin{eqnarray*}
\sum_{i=1}^n F_i^2 & = &  F_nF_{n+1}.
\end{eqnarray*}
\begin{proof}
 We prove the statement by induction.  First we verity the statement for $n=1$; for $n=1$ we have:
\begin{eqnarray*}
 Leftside & = & \sum_{i=1}^1 F_1^2  = 1^2 = 1 \\
Rightside & = & F_1F_{1+1}= 1 \cdot 1 = 1,
\end{eqnarray*}
which verifies the statement for $n=1$'  Our induction hypothesis is that for the integer $k \ge 1$  we have:
\begin{eqnarray*}
\sum_{i=1}^k F_i^2 & = &  F_kF_{k+1}.
\end{eqnarray*}
Next consider
\begin{eqnarray*}
\sum_{i=1}^{k+1} F_i^2  & = &  \sum_{i=1}^k F_i^2 + F_{k+1}^2 \\
  & = & F_k F_{k+1} + F_{k+1}^2 \\
  & = & (F_k+ F_{k+1})F_{k+1}\\
  & = & (F_{k+2})F_{k+1} \\
  & = & F_{k+1}F_{(k+1)+1} 
\end{eqnarray*}
Where the second equation follows from the induction hypothesis.  So we have shown that if the statement is true for $n=k$ then it's true for $n=k+1$ so the theorem follows from the induction axiom.
\end{proof}


\end{document}