Exercises 2.4 Exercises
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{.}\)
Answer.
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{.}\)
Answer.
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.
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
\begin{equation*}
(fg)^{(n)}(x) = \sum_{k = 0}^{n} \binom{n}{k} f^{(k)}(x) g^{(n - k)}(x).
\end{equation*}
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{.}\)
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
\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{.}\)
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.
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.
