## Exercises2.4Exercises

### 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{.}$$

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{.}$$

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 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{.}$$

### 12.Power 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 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.

### 17.Fibonacci 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 Item 2.4.17.a and Item 2.4.17.b use mathematical induction. Item 2.4.17.c Show that $$f_1 = 1\text{,}$$ $$f_2 = 1\text{,}$$ and $$f_{n + 2} = f_{n + 1} + f_n\text{.}$$ Item 2.4.17.d Use part Item 2.4.17.c. Item 2.4.17.e Use part Item 2.4.17.b and Exercise 2.4.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.