<< . .

. 48
( : 70)



. . >>

Suppose that n and m are strictly positive integers with n2 = 2m2 , Draw
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

<< . .

. 48
( : 70)



. . >>