path: root/gupta/hw6.tex

\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