Solution Set of Homework Assignment 3
1.(p.88) 22. We only have to determine whether there are positive real numbers C1, C2, and
a positive integer k s.t.
C1 | g(x) | £ | f(x) | £ C2 | g(x) |, whenever x > k.
a)Taking C1=1, C2=10, k=1, x £ 3x + 7 £ 10x, whenever x>1.
b)Taking C1=1, C2=3, k=3, x2£ 2x2 + x - 7 £ 3x2, whenever x>3.
c)Taking C1=1/2, C2=2, k=1, (1/2)x £ ë x + 1/2û £ 2x, whenever x>1.
d)Taking C1=2, C2=3, k=2, log2x2 =2log2x £ log(x2+1)£ 3log2x=log2x3, whenever x>2.
e)Taking C1=1/4, C2=1, k=1, (1/4) log2x £ log10x = log2x / log210 £ log2x, whenever x>1.
2.(p.182) 34. To show that the statements are equivalent, we can prove that the implications
i)® ii), ii)® iii), iii)® i) are true.
a.i)® ii) : If i) is true, n = 5k, where k is an integer. Since n2=5× 5k2 , ii) is true.
b.ii)® iii): If ii) is true, then n2 = 0 (mod 5) ¹ ± 1 (mod 5). Thus iii) is true.
c.iii)® i) : We can use an indirect proof to show that iii)® i) is true. Assume that i) is false. Then n º 1 (mod 5) or n º 2 (mod 5) or n º 3 (mod 5) or n º 4 (mod 5). If n º 1 (mod 5),
i.e. n = 5k + 1 ,where k is an integer, then n2 = 25k2 + 10k +1 º 1 (mod 5). If n º 2 (mod 5),
then n2 º 4 (mod 5) º -1 (mod 5). If n º 3 (mod 5), then n2 º 4 (mod 5) º -1 (mod 5). If n º
3 (mod 5), then n2 º 1 (mod 5). Hence n2 º ± 1 (mod 5). This means that iii) is false. Thus
if iii) is true, then i) is true.
From a, b, c, 3 statements i), ii), iii) are equivalent.
(p.182) 36. Disproof We can show that there are not 4 consecutive odd positive integers that are
primes. We know that 3, 5, 7, 9 are not such consecutive odd positive integers. Now consider a
sequence of 4 consecutive odd positive integers, p, p+2, p+4, p+6 where p is a odd positive
integer s.t. p > 3. For all of these numbers to be primes, it is necessary that p=3k+1 or p=3k+2,
where k is an positive integer. If p=3k+1, then p+2=(3k+1)+2=3(k+1) so p+2 is not a prime.
And if p=3k+2, then p+4=(3k+2)+4=3(k+2) so p+4 is not a prime. Hence any sequence of 4
consecutive odd positive integers cannot be primes. Thus it is not true that given a positive
integer n, there are n consecutive odd positive integers that are primes.
3. (p.78) 12.
4.(p.89) 30. To disprove that if f(x) is O(g(x)) then 2f(x) is O(2g(x)), we can find a
counterexample. Let f(x) = 2x and g(x) = x. Then clearly 2x = O(x). Suppose that there exists
a constant C such that 22x £ C× 2x. Since C is positive, we can let C = 2C0 for a constant C0
without loss of generality. Then 22x £ 2x+C0. We cannot find a constant k such that 22x £ 2x+C0
whenever x > k. Thus it is not true that if f(x) is O(g(x)) then 2f(x) is O(2g(x)).
5. (1/2)n << 2 = n1/log n << 1001n1001001 << (log n)log n = n log log n << nlog n << 10010n +1.000001n <<
1.0001n << (log n)n.