a triangle ABC with AB and BC of length m units and CA of length n

units. Explain why ABC is a right angled triangle. Let the circle “ with

centre A passing through B cut AC at D and let the tangent to “ at D cut

BC at E. Show that AE, ED and DC all have the same length. Deduce

that ECD is a right angled triangle with sides ED and DC of integer length

m units and side CE of integer length n units. Show that n 2 = 2m 2 and

n > n ≥ 1. Conclude that the equation n2 = 2m2 has no non-zero integer

solutions.

433

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.2. [1.2, P] If dn ≥ 1 for all n and dn + d’1 tends to a limit as

n

n ’ ∞, show that dn tends to a limit.

Show, by giving an example, that the result is false if we replace the

condition dn ≥ 1 by dn ≥ k for some ¬xed k with 0 < k < 1.

Can you ¬nd a result similar to that of the ¬rst paragraph involving

dn ∈ C?

Exercise K.3. [1.4, P] Prove that, if

an + b n 2an bn

a1 > b1 > 0 and an+1 = , bn+1 = ,

2 an + b n

then an > an+1 > bn+1 > bn . Prove that, as n ’ ∞, an and bn both tend to

√

the limit (a1 b1 ).

Use this result to give an example of an increasing sequence of rational

numbers tending to a limit l which is not rational.

Exercise K.4. [1.3, P] Let f, g : R ’ R be functions such that the com-

position g —¦ f is continuous at x.

(i) Show, by means of examples, that the continuity of f at x is neither

a necessary nor a su¬cient condition for the continuity of g at f (x).

(ii) Show, by means of examples, that the continuity of g at f (x) is neither

a necessary nor a su¬cient condition for the continuity of f at x.

Exercise K.5. [1.3, P] The function f : [0, 1] ’ [0, 1] is de¬ned by

1 ’ x if x is rational,

f (x) =

x if x is irrational

Consider the following statements, prove those which are true and demon-

strate the falsity of the remainder.

(i) f (f (x)) = x for all x ∈ [0, 1].

(ii) f (x) + f (1 ’ x) = 1 for all x ∈ [0, 1].

(iii) f is bijective.

(iv) f is everywhere discontinuous in [0, 1].

(v) f (x + y) ’ f (x) ’ f (y) is rational for all x, y ∈ [0, 1] such that

x + y ∈ [0, 1].

Exercise K.6. [1.3, P] Enumerate the rationals in [0, 1] as a sequence q1 ,

q2 , . . . and let H be the usual Heaviside function (so H(t) = 0 for t ¤ 0,

H(t) = 1 for t > 0). Show that the equation

∞

2’n H(x ’ qn )

f (x) =

n=1

434 A COMPANION TO ANALYSIS

gives a well de¬ned function f : [0, 1] ’ R which is discontinuous at rational

points and continuous at irrational points.

Exercise K.7. [1.4, P] A bounded sequence of real numbers an satis¬es

the condition

an’1 + an+1

an ¤

2

for all n ≥ 1. By showing that the sequence an+1 ’ an is decreasing, or

otherwise, show that the sequence an converges.

What, if anything, can we deduce if the sequence can be unbounded?

What, if anything, can we deduce if the sequence an is bounded but we have

the reverse inequality

an’1 + an+1

an ≥

2

for all n ≥ 1? Prove your answers.

Exercise K.8. [1.4, P] The function f : (0, 1) ’ R is continuous on the

open interval (0, 1) and satis¬es 0 < f (x) < x. The sequence of functions

fn : (0, 1) ’ R is de¬ned by

f1 (x) = f (x), fn (x) = f (fn’1 (x)) for n ≥ 2.

Prove that fn (x) ’ 0 as n ’ ∞ for all x ∈ (0, 1).

Show, by means of a counterexample, that the result need not be true if

f is not continuous everywhere in (0, 1).

Enter any number on your calculator. Press the sine button repeatedly.

What appears to happen? Prove your conjecture.

Exercise K.9. [1.4, T] (i) If δ > 0, use the binomial theorem to show that

n2

(1 + δ)n ≥ δ.

2

Deduce that n’1 (1 + δ)n ’ ∞ as n ’ ∞. Show that, if |x| < 1, then

nxn ’ 0 as n ’ ∞.

(ii) Show, more generally, that, if δ > 0, and k is any integer, n’k (1 +

δ)n ’ ∞ as n ’ ∞. Show that, if |x| < 1, then nk xn ’ 0 as n ’ ∞.

Exercise K.10. [1.4, P] Let x1 , x2 , . . . be a sequence of positive real num-

bers and suppose that

x1 + x 2 + · · · + x n

’1

n

435

Please send corrections however trivial to twk@dpmms.cam.ac.uk

as n ’ ∞. Choose m(n) so that 1 ¤ m(n) ¤ n and xm(n) = max(x1 , x2 , . . . , xn ).

Show that xn /n ’ 0 and xm(n) /n ’ 0 as n ’ ∞.

By comparing x± with xr x±’1 , or otherwise, show that

r m(n)

x± + x ± + · · · + x ± 0 if ± > 1,

1 2 n

’

n± ∞ if 0 ¤ ± < 1,

as n ’ ∞.

Exercise K.11. [1.5, P] Which of the following statements are true and

which are false? Give a proof or counterexample.

(i) The sum of a rational number and an irrational number is irrational.

(ii) The product of a rational number and an irrational number is irra-

tional.

(iii) If x is a real number and > 0, we can ¬nd an irrational number y

with |x ’ y| < .

(iv) If each xn is irrational and xn ’ x, then x is irrational.

(v) If x and y are irrational then xy is irrational.

[Hint. This is an old chestnut. Consider a = 21/2 and observe that (aa )a = 2.]

Exercise K.12. (Liouville™s theorem.) [1.5, T] A real number x is called

algebraic if

n

ar x r = 0

r=0

for some ar ∈ Z [0 ¤ r ¤ n], an = 0 and n ≥ 1, (in other words, x is a root

of a non-trivial polynomial with integer coe¬cients). Liouville proved that

not all real numbers are algebraic. Here is a version of his proof.

(i) If x and y are real and n is a strictly positive integer, show, by ex-

tracting the factor x ’ y from xn ’ y n , that

|xn ’ y n | ¤ n(max(|x|, |y|))n’1 |x ’ y|.

(ii) If P is a polynomial and R > 0 show, using (i), that there exists a K,

depending on P and R, such that

|P (x) ’ P (y)| ¤ K|x ’ y|

whenever |x|, |y| ¤ R.

(iii) Suppose that

n

ar t r = 0

P (t) =

r=0

436 A COMPANION TO ANALYSIS

for some ar ∈ Z [0 ¤ r ¤ n], an = 0 and n ≥ 1. Show that N n P (M/N )

is an integer whenever M is an integer and N is a strictly positive integer.

Conclude that, if M and N are as stated, either P (M/N ) = 0 or |P (M/N )| ≥

N ’n .

(iv) Let P , R, K, M and N be as in parts (ii) and (iii). Suppose that ·

is a real number with P (·) = 0. If · and M/N lie in the interval [’R, R],

show that

N ’n ¤ K|· ’ M/N |.

(v) Use (iv) to prove that, if · is an algebraic number which is not a

rational number, then we can ¬nd n and L (depending on ·) such that

|· ’ M/N | ≥ LN ’n

whenever M is an integer and N is a strictly positive integer.

(vi) Explain why ∞ 10’k! converges. Let us write » = ∞

10’k! .

k=1 k=1

Show that

J

10’k! | ¤ 2 — 10’(J+1)! .

|» ’

k=1

By considering N = 10J! and M = J 10J!’k! , or otherwise, show that (a)

k=1

» is irrational and (b) » is not an algebraic number.

Note that we have shown that » is too well approximable by rationals

to be an algebraic number. We discuss approximation problems again in

Exercises K.13 and K.14.

(vii) In the ¬rst part of the question I deliberately avoided using the

mean value inequality (Theorem 1.7). Prove (ii) directly, using the mean

value inequality.

(viii) Show that no real number of the form

∞

mk 10’k!

k=1

with mk taking the value 1 or 2 can be algebraic. If you know enough about

countability, show that the collection of numbers of the form just given is

uncountable.

Exercise K.13. (Continued fractions.) [1.5, T] In this exercise we take

a ¬rst glance at continued fractions.

437

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Consider the following process. If x = x0 ∈ [0, 1), either x0 = 0 and we

stop or we set

1

r1 =

x0

(that is, r1 is the integer part of 1/x0 ). We set

1

’ r1 ,

x1 =

x0

so that x1 is the fractional part of 1/x0 and x1 ∈ [0, 1). We now repeat the

process so that (unless the process terminates) we have xn ∈ [0, 1),

1 1

’ rn+1 .

rn+1 = , xn+1 =

xn xn

Show that, if the process terminates, x must be rational.

For the rest of the question we shall consider the case in which the process

does not terminate unless we explicitly state otherwise. Show, by induction,

or otherwise that

x = (r1 + (r2 + (r3 + (r4 + . . . (rn + (rn+1 + xn+1 )’1 )’1 . . . )’1 )’1 )’1 )’1 .

This formula is usually written out as

1

x=

1

r1 +

1

r2 +

1

r3 +

1

r4 + · · · +

1

rn +

rn+1 + xn+1

but this works better in handwriting than in print so we shall use the compact

(but less suggestive) notation

x = [r1 , r2 , r3 , r4 , . . . , rn , rn+1 + xn+1 ].

We are interested in what happens when we consider the ˜truncation™

yn+1 = [r1 , r2 , r3 , r4 , . . . , rn , rn+1 ].

438 A COMPANION TO ANALYSIS

Write out the formula for yn in the style of . Show by induction, using

the formula xn+1 = x1n ’ rn+1 , or otherwise, that

pn+1 + pn xn+1

x= ,

qn+1 + qn xn+1

where

pn+1 = rn+1 pn + pn’1 , qn+1 = rn+1 qn + qn’1 ,

and p0 = 0, q0 = 1, p1 = 1, q1 = r1 . If you have met Euclid™s algorithm, you

should note that the recurrence equations for pn and qn are precisely those

which occur in that process. By considering the appropriate interpretation

of right hand side of equation when xn+1 = 0, show that

pn

yn =

qn

for n ≥ 1.

By using the recurrence equations for pn and qn , show that

pn’1 qn ’ pn qn’1 = (’1)n

for all n ≥ 1. Use this fact together with equation to show that

(’1)n xn+1

pn+1

x’ =

qn+1 qn+1 (qn+1 + qn xn+1 )

for all n ≥ 0. Hence show that x ’ pn /qn is alternately positive and negative

and that

1 pn 1

< x’ <

qn’1 qn qn qn+1 qn

for all n ≥ 1. By looking at the recurrence relations for qn , show that qn ≥ n

and deduce that pn /qn ’ x as n ’ ∞. It is thus natural to say that we have

expressed x as an in¬nite continued fraction

1

x= .

1

r1 +

1

r2 +

1

r3 +

r4 + . . .

439

Please send corrections however trivial to twk@dpmms.cam.ac.uk

We know that the process of constructing successive xn cannot terminate

if x is irrational, but we did not discuss the case x rational. Show that if r,

s, p, q are integers with s > r ≥ 0, q > p ≥ 0, then either r/s = p/q or

rp 1

’ ≥.

sq qs

By considering equation , conclude that, if x is rational, the process

of forming xn will indeed terminate. It is easy to see (but I leave it up the

reader to decide whether to check the details) that we can then express any

rational x with 0 < x < 1 as a continued fraction

x = [r1 , r2 , r3 , r4 , . . . , rN ]

for appropriate rj and N .

In this question we have shown how to express any real number x with

0 < x < 1 as a continued fraction. (So any real number can be written in the

form m or m + y where m is an integer and y can be expressed as a continued

fraction.) We have not discussed whether a general continued fraction

1

,

1

s1 +

1

s2 +

1

s3 +

s4 + . . .

with sn a strictly positive integer, converges. (A fairly simple adaptation

of the argument above shows that it does. Of course, we need to use the

fundamental axiom of analysis at some point.)

Exercise K.14. [1.5, T, ‘ ] In this exercise we continue the discussion of

Exercise K.13. We shall suppose, as before, that 0 < x < 1 and x is irra-

tional. One major advantage of continued fractions is that they give very

good rational approximations, as was shown in , which gave us the

estimate

pn 1 1

x’ ¤ 2.

< (†)

qn qn+1 qn qn

Conclude that, if x is a real number, we can ¬nd integers p and q with q ≥ 1

such that

p 1

x’ < 2.

q q

440 A COMPANION TO ANALYSIS

Since the larger qn is (for ¬xed n), the better the inequality (†), it is

natural to ask how small qn can be.

Use induction and the recurrence relation for qn obtained in Exercise K.13

to show that q(n) ≥ Fn where

Fn+1 = Fn + Fn’1

and F0 = 1, F1 = 1. By directly solving the recurrence relation, if you know

how, or by inductive veri¬cation, if you do not, show that

n+1 n+1

„1 ’ „ 2

√

Fn = ,

5

√ √

where „1 = (1 + 5)/2 and „2 = (1 ’ √ 5)/2. Explain why, if n is su¬ciently

n+1

large Fn is the integer closest to „1 / 5.

It is interesting to look for an example of a ˜worst behaved™ continued

fraction. If qn = Fn then the associated recurrence relation tells us that

rn = 1 and suggests we look at

1

x= .

1

1+

1

1+

1

1+

1 + ...

Since we have not proved the convergence of this continued fraction, our

argument is now merely heuristic. Explain why

1

x=

1+x

√

and deduce that, if 1 > x > 0,√ must have x = ( 5 ’ 1)/2. Returning to

we

full rigour, show that, if x = ( 5 ’ 1)/2, then the process of Exercise K.13

does, indeed, give

1

x= .

1

1+

1

1+

1

1+

1 + ...

as required.

441

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Hardy and Wright™s delightful The Theory of Numbers [25] contains a dis-

cussion of the problem of approximating real numbers by rationals and shows