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.