Chapter 4

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Every odd prime is of the form \(4 n+1\) or \(4 n+3\).

Let \(f, g,\) and \(h\) be three functions such that \(f(n)=O(g(n))\) and \(g(n)=\) \(\mathrm{O}(h(n)) .\) Show that \(f(n)=\mathrm{O}(h(n))\).

Disprove each statement. If \(\operatorname{gcd}\\{a, b\\}=1\) and \(\operatorname{gcd}\\{b, c\\}=1,\) then \(\operatorname{gcd}\\{a, c\\}=1,\) where \(a, b,\) and \(c\) are positive integers.

Let \(f(n)=\sum_{i=0}^{m} a_{i} n^{i},\) where each \(a_{i}\) is a real number and \(a_{m} \neq 0 .\) Prove that \(f(n)=\Theta\left(n^{m}\right).\)

\(\operatorname{Let} f(n)=\sum_{i=0}^{m} a_{i} n^{i},\) where each \(a_{i}\) is a real number and \(a_{m} \neq 0 .\) Prove that \(f(n)=\Theta\left(n^{m}\right)\).

Let \(f, g : \mathbb{N} \rightarrow \mathbb{R}\) . Prove that \(f(n)=\Theta(g(n))\) if and only if \(A | g(n) \leq\) \(f(n)| \leq B| g(n)\) ' for some constants \(A\) and \(B.\)

Let \(f, g: \mathbb{N} \rightarrow \mathbb{R} .\) Prove that \(f(n)=\Theta(g(n))\) if and only if \(A|g(n)| \leq\) \(|f(n)| \leq B|g(n)|\) for some constants \(A\) and \(B\).

Let \(A, A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}\) be any sets, and \(p_{1}, p_{2}, \ldots, p_{n}, q, q_{1}\) \(q_{2}, \ldots, q_{n}\) be any propositions. Using induction prove each. $$A \cup\left(\bigcap_{i=1}^{n} B_{i}\right)=\bigcap_{i=1}^{n}\left(A \cup B_{i}\right)$$

Let \(A, A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}\) be any sets, and \(p_{1}, p_{2}, \ldots, p_{n}, q, q_{1}\) \(q_{2}, \ldots, q_{n}\) be any propositions. Using induction prove each. $$A \bigcap_{i=1}^{n}\left(\cup B_{i}\right)=\bigcup_{i=1}^{n}\left(A \cap B_{i}\right)$$

Disprove each statement. Let \(n\) be a positive integer. Prove that \((n+1) !+2,(n+1) !+3, \dots\) \((n+1) !+(n+1)\) are \(n\) consecutive composite numbers.

Let \(A, A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}\) be any sets, and \(p_{1}, p_{2}, \ldots, p_{n}, q, q_{1}\) \(q_{2}, \ldots, q_{n}\) be any propositions. Using induction prove each. $$\sim\left(p_{1} \wedge p_{2} \wedge \cdots \wedge p_{n}\right) \equiv\left(\sim p_{1}\right) \vee\left(\sim p_{2}\right) \vee \cdots \vee\left(\sim p_{n}\right)$$

Let \(A, A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}\) be any sets, and \(p_{1}, p_{2}, \ldots, p_{n}, q, q_{1}\) \(q_{2}, \ldots, q_{n}\) be any propositions. Using induction prove each. $$\sim\left(p_{1} \vee p_{2} \vee \cdots \vee p_{n}\right) \equiv\left(\sim p_{1}\right) \wedge\left(\sim p_{2}\right) \wedge \cdots \wedge\left(\sim p_{n}\right)$$

Prove that any postage of \(\mathrm{n}( \geq 2)\) cents can be made using two- and three-cent stamps. (Hint: Use the division algorithm and induction.)

Prove that any postage of \(\mathrm{n}(\geq 2)\) cents can be made using two- and three-cent stamps. (Hint: Use the division algorithm and induction.)

Let \(a\) and \(b\) be any two positive integers with \(a \geq b\). Using the sequence of equations in the euclidean algorithm prove that \(\operatorname{gcd}\\{a, b\\}=\operatorname{gcd}\left\\{r_{n-1}, r_{n}\right\\}, n \geq 1\).

Prove the strong version of mathematical induction, using the weak version.

Prove the weak version of induction, using the well-ordering principle.

Let \(S_{n}\) denote the sum of the elements in the \(n\) th set of the sequence of sets of squares \(\\{1\\},\\{4,9\\},\\{16,25,36\\}, \ldots .\) Find a formula for \(S_{n}\).(J. M. Howell, 1989 )

Redo Exercise 59 using the sequence of triangular numbers \\{1\\} \(\\{3,6\\},\\{10,15,21\\}, \ldots\) (J. M. Howell, 1988 )