$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section2.3Exercises

###### 1

Prove that

\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}

for $n \in {\mathbb N}\text{.}$

Hint

The base case, $S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2$ is true. Assume that $S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6$ is true. Then

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2\\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6, \end{align*}

and so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

###### 2

Prove that

\begin{equation*} 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n + 1)^2}{4} \end{equation*}

for $n \in {\mathbb N}\text{.}$

###### 3

Prove that $n! \gt 2^n$ for $n \geq 4\text{.}$

Hint

The base case, $S(4): 4! = 24 \gt 16 =2^4$ is true. Assume $S(k): k! \gt 2^k$ is true. Then $(k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}$ so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

###### 4

Prove that

\begin{equation*} x + 4x + 7x + \cdots + (3n - 2)x = \frac{n(3n - 1)x}{2} \end{equation*}

for $n \in {\mathbb N}\text{.}$

###### 5

Prove that $10^{n + 1} + 10^n + 1$ is divisible by 3 for $n \in {\mathbb N}\text{.}$

###### 6

Prove that $4 \cdot 10^{2n} + 9 \cdot 10^{2n - 1} + 5$ is divisible by 99 for $n \in {\mathbb N}\text{.}$

###### 7

Show that

\begin{equation*} \sqrt[n]{a_1 a_2 \cdots a_n} \leq \frac{1}{n} \sum_{k = 1}^{n} a_k. \end{equation*}
###### 8

Prove the Leibniz rule for $f^{(n)} (x)\text{,}$ where $f^{(n)}$ is the $n$th derivative of $f\text{;}$ that is, show that

\begin{equation*} (fg)^{(n)}(x) = \sum_{k = 0}^{n} \binom{n}{k} f^{(k)}(x) g^{(n - k)}(x). \end{equation*}
Hint

Follow the proof in Example Example 2.1.4.

###### 9

Use induction to prove that $1 + 2 + 2^2 + \cdots + 2^n = 2^{n + 1} - 1$ for $n \in {\mathbb N}\text{.}$

###### 10

Prove that

\begin{equation*} \frac{1}{2}+ \frac{1}{6} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1} \end{equation*}

for $n \in {\mathbb N}\text{.}$

###### 11

If $x$ is a nonnegative real number, then show that $(1 + x)^n - 1 \geq nx$ for $n = 0, 1, 2, \ldots\text{.}$

Hint

The base case, $S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x$ is true. Assume $S(k): (1 + x)^k -1 \geq kx$ is true. Then

\begin{align*} (1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1\\ & = (1 + x)^k + x(1 + x)^k - 1\\ & \geq kx + x(1 + x)^k\\ & \geq kx + x\\ & = (k + 1)x, \end{align*}

so $S(k + 1)$ is true. Therefore, $S(n)$ is true for all positive integers $n\text{.}$

###### 12Power Sets

Let $X$ be a set. Define the power set of $X\text{,}$ denoted ${\mathcal P}(X)\text{,}$ to be the set of all subsets of $X\text{.}$ For example,

\begin{equation*} {\mathcal P}( \{a, b\} ) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}. \end{equation*}

For every positive integer $n\text{,}$ show that a set with exactly $n$ elements has a power set with exactly $2^n$ elements.

###### 13

Prove that the two principles of mathematical induction stated in Section Section 2.1 are equivalent.

###### 14

Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if $S \subset {\mathbb N}$ such that $1 \in S$ and $n + 1 \in S$ whenever $n \in S\text{,}$ then $S = {\mathbb N}\text{.}$

###### 15

For each of the following pairs of numbers $a$ and $b\text{,}$ calculate $\gcd(a,b)$ and find integers $r$ and $s$ such that $\gcd(a,b) = ra + sb\text{.}$

1. 14 and 39

2. 234 and 165

3. 1739 and 9923

4. 471 and 562

5. 23,771 and 19,945

6. $-4357$ and 3754

###### 16

Let $a$ and $b$ be nonzero integers. If there exist integers $r$ and $s$ such that $ar + bs =1\text{,}$ show that $a$ and $b$ are relatively prime.

###### 17Fibonacci Numbers

The Fibonacci numbers are

\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, \ldots. \end{equation*}

We can define them inductively by $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n$ for $n \in {\mathbb N}\text{.}$

1. Prove that $f_n \lt 2^n\text{.}$

2. Prove that $f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\text{,}$ $n \geq 2\text{.}$

3. Prove that $f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\text{.}$

4. Show that $\lim_{n \rightarrow \infty} f_n / f_{n + 1} = (\sqrt{5} - 1)/2\text{.}$

5. Prove that $f_n$ and $f_{n + 1}$ are relatively prime.

Hint

For (a) and (b) use mathematical induction. (c) Show that $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n\text{.}$ (d) Use part (c). (e) Use part (b) and Exercise Exercise 2.3.16.

###### 18

Let $a$ and $b$ be integers such that $\gcd(a,b) = 1\text{.}$ Let $r$ and $s$ be integers such that $ar + bs =1\text{.}$ Prove that

\begin{equation*} \gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1. \end{equation*}
###### 19

Let $x, y \in {\mathbb N}$ be relatively prime. If $xy$ is a perfect square, prove that $x$ and $y$ must both be perfect squares.

Hint

Use the Fundamental Theorem of Arithmetic.

###### 20

Using the division algorithm, show that every perfect square is of the form $4k$ or $4k + 1$ for some nonnegative integer $k\text{.}$

###### 21

Suppose that $a, b, r, s$ are pairwise relatively prime and that

\begin{align*} a^2 + b^2 & = r^2\\ a^2 - b^2 & = s^2. \end{align*}

Prove that $a\text{,}$ $r\text{,}$ and $s$ are odd and $b$ is even.

###### 22

Let $n \in {\mathbb N}\text{.}$ Use the division algorithm to prove that every integer is congruent mod $n$ to precisely one of the integers $0, 1, \ldots, n-1\text{.}$ Conclude that if $r$ is an integer, then there is exactly one $s$ in ${\mathbb Z}$ such that $0 \leq s \lt n$ and $[r] = [s]\text{.}$ Hence, the integers are indeed partitioned by congruence mod $n\text{.}$

###### 23

Define the least common multiple of two nonzero integers $a$ and $b\text{,}$ denoted by $\lcm(a,b)\text{,}$ to be the nonnegative integer $m$ such that both $a$ and $b$ divide $m\text{,}$ and if $a$ and $b$ divide any other integer $n\text{,}$ then $m$ also divides $n\text{.}$ Prove that any two integers $a$ and $b$ have a unique least common multiple.

Hint

Let $S = \{s \in {\mathbb N} : a \mid s\text{,}$ $b \mid s \}\text{.}$ Then $S \neq \emptyset\text{,}$ since $|ab| \in S\text{.}$ By the Principle of Well-Ordering, $S$ contains a least element $m\text{.}$ To show uniqueness, suppose that $a \mid n$ and $b \mid n$ for some $n \in {\mathbb N}\text{.}$ By the division algorithm, there exist unique integers $q$ and $r$ such that $n = mq + r\text{,}$ where $0 \leq r \lt m\text{.}$ Since $a$ and $b$ divide both $m\text{,}$ and $n\text{,}$ it must be the case that $a$ and $b$ both divide $r\text{.}$ Thus, $r = 0$ by the minimality of $m\text{.}$ Therefore, $m \mid n\text{.}$

###### 24

If $d= \gcd(a, b)$ and $m = \lcm(a, b)\text{,}$ prove that $dm = |ab|\text{.}$

###### 25

Show that $\lcm(a,b) = ab$ if and only if $\gcd(a,b) = 1\text{.}$

###### 26

Prove that $\gcd(a,c) = \gcd(b,c) =1$ if and only if $\gcd(ab,c) = 1$ for integers $a\text{,}$ $b\text{,}$ and $c\text{.}$

###### 27

Let $a, b, c \in {\mathbb Z}\text{.}$ Prove that if $\gcd(a,b) = 1$ and $a \mid bc\text{,}$ then $a \mid c\text{.}$

Hint

Since $\gcd(a,b) = 1\text{,}$ there exist integers $r$ and $s$ such that $ar + bs = 1\text{.}$ Thus, $acr + bcs = c\text{.}$ Since $a$ divides both $bc$ and itself, $a$ must divide $c\text{.}$

###### 28

Let $p \geq 2\text{.}$ Prove that if $2^p - 1$ is prime, then $p$ must also be prime.

###### 29

Prove that there are an infinite number of primes of the form $6n + 5\text{.}$

Hint

Every prime must be of the form 2, 3, $6n + 1\text{,}$ or $6n + 5\text{.}$ Suppose there are only finitely many primes of the form $6k + 5\text{.}$

###### 30

Prove that there are an infinite number of primes of the form $4n - 1\text{.}$

###### 31

Using the fact that 2 is prime, show that there do not exist integers $p$ and $q$ such that $p^2 = 2 q^2\text{.}$ Demonstrate that therefore $\sqrt{2}$ cannot be a rational number.