HW 6 Sols
HW 6 Sols
HW 6 Sols
since 1n−k = 1.
2. This problem involves lists made from the letters T, H, E, O, R, Y , with repetition
allowed.
(a) How many 4-letter lists are there that do not begin with a T or do not end in a
Y?
(b) How many 4-letter lists are there in which the sequence of letters T, H, E appear
consecutively?
Solution:
(a) Let A = the set of 4-letter lists that do not begin with a T , and let B = the set of
4-letter lists that do not end in a Y . Since the number of lists (with repetition)
that do not begin with a T is (5)(6)(6)(6) = 5·63 = 1080, |A| = 1080. The number
of lists (with repetition) that do not end in a Y is (6)(6)(6)(5) = 63 5 = 1080, so
|B| = 1080. We seek |A ∪ B|, which is given by
|A ∪ B| = |A| + |B| − |A ∩ B|.
Therefore, we need to determine |A ∩ B|. In other words, we need to determine
the number of 4-letter lists that do not begin with a T and end with a Y , but this
is given by (5)(6)(6)(5) = 52 62 = 900. So, there are 1080 + 1080 − 900 = 1, 260
4-letter lists that do not begin with a T or do not end in a Y .
1
(b) T, H, E can be either the first three letters or the second three letters. There are
1(1)(1)6 = 6 lists where T, H, E are the first three letters and, similarly, 6 lists
where T, H, E are the second three letters. Therefore, since these two sets are
mutually exclusive, there are 6 + 6 = 12 4-letter lists in which the sequence of
letters T, H, E appear consecutively.
x3 = (2a + 1)3
= (2a)3 + 3(2a)2 (1) + 3(2a)(1)2 + (1)3 (by the binomial theorem)
= 8a3 + 12a2 + 6a + 1
= 2(4a3 + 6a2 + 3a) + 1.
Proof. Let a, b, c be integers such that a|b and a|c. Then, b = ma for some integer m
and c = na for some integer n. Therefore,
b + c = ma + na = (m + n)a.
4
5. Prove that if x ∈ R and 0 < x < 4, then ≥ 1.
x(4 − x)
4
Solution: Side work: We want to show that ≥ 1. This is the same as
x(4 − x)
showing that 4 ≥ x(4 − x) = 4x − x2 . [You should answer why this is true.]
x2 − 4x + 4 ≥ 0.
2 Homework 6
Proof. Let x be a real number such that 0 < x < 4. Then
(x − 2)2 ≥ 0
x2 − 4x + 4 ≥ 0
4 ≥ 4x − x2
4 ≥ x(4 − x)
4
≥ 1.
x(4 − x)
Case 1: n is even.
In this case, n = 2a for some integer a. Then
n2 − 3n + 9 = (2a)2 − 3(2a) + 9
= 4a2 − 6a + 9
= 2(2a2 − 3a + 4) + 1.
Proof. Suppose that n is a nonnegative integer. There are two cases to consider: n = 0
and n > 0.
3 Homework 6
Case 1: n = 0.
If n = 0, then 2n + 6n = 20 + 60 = 1 + 1 = 2, which is even.
Case 2: n > 0.
If n > 0, then we have the following.
2n + 6n = 2n + (2 · 3)n
= 2n + 2n 3n
= 2 · 2n−1 + 2 · 2n−1 3n
= 2(2n−1 + 2n−1 3n ).
a+b a+b
8. Prove that for every two distinct integers a and b, either > a or > b.
2 2
Solution:
Proof. Let a and b be distinct integers. There are two possibilities: a > b or b > a.
Case 1: a > b.
Since a > b, we have
a+b a b
= +
2 2 2
a a
> + (since a > b)
2 2
a+b
=⇒ > a.
2
Case 2: b > a.
Since b > a, we have
a+b a b
= +
2 2 2
b b
> + (since b > a)
2 2
a+b
=⇒ > b.
2
a+b
These cases show that if a and b are distinct integers, then either > a or
2
a+b
> b.
2
4 Homework 6
9. Evaluate the proof of the following proposition.
Proof. Assume, without loss of generality, that x is even. Then x = 2a for some integer
a. Thus,
xy 2 = (2a)y 2 = 2(ay 2 ).
Since ay 2 is an integer, xy 2 is even.
Solution: The problem with this proof is the assumption “without loss of generality.”
This proof really only shows that if x is an even integer and y is an arbitrary integer,
then xy 2 is even. To show the given proposition, we need to also analyze the case
where x is odd.
5 Homework 6