Skip to main content
\(\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}\).

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}\).

3

Prove that \(n! \gt 2^n\) for \(n \geq 4\).

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}\).

5

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

6

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

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)\), where \(f^{(n)}\) is the \(n\)th derivative of \(f\); 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*}

9

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

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}\).

11

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

12Power Sets

Let \(X\) be a set. Define the power set of \(X\), denoted \({\mathcal P}(X)\), to be the set of all subsets of \(X\). For example, \begin{equation*}{\mathcal P}( \{a, b\} ) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}.\end{equation*} For every positive integer \(n\), 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\), then \(S = {\mathbb N}\).

15

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

  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\), 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\), \(f_2 = 1\), and \(f_{n + 2} = f_{n + 1} + f_n\) for \(n \in {\mathbb N}\).

  1. Prove that \(f_n \lt 2^n\).

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

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

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

  5. Prove that \(f_n\) and \(f_{n + 1}\) are relatively prime.

18

Let \(a\) and \(b\) be integers such that \(\gcd(a,b) = 1\). Let \(r\) and \(s\) be integers such that \(ar + bs =1\). 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.

20

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

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\), \(r\), and \(s\) are odd and \(b\) is even.

22

Let \(n \in {\mathbb N}\). Use the division algorithm to prove that every integer is congruent mod \(n\) to precisely one of the integers \(0, 1, \ldots, n-1\). 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]\). Hence, the integers are indeed partitioned by congruence mod \(n\).

23

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

24

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

25

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

26

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

27

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

28

Let \(p \geq 2\). 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\).

30

Prove that there are an infinite number of primes of the form \(4n - 1\).

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\). Demonstrate that therefore \(\sqrt{2}\) cannot be a rational number.