\documentclass[12pt,oneside]{amsart} \usepackage{geometry} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} %\usepackage{pdfpages} \usepackage{enumerate} \usepackage[all]{xy} \usepackage{graphicx} \graphicspath{ {./images/} } \usepackage{appendix} %\usepackage{caption} \usepackage{subcaption} \usepackage{color} \usepackage{verbatim} \usepackage{mathtools} \usepackage{tikz-cd} \usepackage[section]{placeins} \usepackage{showkeys} \usepackage{hyperref} \usepackage{enumitem} \usepackage{multicol} \hypersetup{ colorlinks=true, allcolors=blue, } %ENVIRONMENTS \newtheorem{theorem}{Theorem} \newtheorem*{theorem*}{Theorem} \newtheorem{corollary}{Corollary} \newtheorem{lemma}{Lemma} \newtheorem{remark}{Remark} \newtheorem{conjecture}{Conjecture} \newtheorem{example}{Example} \newtheorem{proposition}{Proposition} \theoremstyle{definition} \newtheorem{definition}{Definition} \newtheorem{note}{Note} %OPERATORS \DeclareMathOperator{\dist}{dist} %SYMBOLS \def\a{\alpha} \def\b{\beta} \def\m{\mu} \def\n{\nu} \def\u{\upsilon} \def\l{\lambda} \def\CC{\mathbb{C}} \def\R{\mathbb{R}} \def\Q{\mathbb{Q}} \def\Z{\mathbb{Z}} \def\N{\mathbb{N}} \def\T{\mathbb{T}} \def\H{\mathbb{H}} \def\S{\Sigma} \def\s{\sigma} \def\e{\epsilon} \def\B{\mathcal{B}} \def\O{\Omega} \def\o{\omega} \def\C{\mathcal{C}} \def\U{\mathcal{U}} \def\A{\mathcal{A}} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Homework 8 - Discrete Math Spring 2023} \author{John Adamski} \address{Department of Mathematics, Fordham University} \email{adamski@fordham.edu} %\address{Department of Mathematics, The City College of New York, CUNY} %\email{jadamski@ccny.cuny.edu} \urladdr{www.johnadamski.com} %\begin{abstract} %Great stuff! %\end{abstract} %\tableofcontents \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem*}\label{9.2} Prove or disprove: For every natural number $n$, the integer $2n^2 - 4n + 31$ is prime. \end{theorem*} \begin{proof} The statement is false. We show this by proving the negation: There exists a natural number $n$ such that $2n^2 - 4n + 31$ is not prime. Let $n=31$. Then $n$ is a natural number and \begin{equation*} n^2 - 4n + 31 = 31^1 - 4\cdot31 + 31 = 31(31 - 4 + 1) = 31\cdot28 \end{equation*} is not prime. \end{proof} \begin{theorem*}\label{9.6} Prove of disprove: If $A, B,$ and $C$ are sets, then \begin{equation*} (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D). \end{equation*} \end{theorem*} \begin{proof} The statement is true and follows directly from definitions and logical equivalences. \begin{align*} (A \times B) \cap (C \times D) &= \{(x, y) : (x \in A) \wedge (y \in B)\} \cap \{(x, y) : (x \in C) \wedge (y \in D)\} \\ &= \{(x, y) : ((x \in A) \wedge (y \in B)) \wedge ((x \in C) \wedge (y \in D))\} \\ &= \{(x, y) : ((x \in A) \wedge (x \in C)) \wedge ((y \in B) \wedge (y \in D))\} \\ &= \{(x, y) : (x \in (A \cap C)) \wedge (y \in (B \cap D))\} \\ &= (A \cap C) \times (B \cap D). \end{align*} \end{proof} \begin{theorem*}\label{9.30} Prove or disprove: There exist integers $a$ and $b$ for which $42a + 7b = 1$. \end{theorem*} \begin{proof} The statement is false. To show this, let us assume for the sake of contradiction that the statement is true. Thus, we have two integers $a$ and $b$ such that \begin{equation*} 1 = 42a + 7b = 7(6a + b). \end{equation*} Since $6a + b \in\Z$, this shows that $7 \mid 1$ $\Rightarrow\Leftarrow$. This contradicts the fact that $7\nmid1$, and so the statement must be false. \end{proof} \begin{theorem*}\label{9.34} Prove or disprove: If $X \subseteq A \cup B$, then $X \subseteq A$ or $X \subseteq B$. \end{theorem*} \begin{proof} The statement is false. Note that the statement is a universally quantified statement: \begin{equation*} \forall \mbox{ sets }A\mbox{ and }B, (X \subseteq A \cup B) \Rightarrow \left((X \subseteq A) \vee (X \subseteq B)\right). \end{equation*} Therefore, to disprove the statement it is enough to provide one counterexample -- three sets $A, B,$ and $X$ such that $X \subseteq A \cup B$ and $\sim ((X \subseteq A) \vee (X \subseteq B))$, in other words $(X \nsubseteq A) \wedge (X \nsubseteq B)$. Let $A = \{1, 2\}$, $B = \{2, 3\}$, and $X = \{1, 2, 3\}$. Since $X = A \cup B$, we see that $X \subseteq A \cup B$. However, since $3 \in X$ but $3 \notin A$, we see that $X \nsubseteq A$. And since $1 \in A$ but $1 \notin B$, we see that $X \nsubseteq B$. % Therefore, this is a counterexample that disproves the statement. \end{proof} \begin{theorem*}\label{10.2} Prove that \begin{equation*} 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*} for every positive integer $n$. \end{theorem*} \begin{proof} Let $P(n)$ be the statement \begin{equation*} P(n)\;:\; 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6}. \end{equation*} We must prove that all of the statements $P(1), P(2), P(3), \ldots$ are all true. We proceed by induction. First, observe that \begin{equation*} 1^2 = \frac{1(1 + 1)(2\cdot1 + 1)}{6} = \frac{1\cdot2\cdot3}{6}, \end{equation*} and so $P(1)$ is true. Now assume that $P(n)$ is true for some integer $n$. We will use this to show that \begin{equation*} P(n+1)\;:\; 1^2 + 2^2 + 3^2 + \ldots + (n + 1)^2 = \frac{(n + 1)((n + 1) + 1)(2(n + 1) + 1)}{6} \end{equation*} is true. We have \begin{align*} 1^2 + 2^2 + 3^2 + \ldots + n^2 + (n+1)^2 &= (1^2 + 2^2 + 3^2 + \ldots + n^2) + (n+1)^2 \\ &= \frac{n(n + 1)(2n + 1)}{6} + (n+1)^2 \\ &= \frac{n(n + 1)(2n + 1) +6(n + 1)^2}{6} \\ &= \frac{(n + 1)[n(2n+1) + 6(n + 1)]}{6} \\ &= \frac{(n+1)(2n^2 + 7n + 6)}{6} \\ &= \frac{(n+1)(n + 2)(2n + 3)}{6} \\ &= \frac{(n+1)((n+1)+1)(2(n+1)+1)}{6} \end{align*} This completes the proof.\footnote{Notice that in the very last equation I've used parentheses to isolate $(n+1)$ in order to make it very clear that this is the statement $P(n+1)$.} \end{proof} \begin{theorem*}\label{10.6} Prove that \begin{equation*} \sum_{i = 1}^n (8i - 5) = 4n^2 - n \end{equation*} for every positive integer $n$. \end{theorem*} \begin{proof} We proceed by induction. First, observe that \begin{equation*} \sum_{i=1}^1 (8i - 5) = 8\cdot1 - 5 = 3 = 4\cdot1^2 - 1, \end{equation*} and so the statement is true for $n=1$. Now assume that the statement is true for some positive integer $n$. We must show that this implies that the statement is true for $n+1$. We have \begin{align*} \sum_{i = 1}^{n+1}(8i - 5) &= \sum_{i = 1}^{n}(8i - 5) + 8(n + 1) - 5 \\ &= 4n^2 - n + 8(n + 1) - 5 \\ &= 4n^2 + 7n + 3 \\ &= (4n^2 + 8n + 4) - (n + 1) \\ &= 4(n + 1)^2 - (n + 1). \end{align*} This completes the proof.\footnote{Out of context, it is very strange to rewrite the polynomial $4n^2 + 7n + 3$ as the polynomial $(4n^2 + 8n + 4) - (n + 1)$. But within the context of this proof by induction, we are motivated to arrive at the final expression $4(n+1)^2 - (n+1)$. You may find it helpful to work backwards from the final expression in order to construct such a sequence of equations.} \end{proof} \begin{theorem*}\label{10.10} Prove that $3 \mid (5^{2n} - 1)$ for every integer $n\geq 0$. \end{theorem*} \begin{proof} We proceed by induction. First, observe that \begin{equation*} 5^{2\cdot0} - 1 = 1 - 1 = 0 = 3\cdot0, \end{equation*} and so $3 \mid 5^{2\cdot0} - 1$. In other words, $3 \mid (5^{2n} - 1)$ is true when $n = 0$. Now let us assume that $3 \mid (5^{2n} - 1)$ is true for some integer $n\geq0$. That is, $5^{2n} - 1 = 3a$ for some $a\in\Z$. We must show that $3 \mid (5^{2(n+1)} - 1)$. We have \begin{align*} 5^{2(n + 1)} - 1 &= 5^{2n + 2} - 25 + 24 \\ &= 25(5^{2n} - 1) + 24 \\ &= 25(3a) + 24 \\ &= 3(25a + 8). \end{align*} Since $25a + 8 \in \Z$, this shows, by definition, that $3 \mid (5^{2(n+1)} - 1)$. \end{proof} \begin{theorem*}\label{10.16} Prove that $2^n + 1 \leq 3^n$ for every positive integer $n$. \end{theorem*} \begin{proof} We proceed by induction. First, observe that $2^1 + 1 \leq 3^1$, and so the statement is true for $n = 1$. Now assume that $2^n + 1 \leq 3^n$ is true for some positive integer $n$. We must show that this implies that $2^{n+1} + 1 \leq 3^{n+1}$. We have \begin{align*} 2^{n + 1} + 1 &< 2^{n + 1} + 2 = 2(2^n + 1) \\ &\leq 2(3^n) \\ &< 3(3^n) = 3^{n+1}. \end{align*} Therefore $2^{n + 1} + 1 \leq 3^{n+1}$. This completes the proof.\footnote{Note that we could have used only $\leq$ in the final argument, instead of using $<$, $=$ and $\leq$. I chose to write my proof as I did in the hope that it helps the reader more easily see how the expressions are changing from one to the next. Different authors may make different choices, and that's perfectly fine.} \end{proof} \begin{theorem*}\label{10.19} Prove that \begin{equation*} \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \ldots + \frac{1}{n^2} \leq 2 - \frac{1}{n} \end{equation*} for every $n \in \N$. \end{theorem*} \begin{proof} We preceed by induction. First, observe that \begin{equation*} \frac{1}{1} \leq 2 - \frac{1}{1} \end{equation*} is true, and so the statement is true for $n = 1$. Now let us assume that \begin{equation*} \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \ldots + \frac{1}{n^2} \leq 2 - \frac{1}{n}. \end{equation*} We must show that this implies that \begin{equation*} \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \ldots + \frac{1}{n^2} + \frac{1}{(n+1)^2} \leq 2 - \frac{1}{n+1}. \end{equation*} Before we do this, notice that for all $n \in \N$, we have \begin{equation*} n + 1 \geq n \end{equation*} and, multplying both sides by $n + 1$ yields \begin{equation*} (n + 1)^2 \geq n(n+1). \end{equation*} Taking the reciprocals of both sides and reversing the inequality, we see that \begin{equation} \frac{1}{(n + 1)^2} \leq \frac{1}{n(n+1)}. \end{equation} We will use this inequality in the following argument. \begin{align*} \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \ldots + \frac{1}{n^2} + \frac{1}{(n+1)^2} &= \left(\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \ldots + \frac{1}{n^2}\right) + \frac{1}{(n+1)^2} \\ &\leq \left(2 - \frac{1}{n}\right) + \frac{1}{(n+1)^2} \\ &\leq 2 - \frac{1}{n} + \frac{1}{n(n + 1)} \\ &= 2 - \frac{1}{n + 1}. \end{align*} Notice that inequality (1) was used in the third line. This completes the proof. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\begin{thebibliography}{99} %\bibitem{} %\newblock %\newblock %\end{thebibliography} \end{document}