Skip to main content

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

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

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*}

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

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. \(23771\) and \(19945\)
  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.

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.

Suppose that \(p\) is a prime and \(p \neq 2\text{.}\) If \(a\) and \(b\) are integers and \(p\) divides both \(a+b\) and \(a-b\text{,}\) then \(p\) divides both \(a\) and \(b\text{.}\)

20.

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.

21.

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

22.

If \(a, b, c\) are integers such that \(a^2+b^2=c^2\text{,}\) then show that \(a\) and \(b\) can’t both be odd.

23.

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.

24.

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

25.

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

26.

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

27.

Define the least common multiple of two nonzero integers \(a\) and \(b\text{,}\) denoted by \(\lcm(a,b)\text{,}\) to be the smallest positive integer \(m\) such that both \(a\) and \(b\) divide \(m\text{.}\) Prove the least common multiple for any two integers \(a\) and \(b\) exists and that any common multiple of \(a\) and \(b\) is divisible by \(\lcm(a,b)\text{.}\)

28.

Let \(a\) and \(b\) be non-zero integers.
  1. First suppose that \(a\) and \(b\) are positive and \(\gcd(a,b) = 1\text{.}\) In this case, show that \(\lcm(a,b) = ab\text{.}\)
  2. If \(a\) and \(b\) are positive, and \(d = \gcd(a,b)\) and \(m = \lcm(a,b)\text{,}\) then show that \(dm=ab\text{.}\)
  3. If \(a\) and \(b\) are any non-zero integers, with \(d = \gcd(a,b)\) and \(m = \lcm(a,b)\text{,}\) then show that \(dm=\lvert ab \rvert\text{.}\)

29.

Let \(a\) and \(b\) be positive integers. Show that \(\lcm(a,b) = ab\) if and only if \(\gcd(a,b) = 1\text{.}\)

30.

Let \(p \geq 2\text{.}\) Prove that if \(2^p - 1\) is prime, then \(p\) must also be prime.

31.

Prove that there are an infinite number of primes of the form \(6n + 5\text{.}\)

32.

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

33.

Using the fact that \(2\) is prime, show that there do not exist non-zero integers \(p\) and \(q\) such that \(p^2 = 2 q^2\text{.}\) Demonstrate that therefore \(\sqrt{2}\) cannot be a rational number.
PrevTopNext