1 files changed, 227 insertions, 0 deletions
diff --git a/gupta/hw6.tex b/gupta/hw6.tex
new file mode 100644
index 0000000..4362d26
--- /dev/null
+++ b/gupta/hw6.tex
@@ -0,0 +1,227 @@
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+\font\bigbf=cmbx12 at 24pt
+
+\def\answer{\smallskip{\bf Answer.}\par}
+\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
+depth 0pt{\parfillskip0pt\medskip}}
+\let\endanswer\endproof
+\def\section#1{\medskip\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in%
+\noindent{\bf #1}}
+\let\impl\to
+\def\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+\def\problem#1{\par\penalty-100\item{#1}}
+
+\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday
+2022-02-17 at 11:59 pm}\hrule height .5pt}}
+
+\centerline{\bigbf Homework 6 - Holden Rohrer}
+\bigskip
+
+\noindent{\bf Collaborators:} None
+
+\section{Hammack 10: 4, 8, 20, 26}
+Prove the following statements with either induction, strong induction,
+or proof by smallest counterexample.
+
+\problem{4.} If $n\in\bb N,$ then $1\cdot 2 + 2\cdot 3 + 3\cdot 4 +
+4\cdot 5 + \cdots + n(n+1) = {n(n+1)(n+2)\over 3}.$
+
+\answer
+We will show that $\sum_{k=1}^n k(k+1) = {n(n+1)(n+2)\over 3}$ by
+induction.
+
+For the case $n = 1,$ $1\cdot 2 = {1(1+1)(1+2)\over 3} = 6/3 = 2.$
+
+In the inductive case, assume that this statement is true for some $n
+\geq 1,$ giving
+$$\sum_{k=1}^n k(k+1) = {n(n+1)(n+2)\over 3}.$$
+We will show that this statement is true for $n+1:$
+$$\sum_{k=1}^{n+1} k(k+1) = {(n+1)(n+2)(n+3)\over 3}.$$
+This is true only if
+$$\sum_{k=1}^{n+1} k(k+1) - \sum_{k=1}^n k(k+1) = (n+1)(n+2) =
+{(n+1)(n+2)(n+3)\over 3} - {n(n+1)(n+2)\over 3}.$$
+
+$${(n+1)(n+2)(n+3)\over 3} - {n(n+1)(n+2)\over 3} =
+{(n+3-n)(n+1)(n+2)\over 3} = (n+1)(n+2),$$
+thus proving the statement for $n+1.$
+
+Therefore, this identity is true for all $j\in\bb N.$
+\endanswer
+
+\problem{8.} If $n\in\bb N,$ then ${1\over 2!} + {2\over 3!} + {3\over
+4!} + \cdots + {n\over (n+1)!} = 1 - {1\over (n+1)!}$
+
+\answer
+We will show this statement for all $n\in\bb N$ by induction.
+
+In the base case $n = 1,$ ${1\over 2!} = 1/2 = 1 - {1\over 2!},$ so the
+statement is true.
+
+In the inductive case, assume that the statement is true for some $n\geq
+1.$ We will show the statement for $n+1:$
+$${1\over 2!} + {2\over 3!} + \cdots + {n+1\over (n+2)!} = 1 - {1\over
+(n+2)!}.$$
+Then,
+$$1-{1\over (n+2)!} = 1-{n+2\over(n+2)!}+{n+1\over (n+2)!} = 1-{1\over
+(n+1)!} + {n+1\over (n+2)!}.$$
+By the inductive hypothesis,
+$$1-{1\over (n+1)!} + {n+1\over (n+2)!} = {1\over 2!} + {2\over 3!} +
+\cdots + {n\over (n+1)!} + {n+1\over (n+2)!},$$
+proving our inductive step.
+
+Therefore, for all $j\in\bb N,$ this identity is true.
+\endanswer
+
+\problem{20.} Prove that $(1+2+3+\cdots+n)^2 = 1^3 + 2^3 + 3^3 + \cdots
++ n^3$ for every $n\in\bb N.$
+
+\answer
+We will show this identity for all $n\in\bb N$ by induction.
+
+In the base case, $1^2 = 1^3,$ so the statement is immediate.
+
+In the inductive case, assume $(1+2+3+\cdots+k)^2 = 1^3 + 2^3 + 3^3 +
+\cdots + k^3$ for some $k\in\bb N.$
+We will show that $(1+2+3+\cdots+k+(k+1))^2 = 1^3 + 2^3 + 3^3 + \cdots +
+(k+1)^3.$
+
+$$(1+2+\cdots+k+(k+1))^2 = (1+2+\cdots+k)^2 + 2(1+2+\cdots+k)(k+1) +
+(k+1)^2.$$
+With the result $1+2+\cdots+k = {k(k+1)\over 2},$
+we get this equal to
+$$(1+2+\cdots+k)^2 + k(k+1)(k+1) + 1(k+1)^2,$$
+and from the inductive hypothesis, this is equal to
+$$1^3 + 2^3 + \cdots + k^3 + k(k+1)(k+1) + 1(k+1)^2 = 1^3 + 2^3 + \cdots
++ k^3 + (k+1)^3.$$
+
+We have thus proven that for any $n\in\bb N,$ $(1+2+3+\cdots+n)^2 = 1^3
++ 2^3 + 3^3 + \cdots + n^3.$
+\endanswer
+
+\problem{26.} Concerning the Fibonacci sequence, prove that
+$\sum_{k=1}^n F_k^2 = F_nF_{n+1}.$
+
+\answer
+We will show this identity, for all $n\in\bb Z$ s.t. $n\geq 1,$ by
+induction.
+
+For $n=1,$ $F_1^2 = 1 = F_1F_2.$
+
+Assume for some $n\geq 1,$ $\sum_{k=1}^n F_k^2 = F_nF_{n+1}.$
+We will show the statement for $n+1:$
+$$\sum_{k=1}^{n+1} F_k^2 = F_{n+1}F_{n+2}.$$
+We get the following from the definition of the Fibonacci numbers above
+2:
+$$F_{n+1}F_{n+2} = F_{n+1}(F_n + F_{n+1}) = F_{n+1}^2 + F_{n+1}F_n,$$
+and from our inductive hypothesis,
+$$F_{n+1}^2 + F_{n+1}F_n = F_{n+1}^2 + \sum_{k=1}^n F_k^2 =
+\sum_{k=1}^{n+1} F_k^2,$$
+completing our inductive step.
+
+This shows that for all $j\in\bb Z,$ where $j\geq 1,$
+$$\sum_{k=1}^j F_k^2 = F_jF_{j+1}.$$
+\endanswer
+
+\section{Hammack 11.1: 4, 14, 15}
+
+\problem{4.}
+Let $A = \{a,b,c,d\}.$ Suppose $R$ is the relation
+$$\vbox{\halign{&\quad$#$\quad\cr
+    R&=&\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(a,c),(c,a),\cr
+    &&(a,d),(d,a),(b,c),(c,b),(b,d),(d,b),(c,d),(d,c)\}\cr
+}}$$
+Is R Reflexive? Symmetric? Transitive? If a property does not hold, say
+why.
+
+\answer
+This is reflexive, symmetric, and transitive.
+\endanswer
+
+\problem{14.}
+Suppose $R$ is symmetric and transitive relation on set $A,$ and there
+is an element $a\in A$ for which $aRx$ for every $x\in A.$ Prove that
+$R$ is reflexive.
+
+\answer
+For every $x\in A,$ $aRx$ is given and $xRa$ by symmetry. By
+transitivity, $xRx$ for every element, so the relationship is reflexive.
+\endanswer
+
+\problem{15.} Prove or disprove: if a relation is symmetric and
+transitive, then it is also reflexive.
+
+\answer
+The empty relation $\emptyset$ is vacuously symmetric and transitive but
+on a nonempty set containing $x,$ the empty relation doesn't contain
+$(x,x).$
+\endanswer
+
+\section{Hammack 11.2: 6, 8, 10, 12}
+
+\problem{6.} Let $A = \{1,2,3,4,5,6\},$ and consider the following
+equivalence relation on $A:$ $$R =
+\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,3),(3,2),(4,5),(5,4),(4,6),
+(6,4),(5,6),(6,5)\}.$$
+List the equivalence classes of $R.$
+
+\answer
+The equivalence classes are $\{2,3\},$ $\{4,5,6\},$ and $\{1\}.$
+\endanswer
+
+\problem{8.} Define a relation $R$ on $\bb Z$ as $xRy$ if and only if
+$x^2+y^2$ is even. Prove $R$ is an equivalence relation. Describe its
+equivalence classes.
+
+\answer
+$R$ is reflexive, symmetric, and transitive, so it is an equivalence
+relation.
+The relation is reflexive because $x^2 + x^2 = 2(x^2),$ and $x^2\in\bb
+Z,$ so the sum is even.
+The relation is symmetric because $x^2 + y^2 = y^2 + x^2,$ so the left
+side is even if and only if the right side is even.
+And for some $j,k\in\bb Z,$ $xRy$ and $yRz$ implies $x^2+y^2 = 2j$ and
+$y^2+z^2 = 2k,$ so $x^2 + y^2 + y^2 + z^2 - 2y^2 = x^2 + z^2 =
+2(j+k-y^2).$
+The number $j+k-y^2\in\bb Z,$ so $xRz,$ and the relation is transitive.
+
+The equivalence classes are the even numbers and the odd numbers.
+\endanswer
+
+\problem{10.} Suppose $R$ and $S$ are two equivalence relations on a set
+$A.$ Prove that $R\cap S$ is also an equivalence relation.
+
+\answer
+The equivalence relations $R$ and $S$ on $A$ are, by definition,
+reflexive, symmetric, and transitive.
+$R\cap S$ is therefore reflexive because $x\in A$ implies $(x,x)\in R$
+and $(x,x)\in S,$ (by reflection), so $(x,x)\in R\cap S.$
+
+Only if $xRy$ and $xSy,$ $x(R\cap S)y,$ and by symmetry, $yRx$ and
+$ySx,$ so $y(R\cap S)x,$ giving symmetry of the new relation.
+
+Similarly, if $x(R\cap S)y$ and $y(R\cap S)z,$ $xRy$ and $xRz,$ so by
+transitivity, $xRz,$ and similarly, $xSz,$ so $x(R\cap S)z,$ making the
+intersection of any equivalence relations also an equivalence relation.
+\endanswer
+
+\problem{12.} Prove or disprove: If $R$ and $S$ are two equivalence
+relations on a set $A,$ then $R\cup S$ is also an equivalence relation
+on $A.$
+
+\answer
+{\bf Disproof.}
+
+Let $R$ be a relation with equivalence classes $\{1,2\}, \{3\}$ and $S$
+be a relation with equivalence classes $\{1\}, \{2,3\}.$ $\{(1,2),
+(2,3)\} \subseteq R\cup S,$ but $(1,3)\not\in R\cup S$ because
+$1\mathbin{\not\hskip-3pt R} 3$ and $1\mathbin{\not\hskip-2pt S} 3.$
+\endanswer
+
+\bye