Exercises 2.4 Exercises
1.
Prove that
for
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
3.
Prove that
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
5.
Prove that
6.
Prove that
7.
Show that
8.
Use induction to prove that
9.
Prove the Leibniz rule for
Follow the proof in Example 2.1.4.
10.
Prove that
for
11.
If
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
For every positive integer
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
15.
For each of the following pairs of numbers
14 and 39
234 and 165
1739 and 9923
471 and 562
23,771 and 19,945
and 3754
16.
Let
17. Fibonacci Numbers.
The Fibonacci numbers are
We can define them inductively by
Prove that
Prove that
Prove that
Show that
Prove that
and 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
19.
Let
Use the Fundamental Theorem of Arithmetic.
20.
Using the division algorithm, show that every perfect square is of the form
21.
Suppose that
Prove that
22.
Let
23.
Define the least common multiple of two nonzero integers
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
25.
Show that
26.
Prove that
27.
Let
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
29.
Prove that there are an infinite number of primes of the form
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
31.
Using the fact that 2 is prime, show that there do not exist integers