AATA Exercises

Exercises 2.4 Exercises

1.

Prove that

1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}

for $n \in N .$

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

1^{3} + 2^{3} + \dots + n^{3} = \frac{n^{2} (n + 1)^{2}}{4}

for $n \in N .$

🔗

3.

Prove that $n! > 2^{n}$ for $n \geq 4 .$

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

x + 4 x + 7 x + \dots + (3 n - 2) x = \frac{n (3 n - 1) x}{2}

for $n \in N .$

🔗

5.

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

🔗

6.

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

🔗

7.

Show that

\sqrt[n]{a_{1} a_{2} \dots a_{n}} \leq \frac{1}{n} \sum_{k = 1}^{n} a_{k} .

🔗

8.

Use induction to prove that $1 + 2 + 2^{2} + \dots + 2^{n} = 2^{n + 1} - 1$ for $n \in N .$

🔗

9.

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

(f g)^{(n)} (x) = \sum_{k = 0}^{n} (\binom{n}{k}) f^{(k)} (x) g^{(n - k)} (x) .

Hint.

Follow the proof in Example 2.1.4.

🔗

10.

Prove that

\frac{1}{2} + \frac{1}{6} + \dots + \frac{1}{n (n + 1)} = \frac{n}{n + 1}

for $n \in N .$

🔗

11.

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

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,$ denoted $P (X),$ to be the set of all subsets of $X .$ For example,

P ({a, b}) = {\emptyset, {a}, {b}, {a, b}} .

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 N$ such that $1 \in S$ and $n + 1 \in S$ whenever $n \in S,$ then $S = 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) = r a + s b .$

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 $a r + b s = 1,$ show that $a$ and $b$ are relatively prime.

🔗

17. Fibonacci Numbers.

The Fibonacci numbers are

1, 1, 2, 3, 5, 8, 13, 21, \dots .

We can define them inductively by $f_{1} = 1,$ $f_{2} = 1,$ and $f_{n + 2} = f_{n + 1} + f_{n}$ for $n \in N .$

Prove that $f_{n} < 2^{n} .$
Prove that $f_{n + 1} f_{n - 1} = f_{n}^{2} + (- 1)^{n},$ $n \geq 2 .$
Prove that $f_{n} = [(1 + \sqrt{5})^{n} - (1 - \sqrt{5})^{n}] / 2^{n} \sqrt{5} .$
Show that $lim_{n \to \infty} f_{n} / f_{n + 1} = (\sqrt{5} - 1) / 2 .$
Prove that $f_{n}$ and $f_{n + 1}$ are relatively prime.

Hint.

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 .$ Let $r$ and $s$ be integers such that $a r + b s = 1 .$ Prove that

gcd (a, s) = gcd (r, b) = gcd (r, s) = 1.

🔗

19.

Let $x, y \in N$ be relatively prime. If $x y$ 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 $4 k$ or $4 k + 1$ for some nonnegative integer $k .$

🔗

21.

Suppose that $a, b, r, s$ are pairwise relatively prime and that

\begin{aligned} a^{2} + b^{2} & = r^{2} \\ a^{2} - b^{2} & = s^{2} . \end{aligned}

Prove that $a,$ $r,$ and $s$ are odd and $b$ is even.

🔗

22.

Let $n \in N .$ Use the division algorithm to prove that every integer is congruent mod $n$ to precisely one of the integers $0, 1, \dots, n - 1 .$ Conclude that if $r$ is an integer, then there is exactly one $s$ in $Z$ such that $0 \leq s < 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 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),$ prove that $d m = | a b | .$

🔗

25.

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

🔗

26.

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

🔗

27.

Let $a, b, c \in Z .$ Prove that if $gcd (a, b) = 1$ and $a ∣ b c,$ then $a ∣ c .$

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 .$ 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 $6 n + 5 .$

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 $4 n - 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.