__Solution Set of Homework Assignment 3__

1.(p.88) 22. We only have to determine whether there are positive real numbers C_{1},
C_{2}, and

a positive integer k s.t.

C

_{1}| g(x) | £ | f(x) | £ C_{2}| g(x) |, whenever x > k.a)Taking C

_{1}=1, C_{2}=10, k=1, x £ 3x + 7 £ 10x, whenever x>1.b)Taking C

_{1}=1, C_{2}=3, k=3, x^{2£ }2x^{2}+ x - 7 £ 3x^{2}, whenever x>3.c)Taking C

_{1}=1/2, C_{2}=2, k=1, (1/2)x £ ë x + 1/2û £ 2x, whenever x>1.d)Taking C

_{1}=2, C_{2}=3, k=2, log_{2}x^{2}=2log_{2}x £ log(x^{2}+1)£ 3log_{2}x=log_{2}x^{3}, whenever x>2.e)Taking C

_{1}=1/4, C_{2}=1, k=1, (1/4) log_{2}x £ log_{10}x = log_{2}x / log_{2}10 £ log_{2}x, 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 n

^{2}=5× 5k^{2 }, ii) is true.b.ii)® iii): If ii) is true, then n

^{2 }= 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 n

^{2}= 25k^{2}+ 10k +1 º 1 (mod 5). If n º 2 (mod 5),

then n^{2 º }4 (mod 5) º
-1 (mod 5). If n º 3 (mod 5), then n^{2 º
}4 (mod 5) º -1 (mod 5). If n º

3 (mod 5), then n^{2 º }1 (mod 5). Hence n^{2 º }± 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 2^{f(x)} is O(2^{g(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 2^{2x} £ C× 2^{x}. Since C is positive, we can let C = 2^{C0 }for
a constant C0

without loss of generality. Then 2^{2x} £ 2^{x+C0}.
We cannot find a constant k such that 2^{2x} £ 2^{x+C0
}

whenever x > k. Thus it is not true that if f(x) is O(g(x)) then 2^{f(x)}
is O(2^{g(x)}).

5. (1/2)^{n} << 2 = n^{1/log n} << 1001n^{1001001 }<<
(log n)^{log n }= n ^{log log n} << n^{log n} <<
10010n +1.000001^{n} <<

1.0001^{n} << (log n)^{n}.