Exercises from Section 1.2.2

Tord M. Johnson

January 30, 2014

1. [00] What is the smallest positive rational number?

There is no smallest positive rational number. To see why, let q > 0 be this smallest number, in which case, clearly, q > q2 > 0, a contradiction. Hence, there is no smallest positive rational number.

2. [00] Is 1 + 0.239999999 a decimal expansion?

The expression 1 + 0.239999999 is not a valid decimal expansion, at least according to the definition given in the text on page 21, as it violates the requirement that the sequence of digits doesn’t end with infinitely many 9s.

3. [02] What is (3)3?

We can simplify the expression using the rules (4) on page 22, and simple arithmetic.

(3)3 = (3)2 (3) = (3)1 (3)(3) = (3)1 9 = (3)0 (3)(9) = (3)0 27 = 1 27 = 1 27

And so, (3)3 = 1 27.

4. [05] What is (0.125)23?

We can simplify the expression using the rules (4) and (6) on page 22, and simple arithmetic.

(0.125)23 = (1 8)23 = (1 8)23 = (8)(1 8)13 = (8)(8)(1 8)03 = (64)(1 8)03 = (64)(1)3 = 643 = 4

And so, (0.125)23 = 4.

5. [05] We defined real numbers in terms of a decimal expansion. Discuss how we could have defined them in terms of a binary expansion instead, and give a definition to replace Eq. (2).

We could have defined real numbers in terms of a binary expansion by simply using the base two number system instead of base ten.

A real number is a quantity x that has a binary expansion

x = n + 0.d1d2d3, (5.1)

where n is an integer, each di is a digit between 0 and 1, and the sequence of digits doesn’t end with infinitely many 1s. The representation (5.1) means that

n + d1 2 + d2 4 + + dk 2k x < n + d1 2 + d2 4 + + dk 2k + 1 2k, (5.2)

for all positive integers k.

6. [10] Let x = m + 0.d1d2 and y = n + 0.e1e2 be real numbers. Give a rule for determining whether x = y, x < y, or x > y, based on the decimal representation.

Given x = m + 0.d1d2 and y = n + 0.e1e2 be real numbers, we can define the following relations.

x = y. x is equivalent to y if m = n and di = ei for all i 1.

x < y. x is less than y if either m < n or (m = n and) d1 < e1 or (m = n and) di = ei for all 1 i < k and dk < ek.

x > y. x is greater than y if either m > n or (m = n and) d1 > e1 or (m = n and) di = ei for all 1 i < k and dk > ek.

7. [M23] Given that x and y are integers, prove the laws of exponents, starting from the definition given by Eq. (4).

Given integers x, y; a positive real number b; and Eq. (4) on page 22, we may prove Eq. (5).

Proposition. bx+y = bxby for any positive real number b and integers x, y.

Proof. Assume b an arbitrary positive real and x, y integers. We must show that bx+y = bxby. If x = 0, then clearly:

bx+y = b0+y = by = (1)by = b0by = bxby

Then, for the inductive step, we consider two cases, x 0 and x 0.

Case 1. [x 0.] Assuming bk+y = bkby for k 0, we must show that b(k+1)+y = bk+1by. But:

b(k+1)+y = bk+y+1 = bk+yb1 = bkbyb1 = bkb1by = bk+1by

as we needed to show in this case.

Case 2. [x 0.] Assuming bk+y = bkby for k 0, we must show that b(k1)+y = bk1by. But:

b(k1)+y = bk+y1 = bk+yb1 = bkbyb1 = bkb11by = bk1by

as we needed to show in this case.

Therefore, bx+y = bxby for any positive real number b and integers x, y as we needed to show. □

Proposition. (bx)y = bxy for any positive real number b and integers x, y.

Proof. Assume b an arbitrary positive real and x, y integers. We must show that (bx)y = bxy. If x = 0, then clearly:

(b0)y = 1y = 1 = b0 = b0y = bxy

Then, for the inductive step, we consider two cases, x 0 and x 0.

Case 1. [x 0.] Assuming (bk)y = bky for k 0, we must show that (bk+1)y = b(k+1)y. But from the previous proposition:

(bk+1)y = (bkb1)y = (bkb)y = (bk)yby = bkyby = bky+y = b(k+1)y

as we needed to show in this case.

Case 2. [x 0.] Assuming (bk)y = bky for k 0, we must show that (bk1)y = b(k1)y. But from the previous proposition:

(bk1)y = (bkb1)y = (bk)y(b1)y = bkyby = bkyy = b(k1)y

as we needed to show in this case.

Therefore, (bx)y = bxy for any positive real number b and integers x, y as we needed to show. □

8. [25] Let m be a positive integer. Prove that every positive real number u has a unique positive mth root, by giving a method to construct successively the values n,d1,d2, in the decimal expansion of the root.

Given a positive real number u and positive integer m, we may present a method to construct um = n + d1d2, and in so doing, prove that um exists uniquely.

First, determine n by evaluating for which integer j 0

jm u < (j + 1)m

and let n = j.

Then, for k 1, we successively determine for which integers dk, 1 dk 9

(n + 1ik di 10i)m u < (n + 1ik di 10i + 1 10k)m

for k as great as we please.

9. [M23] Given that x and y are rational, prove the laws of exponents under the assumption that the laws hold when x and y are integers.

We may prove the laws of exponents for rational exponents, assuming the laws for integer exponents.

Proposition. bx+y = bxby for any positive real number b and rationals x, y.

Proof. Assume b an arbitrary positive real and x = pq, y = rs rationals. We must show that bx+y = bxby. But:

bx+y = bpq+rs = b(ps+rq)(qs) = (bps+rq)1(qs) = (bpsbrq)1(qs) = (bps)1(qs))(brq)1(qs) = bpsqsbrqqs = bpqbrs = bxby

Proposition. (bx)y = bxy for any positive real number b and rationals x, y.

Proof. Assume b an arbitrary positive real and x = pq, y = rs rationals. We must show that (bx)y = bxy. But:

(bx)y = (bpq)rs = ((bp)1q)rs = (bp)r(qs) = (bpr)1(qs) = b(pr)(qs) = b(pq)(rs) = bxy

10. [18] Prove that log 102 is not a rational number.

We may prove that log 102 is not a rational number.

Proposition. log 102 is irrational.

Proof. Assume that it is not. That is, assume log 102 = pq for some positive integers p, q. That is, assume 10pq = 2 or equivalently, 10p = 2q. But no such positive integers exist. Hence, log 102 is irrational. □

11. [10] If b = 10 and x log 102, to how many decimal places of accuracy will we need to know the value of x in order to determine the first three decimal places of the decimal expansion of bx? [Note: You may use the result of exercise 10 in your discussion.]

As a result of the proof from exercise 10, since log 102 is irrational, bx for b = 10 and x = log 102 (that is, an irrational power x of 10), we may never know enough decimal places of x in order to determine the first three decimal places of the decimal expansion of bx.

12. [02] Explain why Eq. (10) follows from Eqs. (8).

Eq. (10) claims that

log 102 = 0.30102999

and by the definition of Eq. (7) and results of Eqs. (8) we have that

1.9999999739 = 100.30102999 2 < 100.30103000 = 2.0000000199

Taking logarithms yields

0.30102999 log 102 < 0.30103000

and so by definition of decimal expansion, log 102 = 0.30102999 .

13. [M23] (a) Given that x is a positive real number and n is a positive integer, prove the inequality 1 + xn 1 xn. (b) Use this fact to justify the remarks following (7).

First, we must prove a relation.

Proposition. 1 + xn 1 xn for any positive real numbers x and all positive integers n.

Proof. Let x by an arbitrary positive real number so that x > 0. We must show that 1 + xn 1 xn for all integers n > 0, or equivalently, that ny + 1 (y + 1)n for y = xn.

For n = 1, clearly y + 1 (y + 1)1. Then, assuming ky + 1 (y + 1)k for k > 0, we must show that (k + 1)y + 1 (y + 1)k+1. But:

(k + 1)y + 1 = ky + 1 + y (y + 1)k + y (y + 1)k + (y + 1) (y + 1)k(y + 1) = (y + 1)k+1

For x = b 1 and n = 10k, this fact tells us that

1 + (b 1)10k 1 = b110k 1 (b 1)10k

Since bn+d110++dk10k bn+1, we have

bn+d110++dk10k b110k 1 bn+1(b 1)10k

for the difference bn+d110++dk10k b110k 1 = bn+d110++dk10k+110k bn+d110++dk10k , which justifies the remarks following Eq. (7).

14. [15] Prove Eq. (12).

We may prove Eq. (12).

Proposition. log b(cy) = ylog bc if c > 0.

Proof. Let c > 0. We must show that log b(cy) = ylog bc. By the laws of exponents:

cy = (blog bc)y = by log bc

Taking logarithms yields:

log b(cy) = log b(by log bc) = ylog bc

As we need to show. □

15. [10] Prove or disprove:

log bxy = log bx log by,      if x,y > 0.

We are able to prove the proposition.

Proposition. log bxy = log bx log by if x,y > 0.

Proof. Let x,y > 0. We must show that log bxy = log bx log by. But by Eqs. (11) and (12):

log bx log by = log bx + log b(y1) = log bx + log b(1y) = log bxy

As we needed to show. □

16. [00] How can log 10x be expressed in terms of ln x and ln 10?

By Eq. (14)

log 10x = ln x ln 10.

17. [05] What is lg 32? log ππ? ln e? log b1? log b(1)?

Since 25 = 32,

lg 32 = 5.

Since π1 = π,

log ππ = 1.

Since e1 = e,

ln e = 1.

By the law of exponents, that b0 = 1, we have

log b1 = 0;

but since bn 0 for all positive real numbers b and integers n,

log b(1)

is undefined.

18. [10] Prove or disprove: log 8x = 1 2 lg x.

We are able to disprove the proposition, by way of counterexample. Consider x = 8. log 8x = log 88 = 13 2 = 1 2 lg 8 = 1 2 lg x.

19. [20] If n is an integer whose decimal representation is 14 digits long, will the value of n fit in a computer word with a capacity of 47 bits and a sign bit?

If n is an integer whose decimal representation is 14 digits long, then we have that n < 1014, or equivalently that log 10n < 14. We can convert this to the binary case by converting logarithms.

log 10n < 14 n < 1014 ln n < ln 1014

Note that ln 1014 = 14ln 10 < 14 × 3 = 42 < 47, so that ln n < 47. That is, the binary representation of an integer n whose decimal representation is 14 digits long will fit within 47 bits (and a sign bit).

20. [10] Is there any simple relation between log 102 and log 210?

log 102 and log 210 are reciprocals of each other. That is, log 102 = ln 2 ln 10 and log 210 = ln 10 ln 2 .

21. [15] (Logs of logs.) Express log b log bx in terms of ln ln x, ln ln b, and ln b.

We can express log b log bx in terms of ln ln x, ln ln b, and ln b as follows:

log b log bx = log b ln x ln b = log b ln x log b ln b = ln ln x ln b ln ln b ln b = ln ln x ln ln b ln b .

22. [20] (R. W. Hamming.) Prove that

lg x ln x + log 10x,

with less than 1% error! (Thus a table of natural logarithms and of common logarithms can be used to get approximate values of binary logarithms as well.)

We are able to prove that lg x ln x + log 10x with less than 1% error.

Proposition. lg x ln x + log 10x with less than 1% error.

Proof. Let x be an arbitrary positive real number. We must show that lg x ln x + log 10x with less than 1% error; that is, we must show that | ln x+log 10xlg x lg x | < 0.01. But:

|ln x + log 10x lg x lg x | = |ln x + ln x ln 10 ln x ln 2 ln x ln 2 | = |ln 2ln x + ln 2 ln 10 ln x ln x ln x | = |ln 2 + ln 2 ln 10 1| < 0.01

as we needed to show. □

23. [M25] Give a geometric proof that ln xy = ln x + ln y based on Fig. 6.

We know from the integral calculus that ln x + ln y = ln xy since by definition ln x = 1x1 udu and

ln x + ln y =1x1 udu +1y1 vdv =1x1 udu +1y 1 xwd(xw) =1x1 udu +xxy1 udu =1xy1 udu

We can see this geometrically by observing first the areas for ln x


PIC

and ln y separately.


PIC

We then transform the area for ln y in such a way as to preserve its area, by dividing its height by x while multiplying its width by x, which yields an equivalent area, but shifted to the right.


PIC

These two areas can in fact be arranged continguously, giving us exactly the area for ln xy.


PIC

24. [15] Explain how the method used for calculating logarithms to the base 10 at the end of this section can be modified to produce logarithms to base 2.

We will show how to calculate log 2x and to express the answer in the binary system, as

log 2x = n + b12 + b24 + b38 + .

First we shift the decimal point of x to the left or to the right so that we have 1 x2n < 2; this determines the integer part, n. To obtain b1,b2,, we now set x0 = x2n and, for k 1,

bk = 0, xk = xk12, if x k12 < 2; bk = 1, xk = xk122, if x k12 2.

The validity of this procedure follows from the fact that

1 xk = x2k 22k(n+b 12++bk2k) < 2,

for k = 0,1,2,.

25. [22] Suppose that we have a binary computer and a number x, 1 x < 2. Show that the following algorithm, which uses only shifting, addition, and subtraction operations proportional to the number of places of accuracy desired, may be used to calculate an approximation to y = log bx:

L1.
[Initialize.] Set y 0, z x shifted right 1, k 1.
L2.
[Test for end.] If x = 1, stop.
L3.
[Compare.] If x z < 1, set z z shifted right 1, k k + 1, and repeat this step.
L4.
[Reduce values.] Set x x z, z x shifted right k, y y + log b(2k(2k 1)), and go to L2.

[Notes: This method is very similar to the method used for division in computer hardware. The idea goes back in essence to Henry Briggs, who used it (in decimal rather than binary form) to compute logarithm tables, published in 1624. We need an auxiliary table of the constants log b2, log b(43), log b(87), etc., to as many values as the precision of the computer. The algorithm involves intentional computational errors, as numbers are shifted to the right, so that eventually x will be reduced to 1 and the algorithm will terminate. The purpose of this exercise is to explain why it will terminate and why it computes an approximation to log bx.]

The algorithm relies on the identity

log b(x) = log b(x2k 1 2k 2k 2k 1) = log b(x x 2k) + log b( 2k 2k 1)

and the fact that

z x 2k

so that y + log b(x) log b(x0) for initial x, x0.

To see this is the case, note that after L1, since y = 0 and x = x0, we have y + log b(x) log b(x0). At L2, if x = 1, log b(x) = log b(1) = 0, and so we stop with y + log b(x) = y log b(x0). Otherwise, we continue with x > 1. Through L3, we maintain the invariant z x 2k, until finally x z 1, x > 1, z 0, and x > z. After L4, y + log b(x) log b(x0) is transformed by assignments into y + log b( 2k 2k1) + log b(x x 2k) log b(x0), which is equivalent to y + log b(x) log b(x0), the same assertion as previously held before L2, with x approaching 1 as z approaches 0, ultimately terminating when x = 1.

26. [M27] Find a rigorous upper bound on the error made by the algorithm in the previous exercise, based on the precision used in the arithmetic operations.

We want to determine an upper bound on the error made by the algorithm in the previous exercise, based on the precision p, the number of fractional digits. That is, the relative error 𝜖 such that

|y + log b(x) log b(x0) 1| 𝜖

for initial x, x0.

According to Brigg’s method, we have log b(x) = 1k(mk log b( 2k 2k1)) with 0 mk < 2. In our approximation, however, we add at most p terms, and each is truncated by the limited precision p, giving us the following sum:

1kp2p log b( 2k 2k1) 2p

with all mk = 1, the worst possible truncation. And according to the method, the above sum is an approximation of a factorization, giving us the following logarithm:

log b 1kp 2k 2k 1

And so, the upper bound on the error based on the precision p is precisely:

|y + log b(x) log b(x0) 1| 𝜖 =| 1kp2p log b( 2k 2k1 ) 2p log b 1kp 2k 2k1 1|

For example, for b = 2 and p = 8, 𝜖 < 1%.

27. [M25] Consider the method for calculating log 10x discussed in the text. Let xk denote the computed approximation to xk, determined as follows: x(1 δ) 10nx0 x(1 + 𝜖); and in the determination of xk by Eqs. (18), the quantity yk is used in place of (xk1)2, where (xk1)2(1 δ) yk (xk1)2(1 + 𝜖) and 1 yk < 100. Here δ and 𝜖 are small constants that reflect the upper and lower errors due to rounding or trunctation. If log x denotes the result of the calculations, show that after k steps we have

log 10x + 2log 10(1 δ) 12k < log x log 10x + 2log 10(1 + 𝜖).

We may prove the bounds of the approximation.

Proposition. log 10x + 2log 10(1 δ) 12k < log x log 10x + 2log 10(1 + 𝜖) after k steps.

Proof. We must show that

log 10x + 2log 10(1 δ) 12k < log x log 10x + 2log 10(1 + 𝜖)

holds after k steps. It is sufficient to show that

x2k (1 δ)2k+11 102k(n+ 1jk(bj2j)) xk x2k (1 + 𝜖)2k+11

since, by taking logarithms and given that log x = n + 1jk(bj2j):

2k log 10x + 2k log 10(1 δ)(2 12k) 2k log x 2k log 10x + 2k log 10(1 + 𝜖)(2 12k) log 10x + log 10(1 δ)(2 12k) log x log 10x + log 10(1 + 𝜖)(2 12k) log 10x + 2log 10(1 δ) log x log 10x + 2log 10(1 + 𝜖)

It also given that

x(1 δ) 10nx 0 x(1 + 𝜖)

and that

xk+1 = 10bk+1 x k2.

First, we must show that the relation holds for k = 0. But this case is given, as:

x20 (1 δ)20+11 1020(n+ 1j0(bj2j)) x0 x20 (1 + 𝜖)2k+11

Then, assuming the relation holds for arbitrary k 0:

x2k (1 δ)2k+11 102k(n+ 1jk(bj2j)) xk x2k (1 + 𝜖)2k+11

we must show it holds for k + 1:

x2k+1 (1 δ)2k+21 102k+1(n+ 1jk+1(bj2j)) xk+1 x2k+1 (1 + 𝜖)2k+21

We may take squares of the induction hypothesis:

(x2k (1 δ)2k+11 )2 (102k(n+ 1jk(bj2j)) xk)2 (x2k (1 + 𝜖)2k+11 )2

and evalate each part in turn.

For the lower bound, since (1 δ) < 1, we have:

(x2k (1 δ)2k+11 )2 (x2k (1 δ)2k+11 )2(1 δ) = x2k2 (1 δ)2(2k+11)+1 = x2k+1 (1 δ)2k+21

For the upper bound, since (1 + δ) > 1, we have:

(x2k (1 + 𝜖)2k+11 )2 (x2k (1 + 𝜖)2k+11 )2(1 + 𝜖) = x2k2 (1 + 𝜖)2(2k+11)+1 = x2k+1 (1 + 𝜖)2k+21

And for the middle approximation, since xk+1 = 10bk+1x k2, we have:

(102k(n+ 1jk(bj2j)) xk)2 = 102(2k)(n+ 1jk(bj2j)) 10bk+1 xk210bk+1 = 102k+1(n+ 1jk(bj2j))+2k+1(b k+12k+1) xk+1 = 102k+1(n+ 1jk(bj2j)+b k+12k+1) xk+1 = 102k+1(n+ 1jk+1(bj2j)) xk+1

That is

x2k+1 (1 δ)2k+21 102k+1(n+ 1jk+1(bj2j)) xk+1 x2k+1 (1 + 𝜖)2k+21

as we needed to show. □

28. [HM30] (R. Feynman.) Develop a method for computing bx when 0 x < 1, using only shifting, addition, and subtraction (similar to the algorithm in exercise 25), and analyze its accuracy.

The method below computes an approximation to bx for 0 x < 1, using only shifting, addition, and subtraction, similar to the algorithm in exercise 25 in that it uses the same auxiliary table of constants.

Algorithm M (Digit-by-digit exponentiation.). Given a number x, 0 x < 1, calculate an approximation y = bx given machine precision p.

M1.
[Initialize.] Set x 1 x, y b, k 1.
M2.
[Test for end.] If x 0, stop.
M3.
[Compare.] If x log b(2k(2k 1)) < 0 and k < p, k k + 1, and repeat this step.
M4.
[Reduce values.] Set x x log b(2k(2k 1)), y y (y shifted right k), and go to M2. (Note that the operation on y is equivalent to y y × (2k 1)2k.)

While decreasing x by log b(2k(2k 1)) = log b((2k 1)2k), we increase y by y(2k 1)2k, so that ybx remains approximately constant.

The upper bound on the error made by the algorithm, based on the precision p, the number of fractional digits, can be represented by the relative error 𝜖 such that

|ybx bx0 1| 𝜖

for initial x, x0.

According to the digit-by-digit method, we have bx = 1k( 2k 2k1)mk with 0 mk < 2. In our approximation, however, we multiply at most p factors, and each is truncated by the limited precision p, giving us the following product:

1kp2p 2k 2k1 2p

with all mk = 1, the worst possible truncation. And according to the method, the above product is an approximation of a factorization, giving us the following logarithm:

b 1kp log b 2k 2k1

And so, the upper bound on the error based on the precision p is precisely:

|ybx bx0 1| 𝜖 =| 1kp2p 2k 2k1 2p b 1kp log b 2k 2k1 1|

For example, for b = 2 and p = 8, 𝜖 < 1%.

________________________________________________________________________________

Note: Similar algorithms can be given for trigonometric functions; see J. E. Meggitt, IBM J. Res. and Dev. 6 (1962), 210-226; 7 (1963), 237-245. See also T. C. Chen, IBM J. Res. and Dev. 16 (1972), 380-388; V. S. Linsky, Vychisl. Mat. 2 (1957), 90-119; D. E. Knuth, Metafont: The Program (Reading, Mass.: Addison-Wesley, 1986), §120-§147.

29. [HM20] Let x be a real number greater than 1. (a) For what real number b > 1 is blog bx a minimum? (b) For what integer b > 1 is it a minimum? (c) For what integer b > 1 is (b + 1)log bx a minimum?

a.
Let x and b be real numbers greater than 1. b = e is a minimum for blog bx. The minimum of blog bx is the minimum of b ln b, and d db b ln b = ln b1 (ln b)2 = 0 if and only if ln b = 1 and b = e.
b.
Let x be a real number and b be an integer, both greater than 1. b = e = 3 is a minimum for blog bx, since
| e ln e e| <| e ln e e|.
c.
Let x be a real number and b be an integer, both greater than 1. b = α = 4 for α = eW(1 e)+1, the Lambert W-function or product logarithm, is the minimum of (b + 1)log bx. The minimum of (b + 1)log bx is the minimum of b+1 ln b, and d db b+1 ln b = bln b b 1 = 0 if and only if b = eW(1 e)+1 = α, and
|α + 1 ln α α| <|α + 1 ln α α|.

30. [12] Simplify the expression (ln n)ln n ln ln n, assuming that n > 1 and ne.

We may simplify the expression, assuming n > 1 and ne by noting that

ln n = eln ln n = (nlog ne)ln ln n = (n 1 ln n )ln ln n = n ln ln n ln n

or equivalently that

n = (ln n) ln n ln ln n .