## Exercises 2.4 Exercises

### 1.

Prove that

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

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

### 2.

Prove that

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

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

### 8.

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

### 9.

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

Follow the proof in ExampleÂ 2.1.4.

### 10.

Prove that

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

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

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,

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

14 and 39

234 and 165

1739 and 9923

471 and 562

23,771 and 19,945

\(-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

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

Prove that \(f_n \lt 2^n\text{.}\)

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

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

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

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

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

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

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

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.

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

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

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.