INSTRUCTOR’S SOLUTIONS MANUAL
ELEMENTARY NUMBER THEORY AND ITS APPLICATIONS
7TH EDITION
CHAPTER NO. 01: THE INTEGERS
1.1. Numbers, Sequences, and Sums
1.1.1. a. The set of integers greater than 3 is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.
b. The set of even positive integers is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.
c. The set of positive rational numbers is not well-ordered. This set does not have a least element.
If a/b were the least positive rational number then a/(b + a) would be a smaller positive rational
number, which is a contradiction.
d. The set of positive rational numbers of the form a/2 is well-ordered. Consider a subset of numbers
of this form. The set of numerators of the numbers in this subset is a subset of the set of positive
integers, so it must have a least element b. Then b/2 is the least element of the subset.
e. The set of nonnegative rational numbers is not well-ordered. The set of positive rational numbers
is a subset with no least element, as shown in part (c).
1.1.2. Let S be the set of all positive integers of the form a − bk. S is not empty since a − b(−1) = a + b is a
positive integer. Then the well-ordering principle implies that S has a least element, which is the num-
ber we’re looking for.
1.1.3. Suppose that x and y are rational numbers. Then x = a/b and y = c/d, where a, b, c, and d are integers
̸ 0 and d ̸= 0. Then xy = (a/b) · (c/d) = ac/bd and x + y = a/b + c/d = (ad + bc)/bd where bd ̸=
with b =
0. Since both x + y and xy are ratios of integers, they are both rational.
1.1.4. a. Suppose that x is rational and y is irrational. Then there exist integers a and b such that x = ab where
a and b are integers with b ≠ 0. Suppose that x + y is rational. Then there exist integers c and d with
d ̸= 0 such that x + y = dc . This implies that y = (x + y) − x = (a/b) − (c/d) = (ad − bc)/bd, which
means that y is rational, a contradiction. Hence x + y is irrational.
√ √
b. This is false. A counterexample is given by 2 + (− 2) = 0.
√
c. This is false. A counterexample is given by 0 · 2 = 0.
√ √
d. This is false. A counterexample is given by 2 · 2 = 2.
√ √
1.1.5. Suppose that 3 were√ rational. Then√ there would exist positive integers a and b with √ 3 = a/b. Con-
sequently, the set S = {k 3 | k and k 3 are positive integers} √ is nonempty since
√ a = b √3. Therefore,
√ by
the√ well-ordering
√ property, S has a smallest element,
√ say s = t √ 3. We have s 3 − s = s 3 − t 3 = (s −
t) 3. Since s 3 = 3t√and s are both√ integers, s
√ 3 − s = (s − t) 3 must also be an
√ √integer. Furthermore,
√
it is positive, since s 3 − s = s( 3 − 1) and 3 > 1. It is less than s since s = t 3, s √3 = 3t, and 3 <
3. This contradicts the choice of s as the smallest positive integer in S. It follows that 3 is irrational.
1.1.6. Let S be a set of negative integers. Then the set T = {−s : s ∈ S} is a set of positive integers. By the
well-ordering principle, T has a least element t0 . We prove that −t0 is a greatest element of S. First note
, that since t0 ∈ S, then t0 = −s0 for some s0 ∈ S. Then −t0 = s0 ∈ S. Second, if s ∈ S, then −s ∈ T , so
t0 ≤ −s. Multiplying by −1 yields s ≤ −t0 . Since the choice of s was arbitrary, we see that −t0 is greater
than or equal to every element of S.
1.1.7. a. Since 0 ≤ 1/4 < 1, we have [1/4] = 0.
b. Since −1 ≤ −3/4 < 0, we have [−3/4] = −1.
c. Since 3 ≤ 22/7 < 4, we have [22/7] = 3.
d. Since −2 ≤ −2 < −1, we have [−2] = −2.
e. We compute [1/2 + [1/2]] = [1/2 + 0] = [1/2] = 0.
f. We compute [−3 + [−1/2]] = [−3 − 1] = [−4] = −4.
1.1.8. a. Since −1 ≤ −1/4 < 0, we have [−1/4] = −1.
b. Since −4 ≤ −22/7 < −3, we have [−22/7] = −4.
c. Since 1 ≤ 5/4 < 2, we have [5/4] = 1.
d. We compute [[1/2]] = [0] = 0.
e. We compute [[3/2] + [−3/2]] = [1 + (−2)] = [−1] = −1.
f. We compute [3 − [1/2]] = [3 − 0] = [3] = 3.
1.1.9. a. Since [8/5] = 1, we have {8/5} = 8/5 − [8/5] = 8/5 − 1 = 3/5.
b. Since [1/7] = 0, we have {1/7} = 1/7 − [1/7] = 1/7 − 0 = 1/7.
c. Since [−11/4] = −3, we have {−11/4} = −11/4 − [−11/4] = −11/4 − (−3) = 1/4.
d. Since [7] = 7, we have {7} = 7 − [7] = 7 − 7 = 0.
1.1.10. a. Since [−8/5] = −2, we have {−8/5} = −8/5 − [−8/5] = −8/5 − (−2) = 2/5.
b. Since [22/7] = 3, we have {22/7} = 22/7 − [22/7] = 22/7 − 3 = 1/7.
c. Since [−1] = −1, we have {−1} = −1 − [−1] = −1 − 1 = 0.
d. Since [−1/3] = −1, we have {−1/3} = −1/3 − [−1/3] = −1/3 − (−1) = 2/3.
1.1.11. If x is an integer, then [x] + [−x] = x − x = 0. Otherwise, x = z + r, where z is an integer and r is a
real number with 0 < r < 1. In this case, [x] + [−x] = [z + r] + [−z − r] = z + (−z − 1) = −1.
1.1.12. Let x = [x] + r where 0 ≤ r < 1. We consider two cases. First suppose that r < 21 . Then x + 12 =
[x] + (r + 12 ) < [x] + 1 since r + 21 < 1. It follows that [x + 12 ] = [x]. Also 2x = 2[x] + 2r < 2[x] + 1
since 2r < 1. Hence [2x] = 2[x]. It follows that [x] + [x + 12 ] = [2x]. Next suppose that 12 ≤ r < 1. Then
[x] + 1 ≤ x + (r + 12 ) < [x] + 2, so that [x + 12 ] = [x] + 1. Also 2[x] + 1 ≤ 2[x] + 2r = 2([x] + r) = 2x <
2[x] + 2 so that [2x] = 2[x] + 1. It follows that [x] + [x + 12 ] = [x] + [x] + 1 = 2[x] + 1 = [2x].
1.1.13. We have [x] ≤ x and [y] ≤ y. Adding these two inequalities gives [x] + [y] ≤ x + y. Hence [x + y] ≥
[[x] + [y]] = [x] + [y].
,1.1.14. Let x = a+r and y = b+s, where a and b are integers and r and s are real numbers such that 0 ≤ r, s <
1. By Exercise 12, [2x] + [2y] = [x] + [x + 12 ] + [y] + [y + 12 ]. We now need to show that [x + 12 ] + [y + 12 ] ≥
[x + y]. Suppose 0 ≤ r, s < 12 . Then [x + 12 ] + [y + 12 ] = a + b + [r + 12 ] + [s + 12 ] = a + b, and [x + y] =
a+b+[r +s] = a+b, as desired. Suppose that 12 ≤ r, s < 1. Then [x+ 21 ]+[y + 21 ] = a+b+[r + 12 ]+[s+ 12 ] =
a + b + 2, and [x + y] = a + b + [r + s] = a + b + 1, as desired. Suppose that 0 ≤ r < 12 ≤ s < 1. Then
[x + 21 ] + [y + 12 ] = a + b + 1, and [x + y] ≤ a + b + 1.
1.1.15. Let x = a + r and y = b + s, where a and b are integers and r and s are real numbers such that 0 ≤
r, s < 1. Then [xy] = [ab + as + br + sr] = ab + [as + br + sr], whereas [x][y] = ab. Thus we have [xy] ≥
[x][y] when x and y are both positive. If x and y are both negative, then [xy] ≤ [x][y]. If one of x and y
is positive and the other negative, then the inequality could go either direction. For examples take x =
−1.5, y = 5 and x = −1, y = 5.5. In the first case we have [−1.5 · 5] = [−7.5] = −8 > [−1.5][5] = −2 · 5 =
−10. In the second case we have [−1 · 5.5] = [−5.5] = −6 < [−1][5.5] = −1 · 5 = −5.
1.1.16. If x is an integer then −[−x] = −(−x) = x, which certainly is the least integer greater than or equal
to x. Let x = a + r, where a is an integer and 0 < r < 1. Then −[−x] = −[−a − r] = −(−a + [−r]) =
a − [−r] = a + 1, as desired.
1.1.17. Let x = [x] + r. Since 0 ≤ r < 1, x + 12 = [x] + r + 12 . If r < 12 , then [x] is the integer nearest to x and
[x+ 12 ] = [x] since [x] ≤ x+ 21 = [x]+r + 12 < [x]+1. If r ≥ 21 , then [x]+1 is the integer nearest to x (choos-
ing this integer if x is midway between [x] and [x+1]) and [x+ 12 ] = [x]+ 1 since [x]+1 ≤ x+r+ 12 < [x]+2.
1.1.18. Let y = x + n. Then [y] = [x] + n, since n is an integer. Therefore the problem is equivalent to proving
that [y/m] = [[y]/m] which is done in Example 1.37.
1.1.19. Let x = k + ϵ where k is an integer and 0 ≤ ϵ < 1. Further, let k = a2 + b, where a is thee
largest integer
√
2 2 2 2 2
√
such that a ≤ k. Then a ≤ k = a + b ≤ x = a + b + ϵ < (a + 1) . Then [ x] = a and [ [x]] = [ k] =
a also, proving the theorem.
1.1.20. Let x = k + ϵ where k is an integer and 0 ≤ ϵ < 1. Choose w from 0, 1, 2, . . . , m − 1 such that w/m ≤
ϵ < (w + 1)/m. Then w ≤ mϵ < w + 1. Then [mx] = [mk + mϵ] = mk + [mϵ] = mk + w. On the
other hand, the same inequality gives us (w + j)/m ≤ ϵ + j/m < (w + 1 + j)/m, for any integer j =
0, 1, 2, . . . , m − 1. Note that this implies [ϵ + j/m] = [(w + j)/m] which is either 0 or 1 for j in this range.
Indeed, it equals 1 precisely when w +j ≥ m, which happens for exactly w values of j in this range. Now
em−1 em−1 em−1 em−1
we compute j=0 [x + j/m] = j=0 [k + ϵ + j/m] = j=0 k + [ϵ + j/m] = mk + j=0 [(w + j)/m] =
em−1
mk + j=m−w 1 = mk + w which is the same as the value above.
1.1.21. a. Since the difference between any two consecutive terms of this sequence is 8, we may compute the
nth term by adding 8 to the first term n − 1 times. That is, an = 3 + (n − 1)8 = 8n − 5.
b. For each n, we have an − an−1 = 2n−1 , so we may compute the nth term of this sequence by adding
all the powers of 2, up to the (n − 1)th, to the first term. Hence an = 5 + 2 + 22 + 23 + · · · + 2n−1 =
5 + 2n − 2 = 2n + 3.
c. The nth term of this sequence appears√ to be zero,
√ unless n is a perfect square, in which case the term
is 1. If n is not a perfect square,
√ then√[ n] < n, where
√ [x]√represents the greatest integer function.
If n is a perfect square, then [ n] = n. Therefore, [[ n]/ n] equals 1 if n is a perfect square and 0
otherwise, as desired.
d. This is a Fibonacci-like sequence, with an = an−1 + an−2 , for n ≥ 3, and a1 = 1, and a2 = 3.
1.1.22. a. Each term given is 3 times the preceding term, so we conjecture that the nth term is the first term
multiplied by 3, n − 1 times. So an = 2 · 3n−1 .
, b. In this sequence, an = 0 if n is a multiple of 3, and equals 1 otherwise. Let [x] represent the greatest
integer function. Since [n/3] < n/3 when n is not a multiple of 3 and [n/3] = n/3 when n is a mul-
tiple of 3, we have that an = 1 − [[n/3]/(n/3)] .
c. If we look at the difference of successive terms, we have the sequence 1, 1, 2, 2, 3, 3, . . . . So if n is
odd, say n = 2k + 1, then an is obtained by adding 1 + 1 + 2 + 2 + 3 + 3 + · · · + k + k = 2tk to the first
term, which is 1. (Here tk stands for the kth triangular number.) So if n is odd, then an = 1 + 2tk
where k = (n − 1)/2. If n is even, say n = 2k, then an = a2k+1 − k = 1 − k + 2tk .
d. This is a Fibonacci-like sequence, with an = an−1 + 2an−2 , for n ≥ 3, and a1 = 3, and a2 = 5.
1.1.23. Three possible answers are an = 2n−1 , an = (n2 − n + 2)/2, and an = an−1 + 2an−2 .
1.1.24. Three possible answers are an = an−1 an−2 , an = an−1 + 2n − 3, and an = the number of letters in the
nth word of the sentence “If our answer is correct we will join the Antidisestablishmentarianism Society
and boldly state that ‘If our answer is correct we will join the Antidisestablishmentarianism Society and
boldly state....’ ”
1.1.25. This set is exactly the sequence an = n − 100, and hence is countable.
1.1.26. The function f (n) = 5n is a one-to-one correspondence between this set and the set of integers, which
is known to be countable.
1.1.27. One way to√show this is to imitate the proof that the set of rational
√ numbers is countable, replacing
a/b with a + b 2. Another way is to consider the function f (a + b 2) = 2a 3b which is a one-to-one map
of this set into the rational numbers, which is known to be countable.
1.1.28. Let A and B be two countable sets. If one or both of the sets are finite, say A is finite, then the listing
a1 , a2 , . . . , an , b1 , b2 , . . ., where any bi which is also in A is deleted from the list, demonstrates the count-
ability of A ∪ B. If both sets are infinite, then each can be represented as a sequence: A = {a1 , a2 , . . .},
and B = {b1 , b2 , . . .}. Consider the listing a1 , b1 , a2 , b2 , a3 , b3 , . . . and form a new sequence ci as follows.
Let c1 = a1 . Given that cn is determined, let cn+1 be the next element in the listing which is different
from each ci with i = 1, 2, . . . , n. Then this sequence is exactly the elements of A ∪ B, which is therefore
countable.
1.1.29. Suppose {Ai } is a countable collection of countable sets. Then each Ai can be represented by a se-
quence, as follows:
A1 = a11 a12 a13 ...
A2 = a21 a22 a23 ...
A3 = a31 a32 a33 ...
..
.
Consider the listing a11 , a12 , a21 , a13 , a22 , a31 , . . . , in which we first list the elements with subscripts
adding to 2, then the elements with subscripts adding to 3 and so on. Further, we order the elements
with subscripts adding to k in order of the first subscript. Form a new sequence ci as follows. Let c1 =
a1 . Given that cn is determined, let cn+1 be the next element in the listing which is different from each
e∞
ci with i = 1, 2, . . . , n. Then this sequence is exactly the elements of Ai , which is therefore countable.
i=1
√ √
1.1.30. a. Note that 2√≈ 1.4 = 7/5, so we might guess that 2 − 7/5 ≈ 0. If we multiply through by 5 we
expect that 5 2 − 7 should be small, and its value is approximately 0.071 which is much less than
1/8 = 0.125. So we may take a = 5 ≤ 8 and b = 7.
√ √
b. As in part (a), note that 3 2 = 1.2599 . . . ≈ 1.25 = 5/4, so we investigate 4 3 2 − 5 = 0.039 . . . ≤ 1/8.
So we may take a = 4 ≤ 8 and b = 5.
ELEMENTARY NUMBER THEORY AND ITS APPLICATIONS
7TH EDITION
CHAPTER NO. 01: THE INTEGERS
1.1. Numbers, Sequences, and Sums
1.1.1. a. The set of integers greater than 3 is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.
b. The set of even positive integers is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.
c. The set of positive rational numbers is not well-ordered. This set does not have a least element.
If a/b were the least positive rational number then a/(b + a) would be a smaller positive rational
number, which is a contradiction.
d. The set of positive rational numbers of the form a/2 is well-ordered. Consider a subset of numbers
of this form. The set of numerators of the numbers in this subset is a subset of the set of positive
integers, so it must have a least element b. Then b/2 is the least element of the subset.
e. The set of nonnegative rational numbers is not well-ordered. The set of positive rational numbers
is a subset with no least element, as shown in part (c).
1.1.2. Let S be the set of all positive integers of the form a − bk. S is not empty since a − b(−1) = a + b is a
positive integer. Then the well-ordering principle implies that S has a least element, which is the num-
ber we’re looking for.
1.1.3. Suppose that x and y are rational numbers. Then x = a/b and y = c/d, where a, b, c, and d are integers
̸ 0 and d ̸= 0. Then xy = (a/b) · (c/d) = ac/bd and x + y = a/b + c/d = (ad + bc)/bd where bd ̸=
with b =
0. Since both x + y and xy are ratios of integers, they are both rational.
1.1.4. a. Suppose that x is rational and y is irrational. Then there exist integers a and b such that x = ab where
a and b are integers with b ≠ 0. Suppose that x + y is rational. Then there exist integers c and d with
d ̸= 0 such that x + y = dc . This implies that y = (x + y) − x = (a/b) − (c/d) = (ad − bc)/bd, which
means that y is rational, a contradiction. Hence x + y is irrational.
√ √
b. This is false. A counterexample is given by 2 + (− 2) = 0.
√
c. This is false. A counterexample is given by 0 · 2 = 0.
√ √
d. This is false. A counterexample is given by 2 · 2 = 2.
√ √
1.1.5. Suppose that 3 were√ rational. Then√ there would exist positive integers a and b with √ 3 = a/b. Con-
sequently, the set S = {k 3 | k and k 3 are positive integers} √ is nonempty since
√ a = b √3. Therefore,
√ by
the√ well-ordering
√ property, S has a smallest element,
√ say s = t √ 3. We have s 3 − s = s 3 − t 3 = (s −
t) 3. Since s 3 = 3t√and s are both√ integers, s
√ 3 − s = (s − t) 3 must also be an
√ √integer. Furthermore,
√
it is positive, since s 3 − s = s( 3 − 1) and 3 > 1. It is less than s since s = t 3, s √3 = 3t, and 3 <
3. This contradicts the choice of s as the smallest positive integer in S. It follows that 3 is irrational.
1.1.6. Let S be a set of negative integers. Then the set T = {−s : s ∈ S} is a set of positive integers. By the
well-ordering principle, T has a least element t0 . We prove that −t0 is a greatest element of S. First note
, that since t0 ∈ S, then t0 = −s0 for some s0 ∈ S. Then −t0 = s0 ∈ S. Second, if s ∈ S, then −s ∈ T , so
t0 ≤ −s. Multiplying by −1 yields s ≤ −t0 . Since the choice of s was arbitrary, we see that −t0 is greater
than or equal to every element of S.
1.1.7. a. Since 0 ≤ 1/4 < 1, we have [1/4] = 0.
b. Since −1 ≤ −3/4 < 0, we have [−3/4] = −1.
c. Since 3 ≤ 22/7 < 4, we have [22/7] = 3.
d. Since −2 ≤ −2 < −1, we have [−2] = −2.
e. We compute [1/2 + [1/2]] = [1/2 + 0] = [1/2] = 0.
f. We compute [−3 + [−1/2]] = [−3 − 1] = [−4] = −4.
1.1.8. a. Since −1 ≤ −1/4 < 0, we have [−1/4] = −1.
b. Since −4 ≤ −22/7 < −3, we have [−22/7] = −4.
c. Since 1 ≤ 5/4 < 2, we have [5/4] = 1.
d. We compute [[1/2]] = [0] = 0.
e. We compute [[3/2] + [−3/2]] = [1 + (−2)] = [−1] = −1.
f. We compute [3 − [1/2]] = [3 − 0] = [3] = 3.
1.1.9. a. Since [8/5] = 1, we have {8/5} = 8/5 − [8/5] = 8/5 − 1 = 3/5.
b. Since [1/7] = 0, we have {1/7} = 1/7 − [1/7] = 1/7 − 0 = 1/7.
c. Since [−11/4] = −3, we have {−11/4} = −11/4 − [−11/4] = −11/4 − (−3) = 1/4.
d. Since [7] = 7, we have {7} = 7 − [7] = 7 − 7 = 0.
1.1.10. a. Since [−8/5] = −2, we have {−8/5} = −8/5 − [−8/5] = −8/5 − (−2) = 2/5.
b. Since [22/7] = 3, we have {22/7} = 22/7 − [22/7] = 22/7 − 3 = 1/7.
c. Since [−1] = −1, we have {−1} = −1 − [−1] = −1 − 1 = 0.
d. Since [−1/3] = −1, we have {−1/3} = −1/3 − [−1/3] = −1/3 − (−1) = 2/3.
1.1.11. If x is an integer, then [x] + [−x] = x − x = 0. Otherwise, x = z + r, where z is an integer and r is a
real number with 0 < r < 1. In this case, [x] + [−x] = [z + r] + [−z − r] = z + (−z − 1) = −1.
1.1.12. Let x = [x] + r where 0 ≤ r < 1. We consider two cases. First suppose that r < 21 . Then x + 12 =
[x] + (r + 12 ) < [x] + 1 since r + 21 < 1. It follows that [x + 12 ] = [x]. Also 2x = 2[x] + 2r < 2[x] + 1
since 2r < 1. Hence [2x] = 2[x]. It follows that [x] + [x + 12 ] = [2x]. Next suppose that 12 ≤ r < 1. Then
[x] + 1 ≤ x + (r + 12 ) < [x] + 2, so that [x + 12 ] = [x] + 1. Also 2[x] + 1 ≤ 2[x] + 2r = 2([x] + r) = 2x <
2[x] + 2 so that [2x] = 2[x] + 1. It follows that [x] + [x + 12 ] = [x] + [x] + 1 = 2[x] + 1 = [2x].
1.1.13. We have [x] ≤ x and [y] ≤ y. Adding these two inequalities gives [x] + [y] ≤ x + y. Hence [x + y] ≥
[[x] + [y]] = [x] + [y].
,1.1.14. Let x = a+r and y = b+s, where a and b are integers and r and s are real numbers such that 0 ≤ r, s <
1. By Exercise 12, [2x] + [2y] = [x] + [x + 12 ] + [y] + [y + 12 ]. We now need to show that [x + 12 ] + [y + 12 ] ≥
[x + y]. Suppose 0 ≤ r, s < 12 . Then [x + 12 ] + [y + 12 ] = a + b + [r + 12 ] + [s + 12 ] = a + b, and [x + y] =
a+b+[r +s] = a+b, as desired. Suppose that 12 ≤ r, s < 1. Then [x+ 21 ]+[y + 21 ] = a+b+[r + 12 ]+[s+ 12 ] =
a + b + 2, and [x + y] = a + b + [r + s] = a + b + 1, as desired. Suppose that 0 ≤ r < 12 ≤ s < 1. Then
[x + 21 ] + [y + 12 ] = a + b + 1, and [x + y] ≤ a + b + 1.
1.1.15. Let x = a + r and y = b + s, where a and b are integers and r and s are real numbers such that 0 ≤
r, s < 1. Then [xy] = [ab + as + br + sr] = ab + [as + br + sr], whereas [x][y] = ab. Thus we have [xy] ≥
[x][y] when x and y are both positive. If x and y are both negative, then [xy] ≤ [x][y]. If one of x and y
is positive and the other negative, then the inequality could go either direction. For examples take x =
−1.5, y = 5 and x = −1, y = 5.5. In the first case we have [−1.5 · 5] = [−7.5] = −8 > [−1.5][5] = −2 · 5 =
−10. In the second case we have [−1 · 5.5] = [−5.5] = −6 < [−1][5.5] = −1 · 5 = −5.
1.1.16. If x is an integer then −[−x] = −(−x) = x, which certainly is the least integer greater than or equal
to x. Let x = a + r, where a is an integer and 0 < r < 1. Then −[−x] = −[−a − r] = −(−a + [−r]) =
a − [−r] = a + 1, as desired.
1.1.17. Let x = [x] + r. Since 0 ≤ r < 1, x + 12 = [x] + r + 12 . If r < 12 , then [x] is the integer nearest to x and
[x+ 12 ] = [x] since [x] ≤ x+ 21 = [x]+r + 12 < [x]+1. If r ≥ 21 , then [x]+1 is the integer nearest to x (choos-
ing this integer if x is midway between [x] and [x+1]) and [x+ 12 ] = [x]+ 1 since [x]+1 ≤ x+r+ 12 < [x]+2.
1.1.18. Let y = x + n. Then [y] = [x] + n, since n is an integer. Therefore the problem is equivalent to proving
that [y/m] = [[y]/m] which is done in Example 1.37.
1.1.19. Let x = k + ϵ where k is an integer and 0 ≤ ϵ < 1. Further, let k = a2 + b, where a is thee
largest integer
√
2 2 2 2 2
√
such that a ≤ k. Then a ≤ k = a + b ≤ x = a + b + ϵ < (a + 1) . Then [ x] = a and [ [x]] = [ k] =
a also, proving the theorem.
1.1.20. Let x = k + ϵ where k is an integer and 0 ≤ ϵ < 1. Choose w from 0, 1, 2, . . . , m − 1 such that w/m ≤
ϵ < (w + 1)/m. Then w ≤ mϵ < w + 1. Then [mx] = [mk + mϵ] = mk + [mϵ] = mk + w. On the
other hand, the same inequality gives us (w + j)/m ≤ ϵ + j/m < (w + 1 + j)/m, for any integer j =
0, 1, 2, . . . , m − 1. Note that this implies [ϵ + j/m] = [(w + j)/m] which is either 0 or 1 for j in this range.
Indeed, it equals 1 precisely when w +j ≥ m, which happens for exactly w values of j in this range. Now
em−1 em−1 em−1 em−1
we compute j=0 [x + j/m] = j=0 [k + ϵ + j/m] = j=0 k + [ϵ + j/m] = mk + j=0 [(w + j)/m] =
em−1
mk + j=m−w 1 = mk + w which is the same as the value above.
1.1.21. a. Since the difference between any two consecutive terms of this sequence is 8, we may compute the
nth term by adding 8 to the first term n − 1 times. That is, an = 3 + (n − 1)8 = 8n − 5.
b. For each n, we have an − an−1 = 2n−1 , so we may compute the nth term of this sequence by adding
all the powers of 2, up to the (n − 1)th, to the first term. Hence an = 5 + 2 + 22 + 23 + · · · + 2n−1 =
5 + 2n − 2 = 2n + 3.
c. The nth term of this sequence appears√ to be zero,
√ unless n is a perfect square, in which case the term
is 1. If n is not a perfect square,
√ then√[ n] < n, where
√ [x]√represents the greatest integer function.
If n is a perfect square, then [ n] = n. Therefore, [[ n]/ n] equals 1 if n is a perfect square and 0
otherwise, as desired.
d. This is a Fibonacci-like sequence, with an = an−1 + an−2 , for n ≥ 3, and a1 = 1, and a2 = 3.
1.1.22. a. Each term given is 3 times the preceding term, so we conjecture that the nth term is the first term
multiplied by 3, n − 1 times. So an = 2 · 3n−1 .
, b. In this sequence, an = 0 if n is a multiple of 3, and equals 1 otherwise. Let [x] represent the greatest
integer function. Since [n/3] < n/3 when n is not a multiple of 3 and [n/3] = n/3 when n is a mul-
tiple of 3, we have that an = 1 − [[n/3]/(n/3)] .
c. If we look at the difference of successive terms, we have the sequence 1, 1, 2, 2, 3, 3, . . . . So if n is
odd, say n = 2k + 1, then an is obtained by adding 1 + 1 + 2 + 2 + 3 + 3 + · · · + k + k = 2tk to the first
term, which is 1. (Here tk stands for the kth triangular number.) So if n is odd, then an = 1 + 2tk
where k = (n − 1)/2. If n is even, say n = 2k, then an = a2k+1 − k = 1 − k + 2tk .
d. This is a Fibonacci-like sequence, with an = an−1 + 2an−2 , for n ≥ 3, and a1 = 3, and a2 = 5.
1.1.23. Three possible answers are an = 2n−1 , an = (n2 − n + 2)/2, and an = an−1 + 2an−2 .
1.1.24. Three possible answers are an = an−1 an−2 , an = an−1 + 2n − 3, and an = the number of letters in the
nth word of the sentence “If our answer is correct we will join the Antidisestablishmentarianism Society
and boldly state that ‘If our answer is correct we will join the Antidisestablishmentarianism Society and
boldly state....’ ”
1.1.25. This set is exactly the sequence an = n − 100, and hence is countable.
1.1.26. The function f (n) = 5n is a one-to-one correspondence between this set and the set of integers, which
is known to be countable.
1.1.27. One way to√show this is to imitate the proof that the set of rational
√ numbers is countable, replacing
a/b with a + b 2. Another way is to consider the function f (a + b 2) = 2a 3b which is a one-to-one map
of this set into the rational numbers, which is known to be countable.
1.1.28. Let A and B be two countable sets. If one or both of the sets are finite, say A is finite, then the listing
a1 , a2 , . . . , an , b1 , b2 , . . ., where any bi which is also in A is deleted from the list, demonstrates the count-
ability of A ∪ B. If both sets are infinite, then each can be represented as a sequence: A = {a1 , a2 , . . .},
and B = {b1 , b2 , . . .}. Consider the listing a1 , b1 , a2 , b2 , a3 , b3 , . . . and form a new sequence ci as follows.
Let c1 = a1 . Given that cn is determined, let cn+1 be the next element in the listing which is different
from each ci with i = 1, 2, . . . , n. Then this sequence is exactly the elements of A ∪ B, which is therefore
countable.
1.1.29. Suppose {Ai } is a countable collection of countable sets. Then each Ai can be represented by a se-
quence, as follows:
A1 = a11 a12 a13 ...
A2 = a21 a22 a23 ...
A3 = a31 a32 a33 ...
..
.
Consider the listing a11 , a12 , a21 , a13 , a22 , a31 , . . . , in which we first list the elements with subscripts
adding to 2, then the elements with subscripts adding to 3 and so on. Further, we order the elements
with subscripts adding to k in order of the first subscript. Form a new sequence ci as follows. Let c1 =
a1 . Given that cn is determined, let cn+1 be the next element in the listing which is different from each
e∞
ci with i = 1, 2, . . . , n. Then this sequence is exactly the elements of Ai , which is therefore countable.
i=1
√ √
1.1.30. a. Note that 2√≈ 1.4 = 7/5, so we might guess that 2 − 7/5 ≈ 0. If we multiply through by 5 we
expect that 5 2 − 7 should be small, and its value is approximately 0.071 which is much less than
1/8 = 0.125. So we may take a = 5 ≤ 8 and b = 7.
√ √
b. As in part (a), note that 3 2 = 1.2599 . . . ≈ 1.25 = 5/4, so we investigate 4 3 2 − 5 = 0.039 . . . ≤ 1/8.
So we may take a = 4 ≤ 8 and b = 5.
