Advanced book on Mathematics Olympiad

486 Real Analysis

an+ 1 =an and bn+ 1 =

an+bn

2

iff

(

an+bn

2

)

<

an+bn

2

,

or

an+ 1 =

an+bn

2

and bn+ 1 =bn iff

(

an+bn

2

)

>

an+bn

2

.

Becausebn−an=b 2 −na→0, the intersection of the nested sequence of intervals

[a 1 ,b 1 ]⊃[a 2 ,b 2 ]⊃[a 3 ,b 3 ]⊃···⊃[an,bn] ⊃ ···

consists of one point; call itξ. Note that

ξ=lim

n→∞

an=lim

n→∞

bn.

We have constructed the two sequences such thatan<f(an)<f(bn)<bnfor alln,
and the squeezing principle implies that(f (an))nand(f (bn))nare convergent, and

lim

n→∞

f(an)= lim

n→∞

f(bn)=ξ.

Now the monotonicity offcomes into play. Froman≤ξ≤bn, we obtainf(an)≤
f(ξ)≤f(bn). Again, by the squeezing principle,

f(ξ)=lim

n→∞

f(an)= lim

n→∞

f(bn)=ξ.

This contradicts our initial assumption, proving the existence of a pointξwith the desired
property.

Remark.This result is known as Knaster’s theorem. Its most general form is the Knaster–
Tarski theorem: LetLbe a complete lattice and letf:L→Lbe an order-preserving
function. Then the set of fixed points offinLis also a complete lattice, and in particular
this set is nonempty.

349.LetP 1 (x)=xandPn+ 1 (x)=Pn(x)(Pn(x)+^1 n), forn≥1. ThenPn(x)is a
polynomial of degree 2n−^1 with positive coefficients andxn =Pn(x 1 ). Because the
inequalityxn+ 1 >xnis equivalent toxn> 1 −n^1 , it suffices to show that there exists a
unique positive real numbertsuch that 1−^1 n<Pn(t) <1 for alln. The polynomial
functionPn(x)is strictly increasing forx ≥0, andPn( 0 )=0, so there exist unique
numbersanandbnsuch thatPn(an)= 1 −^1 nandPn(bn)=1, respectively. We have that
an<an+ 1 , sincePn+ 1 (an)= 1 −^1 nandPn+ 1 (an+ 1 )= 1 −n^1 + 1. Similarly,bn+ 1 <bn,
sincePn+ 1 (bn+ 1 )=1 andPn+ 1 (bn)= 1 +^1 n.
It follows by induction onnthat the polynomial functionPn(x)is convex forx≥0,
since