SOLUTION MANUAL FOR A FIRST COURSE IN ABSTRACT ALGEBRA, WITH APPLICATIONS 8TH EDITION BY JOSEPH J. ROTMAN LATEST 2024
Exercises for Chapter 1
1.1 True
... [Show More] or false with reasons.
(i) There is a largest integer in every nonempty set of negative inte- gers.
Solution. True. If C is a nonempty set of negative integers, then
−C = {−n : n ∈ C }
is a nonempty set of positive integers. If −a is the smallest element of −C , which exists by the Least Integer Axiom, then −a ≤ −c for all c ∈ C , so that a ≥ c for all c ∈ C .
(ii) There is a sequence of 13 consecutive natural numbers containing exactly 2 primes.
Solution. True. The integers 48 through 60 form such a sequence; only 53 and 59 are primes.
(iii) There are at least two primes in any sequence of 7 consecutive natural numbers.
Solution. False. The integers 48 through 54 are 7 consecutive natural numbers, and only 53 is prime.
(iv) Of all the sequences of consecutive natural numbers not containing 2 primes, there is a sequence of shortest length.
Solution. True. The set C consisting of the lengths of such (finite) sequences is a nonempty subset of the natural numbers.
(v) 79 is a prime.
Solution. True. √79 < √81 9, and 79 is not divisible by 2, 3,
5, or 7.
(vi) There exists a sequence of statements S(1), S(2), ... with S(2n) true for all n ≥ 1 and with S(2n − 1) false for every n ≥ 1. Solution. True. Define S(2n − 1) to be the statement n /= n, and define S(2n) to be the statement n = n.
(vii) For all n 0, we have n Fn , where Fn is the nth Fibonacci number.
Solution. True. We have 0 = F0, 1 = F1, 1 = F2, and 2 = F3. Use the second form of induction with base steps n = 2 and n = 3 (verifying the inductive step will show why we choose these numbers). By the inductive hypothesis, n 2 Fn−2 and n 1 Fn 1. Hence, 2n 3 Fn . But n 2n 3 for all n 3,
as desired.
(viii) If m and n are natural numbers, then (mn)!= m!n!.
Solution. False. If m = 2 = n, then (mn)!= 24 and m!n!= 4.
1.2 (i) For any n ≥ 0 and any r /= 1, prove that
1 + r + r 2 + r 3 + ••• + rn = (1 − rn+1)/(1 − r).
Solution. We use induction on n ≥ 1. When n = 1, both sides equal 1 + r . For the inductive step, note that
[1 + r + r 2 + r 3 + ••• + rn ]+ rn+1 = (1 − rn+1)/(1 − r) + rn+1
1 − rn+1 + (1 − r)rn+1
1 − r
(ii) Prove that
1 rn+2
1 − r .
1 + 2 + 22 + ••• + 2n = 2n+1 − 1.
Solution. This is the special case of the geometric series when r = 2; hence, the sum is (1 − 2n+1)/(1 − 2) = 2n+1 − 1. One can also prove this directly, by induction on n ≥ 0.
1.3 Show, for all n 1, that 10n leaves remainder 1 after dividing by 9. Solution. This may be rephrased to say that there is an integer qn with 10n 9qn 1. If we define q1 1, then 10 q1 1, and so the base step is true.
For the inductive step, there is an integer qn with 10n+1 = 10 × 10n = 10(9qn + 1)
= 90qn + 10 = 9(10qn + 1) + 1.
Define qn+1 = 10qn + 1, which is an integer.
1.4 Prove that if 0 a b, then an bn for all n 0.
Solution. Base step. a0 1 b0, and so a0 b0.
Inductive step. The inductive hypothesis is
an ≤ bn.
Since a is positive, Theorem 1.4(i) gives an+1 = aan ≤ abn ; since b is positive, Theorem 1.4(i) now gives abn ≤ bbn = bn+1.
1.5 Prove that 12 + 22 + ••• + n2 = 1 n(n + 1)(2n + 1) = 1 n3 + 1 n2 + 1 n.
Solution. The proof is by induction on n ≥ 1. When n = 1, the left side is
1 and the right side is 1 + 1 + 1 = 1.
3 2 6
For the inductive step,
[12 + 22 + ••• + n2]+ (n + 1)2 = 1 n3 + 1 n2 + 1 n + (n + 1)2
= 1 (n + 1)3 + 1 (n + 1)2 + 1 (n + 1),
3 2 6
after some elementary algebraic manipulation.
1.6 Prove that 13 + 23 + ••• + n3 = 1 n4 + 1 n3 + 1 n2.
Solution. Base step: When n 1, both sides equal 1.
Inductive step:
[13 + 23 + ••• + n3]+ (n + 1)3 = 1 n4 + 1 n3 + 1 n2 + (n + 1)3.
Expanding gives
4 2 4
1 n4 + 3 n3 + 13 n2 + 3n + 1,
which is
4 2 4
1 (n + 1)4 + 1 (n + 1)3 + 1 (n + 1)2.
1.7 Prove that 14 + 24 + ••• + n4 = 1 n5 + 1 n4 + 1 n3 − 1 n.
Solution. The proof is by induction on n ≥ 1. If n − 1, then the left side is
1, while the right side is 1 + 1 + 1 − 1 = 1 as well.
5 2 3 30
For the inductive step,
14 + 24 + ••• + n4 + (n + 1)4 = 1 n5 + 1 n4 + 1 n3 − 1 n + (n + 1)4.
It is now straightforward to check that this last expression is equal to
1 (n + 1)5 + 1 (n + 1)4 + 1 (n + 1)3 − 1 (n + 1).
1.8 Find a formula for 1 3 5 (2n 1), and use mathematical induction to prove that your formula is correct.
Solution. We prove by induction on n ≥ 1 that the sum is n2.
2Base Step. When n = 1, we interpret the left side to mean 1. Of course,
1 1, and so the base step is true.
Inductive Step.
1 + 3 + 5 + ••• + (2n − 1) + (2n + 1)
= 1 + 3 + 5 + ••• + (2n − 1)]+ (2n + 1)
= n2 + 2n + 1
= (n + 1)2.
1.9 Find a formula for 1 + .n j ! j , and use induction to prove that your
Solution. A list of the sums for n 1, 2, 3, 4, 5 is 2, 6, 24, 120, 720. These are factorials; better, they are 2 , 3 , 4 , 5 , 6 . We have been led to the guess
n
S(n) : 1 + j ! j = (n + 1)!.
j =1
We now use induction to prove that the guess is always true. The base step S(1) has already been checked; it is on the list. For the inductive step, we must prove
n+1
S(n + 1) : 1 + j ! j = (n + 2)!.
j =1
Rewrite the left side as
n
1 + j ! j + (n + 1)!(n + 1).
j =1
By the inductive hypothesis, the bracketed term is (n 1) , and so the left side equals
(n + 1)!+ (n + 1)!(n + 1) = (n + 1)![1 + (n + 1)]
= (n + 1)!(n + 2)
= (n + 2)!.
By induction, S(n) is true for all n ≥ 1.
1.10 (M. Barr) There is a famous anecdote describing a hospital visit of G. H. Hardy to Ramanujan. Hardy mentioned that the number 1729 of the taxi he had taken to the hospital was not an interesting number. Ramanujan disagreed, saying that it is the smallest positive integer that can be written as the sum of two cubes in two different ways.
(i) Prove that Ramanujan’s statement is true.
Solution. First, 1729 is the sum of two cubes in two different ways:
1729 = 13 + 123; 1927 = 93 + 103.
Second, no smaller number n has this property. If n a3 b3, then a, b 12. It is now a matter of checking all pairs a3 b3 for such a and b. [Show Less]